Let k \geq 0 be an integer.  The concept of a polynomial P: {\Bbb R} \to {\Bbb R} of one variable of degree <k (or \leq k-1) can be defined in one of two equivalent ways:

  • (Global definition) P: {\Bbb R} \to {\Bbb R} is a polynomial of degree <k iff it can be written in the form P(x) = \sum_{0 \leq j < k} c_j x^j for some coefficients c_j \in {\Bbb R}.
  • (Local definition) P: {\Bbb R} \to {\Bbb R} is a polynomial of degree <k if it is k-times continuously differentiable and \frac{d^k}{dx^k} P \equiv 0.

From single variable calculus we know that if P is a polynomial in the global sense, then it is a polynomial in the local sense; conversely, if P is a polynomial in the local sense, then from the Taylor series expansion

\displaystyle P(x) = \sum_{0 \leq j < k} \frac{P^{(j)}(0)}{j!} x^j

we see that P is a polynomial in the global sense. We make the trivial remark that we have no difficulty dividing by j! here, because the field {\Bbb R} is of characteristic zero.

The above equivalence carries over to higher dimensions:

  • (Global definition) P: {\Bbb R}^n \to {\Bbb R} is a polynomial of degree <k iff it can be written in the form P(x_1,\ldots,x_n) = \sum_{0 \leq j_1,\ldots,j_n; j_1+\ldots+j_n < k} c_{j_1,\ldots,j_n} x_1^{j_1} \ldots x_n^{j_n} for some coefficients c_{j_1,\ldots,j_n} \in {\Bbb R}.
  • (Local definition) P: {\Bbb R}^n \to {\Bbb R} is a polynomial of degree <k if it is k-times continuously differentiable and (h_1 \cdot \nabla) \ldots (h_k \cdot \nabla) P \equiv 0 for all h_1,\ldots,h_k \in {\Bbb R}^n.

Again, it is not difficult to use several variable calculus to show that these two definitions of a polynomial are equivalent.

The purpose of this (somewhat technical) post here is to record some basic analogues of the above facts in finite characteristic, in which the underlying domain of the polynomial P is F or F^n for some finite field F.  In the “classical” case when the range of P is also the field F, it is a well-known fact (which we reproduce here) that the local and global definitions of polynomial are equivalent.  But in the “non-classical” case, when P ranges in a more general group (and in particular in the unit circle {\Bbb R}/{\Bbb Z}), the global definition needs to be corrected somewhat by adding some new monomials to the classical ones x_1^{j_1} \ldots x_n^{j_n}.  Once one does this, one can recover the equivalence between the local and global definitions.

(The results here are derived from forthcoming work with Vitaly Bergelson and Tamar Ziegler.)

– General theory –

One can extend the local definition of a polynomial to cover maps P: G \to H for any additive groups G, H.  (There is also an important generalisation of this concept to the case of nilpotent groups; we will not concern ourselves with this generalisation here, but see this paper of Leibman [as well as this followup paper].)  Given any such map, and any h \in G, define the shift T^h P: G \to H and the (discrete) derivative \Delta_h P: G \to H by the formulae

T^h P(x) := P(x+h); \Delta_h P = T^h P - P,

thus schematically we have

\Delta_h = T^h - 1. (1)

We say that P is an (additive) polynomial of degree <k (or degree \leq k-1) if \Delta_{h_1} \ldots \Delta_{h_k} P = 0 for all h_1,\ldots,h_k \in G.  Note that this corresponds to the definition of a classical polynomial from {\Bbb R}^n to {\Bbb R} once one adds some regularity conditions, such as k-times differentiability (actually, measurability will already suffice).

Examples 1. The zero function has degree <0.  A constant function has degree \leq 0.  A  homomorphism has degree \leq 1.  Composing a polynomial of degree \leq k with a homomorphism (either on the left or right) will give another polynomial of degree \leq k.  The sum of two polynomials of degree \leq k is again of degree \leq k.  The derivative \Delta_h P of a polynomial of degree <k is of degree <k-1.  Since T^h P = P + \Delta_h P, we conclude that the shift of any polynomial of degree <k is also of degree <k. \diamond

Now we show that the product and composition of polynomials is again a polynomial.

