Newton's identities over finite fields

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.