Every power sum, from the coefficients alone

What the coefficients already know read two facts about the roots of a polynomial straight off its coefficients: their sum and their product. Neither needed the roots. That essay stopped at two numbers, and the natural question is how far the trick goes. The sum of the squares of the roots, the sum of their cubes, the sum of their hundredth powers — are those sitting in the coefficients too?

They are, every one of them, and the rule that extracts them is Newton’s identities. Each power sum comes from the coefficients and the power sums before it, by a short formula in whole-number arithmetic. The roots appear nowhere in the computation. For a polynomial with whole-number coefficients and leading coefficient one, every answer is a whole number — which is not obvious at all, since the roots themselves are usually irrational, often complex, and never written down.

Four arrows that always land on the axis #

The picture is worth reading slowly, because it contains two separate surprises.

The first is that each walk ends on the real axis. The roots of this quartic are two complex pairs, and raising a complex number to a power turns it — the $k$-th power of a root sits at $k$ times its angle, as multiplication as turning explains. The four arrows in each panel point in four unrelated directions, and nothing in their lengths or angles looks like it should cancel. Yet the imaginary parts always cancel exactly. The reason is that the coefficients are real: the roots come in conjugate pairs, a pair’s $k$-th powers are conjugates again, and a number plus its conjugate is real. So the vertical parts of each walk come in equal and opposite pieces.

The second surprise is that the landing point is a whole number. That has no such quick explanation, and it is the content of this essay. The roots of $z^4 - z^3 + z^2 - 2z + 3$ are messy numbers — the quartic has no factor with whole-number coefficients, and its roots come out of nested square and cube roots — and their squares, cubes and fourth powers are messier. Added up, they give $1$, $-1$, $4$, $-5$.

The first of those is the one the coefficients already knew: the roots add to minus the coefficient of $z^3$, which is $1$. The second is the first new one, and it says something useful straight away. The sum of the squares of the roots is $-1$, a negative number. If all four roots were real, their squares would all be positive and so would their sum. So the polynomial has non-real roots, and the proof needed no root at all — only the two coefficients that the sum of squares turns out to depend on.

The rule, and where it comes from #

Write the polynomial as $z^n + a_{n-1}z^{n-1} + \dots + a_1 z + a_0$ and call its roots $r_1, \dots, r_n$. The power sums are $p_k = r_1^k + \dots + r_n^k$, with $p_0 = n$ because every root to the zeroth power is one.

The shortest route to the rule goes through the logarithmic derivative. Because the polynomial is the product of the factors $z - r_i$, its derivative divided by itself is a sum of simple fractions:

$$\frac{p'(z)}{p(z)} = \sum_{i=1}^{n} \frac{1}{z - r_i}.$$

For large $z$ each fraction expands as a geometric series, $\frac{1}{z - r} = \frac1z + \frac{r}{z^2} + \frac{r^2}{z^3} + \cdots$, and adding the expansions over all the roots collects the power sums as coefficients:

$$\frac{p'(z)}{p(z)} = \frac{p_0}{z} + \frac{p_1}{z^2} + \frac{p_2}{z^3} + \cdots.$$

Multiply both sides by $z\,p(z)$ and compare the coefficients of each power of $z$. The left side is $z\,p'(z)$, whose coefficients are the original ones multiplied by their exponents. The right side is the polynomial multiplied by the series of power sums. Matching the two, term by term, gives exactly one new equation for each $k$, and in each one the newest power sum $p_k$ appears once with coefficient one:

$$p_k + a_{n-1}p_{k-1} + a_{n-2}p_{k-2} + \dots + a_{n-k+1}p_1 + k\,a_{n-k} = 0.$$

That is Newton’s rule. Every quantity in it apart from $p_k$ is a coefficient or an earlier power sum, so each equation can be solved for the next sum and the computation walks upwards. In terms of the signed coefficients $e_k = (-1)^k a_{n-k}$ — the elementary symmetric functions of the roots, which is what the coefficients are — it reads $p_1 = e_1$, $p_2 = e_1p_1 - 2e_2$, $p_3 = e_1p_2 - e_2p_1 + 3e_3$, with the alternating pattern continuing.

The table is the whole of the computation. Nothing in the middle columns was taken from the roots: the fourth column is built entirely out of four coefficients and the entries above it, and the last column exists only to show that the arithmetic has been describing the roots all along. Since the rule multiplies and adds whole numbers and divides by nothing, a monic polynomial with whole-number coefficients has whole-number power sums of every order. That answers the landing-point question from the first figure — the walks end on whole numbers because the rule that computes where they end never leaves the whole numbers.

Past the degree, the polynomial becomes the rule #

A dashed line runs across the table below row four, and the formula changes character there.

For $k$ up to the degree $n$, each equation carries a final term $k\,a_{n-k}$, which injects one new coefficient. Past the degree there are no coefficients left to inject, and the rule is simply

$$p_k = -a_{n-1}p_{k-1} - a_{n-2}p_{k-2} - \dots - a_0\,p_{k-n}.$$

There is a one-line reason for this form that avoids the series entirely. Every root satisfies the polynomial, so $r^n = -a_{n-1}r^{n-1} - \dots - a_0$. Multiply through by $r^{k-n}$ and add the result over all the roots: the left side becomes $p_k$ and the right side becomes the same combination of earlier power sums. The power sums obey the polynomial as a recurrence, and the roots are exactly the numbers whose powers such a recurrence adds up.

That turns up in places that do not mention polynomials. The recurrence of $x^2 - x - 1$ is the Fibonacci rule, and its power sums start from $p_0 = 2$ and $p_1 = 1$: they are the Lucas numbers $2, 1, 3, 4, 7, 11, 18, \dots$, which are $\varphi^k + \psi^k$ for the golden ratio and its conjugate, and are whole although both terms are irrational. The same list, from $1$ on, appears in a matrix that counts the returns, as the number of points a map returns to after $k$ steps — computed there as the trace of the $k$-th power of a matrix. The coincidence is not one. The trace of a matrix power is the power sum of its eigenvalues, the eigenvalues are the roots of its characteristic polynomial, and that polynomial for the two-node graph there is $x^2 - x - 1$.

Read backwards, the same fact gives a way to compute a characteristic polynomial from traces alone, one coefficient per power of the matrix, which is how the determinant of a two-by-two matrix comes out as half of $(\operatorname{tr}A)^2 - \operatorname{tr}(A^2)$.

A cubic whose sums know the primes #

The cleanest example of the recurrence doing something unexpected is the cubic $x^3 - x - 1$. Its coefficients give $p_0 = 3$, $p_1 = 0$, $p_2 = 2$, and the recurrence past the degree is $p_k = p_{k-2} + p_{k-3}$. The sequence runs

$$3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, \dots$$

and is named after the French engineer Raoul Perrin, who wrote about it in 1899. Its roots are one real number $\rho = 1.32472\ldots$, called the plastic number, and a complex pair $\sigma$ and $\bar\sigma$ of modulus $0.8688$.

The figure separates the two parts of each term. The real root contributes $\rho^n$, which grows. The complex pair contributes $\sigma^n + \bar\sigma^n$, which is twice the real part of $\sigma^n$ — a point spiralling inwards, since its modulus is below one — and the bars are that contribution, oscillating in sign and shrinking geometrically. From $n = 10$ on it is smaller than a half, so Perrin’s number is the whole number nearest to the $n$-th power of the plastic number, exactly as the Lucas numbers are the whole numbers nearest the powers of the golden ratio. At $n = 30$ the power is $4610.019$ and the term is $4610$.

Now the arithmetic. Look at the remainder when the $n$-th term is divided by $n$.

Every prime $p$ divides $P(p)$. The reason is the roots, used once, for a proof rather than for a computation. In the ring of numbers built from $\rho$, $\sigma$ and $\bar\sigma$ by adding and multiplying, expand $(\rho + \sigma + \bar\sigma)^p$ by the multinomial theorem. Every mixed term carries a multinomial coefficient divisible by $p$, so

$$(\rho + \sigma + \bar\sigma)^p = \rho^p + \sigma^p + \bar\sigma^p + p\cdot(\text{something built from the roots}).$$

The left side is $P(1)^p = 0$ and the first three terms on the right are $P(p)$. So $P(p)$ is $p$ times an algebraic integer, and since $P(p)$ is an ordinary whole number, it is an ordinary multiple of $p$. This is Fermat’s little theorem moved from numbers to the roots of a polynomial: raising a sum to a prime power is, modulo that prime, the same as raising each part.

The converse is the tantalising part. Édouard Lucas had studied the sequence in 1876, and Perrin asked whether the property characterises the primes; checked by hand it seemed to. It fails, but not until $271{,}441 = 521^2$, found by William Adams and Daniel Shanks in 1982 with a computer. The figure checks every composite below twenty thousand and finds none — which is a fair picture of how long a false conjecture about primes can hide.

Enough sums to rebuild the polynomial #

Newton’s rule runs in both directions. In the equation for $p_k$ the coefficient $a_{n-k}$ appears once, multiplied by $k$, so the equation can be solved for the coefficient instead of the sum: given $p_1, \dots, p_k$, it returns $a_{n-k}$. So the first $n$ power sums of $n$ numbers determine the numbers, as the roots of the polynomial they rebuild. The sums of the first $n$ powers are a complete description of an unordered list of $n$ complex numbers, and the order was never there to lose.

Fewer sums leave room, and the room is easy to see.

The first two power sums pin down two coefficients and leave the constant term free. Every value of it gives a cubic with the same sum and the same sum of squares, and the roots of those cubics go wherever the constant sends them — three real roots for small $|c|$, one real root and a conjugate pair for large. Only the third sum, $-3c$, tells them apart.

There is one hidden condition in the backwards direction, and it is the division by $k$. Over the rational or real or complex numbers dividing by $k$ is harmless. In arithmetic modulo a prime $p$ it is impossible for $k = p$, and the rule genuinely breaks. Over the integers modulo 2, the polynomials $z^2$ and $z^2 + 1 = (z+1)^2$ have roots $0, 0$ and $1, 1$, and in both cases every power sum is zero, because one plus one is zero modulo two. Two different polynomials, identical power sums of every order. The coefficients can always be turned into power sums; the power sums can be turned back into coefficients only where the degree’s worth of divisions is allowed.

The discriminant is a determinant of power sums #

There is a second place the power sums were hiding in plain sight, and it connects them to a number this subject already treats as central. A shared root, found without finding it built the discriminant — the number that vanishes exactly when a polynomial has a repeated root — as a determinant of coefficients. It is also a determinant of power sums, and the reason fits in two lines.

Put the powers of the roots in a square array $V$, with the $i$-th row holding $r_1^i, r_2^i, \dots, r_n^i$ for $i$ from $0$ to $n - 1$. Multiplying $V$ by its own transpose adds up, in each entry, the products $r^i r^j$ over all the roots — which is the power sum $p_{i+j}$. So the array of power sums, with $p_{i+j}$ in row $i$ and column $j$, is $V$ times its transpose, and its determinant is the square of $\det V$. The square of that determinant, the product of all the squared differences $(r_i - r_j)^2$, is the discriminant.

Check it on Perrin’s cubic. The array is

$$\begin{pmatrix} 3 & 0 & 2 \\ 0 & 2 & 3 \\ 2 & 3 & 2 \end{pmatrix},$$

filled in from the first five terms of the sequence, and its determinant is $-23$, which is exactly the discriminant of $x^3 - x - 1$. The quartic of the first figure gives a four-by-four array from $p_0$ to $p_6$ and a determinant of $4345$, again its discriminant. A repeated root makes two columns of $V$ identical, kills its determinant, and so kills the array’s — which is the number that says how much room is left doing its usual job of detecting a collapse.

The array carries more than its determinant. Its eigenvalues are real, since it is symmetric, and the number that are positive minus the number that are negative is the number of distinct real roots. Perrin’s array has two positive eigenvalues and one negative, a difference of one: one real root, the plastic number. The quartic’s array has two of each, a difference of nought: no real roots, which the negative sum of squares had already proved. That is Charles Hermite’s method from the 1850s, and it rests entirely on sums computed by Newton’s rule.

What the arithmetic does for free #

It is worth collecting what the rule has handed over without a single root.

A reality test. A negative sum of squares proves a real polynomial has non-real roots, as the first figure’s quartic did, and the eigenvalue count of the previous section turns the same idea into an exact count of the real roots.

A size estimate. Because the largest root dominates the power sums once $k$ is large, the ratio $p_{k+1}/p_k$ approaches the root of largest modulus when there is one — Perrin’s sequence gives $1.3247\ldots$ from ratios of its terms. This is Daniel Bernoulli’s method of 1728 for finding the dominant root, and it is the power iteration of numerical linear algebra in disguise: the recurrence is multiplication by a matrix, and repeated multiplication singles out the largest eigenvalue.

Integrality. Anything that can be written as a symmetric polynomial in the roots with whole-number coefficients — not only power sums but any such expression — is a whole-number combination of the coefficients. The power sums are the cleanest case and the one with a recipe, and they were the route by which Albert Girard in 1629 and then Newton came to state it. It is the same principle that let on the circle and never home conclude that certain polynomials built from powers of roots have whole-number coefficients, which is the step that forces roots of unity to repeat.

What four arrows on a page cannot show #

Why the walks are whole. The figure shows four walks landing on four whole numbers, and a reader could suspect that the example was chosen to make that happen. It was not — any monic polynomial with whole-number coefficients would do — but the picture cannot say so. Integrality is a fact about the rule in the second figure, which adds and multiplies whole numbers and never divides, and no amount of looking at arrows would reveal it.

How much cancellation is going on. At higher powers the roots of modulus above one dominate and their arrows grow exponentially long, while the answer stays modest when those dominant roots come in a pair pointing in nearly opposite directions. The eighth power sum of the quartic is $-21$, the sum of four numbers of modulus $10.8$ and $7.5$ in pairs, so the answer is a small remainder left when large arrows nearly cancel. The panels are drawn at different scales so that each walk fits, which hides exactly how delicate the cancellation is by the eighth power.

The error in the check. The last column of the table agrees with the rule to four decimal places, which is all that is printed. The numerically found roots are accurate to about twelve digits, so the check is strong for small $k$ and weakens as the powers grow — the recurrence is exact at every $k$, and the roots, used to confirm it, are not.

Still open: a composite that passes both tests #

Perrin’s test failed at 271,441, and the same fate befell the obvious test from Fermat’s little theorem much earlier, at 341. A natural thought is to combine two tests whose false positives might not overlap. The Baillie–PSW test does exactly that: a composite must fool a Fermat-style test in base 2 and a test built on a Lucas sequence — the power sums $\alpha^n + \beta^n$ of the two roots of a carefully chosen quadratic, computed by the same recurrence as everything in this essay.

No composite that passes both is known. Every number below $2^{64}$ has been checked, which is why the test is used in practice to certify primes of ordinary size. Whether any composite passes it at all is open, and a heuristic argument of Carl Pomerance suggests that infinitely many should — just none small enough to have been found. The situation is Perrin’s conjecture again, one level up: a property the primes provably have, which the composites seem to avoid for as far as anyone has looked.

The recipe that never needed the roots #

Newton’s identities are a short loop: take the coefficients, multiply the earlier power sums by them, add, correct by one term while $k$ is still within the degree, and read off the next sum. The roots of the polynomial never enter, and yet the loop returns exactly the sums of their powers, whole numbers whenever the coefficients are.

Run forwards, the rule gives a reality test, the dominant root, the Lucas and Perrin numbers and the trace of every power of a matrix. Run backwards, it rebuilds a polynomial from $n$ of its sums, provided dividing by the numbers up to $n$ is allowed. And one use of the roots — not to compute anything, only to expand $(\rho + \sigma + \bar\sigma)^p$ — makes a sequence of whole numbers divisible by every prime, which is the most the arithmetic can promise and slightly less than it appeared to.