שורש יחידה

שורש יחידה הוא איבר בשדה (קבוצה של מספרים שמוכפלים ומוספים כרגיל) שהחזקה שלו שווה ל-1.

שורש יחידה מסדר n מקיים ρ^n = 1. אם n הוא המספר הקטן ביותר עם התכונה הזו קוראים לו שורש יחידה פרימיטיבי. בכל שדה יש לכל היותר n שורשי יחידה, ומספר השורשים הפרימיטיביים מסדר n הוא φ(n), כאשר φ היא פונקציית אוילר (היא סופרת כמה מספרים קטנים מ‑n יחסיים ל‑n).

במישור המרוכב יש בדיוק n שורשי יחידה שונים מסדר n. הם ניתנים לביטוי כ־e^{2π i k/n} = cos(2πk/n) + i sin(2πk/n). כל השורשים נמצאים על מעגל היחידה במישור, והנקודות הללו הן קודקודים של מצולע משוכלל בעל n צלעות. לדוגמה: עבור n=3 השורשים הם 1 והמספרים המורכבים (-1 ± i√3)/2, ועבור n=4 הם 1,i,-1,-i.

אם z הוא שורש פרימיטיבי מסדר n, סדרת החזקות ... , z^{-1},1,z,z^2,... מחזורית במחזור של אורך n. כל סדרה מחזורית x_j ניתנת לכתיבה באופן ייחודי כסכום ליניארי של חזקות z^j: x_j = a_0 + a_1 z^j + ... + a_{n-1} z^{(n-1)j}. כאן a_k היא המשרעת (amplitude) של התדירות k. זו הצורה של התמרת פורייה בדידה (DFT), והעובדה שהמטריצה (z^{ij}) הפיכה מבטיחה שהייצוג ייחודי.

שורשי יחידה פרימיטיביים מקיימים יחס אורתוגונליות: סכום המכפלות
sum_{k=1}^n overline{z^{j k}} z^{j' k} = n·δ_{j,j'}
כאשר δ_{j,j'}=1 אם j=j' ואחרת 0. אם מגדירים את מטריצת U בגודל n×n עם U_{j,k}=n^{-1/2} z^{j k}, מקבלים מטריצה אוניטרית. לכן ההופכי של U הוא פשוט הצמוד המרוכב שלה. פתרון בעיות אינטרפולציה טריגונומטרית בעבודתו של גאוס הוביל לתצפיות אלה.

חישוב ההופכי של מטריצה בגישה ישירה דורש O(n^3) פעולות. פעולה של U או U^{-1} על וקטור דורשת O(n^2). אלגוריתם התמרת פורייה המהירה (FFT) מוריד את המורכבות ל‑O(n log n).

שורשי היחידה הם שורשים של הפולינום p(x)=x^n-1, ולכן יש לכל היותר n מהם. אם המאפיין של השדה הוא 0, או שהוא זר ל‑n, ניתן להוסיף לשדה את כל שורשי היחידה ולהשיג הרחבה ספרבילית. אם המאפיין הוא p ו‑n = p^t m כאשר m זר ל‑p, אז בסגור האלגברי יש בדיוק m שורשי יחידה מסדר m.

שורשי היחידה מסדר n יוצרים חבורה ציקלית, כאשר גודל הסדרה שווה למספר השורשים בשדה.

במספרים הרציונליים עצמם יש רק שני שורשי יחידה: 1 ו‑1-. לשורשים הפרימיטיביים מאותו סדר יש אותו פולינום מינימלי. פולינום זה נקרא הפולינום הציקלוטומי למסדר זה, ולו יש מקדמים שלמים, כי שורשי היחידה הם שלמים אלגבריים.

שורש יחידה הוא מספר בשדה (קבוצה של מספרים עם חיבור וכפל) שהחזקה שלו נותנת 1.

שורש מסדר n מקיים ρ^n = 1. אם לא קיים מסדר קטן יותר קוראים לו פרימיטיבי. בכל שדה יש עד n שורשים כאלו.

במספרים המרוכבים יש בדיוק n שורשי יחידה מסדר n. הם על מעגל ישר שצורתו נקראת מעגל היחידה. הנקודות יוצרות מצולע משוכלל עם n קודקודים. למשל, עבור n=3 הקודקודים הם 1 והשניים (-1 ± i√3)/2. עבור n=4 הקודקודים הם 1,i,-1,-i.

אם z הוא שורש פרימיטיבי, החזקות של z חוזרות כל n צעדים. כל סדרה מחזורית אפשר לפרק לסכום של גלים z^{j}. המקצבים a_k מייצגים תדירויות שונות. זה קשור לתמרת פורייה הבדידה, שמשתמשת במטריצה של חזקות z.

שורשים פרימיטיביים מקיימים חוק סכום מיוחד. סכום המכפלות שלהם נותן 0 או n. זה אומר שהשורות של מטריצת פורייה בלתי תלויות. לכן ההופכי של המטריצה הוא פשוט הצמוד שלה.

שורשי היחידה הם שורשים של הפולינום x^n-1, ולכן לא יהיו יותר מ‑n מהם. במקרים מסוימים, בשדה עם מאפיין p, רק חלק מהשורשים יהיו בסגור האלגברי.

ברציונליים יש רק שני שורשי יחידה: 1 ו‑1-. לקבוצה של שורשים פרימיטיביים יש פולינום מיוחד שנקרא פולינום ציקלוטומי. לפולינום הזה יש מקדמים שלמים.