Lemma 1. (Product of polynomials is again polynomial)  Let P: G \to H, Q: G \to K be polynomials of degree \leq h, \leq k respectively for some h,k \geq 0, and let B: H \times K \to L be a bilinear map.  Then B(P,Q) is a polynomial of degree \leq h+k.

Proof. We induct on h+k.  The claim is easy when h or k is zero, so suppose that h,k > 0 and the claim has already been proven for smaller values of h+k.  From the discrete product rule

\Delta_g B(P,Q) = B( \Delta_g P, Q ) + B( T^g P, \Delta_g Q )

and induction we see that \Delta_g B(P,Q) is of degree \leq h+k-1, and thus B(P,Q) has degree \leq h+k as desired.  \Box

Corollary 1. If H is a ring, then the product of two polynomials from G to H of degree \leq h, \leq k respectively is of degree \leq h+k.

Lemma 2. (Composition of polynomials is again polynomial)  Let P: G \to H, Q: H \to K be polynomials of degree \leq h, \leq k respectively for some h,k \geq 0.  Then Q \circ P: G \to K is a polynomial of degree \leq hk.

Proof. For inductive reasons it is convenient to prove the following more general statement: if P: G \to H, Q: H \to K are polynomials of degree \leq h+m, \leq k respectively for some m,h,k \geq 0, and R_1,\ldots,R_m: G \to H are polynomials of degree \leq r_1,\ldots,\leq r_m respectively, where 0 \leq r_j \leq k for all j, then the function S: G \to K defined by

S(x) := [\Delta_{R_1(x)} \ldots \Delta_{R_m(x)} P]( Q(x) )

is a polynomial of degree hk+r_1+\ldots+r_m.  Clearly Lemma 2 follows from the m \geq 0 case of this claim.

We prove this claim by induction on h, then for fixed h by induction on m, then for fixed h and m by induction on r_1+\ldots+r_m.  Thus, assume that the claim has already been shown for all smaller values of h, or for the same value of h and all smaller values of m, or for the same values of h,m and all smaller values of r_1+\ldots+r_m.

If r_m=0 then R_m is constant, and by replacing P with \Delta_{R_m} P and decrementing m, we see that the claim follows from the induction hypothesis.  Similarly if any other of the r_j vanish (since the derivative operators commute with each other).  So we may assume that r_j > 0 for all j.

Let g in G.  By considering the successive differences between the quantities

S(x) = [\Delta_{R_1(x)} \Delta_{R_2(x)} \ldots \Delta_{R_m(x)}]( Q(x) )

{}[\Delta_{R_1(x)} \Delta_{R_2(x)} \ldots \Delta_{R_m(x)}]( T_g Q(x) )

{}[\Delta_{T_g R_1(x)} \Delta_{R_2(x)} \ldots \Delta_{R_m(x)}]( T_g Q(x) )

{}[\Delta_{T_g R_1(x)} \Delta_{T_g R_2(x)} \ldots \Delta_{R_m(x)}]( T_g Q(x) )

\vdots

T_g S(x) = {}[\Delta_{T_g R_1(x)} \Delta_{T_g R_2(x)} \ldots \Delta_{T_g R_m(x)}]( T_g Q(x) ),

we see that \Delta_g S(x) is the sum of

{}[\Delta_{R_1(x)} \Delta_{R_2(x)} \ldots \Delta_{R_m(x)} \Delta_{\Delta g Q(x)} P]( Q(x) )

{}[\Delta_{\Delta_g R_1(x)} \Delta_{R_2(x)} \ldots \Delta_{R_m(x)}]( R_1(x) + T_g Q(x) )

{}[\Delta_{T_g R_1(x)} \Delta_{\Delta_g R_2(x)} \ldots \Delta_{R_m(x)} \Delta_g]( R_2(x) + T_g Q(x) )

\vdots

{}[\Delta_{T_g R_1(x)} \Delta_{T_g R_2(x)} \ldots \Delta_{\Delta_g R_m(x)} \Delta_g]( R_m(x) + T_g Q(x) ).

By the induction hypothesis, each of these terms are polynomials of degree \leq hk+r_1+\ldots+r_m-1. The claim follows. \Box

– The classical case –

Now we consider polynomials taking values in a finite field F.

