uniolympiads Ελληνικά

Polynomials: Vieta, interpolation, roots of unity

Vieta and symmetric functions, multiple roots via gcd⁡(p,p′)\gcd(p, p'), integer polynomials, Lagrange interpolation and finite differences, roots of unity and filters.

What to know by heart

  • Division and roots. For every pp and aa we have p(x)=(x−a)q(x)+p(a)p(x) = (x - a)q(x) + p(a). So aa is a root exactly when (x−a)∣p(x - a) \mid p, and a nonzero polynomial of degree nn has at most nn roots.
  • Identity principle. Two polynomials of degree ≤n\le n that agree at n+1n + 1 points are equal: their difference has n+1n + 1 roots.
  • Fundamental theorem of algebra. Every p∈C[x]p \in \C[x] of degree n≥1n \ge 1 can be written p(x)=an(x−x1)⋯(x−xn)p(x) = a_n (x - x_1) \cdots (x - x_n).
  • Vieta's formulas. If p(x)=anxn+an−1xn−1+⋯+a0p(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_0 has roots x1,…,xnx_1, \dots, x_n, then
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 .

Proof. Expand an∏i(x−xi)a_n \prod_i (x - x_i): the coefficient of xn−kx^{n-k} collects all products of kk roots, with sign (−1)k(-1)^k.

Vieta and symmetric functions

Every symmetric polynomial in the roots is a polynomial in e1,…,ene_1, \dots, e_n, so it can be computed from the coefficients without finding the roots. In practice you need the power sums sk=x1k+⋯+xnks_k = x_1^k + \dots + x_n^k and Newton's identities:

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 .

For k>nk > n we have 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}. Proof: each root satisfies 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; multiply by xik−nx_i^{k-n} and sum.

Two more tools that come from the factorisation:

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).

The first one (the logarithmic derivative) is the basic tool for polynomials with only real roots: differentiating again, (p′/p)′=−∑i(x−xi)−2<0\big(p'/p\big)' = -\sum_i (x - x_i)^{-2} < 0 away from the roots.

Trick. If s2=e12−2e2<0s_2 = e_1^2 - 2e_2 < 0 for a polynomial with real coefficients, then not all roots are real.

Multiple roots and gcd⁡(p,p′)\gcd(p, p')

Lemma. aa is a root of pp of multiplicity ≥2\ge 2 if and only if p(a)=p′(a)=0p(a) = p'(a) = 0. More generally, a root of pp of multiplicity exactly m≥1m \ge 1 is a root of p′p' of multiplicity exactly m−1m - 1.

Proof. If p=(x−a)mqp = (x - a)^m q with q(a)≠0q(a) \ne 0, then p′=(x−a)m−1(mq+(x−a)q′)p' = (x - a)^{m-1}\big(m q + (x - a) q'\big), and the bracket equals mq(a)≠0m q(a) \ne 0 at aa.

Consequence. p∈C[x]p \in \C[x] has simple roots if and only if gcd⁡(p,p′)=1\gcd(p, p') = 1. For example xn−1x^n - 1 has nn distinct roots, since the only root of nxn−1n x^{n-1} is 00. The gcd⁡\gcd is computed by the Euclidean algorithm, so you do not need to know the roots.

Integer polynomials

Lemma. If p∈Z[x]p \in \Z[x] and a,b∈Za, b \in \Z, then (a−b)∣p(a)−p(b)(a - b) \mid p(a) - p(b).

Proof. 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}), and p(a)−p(b)p(a) - p(b) is an integer linear combination of such differences.

Consequences: if a≡b(modm)a \equiv b \pmod m then p(a)≡p(b)(modm)p(a) \equiv p(b) \pmod m; so if p(0)p(0) and p(1)p(1) are both odd, pp has no integer root (every integer is ≡0\equiv 0 or 1(mod2)1 \pmod 2).

Rational roots. If p(x)=anxn+⋯+a0∈Z[x]p(x) = a_n x^n + \dots + a_0 \in \Z[x] and r/sr/s is a root with gcd⁡(r,s)=1\gcd(r, s) = 1, then r∣a0r \mid a_0 and s∣ans \mid a_n.

Proof. Multiply p(r/s)=0p(r/s) = 0 by sns^n: anrn+an−1rn−1s+⋯+a0sn=0a_n r^n + a_{n-1} r^{n-1} s + \dots + a_0 s^n = 0. All terms except a0sna_0 s^n are divisible by rr, so r∣a0snr \mid a_0 s^n and, since gcd⁡(r,s)=1\gcd(r, s) = 1, r∣a0r \mid a_0. Similarly s∣anrns \mid a_n r^n, so s∣ans \mid a_n.

