Symmetric functions — flashcards

Power sums and elementary symmetric polynomials determine each other by a triangular system. This is how information moves between a polynomial's roots and its coefficients without any root ever being computed.

A monic degree-n polynomial needs exactly n roots plus one scale (n+1 numbers) however it's written, but the two standard forms differ in more than notation. Coefficient form is evaluated by Horner's method, a sequential multiply-accumulate whose step k reads step k-1's output by construction — an unavoidable Θ(n) sequential critical path (parallel depth). Root form q∏(x-rᵢ) evaluates its n linear factors independently, then combines them by a parallel product reduction, giving Θ(log n) depth — the standard gap between a linear-recurrence/fold pattern and an associative-reduction pattern, general to computation and not special to polynomials. The mechanism behind the asymmetry: each root-form factor is x read in that root's own private frame (no shared origin across factors), so evaluating in parallel needs no shared reference to compare partial results, only an intrinsic tag (how many factors have deferred to the shared coordinate so far) — a count, not a position. Coefficient form, by contrast, is built by successively converting shared-frame data, which is exactly why extracting it (via Newton's identities, converting power sums to elementary symmetric functions — st/newton-identities) is itself sequential even though it never touches an actual root.

An entire function of controlled growth is determined by its zeros up to an exponential factor. This — completeness of the zero set plus a growth bound — is what licenses Euler's product for sine, not the fact that the zeros happen to be evenly spaced.

ζ(2) = π²/6, obtained by reading the second coefficient of the sine product as an elementary symmetric function of the reciprocal zeros. The inference runs from coefficients to statistics of the roots, not the other way round.

Different families of tractable roots — the falling factorial (Stirling numbers of the first kind), geometric-progression roots (q-calculus, Gaussian binomial coefficients, the q-Pochhammer symbol), Chebyshev nodes (literal projections of roots of unity onto a diameter), and Legendre/Jacobi polynomial roots (eigenvalues of the tridiagonal Jacobi matrix from a three-term recurrence) — are cases of one underlying variational principle: Fekete points, the n→∞ minimizer of −∑ log|rᵢ−rⱼ| over i≠j. With no external field this minimizer is the uniform (arcsine) distribution 1/(π√(1−x²)) on [−1,1], the equilibrium measure. A genuinely different mechanism produces tractable roots without this variational structure: the Ginibre ensemble (eigenvalues of a random Gaussian matrix, uniform on a disk), tractable via random-matrix universality rather than an energy minimization.

Any two complete decompositions of a polynomial into indecomposable factors under composition have the same length, and are related by explicit moves. Compositional structure is nearly unique, with Chebyshev polynomials and monomials the named exceptions.

st/dwork-rationality establishes the zeta function of a variety over a finite field is rational (the first Weil conjecture); the second Weil conjecture (the 'Riemann Hypothesis for curves') states its zeros satisfy |α|=√q. Both were made concrete rather than merely cited: a genus-2 hyperelliptic curve over F_11 was built, its point counts over F_11 and F_121 fed through Newton's identities (st/newton-identities) to obtain the Frobenius characteristic polynomial exactly, and its roots verified to satisfy |α|=√q to eight decimal places. This was then scaled into an actual statistical family — 101 curves at q=11, then 861 at q=31 using a vectorized finite-field-arithmetic implementation — pooling Frobenius angles and tracking the emergence of symplectic-ensemble (USp(4)) endpoint repulsion as q grows, the predicted structure for this family type.

The reciprocal-square identity π²/sin²(πx) = ∑_{n=−∞}^{∞} 1/(x−n)², obtained by Wästlund's lighthouse argument: equal-brightness sources at every integer, brightness ∝ 1/distance², a circle-doubling construction using the inverse-Pythagorean identity 1/a²+1/b²=1/h² at a right angle, iterated to infinity. x = 1/2 gives ∑ 1/(n−1/2)² = π², which is 8 times the sum of reciprocal squares over the positive odd integers, so that sum is π²/8; since ζ(2) = (odd sum) + ¼ζ(2), this forces ζ(2) = π²/6 — Euler's destination, reached by an elementary route with no complex analysis.

Log-differentiating Euler's sine product sin(πx) = πx·∏(1−x²/n²) once gives the cotangent partial-fraction expansion π cot(πx) = ∑ 1/(x−n); differentiating again gives π²/sin²(πx) = ∑ 1/(x−n)² — exactly the lighthouse formula (st/lighthouse-reciprocal-square). Wallis' product is instead the x=1/2 evaluation of the original, undifferentiated product. So the lighthouse/Basel identity and Wallis' product are two different operations — differentiate twice, versus evaluate at 1/2 — performed on the same underlying product, not two independent facts that happen to coincide.

The Wallis product 2/1·2/3·4/3·4/5·⋯ = π/2 has at least three independent derivations that manage error differently, not three restatements of one argument. (1) Analytic: it is the x=1/2 evaluation of Euler's undifferentiated sine product sin(πx) = πx·∏(1−x²/n²) (st/basel-wallis-same-product) — a substitution into an already-established product, with no limiting process of its own beyond the product's own convergence. (2) Geometric/algebraic: N evenly-spaced points on a circle as the roots of x^N−1, giving two exact finite-N lemmas (observer halfway between two points: distance product = 2; observer replacing one point: distance product = N) whose ratio N·(distance)/2 is an *exact* invariant at every finite N — a single limit, taken once at the very end as N→∞, converts that invariant into π/2 via chord-length-to-arc-length convergence. (3) Classical calculus: Wallis's own route via the reduction formula ∫₀^(π/2) sin^n θ dθ, giving the asymptotic (2n)!!/(2n−1)!! ∼ √(πn) — which stacks two separate approximations (a pointwise limit inside the reduction, and an asymptotic equivalence) that must cancel jointly, rather than carrying one exact quantity to a single final limit. Routes (2) and (3) both pass through the same trigonometric object — a quarter-circle arc — entered through different doors: chord geometry directly, versus a sine substitution turning an algebraic integral into an arc-length integral.

Chord(f) = 2sin(fπ) reduces the question 'which rational f give a rational chord length?' to Niven's theorem: rational values of sin(θ) at rational-multiple-of-π angles θ are confined to {0, ±1/2, ±1}. Translated back, Chord(f) is rational for rational f∈[0,1] only at f=0, 1/6, 1/2, 5/6, 1 — f=1/2 (Wallis' own case) is not the only one, contrary to the natural first guess. At f=1/6 (Chord=1), the same product identity underlying st/wallis-product-three-routes' route (2), ∏_{k≠0} k/(k−f) = f·2π/Chord(f), generalizes cleanly to a second explicit Wallis-type product converging to π/3.

Isaac Newton, c. 1666, published 1707.

Karl Weierstrass, then Jacques Hadamard, 1876 (Weierstrass), 1893 (Hadamard).

Leonhard Euler, 1735.

Joseph Ritt, 1922.

Johan Wästlund, 2010 (Wästlund's paper); popularized 2018 by 3Blue1Brown.

A generating function carries an entire sequence in a single expression; which coefficients you can cheaply extract is a statement about how much of the sequence you needed to store to begin with.

Power sums are the symmetric functions you get by fixing a particular basis. Newton's identities convert between the choices, which is what makes the choice visible as a choice.

Elementary symmetric polynomials, power sums, and Newton's identities converting between them. The precise machinery for moving between a polynomial's roots and its coefficients without ever solving for a root.