Lemma 3. (Global description of classical one-dimensional polynomials) Let F be a field of prime order p.  For any k \geq 0, a function P: F \to F is of degree <k if and only if we can expand P(x) = \sum_{0 \leq j < k} c_j x^j for some coefficients c_j \in F; this expansion is unique for k \leq p.  Also, every function P: F \to F is a polynomial of degree <p.

Proof. The “if” portion of the lemma follows from Corollary 1 (since the identity function x \mapsto x is clearly of degree \leq 1).  For the “only if” part, observe from the binomial identity

\displaystyle T^h = (1 + \Delta_1)^h = \sum_{j=0}^h \binom{h}{j} \Delta_1^j

for any non-negative integer h, that

\displaystyle f(h) = \sum_{j=0}^h \binom{h}{j} \Delta_1^j f(0).

Since h \mapsto \binom{h}{j} = \frac{h(h-1)\ldots(h-j+1)}{j!} can be meaningfully defined on F for 0 \leq j < p, we conclude in particular that f(h) = \sum_{j=0}^{p-1} \binom{h}{j} \Delta_1^j f(0).

Since \binom{h}{j} can be expanded as a linear combination over F of 1, h, \ldots, h^j, we obtain the remaining claims in Lemma 3.  (Note that as the space of functions from F to F is p-dimensional, and generated by 1, x, \ldots, x^{p-1}, these functions must be linearly independent.) \Box

