uniolympiads English

Πολυώνυμα: Vieta, παρεμβολή, ρίζες της μονάδας

Τύποι Vieta και συμμετρικές συναρτήσεις, πολλαπλές ρίζες μέσω gcd⁡(p,p′)\gcd(p, p'), ακέραια πολυώνυμα, παρεμβολή Lagrange και πεπερασμένες διαφορές, ρίζες της μονάδας και φίλτρα.

Τι πρέπει να ξέρεις απέξω

  • Διαίρεση και ρίζες. Για κάθε pp και aa είναι p(x)=(x−a)q(x)+p(a)p(x) = (x - a)q(x) + p(a). Άρα το aa είναι ρίζα ακριβώς όταν (x−a)∣p(x - a) \mid p, και ένα μη μηδενικό πολυώνυμο βαθμού nn έχει το πολύ nn ρίζες.
  • Ταυτοτική αρχή. Δύο πολυώνυμα βαθμού ≤n\le n που συμπίπτουν σε n+1n + 1 σημεία είναι ίσα: η διαφορά τους έχει n+1n + 1 ρίζες.
  • Θεμελιώδες θεώρημα της άλγεβρας. Κάθε p∈C[x]p \in \C[x] βαθμού n≥1n \ge 1 γράφεται p(x)=an(x−x1)⋯(x−xn)p(x) = a_n (x - x_1) \cdots (x - x_n).
  • Τύποι Vieta. Αν p(x)=anxn+an−1xn−1+⋯+a0p(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_0 με ρίζες x1,…,xnx_1, \dots, x_n, τότε
ek=∑i1<⋯<ikxi1⋯xik=(−1)kan−kan,k=1,…,n.e_k = \sum_{i_1 < \dots < i_k} x_{i_1} \cdots x_{i_k} = (-1)^k \frac{a_{n-k}}{a_n}, \qquad k = 1, \dots, n .

Απόδειξη. Ανάπτυξε το an∏i(x−xi)a_n \prod_i (x - x_i): ο συντελεστής του xn−kx^{n-k} μαζεύει όλα τα γινόμενα kk ριζών, με πρόσημο (−1)k(-1)^k.

Vieta και συμμετρικές συναρτήσεις

Κάθε συμμετρικό πολυώνυμο των ριζών γράφεται ως πολυώνυμο των e1,…,ene_1, \dots, e_n, άρα υπολογίζεται από τους συντελεστές χωρίς να βρεις τις ρίζες. Στην πράξη χρειάζεσαι τα αθροίσματα δυνάμεων sk=x1k+⋯+xnks_k = x_1^k + \dots + x_n^k και τους τύπους του Newton:

s1=e1,s2=e1s1−2e2,s3=e1s2−e2s1+3e3.s_1 = e_1, \qquad s_2 = e_1 s_1 - 2 e_2, \qquad s_3 = e_1 s_2 - e_2 s_1 + 3 e_3 .

Για k>nk > n ισχύει sk=e1sk−1−e2sk−2+⋯+(−1)n−1ensk−ns_k = e_1 s_{k-1} - e_2 s_{k-2} + \dots + (-1)^{n-1} e_n s_{k-n}. Απόδειξη: κάθε ρίζα ικανοποιεί xin=e1xin−1−e2xin−2+⋯+(−1)n−1enx_i^n = e_1 x_i^{n-1} - e_2 x_i^{n-2} + \dots + (-1)^{n-1} e_n· πολλαπλασίασε με xik−nx_i^{k-n} και άθροισε.

Δύο ακόμα εργαλεία από την παραγοντοποίηση:

p′(x)p(x)=∑i=1n1x−xi,∑i=1n1xi=en−1en(en≠0).\frac{p'(x)}{p(x)} = \sum_{i=1}^{n} \frac{1}{x - x_i}, \qquad \sum_{i=1}^{n} \frac{1}{x_i} = \frac{e_{n-1}}{e_n} \quad (e_n \ne 0).

Ο πρώτος (λογαριθμική παράγωγος) είναι το βασικό εργαλείο για πολυώνυμα με μόνο πραγματικές ρίζες: παραγωγίζοντας ξανά, (p′/p)′=−∑i(x−xi)−2<0\big(p'/p\big)' = -\sum_i (x - x_i)^{-2} < 0 εκτός των ριζών.

Κόλπο. Αν s2=e12−2e2<0s_2 = e_1^2 - 2e_2 < 0 για πολυώνυμο με πραγματικούς συντελεστές, τότε δεν είναι όλες οι ρίζες πραγματικές.

Πολλαπλές ρίζες και gcd⁡(p,p′)\gcd(p, p')

Λήμμα. Το aa είναι ρίζα πολλαπλότητας ≥2\ge 2 του pp αν και μόνο αν p(a)=p′(a)=0p(a) = p'(a) = 0. Γενικότερα, ρίζα πολλαπλότητας ακριβώς m≥1m \ge 1 του pp είναι ρίζα πολλαπλότητας ακριβώς m−1m - 1 του p′p'.

Απόδειξη. Αν p=(x−a)mqp = (x - a)^m q με q(a)≠0q(a) \ne 0, τότε p′=(x−a)m−1(mq+(x−a)q′)p' = (x - a)^{m-1}\big(m q + (x - a) q'\big) και η παρένθεση στο aa ισούται με mq(a)≠0m q(a) \ne 0.

Συνέπεια. Το p∈C[x]p \in \C[x] έχει απλές ρίζες αν και μόνο αν gcd⁡(p,p′)=1\gcd(p, p') = 1. Για παράδειγμα το xn−1x^n - 1 έχει nn διακεκριμένες ρίζες, αφού η μόνη ρίζα του nxn−1n x^{n-1} είναι το 00. Το gcd⁡\gcd υπολογίζεται με τον αλγόριθμο του Ευκλείδη, άρα δεν χρειάζεται να ξέρεις τις ρίζες.

Ακέραια πολυώνυμα

Λήμμα. Αν p∈Z[x]p \in \Z[x] και a,b∈Za, b \in \Z, τότε (a−b)∣p(a)−p(b)(a - b) \mid p(a) - p(b).

Απόδειξη. ak−bk=(a−b)(ak−1+ak−2b+⋯+bk−1)a^k - b^k = (a - b)(a^{k-1} + a^{k-2} b + \dots + b^{k-1}), και το p(a)−p(b)p(a) - p(b) είναι ακέραιος γραμμικός συνδυασμός τέτοιων διαφορών.

Συνέπειες: αν a≡b(modm)a \equiv b \pmod m τότε p(a)≡p(b)(modm)p(a) \equiv p(b) \pmod m· άρα αν τα p(0)p(0) και p(1)p(1) είναι περιττοί, το pp δεν έχει ακέραια ρίζα (κάθε ακέραιος είναι ≡0\equiv 0 ή 1(mod2)1 \pmod 2).

Ρητές ρίζες. Αν p(x)=anxn+⋯+a0∈Z[x]p(x) = a_n x^n + \dots + a_0 \in \Z[x] και r/sr/s ρίζα με gcd⁡(r,s)=1\gcd(r, s) = 1, τότε r∣a0r \mid a_0 και s∣ans \mid a_n.

Απόδειξη. Πολλαπλασίασε το p(r/s)=0p(r/s) = 0 με sns^n: anrn+an−1rn−1s+⋯+a0sn=0a_n r^n + a_{n-1} r^{n-1} s + \dots + a_0 s^n = 0. Όλοι οι όροι εκτός από τον a0sna_0 s^n διαιρούνται με rr, άρα r∣a0snr \mid a_0 s^n και, αφού gcd⁡(r,s)=1\gcd(r, s) = 1, r∣a0r \mid a_0. Ομοίως s∣anrns \mid a_n r^n, άρα s∣ans \mid a_n.

Παράδειγμα: για το 2x3−x2+2x−12x^3 - x^2 + 2x - 1 οι υποψήφιες ρίζες είναι ±1,±12\pm 1, \pm \frac12, και πράγματι 2x3−x2+2x−1=(2x−1)(x2+1)2x^3 - x^2 + 2x - 1 = (2x - 1)(x^2 + 1).

Παρεμβολή Lagrange και πεπερασμένες διαφορές

Για διακεκριμένα x0,…,xnx_0, \dots, x_n και τιμές y0,…,yny_0, \dots, y_n υπάρχει ακριβώς ένα πολυώνυμο βαθμού ≤n\le n με p(xi)=yip(x_i) = y_i:

p(x)=∑i=0nyi∏j≠ix−xjxi−xj.p(x) = \sum_{i=0}^{n} y_i \prod_{j \ne i} \frac{x - x_j}{x_i - x_j} .

Ύπαρξη: κάθε όρος είναι yiy_i στο xix_i και 00 στα υπόλοιπα κομβικά σημεία. Μοναδικότητα: ταυτοτική αρχή. Συγκρίνοντας τους συντελεστές του xnx^n παίρνεις τη χρήσιμη ταυτότητα: για deg⁡q≤n\deg q \le n, ο συντελεστής του xnx^n στο qq ισούται με ∑iq(xi)/∏j≠i(xi−xj)\sum_i q(x_i) / \prod_{j \ne i}(x_i - x_j).

Πεπερασμένες διαφορές. Ορίζουμε (Δp)(x)=p(x+1)−p(x)(\Delta p)(x) = p(x + 1) - p(x). Αν deg⁡p=n≥1\deg p = n \ge 1 με μεγιστοβάθμιο συντελεστή cc, τότε deg⁡Δp=n−1\deg \Delta p = n - 1 με μεγιστοβάθμιο συντελεστή ncnc, αφού (x+1)n−xn=nxn−1+…(x + 1)^n - x^n = n x^{n-1} + \dots. Επομένως Δnp=n! c\Delta^n p = n!\, c και Δn+1p=0\Delta^{n+1} p = 0. Γράφοντας Δ=E−I\Delta = E - I με (Ep)(x)=p(x+1)(Ep)(x) = p(x + 1), το διώνυμο δίνει

(Δmp)(x)=∑k=0m(−1)m−k(mk)p(x+k),∑k=0n+1(−1)k(n+1k)p(x+k)=0(deg⁡p≤n).(\Delta^m p)(x) = \sum_{k=0}^{m} (-1)^{m-k} \binom{m}{k} p(x + k), \qquad \sum_{k=0}^{n+1} (-1)^{k} \binom{n+1}{k} p(x + k) = 0 \quad (\deg p \le n).

Τύπος Newton. Κάθε pp βαθμού ≤n\le n γράφεται p(x)=∑k=0n(Δkp)(0)(xk)p(x) = \sum_{k=0}^{n} (\Delta^k p)(0) \binom{x}{k}, όπου (xk)=x(x−1)⋯(x−k+1)k!\binom{x}{k} = \frac{x(x-1)\cdots(x-k+1)}{k!}. (Και τα δύο μέλη έχουν βαθμό ≤n\le n και τις ίδιες διαφορές στο 00.)

Ακέραιες τιμές. Αν το pp έχει βαθμό ≤n\le n και παίρνει ακέραιες τιμές σε n+1n + 1 διαδοχικούς ακεραίους m,…,m+nm, \dots, m + n, τότε p(Z)⊆Zp(\Z) \subseteq \Z. Απόδειξη: εφάρμοσε τον τύπο Newton στο p(x+m)p(x + m)· οι διαφορές (Δkp)(m)(\Delta^k p)(m) είναι ακέραιοι, και τα (xk)\binom{x}{k} παίρνουν ακέραιες τιμές σε κάθε ακέραιο. Προσοχή: τέτοιο πολυώνυμο δεν έχει απαραίτητα ακέραιους συντελεστές, π.χ. x(x−1)2\frac{x(x-1)}{2}.

Ρίζες της μονάδας

Έστω ω=e2πi/n\omega = e^{2\pi i/n}. Οι ρίζες του xn−1x^n - 1 είναι οι 1,ω,…,ωn−11, \omega, \dots, \omega^{n-1}, άρα xn−1=∏k=0n−1(x−ωk)x^n - 1 = \prod_{k=0}^{n-1}(x - \omega^k).

Λήμμα (άθροισμα). Για ακέραιο jj,

∑k=0n−1ωjk={n,n∣j,0,n∤j.\sum_{k=0}^{n-1} \omega^{jk} = \begin{cases} n, & n \mid j, \\ 0, & n \nmid j. \end{cases}

Απόδειξη. Αν n∣jn \mid j όλοι οι όροι είναι 11. Αλλιώς ωj≠1\omega^j \ne 1 και η γεωμετρική πρόοδος δίνει ωjn−1ωj−1=0\frac{\omega^{jn} - 1}{\omega^j - 1} = 0.

Φίλτρο ρίζας της μονάδας. Αν P(x)=∑jajxjP(x) = \sum_j a_j x^j, τότε

∑j≡r (mod n)aj=1n∑k=0n−1ω−krP(ωk).\sum_{j \equiv r \ (\mathrm{mod}\ n)} a_j = \frac1n \sum_{k=0}^{n-1} \omega^{-kr} P(\omega^k) .

Απόδειξη. Το δεξί μέλος είναι ∑jaj⋅1n∑kωk(j−r)\sum_j a_j \cdot \frac1n \sum_k \omega^{k(j - r)}, και το εσωτερικό άθροισμα είναι 11 ή 00 από το λήμμα. Κλασικό παράδειγμα, με n=3n = 3 και P(x)=(1+x)mP(x) = (1 + x)^m:

∑j(m3j)=2m+2cos⁡(mπ/3)3,\sum_{j} \binom{m}{3j} = \frac{2^m + 2\cos(m\pi/3)}{3},

αφού 1+ω=eiπ/31 + \omega = e^{i\pi/3} και 1+ω2=e−iπ/31 + \omega^2 = e^{-i\pi/3}.

Το λήμμα με περιστρεφόμενα διανύσματα και το φίλτρο για n=3n = 3

Μέσος όρος πάνω στις ρίζες (Parseval). Αν deg⁡P<N\deg P < N και ζ=e2πi/N\zeta = e^{2\pi i/N}, τότε 1N∑k=0N−1∣P(ζk)∣2=∑j∣aj∣2\frac1N \sum_{k=0}^{N-1} |P(\zeta^k)|^2 = \sum_j |a_j|^2. Ανάπτυξε το ∣P∣2=PP‾|P|^2 = P \overline{P} και εφάρμοσε το λήμμα: επιβιώνουν μόνο οι όροι ajal‾a_j \overline{a_l} με j=lj = l, αφού ∣j−l∣<N|j - l| < N. Άρα, αν ∣P∣≤M|P| \le M στον μοναδιαίο κύκλο, τότε ∑j∣aj∣2≤M2\sum_j |a_j|^2 \le M^2.

Κυκλοτομικά πολυώνυμα. Το Φd(x)=∏(x−ζ)\Phi_d(x) = \prod (x - \zeta), με γινόμενο πάνω στις πρωταρχικές dd-οστές ρίζες, έχει βαθμό φ(d)\varphi(d) και ακέραιους συντελεστές, και

xn−1=∏d∣nΦd(x).x^n - 1 = \prod_{d \mid n} \Phi_d(x) .

Για πρώτο pp είναι Φp(x)=1+x+⋯+xp−1\Phi_p(x) = 1 + x + \dots + x^{p-1}. Π.χ. Φ3=x2+x+1\Phi_3 = x^2 + x + 1, Φ4=x2+1\Phi_4 = x^2 + 1, Φ6=x2−x+1\Phi_6 = x^2 - x + 1, Φ12=x4−x2+1\Phi_{12} = x^4 - x^2 + 1.

Έλεγχος διαιρετότητας. Αν το QQ έχει απλές ρίζες, τότε Q∣PQ \mid P αν και μόνο αν το PP μηδενίζεται σε κάθε ρίζα του QQ. Όταν το QQ είναι γινόμενο κυκλοτομικών, οι ρίζες του είναι ρίζες της μονάδας και η συνθήκη γίνεται αριθμητική στους εκθέτες mod nn. Παράδειγμα: x2+x+1∣x2m+xm+1x^2 + x + 1 \mid x^{2m} + x^m + 1 αν και μόνο αν 3∤m3 \nmid m.

Χρήσιμη ταυτότητα: θέτοντας x=1x = 1 στο xn−1x−1=∏k=1n−1(x−ωk)\frac{x^n - 1}{x - 1} = \prod_{k=1}^{n-1}(x - \omega^k) παίρνεις ∏k=1n−1(1−ωk)=n\prod_{k=1}^{n-1}(1 - \omega^k) = n.

Συζυγείς ρίζες

Λήμμα. Αν το pp έχει πραγματικούς συντελεστές και p(z)=0p(z) = 0, τότε p(zˉ)=0p(\bar z) = 0, με την ίδια πολλαπλότητα.

Απόδειξη. Αφού οι συντελεστές είναι πραγματικοί, p(zˉ)=p(z)‾=0p(\bar z) = \overline{p(z)} = 0. Για την πολλαπλότητα εφάρμοσε το ίδιο στα p′,p′′,…p', p'', \dots (λήμμα πολλαπλών ριζών).

Συνέπειες: το p∈R[x]p \in \R[x] παραγοντοποιείται σε γραμμικούς και τετραγωνικούς πραγματικούς παράγοντες· ένα πραγματικό πολυώνυμο περιττού βαθμού έχει πραγματική ρίζα.

Η ίδια ιδέα για ρητούς συντελεστές: αν a,b∈Qa, b \in \Q, b≠0b \ne 0, d∉Q\sqrt{d} \notin \Q και p(a+bd)=0p(a + b\sqrt d) = 0 με p∈Q[x]p \in \Q[x], τότε p(a−bd)=0p(a - b\sqrt d) = 0. Απόδειξη: διαίρεσε το pp με το m(x)=(x−a)2−b2d∈Q[x]m(x) = (x - a)^2 - b^2 d \in \Q[x], p=mq+(rx+s)p = m q + (rx + s) με r,s∈Qr, s \in \Q. Στο a+bda + b\sqrt d παίρνεις r(a+bd)+s=0r(a + b\sqrt d) + s = 0· αφού το d\sqrt d είναι άρρητο, r=0r = 0 και μετά s=0s = 0. Άρα m∣pm \mid p.

Rouché (προαιρετικό)

Αν τα f,gf, g είναι ολόμορφα σε ανοιχτό σύνολο που περιέχει τον κλειστό δίσκο ∣z∣≤R|z| \le R και ∣g(z)∣<∣f(z)∣|g(z)| < |f(z)| στον κύκλο ∣z∣=R|z| = R, τότε τα ff και f+gf + g έχουν τον ίδιο αριθμό ριζών (με πολλαπλότητα) στον δίσκο ∣z∣<R|z| < R. Παράδειγμα: για z5−5z+1z^5 - 5z + 1 πάρε f=−5zf = -5z, g=z5+1g = z^5 + 1· στον ∣z∣=1|z| = 1 είναι ∣g∣≤2<5=∣f∣|g| \le 2 < 5 = |f|, άρα υπάρχει ακριβώς μία ρίζα στον ανοιχτό μοναδιαίο δίσκο.

Πώς εμφανίζεται στο IMC

  • Συμμετρικές συναρτήσεις. Στο IMC 2000, 1η ημέρα, πρόβλημα 2 οι δύο εξισώσεις, μετά τη διαίρεση με w−zw - z, γράφονται με τα w+zw + z και wzwz. Στο IMC 2024, πρόβλημα 1 η συνθήκη στον μοναδιαίο κύκλο γίνεται πολυωνυμική εξίσωση που παραγοντοποιείται.
  • Λογαριθμική παράγωγος. Στο IMC 1998, 1η ημέρα, πρόβλημα 5 (πολυώνυμο με μόνο πραγματικές ρίζες) ξεκινάς από το p′/p=∑i(x−xi)−1p'/p = \sum_i (x - x_i)^{-1}.
  • Πολλαπλότητες. Στο IMC 2000, 2η ημέρα, πρόβλημα 3 μετράς ρίζες των pp και p−1p - 1 μαζί με τις πολλαπλότητές τους, χρησιμοποιώντας ότι έχουν την ίδια παράγωγο.
  • Ακέραιες τιμές και διαφορές. IMC 2007, 1η ημέρα, πρόβλημα 1· IMC 2011, 2η ημέρα, πρόβλημα 4· IMC 2020, πρόβλημα 4 (μια εξίσωση της μορφής Δp=q\Delta p = q).
  • Ρίζες της μονάδας. IMC 2008, 2η ημέρα, πρόβλημα 1 (διαιρετότητα πολυωνύμων μέσω των ριζών τους)· IMC 2007, 1η ημέρα, πρόβλημα 6 (ακέραιοι συντελεστές και φράγμα στον μοναδιαίο κύκλο, όπου βοηθά ο μέσος όρος Parseval).
  • Βαθμός και μεγιστοβάθμιος συντελεστής. Στο IMC 2025, πρόβλημα 1 ένα γεωμετρικό ερώτημα γίνεται εξίσωση για πολυώνυμο, και όλα κρίνονται από τον βαθμό του.

Παγίδες

  • Πολλαπλότητες στους τύπους Vieta. Οι x1,…,xnx_1, \dots, x_n μετριούνται με πολλαπλότητα. Μην υποθέτεις ότι είναι διακεκριμένες.
  • Ακέραιες τιμές ≠\ne ακέραιοι συντελεστές. Το (x2)\binom{x}{2} παίρνει ακέραιες τιμές αλλά έχει συντελεστή 12\frac12.
  • Το φίλτρο θέλει όλες τις nn ρίζες. Αν ξεχάσεις τον όρο k=0k = 0 (το P(1)P(1)), το αποτέλεσμα είναι λάθος.
  • Συζυγής ρίζα μόνο για πραγματικούς συντελεστές. Το x−ix - i έχει ρίζα ii αλλά όχι −i-i.

Θέματα διαγωνισμών με αυτά τα εργαλεία

Δεν υπάρχουν ακόμα θέματα με αυτά τα εργαλεία.