Example: for 2x3−x2+2x−12x^3 - x^2 + 2x - 1 the candidate roots are ±1,±12\pm 1, \pm \frac12, and indeed 2x3−x2+2x−1=(2x−1)(x2+1)2x^3 - x^2 + 2x - 1 = (2x - 1)(x^2 + 1).

Lagrange interpolation and finite differences

For distinct x0,…,xnx_0, \dots, x_n and values y0,…,yny_0, \dots, y_n there is exactly one polynomial of degree ≤n\le n with 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} .

Existence: each term equals yiy_i at xix_i and 00 at the other nodes. Uniqueness: the identity principle. Comparing coefficients of xnx^n gives a useful identity: for deg⁡q≤n\deg q \le n, the coefficient of xnx^n in qq equals ∑iq(xi)/∏j≠i(xi−xj)\sum_i q(x_i) / \prod_{j \ne i}(x_i - x_j).

Finite differences. Define (Δp)(x)=p(x+1)−p(x)(\Delta p)(x) = p(x + 1) - p(x). If deg⁡p=n≥1\deg p = n \ge 1 with leading coefficient cc, then deg⁡Δp=n−1\deg \Delta p = n - 1 with leading coefficient ncnc, since (x+1)n−xn=nxn−1+…(x + 1)^n - x^n = n x^{n-1} + \dots. Hence Δnp=n! c\Delta^n p = n!\, c and Δn+1p=0\Delta^{n+1} p = 0. Writing Δ=E−I\Delta = E - I with (Ep)(x)=p(x+1)(Ep)(x) = p(x + 1), the binomial theorem gives

(Δ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's formula. Every pp of degree ≤n\le n can be written p(x)=∑k=0n(Δkp)(0)(xk)p(x) = \sum_{k=0}^{n} (\Delta^k p)(0) \binom{x}{k}, where (xk)=x(x−1)⋯(x−k+1)k!\binom{x}{k} = \frac{x(x-1)\cdots(x-k+1)}{k!}. (Both sides have degree ≤n\le n and the same differences at 00.)

Integer values. If pp has degree ≤n\le n and takes integer values at n+1n + 1 consecutive integers m,…,m+nm, \dots, m + n, then p(Z)⊆Zp(\Z) \subseteq \Z. Proof: apply Newton's formula to p(x+m)p(x + m); the differences (Δkp)(m)(\Delta^k p)(m) are integers, and the (xk)\binom{x}{k} take integer values at every integer. Careful: such a polynomial does not necessarily have integer coefficients, e.g. x(x−1)2\frac{x(x-1)}{2}.

Roots of unity

Let ω=e2πi/n\omega = e^{2\pi i/n}. The roots of xn−1x^n - 1 are 1,ω,…,ωn−11, \omega, \dots, \omega^{n-1}, so xn−1=∏k=0n−1(x−ωk)x^n - 1 = \prod_{k=0}^{n-1}(x - \omega^k).

Lemma (sum). For an integer 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}

Proof. If n∣jn \mid j every term is 11. Otherwise ωj≠1\omega^j \ne 1 and the geometric series gives ωjn−1ωj−1=0\frac{\omega^{jn} - 1}{\omega^j - 1} = 0.

Root-of-unity filter. If P(x)=∑jajxjP(x) = \sum_j a_j x^j, then

∑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) .

Proof. The right-hand side is ∑jaj⋅1n∑kωk(j−r)\sum_j a_j \cdot \frac1n \sum_k \omega^{k(j - r)}, and the inner sum is 11 or 00 by the lemma. The classic example, with n=3n = 3 and 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},

since 1+ω=eiπ/31 + \omega = e^{i\pi/3} and 1+ω2=e−iπ/31 + \omega^2 = e^{-i\pi/3}.

The lemma as rotating vectors, and the filter for n=3n = 3

Averaging over the roots (Parseval). If deg⁡P<N\deg P < N and ζ=e2πi/N\zeta = e^{2\pi i/N}, then 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. Expand ∣P∣2=PP‾|P|^2 = P \overline{P} and apply the lemma: only the terms ajal‾a_j \overline{a_l} with j=lj = l survive, since ∣j−l∣<N|j - l| < N. So if ∣P∣≤M|P| \le M on the unit circle, then ∑j∣aj∣2≤M2\sum_j |a_j|^2 \le M^2.

Cyclotomic polynomials. Φd(x)=∏(x−ζ)\Phi_d(x) = \prod (x - \zeta), the product over the primitive dd-th roots of unity, has degree φ(d)\varphi(d) and integer coefficients, and

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