Corollary 2. (Integration lemma) Let f: F \to F be a polynomial of degree \leq k for some 0 \leq k \leq p-2, and let h \in F \backslash 0.  Then there exists a polynomial P: F \to F of degree \leq k+1 such that f = \Delta_h P.  (In particular, this implies the mean zero condition \sum_{x \in F} f(x) = 0.  Conversely, any function f: F \to F with \sum_{x \in F} f(x) = 0 is a polynomial of degree \leq p-2.

Proof. From Lemma 3, the space of polynomials of degree \leq k and \leq k+1 is a vector space over F of dimension k+1 and k+2 respectively.  The derivative operator \Delta_h is a linear transformation from the latter to the former with a one-dimensional kernel (the space of constants), and must therefore be surjective.  The first claim follows. The second claim follows by a similar dimension counting argument. \Box

We can iterate Lemma 3 to describe polynomials in higher dimensions:

Lemma 4. (Global description of classical multi-dimensional polynomials) Let F be a field of prime order p, and let  n \geq 1.  For any k \geq 0, a function P: F^n \to F is of degree <k if and only if we can expand P(x_1,\ldots,x_n) = \sum_{0 \leq j_1,\ldots,j_n: j_1+\ldots+j_n < k} c_{j_1,\ldots,j_n} x_1^{j_1} \ldots x_n^{j_n} for some coefficients c_{j_1,\ldots,j_n} \in F.

Proof. As before, the “if” portion follows from Corollary 1, so it suffices to show the “only if” portion.  But this follows by a multidimensional version of the analogous argument used to show Lemma 3, starting with the identity

T^{(h_1,\ldots,h_n)} = (1 + \Delta_{e_1})^{h_1} \ldots (1+\Delta_{e_n})^{h_n}

for non-negative integers h_1,\ldots,h_n, where e_1,\ldots,e_n is the standard basis of F^n; we leave the details to the reader.  \Box

Remark 2. The above discussion was for fields F = F_p of prime order, but we can use these results to describe classical polynomials for fields F = F_{p^m} of prime power order, by viewing any vector space over F_{p^m} as a vector space over F_p.  Of course, the resulting polynomials one obtains are merely polynomials over F_p, rather than over F_p^m. \diamond

– The non-classical case –

Now we consider polynomials from F or F^n into other additive groups, where F=F_p is as before a field of prime order p.  Thanks to Pontryagin duality, it suffices (in principle, at least) to consider polynomials taking values in the unit circle {\Bbb R}/{\Bbb Z}.  The first basic lemma is the following (taken from my forthcoming paper with Bergelson and Ziegler):

Lemma 5. (Multiplication by p reduces degree) Let f: F^n \to {\Bbb R}/{\Bbb Z} be of degree \leq k+p-1 for some k\geq 0.  Then pf is of degree \leq k.

Proof. Since \Delta_h (pf) = p \Delta_h f for any h, we see by induction that it suffices to show this lemma when k=0.

Let h \in F^n.  Raising (1) to the p^{th} power we have

T^{ph} = 1 + p \Delta_h + \frac{p(p-1)}{2} \Delta_h^2 + \ldots + p \Delta_h^{p-1} + \Delta_h^p.

Of course, T^{ph} = 1.  Applying this identity to f and noting that \Delta_h^p f = 0 by hypothesis, we conclude that

(1 + \frac{p-1}{2} \Delta_h + \ldots + \Delta_h^{p-2}) \Delta_h (pf) = 0.

Inverting (1 + \frac{p-1}{2} \Delta_h + \ldots + \Delta_h^{p-2}) using Neumann series (and the finite degree of f) we conclude that \Delta_h(pf)=0 for all h, thus pf has degree \leq 0 as required. \Box

Corollary 3. (Polynomials are discretely valued) If f: F^n \to {\Bbb R}/{\Bbb Z} is of degree \leq k, then after subtracting a constant from f, f takes values in the (p^{\lfloor (k-1)/(p-1)\rfloor+1})^{th} roots of unity.

In one dimension, there is a converse to Lemma 5:

Lemma 6. Let f: F^n \to {\Bbb R}/{\Bbb Z} be such that pf has degree \leq k.  Then f has degree \leq k+p-1.

Proof. As in Lemma 5, it suffices to establish the case k=0.  But this then follows from the last part of Lemma 3. \Box

As a corollary we can classify all non-classical polynomials:

Theorem 1. (Global description of non-classical multi-dimensional polynomials)  A function f: F^n \to {\Bbb R}/{\Bbb Z} is a polynomial of degree <k if and only if it has the form

\displaystyle f(x) = c_0 + \sum_{0 \leq j_1,\ldots,j_n \leq p-1; m \geq 1: j_1+\ldots+j_n+(p-1)(m-1) < k}

\displaystyle c_{j_1,\ldots,j_m,m} |x_1|^{j_1} \ldots |x_n|^{j_n}/p^m

for some c_0 \in {\Bbb R}/{\Bbb Z} and c_{j_1,\ldots,j_m,m} \in \{0,\ldots,p-1\}, where x \mapsto |x| is the obvious map from F to \{0,\ldots,p-1\}.

Proof. The “if” part follows easily from Lemma 4 in the case k \leq p, and then from Lemma 6 and induction in the general case.  The “only if” part follows from Corollary 3 and Lemma 4 in the case k \leq p.  Now suppose inductively that k > p and the claim has already been proven for smaller values of k.  By Lemma 5 and the induction hypothesis, pf takes the form

\displaystyle pf(x) = c'_0 + \sum_{0 \leq j_1,\ldots,j_n \leq p-1; m \geq 1: j_1+\ldots+j_n+(p-1)(m-1) < k-p+1}

\displaystyle c'_{j_1,\ldots,j_n,m} |x_1|^{j_1} \ldots |x_n|^{j_n}/p^m

and thus

\displaystyle f(x) = c_0 + \sum_{0 \leq j_1,\ldots,j_n \leq p-1; m \geq 1: j_1+\ldots+j_n+(p-1)(m-1) < k-p+1}

\displaystyle c'_{j_1,\ldots,j_n,m} |x_1|^{j_1} \ldots |x_n|^{j_n}/p^{m+1} + g(x)

where c_0 is a p^{th} root of c'_0, and g takes values in p^{th} roots of unity.  Applying Lemma 4 to expand g in monomials, we obtain the claim. \Box

As a corollary to this theorem we obtain a converse to Lemma 5:

Corollary 4. (p^{th} roots of minimal degree) Let f: F^n \to {\Bbb R}/{\Bbb Z} be of degree \leq k for some k\geq 0. Then there exists g: F^n \to {\Bbb R}/{\Bbb Z} of degree \leq k+p-1 such that pg=f.

Interestingly, there does not seem to be a way to establish this theorem without going through a global classification theorem such as Theorem 1.

Another corollary to Theorem 1 is that any function from a finite dimensional vector space F^n to a p^m-torsion group for some m will be a polynomial of finite degree.