הוכחות מתמטיות/שונות/פולינום סימטרי/המשפט היסודי של הפולינומים הסימטריים

יהי $𝔽$ שדה, ויהי $F \in 𝔽 [\vec{X}^{n}]$ פולינום סימטרי.תבנית:ש אזי ניתן להציגו באופן יחיד כפולינום $G (\vec{E}^{n} (\vec{X}^{n})) \in 𝔽 [\vec{X}^{n}]$ , כאשר:

מעלת $G$ אינה עולה על מעלת $F$ .
אם $F$ בעל מקדמים שלמים אזי גם $G$ בעל מקדמים שלמים.

הוכחה

ראשית, נתאר אלגוריתם למציאת הפולינום המבוקש $G$ .

נגדיר תנאי התחלה $m = 1$ וכן $F_{1} = F$ .

מצאו את $L (F_{m}) = c_{m} X_{1}^{a_{1}} \dots X_{n}^{a_{n}}$ כאשר $c_{m} \in 𝔽, c_{m} \neq 0$ .
הגדירו $G_{m} (\vec{Y}^{n}) = c_{m} Y_{1}^{a_{1} - a_{2}} Y_{2}^{a_{2} - a_{3}} \dots Y_{n - 1}^{a_{n - 1} - a_{n}} Y_{n}^{a_{n}}$ .
הציבו $F_{m + 1} (\vec{X}^{n}) = F_{m} (\vec{X}^{n}) - G_{m} (\vec{E}^{n} (\vec{X}^{n}))$ .
אם $F_{m + 1} \neq 0$ , שובו לסעיף 1 והתחילו את התהליך מחדש באינדקס $m + 1$ .תבנית:שאם $F_{m + 1} = 0$ , עברו לסעיף 5.
הציבו $G = G_{1} + \dots + G_{m}$ .

להוכחת האלגוריתם אנו זקוקים לשתי למות.

למה 1: המונום המוביל ב־ $F$ מקיים $a_{1} \geq a_{2} \geq \dots \geq a_{n}$ .

הוכחה: נניח בשלילה כי קיים אינדקס $k$ עבורו $a_{k} < a_{k + 1}$ . קיימת תמורה כלשהיא $σ \in S_{X}$ עבורה