For a prime pp we have Φp(x)=1+x+⋯+xp−1\Phi_p(x) = 1 + x + \dots + x^{p-1}. E.g. Φ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.

Divisibility test. If QQ has simple roots, then Q∣PQ \mid P if and only if PP vanishes at every root of QQ. When QQ is a product of cyclotomic polynomials its roots are roots of unity, and the condition becomes arithmetic on the exponents mod nn. Example: x2+x+1∣x2m+xm+1x^2 + x + 1 \mid x^{2m} + x^m + 1 if and only if 3∤m3 \nmid m.

A useful identity: setting x=1x = 1 in xn−1x−1=∏k=1n−1(x−ωk)\frac{x^n - 1}{x - 1} = \prod_{k=1}^{n-1}(x - \omega^k) gives ∏k=1n−1(1−ωk)=n\prod_{k=1}^{n-1}(1 - \omega^k) = n.

Conjugate roots

Lemma. If pp has real coefficients and p(z)=0p(z) = 0, then p(zˉ)=0p(\bar z) = 0, with the same multiplicity.

Proof. Since the coefficients are real, p(zˉ)=p(z)‾=0p(\bar z) = \overline{p(z)} = 0. For the multiplicity apply the same to p′,p′′,…p', p'', \dots (the multiple-root lemma).

Consequences: p∈R[x]p \in \R[x] factors into real linear and quadratic factors; a real polynomial of odd degree has a real root.

The same idea for rational coefficients: if a,b∈Qa, b \in \Q, b≠0b \ne 0, d∉Q\sqrt{d} \notin \Q and p(a+bd)=0p(a + b\sqrt d) = 0 with p∈Q[x]p \in \Q[x], then p(a−bd)=0p(a - b\sqrt d) = 0. Proof: divide pp by 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) with r,s∈Qr, s \in \Q. At a+bda + b\sqrt d you get r(a+bd)+s=0r(a + b\sqrt d) + s = 0; since d\sqrt d is irrational, r=0r = 0 and then s=0s = 0. So m∣pm \mid p.

Rouché (optional)

If f,gf, g are holomorphic on an open set containing the closed disc ∣z∣≤R|z| \le R and ∣g(z)∣<∣f(z)∣|g(z)| < |f(z)| on the circle ∣z∣=R|z| = R, then ff and f+gf + g have the same number of zeros (with multiplicity) in the disc ∣z∣<R|z| < R. Example: for z5−5z+1z^5 - 5z + 1 take f=−5zf = -5z, g=z5+1g = z^5 + 1; on ∣z∣=1|z| = 1 we have ∣g∣≤2<5=∣f∣|g| \le 2 < 5 = |f|, so there is exactly one root in the open unit disc.

How it appears in the IMC

  • Symmetric functions. In IMC 2000, Day 1, Problem 2 the two equations, after dividing by w−zw - z, are written in terms of w+zw + z and wzwz. In IMC 2024, Problem 1 the condition on the unit circle becomes a polynomial equation that factors.
  • Logarithmic derivative. In IMC 1998, Day 1, Problem 5 (a polynomial with only real roots) you start from p′/p=∑i(x−xi)−1p'/p = \sum_i (x - x_i)^{-1}.
  • Multiplicities. In IMC 2000, Day 2, Problem 3 you count roots of pp and p−1p - 1 together with their multiplicities, using that they have the same derivative.
  • Integer values and differences. IMC 2007, Day 1, Problem 1; IMC 2011, Day 2, Problem 4; IMC 2020, Problem 4 (an equation of the form Δp=q\Delta p = q).
  • Roots of unity. IMC 2008, Day 2, Problem 1 (divisibility of polynomials through their roots); IMC 2007, Day 1, Problem 6 (integer coefficients and a bound on the unit circle, where the Parseval average helps).
  • Degree and leading coefficient. In IMC 2025, Problem 1 a geometric question becomes an equation for a polynomial, and everything is decided by its degree.

Pitfalls

  • Multiplicities in Vieta's formulas. The x1,…,xnx_1, \dots, x_n are counted with multiplicity. Do not assume they are distinct.
  • Integer values ≠\ne integer coefficients. (x2)\binom{x}{2} takes integer values but has the coefficient 12\frac12.
  • The filter needs all nn roots. If you forget the term k=0k = 0 (that is, P(1)P(1)), the result is wrong.
  • Conjugate root only for real coefficients. x−ix - i has the root ii but not −i-i.

Contest problems using these tools

No problems with these tools yet.