# Newton's identities over finite fields

The Newton identities (including over finite fields) are given by $$ke_k = \sum_{i=1}^k (-1)^{i-1} e_{k-i}p_i,$$ where the $e_k$ is the $k$-th elementary symmetric polynomials and the $p_k$ is the $k$-th power sum (see here http://en.wikipedia.org/wiki/Newton%27s_identities).

If we work modulo a prime $\ell$ (over the field $\mathbb{F}_e\\$) and $\ell \mid k$, obviously the identity becomes $0 = 0$. In this case nothing useful is said of $e_k$. My question is whether it is implicit in these identities (but not mentioned) that $$e_k = \left(\dfrac{1}{k}\sum_{i=1}^k (-1)^{i-1} e_{k-i}p_i \right)?$$ That is, $\ell \nmid \frac{1}{k}\sum_{i=1}^k (-1)^{i-1} e_{k-i}p_i$? Thanks.

• What do you mean by $1/k$, if you're working modulo a prime that divides $k$? Jun 8, 2015 at 1:00
• As in removable poles. Say $e_k = 5$ but the identity gives $2 e_k = 2 \cdot 5$ modulo $2$. Here $e_k = (\frac{1}{2} 2 \cdot 5)$. Basically lift the numbers modulo $\ell$ to $\mathbb{Z}$; simplify and get $e_k$ Jun 8, 2015 at 1:05

As Robert Israel explained, consequences of Freshman's dream ruin your day. Relations like $$p_\ell=p_1^\ell$$ make it clear that the power sums may not be algebraically independent even when the exponent is $<n$, if $\ell\le n$. The ring of symmetric polynomials in $n$ variables with coefficients in a field $K$ is always generated by $e_1,e_2,\ldots,e_n$. But if $n!$ is divisible by $\operatorname{char} K$, then, as we saw, it is not generated by $p_1,p_p,\ldots,p_n$. $K[p_1,p_2,\ldots,p_n]$ is then a proper subring of $K[e_1,e_2,\ldots,e_n]$.

It is still often possible to recover the missing $e_i$:s, but we need to use power sums $p_i, i>n$, and we need to work with fields of rational functions. The simplest case is that from Robert's answer, so let's continue with $n=2=\ell$. We get (by Newton, or just a straightforward characteristic two calculation) $$p_3=X_1^3+X_2^3=(X_1+X_2)^3-3X_1X_2(X_1+X_2)=e_1^3+e_2e_1.$$ We can solve for $e_2$ here $$e_2=\frac{p_3+e_1^3}{e_1}=\frac{p_3+p_1^3}{p_1}.$$ So we see that $e_2\in K(p_1,p_3)$. So in this case we can conclude that the fields of symmetric rational functions $$K(e_1,e_2)=K(p_1,p_3).$$ IIRC this generalizes to any number of variables $n$ and any characteristic $\ell$ in the sense that the fields $K(e_i\mid 1\le i\le n)$ and $K(p_i\mid 1\le i)$ have the same transcendence degree, so the former is a finite extension of the latter. I'm ashamed to admit that at the moment I don't know/remember whether they are always equal.

To close I cannot resist the temptation to bring up a point near and dear to my heart. When decoding a received word of a double-error-correcting binary BCH code the receiver's task is to figure out the error locations $X_1$ and $X_2$ based on syndromes that are exactly the power sums $p_i$. Because we are in characteristic two, the above observations imply that the receiver can successfully calculate the (error locator) polynomial $$(T-X_1)(T-X_2)=T^2+e_1T+e_2,$$ if they know $p_1$ and $p_3$. That BCH-code is defined in terms of power sums $p_1$ and $p_3$, so this is just what the doctor ordered! We also notice that the case $p_1=0$, $p_3\neq0$ is a nasty special case, because our formula for $e_2$ then attempts to divide by zero.

• Thank you Jyrki. Would you remember a reference for this? Actually I'm especially interested in the case of the elementary symmetrics that produce the coefficients of characteristic polynomials over GF(2). The characteristic polynomial of $\alpha$ is $\prod_{i=0}^{n-1}(x - \alpha^{2^i})$. Then $e_k = \sum \alpha^{2^{i_1} + \cdots + 2^{i_k}}$. Note the power sums are $p_k = Tr(\alpha^k)$, where $Tr$ is the trace function from $\mathbb{F}_{2^n}$ to $\mathbb{F}_2$. I would like to write down $e_k$, even when $2 \mid k$, in terms of a (non-linear) combination of the $p_i$ here. Jun 8, 2015 at 16:33
• In this special case is there anything more precise that can be said of $e_k$ when $2 \mid k$? Jun 8, 2015 at 16:35
• Do you know if this generalizes to a statement of the form "Over finite fields, elementary symmetric polynomials of degree up to $d$ are in the algebra of the 'power symmetric polynomials' of degree up to $d'$" for some $d'$ related to $d$? Jul 5, 2015 at 13:11

For example, take $\ell = 2$, and two variables. The identity for $k=2$: $$2 e_2 = e_1 p_1 - p_2 = e_1^2 - p_2$$ i.e. $$2 X_1 X_2 = (X_1 + X_2)^2 - (X_1^2 + X_2^2)$$ Mod $2$, this is just the identity $$(X_1 + X_2)^2 = X_1^2 + X_2^2$$ $e_1 = X_1 X_2$ is not in the ideal generated by $X_1 + X_2$ and $X_1^2 + X_2^2$ over $\mathbb F_2$. For example, with $X_1 = X_2 = 1$ you have $X_1 + X_2 = X_1^2 + X_2^2 = 0$, but $X_1 X_2 = 1$.

• Thank you very much. Would you know if there's anything useful that can be said about $e_k$ when $\ell \mid k$, say in the style of Newton's identities or in terms of non-linear combinations of the power sums? Thanks again. Jun 8, 2015 at 5:26

To expand upon Jyrki's answer, it is true that the elementary symmetric polynomials can always be written as rational functions in the power sums, and there is an algorithm to determine how. See this preprint for the details, especially Thm 2.8 and its proof.