Advanced Algebra: Root-of-Unity Filter + Newton's Identities + Interpolation

Notation: $e_k$ are the elementary symmetric polynomials of the roots ($e_1 = \sum x_i$, $e_2 = \sum_{i<j} x_i x_j$, ...) and $p_k = \sum x_i^k$ the power sums. Newton's identities link them: $p_k = e_1 p_{k-1} - e_2 p_{k-2} + \cdots + (-1)^{k}e_{k-1}p_1 + (-1)^{k+1} k\, e_k$. In practice you use the first few: $p_1 = e_1$; $p_2 = e_1 p_1 - 2e_2$; $p_3 = e_1 p_2 - e_2 p_1 + 3e_3$. Both directions matter — given a polynomial, compute power sums of roots WITHOUT finding the roots; given power sums, reconstruct the polynomial.

The killer application: 'suppose $x + y + z = a$, $x^2 + y^2 + z^2 = b$, $x^3 + y^3 + z^3 = c$; find $x^4 + \cdots$' or 'show $x, y, z$ are roots of...' — Newton converts the givens into $e_1, e_2, e_3$, which write down the cubic having $x, y, z$ as roots, and then EVERYTHING about $x, y, z$ is computable, including recursions for all higher $p_k$ via the polynomial itself ($p_k = e_1 p_{k-1} - e_2 p_{k-2} + e_3 p_{k-3}$ for $k > 3$).

Special case worth memorizing raw: $p_3 - 3e_3 = e_1(p_2 - e_2)$ rearranges to the factored classic $x^3 + y^3 + z^3 - 3xyz = (x+y+z)(x^2+y^2+z^2 - xy - yz - zx)$ — so $x + y + z = 0$ forces $p_3 = 3xyz$, a one-line collapse that appears constantly. When power sums and a vanishing $e_1$ meet, this identity is usually the intended door.

Pitfall. Sign slips in Newton's identities — the alternation $+,-,+,\dots$ and the final $k \, e_k$ coefficient are both traps. Re-derive the small cases from $(x+y+z)^2$ and $(x+y+z)^3$ expansions rather than trusting memory beyond $p_3$.

Lagrange interpolation: given $n+1$ points, the unique degree-$\le n$ polynomial through them is $P(x) = \sum_i y_i \prod_{j \ne i} \frac{x - x_j}{x_i - x_j}$. The contest uses are rarely about CONSTRUCTING $P$ — they are about what uniqueness forces: a degree-$n$ polynomial is overdetermined by $n+2$ conditions, so 'a polynomial of degree $n$ satisfying [$n{+}2$ nice conditions]' problems hide a forced identity or contradiction. The evaluation trick: to find $P$ at a NEW point (the classic 'deg-$n$ $P$ has $P(k) = \frac{k}{k+1}$ for $k = 0..n$; find $P(n{+}1)$'), work with $Q(x) = (x+1)P(x) - x$, which has $n+1$ known roots and known degree — one unknown constant, fixed by one more value ($Q(-1) = 1$).

Finite differences are interpolation's discrete twin: $\Delta P(x) = P(x+1) - P(x)$ drops degree by exactly one, so $\Delta^{n+1} P = 0$ for degree $n$ — giving the closed form $P(x) = \sum_k \Delta^k P(0) \binom{x}{k}$ (discrete Taylor, in the binomial basis). Two consequences do constant duty: a polynomial taking integer values on integers is an INTEGER combination of $\binom{x}{k}$ (not necessarily integer coefficients in the monomial basis!), and $\Delta^n$ applied to $x^n$ gives $n!$ — the fastest route to 'evaluate $\sum_k (-1)^k \binom{n}{k} k^n$' type alternating sums, since $\Delta^n P(0) = \sum_k (-1)^{n-k}\binom{n}{k}P(k)$.

Recognition rule: values of a polynomial on consecutive integers → finite differences; values on arbitrary points → Lagrange; more conditions than degree allows → uniqueness/contradiction. All three are the same fact — $n+1$ points determine degree $n$ — dressed for different data.

Pitfall. Forgetting that $Q$'s degree is $n+1$, not $n$ — the factor count must match the degree exactly before writing $Q = c\prod(x - k)$, and the leading constant $c$ is NOT 1 until proven. Count degrees, then spend one evaluation on $c$.

Week 8's filter extracted every $k$-th coefficient at the specific point 1. Full power is extracting at ANY evaluation and combining with other structure: $\sum_{n \equiv r (k)} \binom{N}{n} x^n = \frac{1}{k}\sum_j \omega^{-jr}(1 + \omega^j x)^N$, giving closed forms for filtered binomial sums with weights, not just counts. The modulus-3 and modulus-4 cases produce the exam's favorite constants — expressions in $\sqrt3$ and powers of 2 emerging from $(1 + \omega)^N$ via $1 + \omega = -\omega^2$ (norm 1, argument $\pi/3$).

The filter also runs on generating functions that are not $(1+x)^N$: any rational or product-form series you can EVALUATE at roots of unity is filterable — counting subsets with sum divisible by $k$, walks whose length is constrained mod $k$, strings avoiding patterns mod a period. The pipeline is always: encode as coefficients of $F(x)$, filter with $\frac{1}{k}\sum \omega^{-jr} F(\omega^j)$, and compute the handful of evaluations $F(\omega^j)$ — where step three is where all actual work lives, usually via $|1 + \omega^j|$ and argument bookkeeping.

The mature habit: before filtering, ask whether SYMMETRY already answers the question. Subset sums mod $p$ (prime, over $\{1, \dots, p\}$ or a full residue system) often distribute uniformly for reasons a bijection shows in two lines (shift every element by 1, cyclically); the filter then merely confirms uniformity with more machinery. Filter when residue classes are NOT symmetric — when the generating function's evaluations genuinely differ.

Pitfall. Filtering when a shift bijection already proves uniformity — or asserting uniformity when the classes are lopsided (as here: the answer is NOT $\frac{4^n}{3}$ rounded). Compute $F(\omega)$; its size IS the non-uniformity.

Eisenstein's criterion: if a prime $p$ divides every coefficient of $f(x) = a_n x^n + \cdots + a_0$ EXCEPT the leading one, and $p^2$ does not divide $a_0$, then $f$ is irreducible over $\mathbb{Q}$. Three hypotheses, all load-bearing: $p \mid a_i$ for $i < n$, $p \nmid a_n$, $p^2 \nmid a_0$. The proof idea worth owning is a valuation argument — in a hypothetical factorization, reduce mod $p$ and watch both factors get forced to powers of $x$, which contradicts $p^2 \nmid a_0$.

Most Eisenstein problems hide the prime behind a SHIFT: irreducibility is invariant under $x \mapsto x + a$ (a factorization of one is a factorization of the other), so when $f$ itself shows no usable prime, test $f(x+1)$ or $f(x-1)$. The classic payoff is the cyclotomic polynomial $\Phi_p(x) = x^{p-1} + \cdots + x + 1$: useless to Eisenstein as written, instantly Eisenstein after the shift.

Recognition on the exam: 'show this polynomial is irreducible' with a visible prime structure in the coefficients → Eisenstein directly; with clean coefficients like all-ones or binomial-flavored → shift first, then Eisenstein; with small degree ($\le 3$) → rational-root check is faster, since a cubic factors only through a linear factor.

Pitfall. Forgetting the $p^2 \nmid a_0$ hypothesis — without it Eisenstein is simply false ($x^2 - p^2$ passes the other two conditions at $p$ and factors). Also: Eisenstein failing proves NOTHING; a polynomial can be irreducible with no shift making Eisenstein apply.