Let $k \geq 0$ be an integer.  The concept of a polynomial $P: {\Bbb R} \to {\Bbb R}$ of one variable of degree $ (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 $ 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 $ 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 $ 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 $ 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 $ (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 $ 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 $ 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 $ 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.