X_{σ (m)} = {\begin{matrix} X_{m} & : m \neq k, k + 1 \\ X_{k + 1} & : m = k \\ X_{k} & : m = k + 1 \end{matrix}

אך הפולינום $σ (F) = F$ מכיל את המונום $c X_{1}^{a_{1}} \dots X_{k}^{a_{k + 1}} X_{k + 1}^{a_{k}} \dots X_{n}^{a_{n}}$ , שסדרו גדול מזה של $c X_{1}^{a_{1}} \dots X_{k}^{a_{k}} X_{k + 1}^{a_{k + 1}} \dots X_{n}^{a_{n}}$ .תבנית:ש סתירה.

$◻$

למה 2: המונום המוביל בפיתוחו של הפולינום $G_{m} (\vec{E}^{n} (\vec{X}^{n}))$ הוא $c_{m} X_{1}^{a_{1}} X_{2}^{a_{2}} \dots X_{n}^{a_{n}}$ .

הוכחה: מתקיים כי

\begin{matrix} L (E_{k}) = X_{1} \dots X_{k}, & : 1 \leq k \leq n \\ L (c_{m} E_{1}^{b_{1}} E_{2}^{b_{2}} \dots E_{n}^{b_{n}}) & = c_{m} L (E_{1}^{b_{1}}) L (E_{2}^{b_{2}}) \dots L (E_{n}^{b_{n}}) \\ = c_{m} L (E_{1})^{b_{1}} L (E_{2})^{b_{2}} \dots L (E_{n})^{b_{n}} \\ = c_{m} X_{1}^{b_{1}} (X_{1} X_{2})^{b_{2}} \dots (X_{1} X_{2} \dots X_{n})^{b_{n}} \\ = c_{m} (X_{1})^{b_{1} + \dots + b_{n}} (X_{2})^{b_{2} + \dots + b_{n}} \dots (X_{n - 1})^{b_{n - 1} + b_{n}} (X_{n})^{b_{n}} \\ = c_{m} X_{1}^{a_{1}} X_{2}^{a_{2}} \dots X_{n}^{a_{n}} \end{matrix}

השוויון האחרון מתקיים אם ורק אם

\begin{matrix} a_{k} & = \sum_{i = k}^{n} b_{i}, : 1 \leq k \leq n \\ b_{k} & = {\begin{matrix} a_{k} - a_{k + 1} & : 1 \leq k \leq n - 1 \\ a_{k} & : k = n \end{matrix} \end{matrix}

$◻$

עתה ניגש להוכחת המשפט:

1. יהי $F \neq 0$ פולינום סימטרי במשתנים $X_{1}, \dots, X_{n}$ .תבנית:ש ההוכחה באינדוקציה שלמה על $| D (F) |$ (ראו הגדרה).

אם $| D (F) | = 0$ אזי $F$ פולינום קבוע, וקל להראות כי האלגוריתם מתקיים עבורו.

נניח כי האלגוריתם מתקיים לכל הפולינומים הסימטריים $F$ בעלי $0 \leq | D (F) | \leq k$ , עבור $k \in ℕ$ כלשהוא.תבנית:ש נראה כי האלגוריתם מתקיים גם עבור פולינום סימטרי $F_{1}$ בעל $| D (F_{1}) | = k + 1$ , כאשר $L (F_{1}) = c_{1} X_{1}^{a_{1}} \dots X_{n}^{a_{n}}$ .

על־פי למה 2, מתקיים כי:

\begin{matrix} G_{1} (\vec{Y}^{n}) & = c_{1} Y_{1}^{a_{1} - a_{2}} Y_{2}^{a_{2} - a_{3}} \dots Y_{n - 1}^{a_{n - 1} - a_{n}} Y_{n}^{a_{n}} \\ F_{2} (\vec{X}^{n}) & = F_{1} (\vec{X}^{n}) - G_{1} (\vec{E}^{n} (\vec{X}^{n})) \end{matrix}

הפונקציה $G_{1}$ היא פולינום, שכן $a_{1} \geq a_{2} \geq \dots \geq a_{n}$ .תבנית:ש בנוסף, על־פי תכונות הפולינומים הסימטריים $G_{1} (\vec{E}^{n} (\vec{X}^{n}))$ פולינום סימטרי במשתנים $X_{1}, \dots, X_{n}$ , ולכן גם $F_{2}$ פולינום סימטרי.תבנית:ש הפולינומים $F_{1} (\vec{X}^{n}), G_{1} (\vec{E}^{n} (\vec{X}^{n}))$ מכילים שניהם את $L (F_{1})$ , ולכן הוא מתקזז בהפרשם.תבנית:ש

אם $F_{2} = 0$ אזי $G = G_{1}$ .תבנית:ש אם $F_{2} \neq 0$ אזי $L (F_{2}) ≺ L (F_{1})$ , כלומר $| D (F_{2}) | < | D (F_{1}) | = k + 1$ .תבנית:ש הנחת האינדוקציה מתקיימת עבור $F_{2}$ , ועל כן האלגוריתם מניב פולינום $G^{*}$ עבורו

\begin{matrix} F_{2} (\vec{X}^{n}) & = G^{*} (\vec{E}^{n} (\vec{X}^{n})) \\ F_{1} (\vec{X}^{n}) & = G_{1} (\vec{E}^{n} (\vec{X}^{n})) + G^{*} (\vec{E}^{n} (\vec{X}^{n})) \end{matrix}

2. תכונות המשפט מתקיימות:

על־פי ההגדרה, מעלת $G_{1} (\vec{Y}^{n})$ היא $a_{1}$ ומעלת $F_{1}$ היא לפחות $a_{1} + \dots + a_{n}$ .
אם $F_{1}$ בעל מקדמים שלמים אזי $c_{1} \neq 0$ הנ"ל מספר שלם. לכן גם $G_{1}$ בעל מקדמים שלמים.

$◼$

תוצאות חשובות

משפט. יהי $𝔽 \subseteq 𝔼$ שדה, ויהי $P \in 𝔽 [z]$ פולינום ממעלה $n$ בעל השורשים $α_{1}, \dots, α_{n} \in 𝔼$ (עם ריבוי).תבנית:ש יהי $G \in 𝔽 [\vec{X}^{n}]$ פולינום סימטרי. אזי $G (\vec{α}^{n}) \in 𝔽$ .

הוכחה. על־פי נוסחאות ויאטה מתקיים כי:

\begin{matrix} P (z) & = \sum_{k = 0}^{n} a_{k} z^{k} \in 𝔽 [z] \\ E_{k} (\vec{α}^{n}) & = (- 1)^{k} \frac{a_{n - k}}{a_{n}} \in 𝔽, (1 \leq k \leq n) \end{matrix}

על־פי המשפט היסודי, $G$ ניתן להצגה כפולינום

\begin{matrix} G (\vec{X}^{n}) & = H (\vec{E}^{n} (\vec{X}^{n})) \in 𝔽 [\vec{X}^{n}] \\ G (\vec{α}^{n}) & = H (\vec{E}^{n} (\vec{α}^{n})) \in 𝔽 \end{matrix}

$◻$

משפט. יהי $𝔽 \subseteq 𝔼$ שדה, ויהי $P \in 𝔽 [z]$ פולינום ממעלה $n$ בעל השורשים $α_{1}, \dots, α_{n} \in 𝔼$ (עם ריבוי).תבנית:ש אזי לכל $1 \leq k \leq n$ קיים פולינום מתוקן $P_{k} \in 𝔽 [z]$ אשר שורשיו הם סכומי/מכפלות כל $k$ מבין שורשי $P$ .

הוכחה. יהיו $β_{1}, \dots, β_{m}$ סכומי/מכפלות כל $k$ מבין שורשי $P$ (לאמר $m = (\binom{n}{k})$ ).תבנית:ש עלינו להראות כי מתקיים

P_{k} (z) = \prod_{i = 1}^{m} (z - β_{i}) \in 𝔽 [z]

על־פי נוסחאות ויאטה, מקדמי הפולינום כולם פולינומים סימטריים לפי $β_{1}, \dots, β_{m}$ .

יהי $G \in 𝔽 [\vec{Y}^{m}]$ פולינום סימטרי, ויהיו $Y_{1}, \dots, Y_{m}$ סכומי/מכפלות כל $k$ מבין המשתנים $X_{1}, \dots, X_{n}$ .תבנית:ש אזי $G$ ניתן להצגה כפולינום

G (\vec{Y}^{m}) = H (\vec{X}^{n})

קל לראות כי בהפעלת תמורה על $X_{1}, \dots, X_{n}$ מתקיימת גם תמורה על $Y_{1}, \dots, Y_{m}$ .תבנית:ש לכן $H \in 𝔽 [\vec{X}^{n}]$ פולינום סימטרי, ועל־פי המשפט הקודם מתקיים כי

G (\vec{β}^{m}) = H (\vec{α}^{n}) \in 𝔽

$◻$

מסקנה

יהי $𝔼$ שדה, ויהי $P \in ℤ [z]$ פולינום מתוקן ממעלה $n$ בעל השורשים $α_{1}, \dots, α_{n} \in 𝔼$ (עם ריבוי).תבנית:ש אזי לכל $1 \leq k \leq n$ מתקיים $P_{k} \in ℤ [z]$ .

תבנית:תוכן

הוכחות מתמטיות/שונות/פולינום סימטרי/המשפט היסודי של הפולינומים הסימטריים

הוכחה

תוצאות חשובות

מסקנה

תפריט ניווט

חיפוש