Let be an integer. The concept of a polynomial
of one variable of degree
(or
) can be defined in one of two equivalent ways:
- (Global definition)
is a polynomial of degree
iff it can be written in the form
for some coefficients
.
- (Local definition)
is a polynomial of degree
if it is k-times continuously differentiable and
.
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
we see that P is a polynomial in the global sense. We make the trivial remark that we have no difficulty dividing by here, because the field
is of characteristic zero.
The above equivalence carries over to higher dimensions:
- (Global definition)
is a polynomial of degree
iff it can be written in the form
for some coefficients
.
- (Local definition)
is a polynomial of degree
if it is k-times continuously differentiable and
for all
.
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 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
), the global definition needs to be corrected somewhat by adding some new monomials to the classical ones
. 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 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
, define the shift
and the (discrete) derivative
by the formulae
,
thus schematically we have
. (1)
We say that P is an (additive) polynomial of degree (or degree
) if
for all
. Note that this corresponds to the definition of a classical polynomial from
to
once one adds some regularity conditions, such as k-times differentiability (actually, measurability will already suffice).
Examples 1. The zero function has degree . A constant function has degree
. A homomorphism has degree
. Composing a polynomial of degree
with a homomorphism (either on the left or right) will give another polynomial of degree
. The sum of two polynomials of degree
is again of degree
. The derivative
of a polynomial of degree <k is of degree <k-1. Since
, we conclude that the shift of any polynomial of degree <k is also of degree <k.
Now we show that the product and composition of polynomials is again a polynomial.
Lemma 1. (Product of polynomials is again polynomial) Let
be polynomials of degree
,
respectively for some
, and let
be a bilinear map. Then
is a polynomial of degree
.
Proof. We induct on h+k. The claim is easy when h or k is zero, so suppose that and the claim has already been proven for smaller values of h+k. From the discrete product rule
and induction we see that is of degree
, and thus
has degree
as desired.
Corollary 1. If H is a ring, then the product of two polynomials from G to H of degree
respectively is of degree
.
Lemma 2. (Composition of polynomials is again polynomial) Let
be polynomials of degree
respectively for some
. Then
is a polynomial of degree
.
Proof. For inductive reasons it is convenient to prove the following more general statement: if are polynomials of degree
respectively for some
, and
are polynomials of degree
respectively, where
for all j, then the function
defined by
is a polynomial of degree . Clearly Lemma 2 follows from the
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 . 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
.
If then
is constant, and by replacing P with
and decrementing m, we see that the claim follows from the induction hypothesis. Similarly if any other of the
vanish (since the derivative operators commute with each other). So we may assume that
for all j.
Let g in G. By considering the successive differences between the quantities
we see that is the sum of
By the induction hypothesis, each of these terms are polynomials of degree . The claim follows.
— 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
, a function
is of degree
if and only if we can expand
for some coefficients
; this expansion is unique for
. Also, every function
is a polynomial of degree <p.
Proof. The “if” portion of the lemma follows from Corollary 1 (since the identity function is clearly of degree
). For the “only if” part, observe from the binomial identity
for any non-negative integer h, that
Since can be meaningfully defined on F for
, we conclude in particular that
Since can be expanded as a linear combination over F of
, 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
, these functions must be linearly independent.)
Corollary 2. (Integration lemma) Let
be a polynomial of degree
for some
, and let
. Then there exists a polynomial
of degree
such that
. (In particular, this implies the mean zero condition
. Conversely, any function
with
is a polynomial of degree
.
Proof. From Lemma 3, the space of polynomials of degree and
is a vector space over F of dimension k+1 and k+2 respectively. The derivative operator
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.
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
. For any
, a function
is of degree
if and only if we can expand
for some coefficients
.
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
for non-negative integers , where
is the standard basis of
; we leave the details to the reader.
Remark 2. The above discussion was for fields of prime order, but we can use these results to describe classical polynomials for fields
of prime power order, by viewing any vector space over
as a vector space over
. Of course, the resulting polynomials one obtains are merely polynomials over
, rather than over
.
— The non-classical case —
Now we consider polynomials from F or into other additive groups, where
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
. The first basic lemma is the following (taken from my forthcoming paper with Bergelson and Ziegler):
Lemma 5. (Multiplication by p reduces degree) Let
be of degree
for some
. Then
is of degree
.
Proof. Since for any h, we see by induction that it suffices to show this lemma when k=0.
Let . Raising (1) to the
power we have
.
Of course, . Applying this identity to f and noting that
by hypothesis, we conclude that
.
Inverting using Neumann series (and the finite degree of f) we conclude that
for all h, thus
has degree
as required.
Corollary 3. (Polynomials are discretely valued) If
is of degree
, then after subtracting a constant from f, f takes values in the
roots of unity.
In one dimension, there is a converse to Lemma 5:
Lemma 6. Let
be such that pf has degree
. Then f has degree
.
Proof. As in Lemma 5, it suffices to establish the case k=0. But this then follows from the last part of Lemma 3.
As a corollary we can classify all non-classical polynomials:
Theorem 1. (Global description of non-classical multi-dimensional polynomials) A function
is a polynomial of degree
if and only if it has the form
for some
and
, where
is the obvious map from F to
.
Proof. The “if” part follows easily from Lemma 4 in the case , 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
. Now suppose inductively that
and the claim has already been proven for smaller values of k. By Lemma 5 and the induction hypothesis, pf takes the form
and thus
where is a
root of
, and g takes values in
roots of unity. Applying Lemma 4 to expand g in monomials, we obtain the claim.
As a corollary to this theorem we obtain a converse to Lemma 5:
Corollary 4. (
roots of minimal degree) Let
be of degree
for some
. Then there exists
of degree
such that
.
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 to a
-torsion group for some m will be a polynomial of finite degree.
15 comments
Comments feed for this article
13 November, 2008 at 11:25 am
jatkesha
Dear Prof. Tao,
Sorry for digressing here. Unfortunately, the formatting of the post when it is read in Google Reader is haywire. Could you please do something about it?
Regards,
Jatkesha
13 November, 2008 at 12:25 pm
James Cranch
Sorry, I’ve nothing intelligent to say.
The words “this paper of Leibman” look like they should have a link associated to them, but don’t.
13 November, 2008 at 2:17 pm
John Armstrong
Jatkesha, unfortunately it’s out of Dr. Tao’s hands. Google Reader has recently changed and it now renders every <img> tag as a new paragraph. It’s a Google problem, not a WordPress problem.
13 November, 2008 at 3:42 pm
bengreen
Terry: an enjoyable post.
James: There are two papers of Leibman relevant here: Polynomial sequences in groups, J. Alg 201 (1998), 189-206 and Polynomial mappings in groups, Israel J. Math 129 (2002), 29-60. A digested version of these results for the consumption of additive combinatorialists may be found in Sec. 6 of the paper Quantitative distribution of polynomial sequences on nilmanifolds by Terry and I.
13 November, 2008 at 4:07 pm
Terence Tao
Thanks for the corrections!
13 November, 2008 at 4:59 pm
ohnym
dear professor terrence tao
im send a letter to you that contained way of the proof of the goldbach’s conjecture. ( elementary proof )
please see that.
13 November, 2008 at 10:31 pm
mirror2image
There was a fun problem, which I’ve encountered while in university, many many years ago. It was form small pamphlet, something like “hard problems in mathematical analysis” for students, printed by Leningrad University. F is infinitely differentiable function. Prove that if for every x exist k such that k derivative of F is zero for x, F is polynomial. Took me a week or two to figure it. May be even three, don’t remember now…
14 November, 2008 at 12:47 am
user
@jatkesha: If you are using Firefox you can install the extension Stylish (or edit user.css directly) and add a CSS rule along the lines of:
@-moz-document url-prefix(“https://www.google.com/reader/”), url-prefix(“http://www.google.com/reader/”) {
img.content-block-fix { display: inline !important; margin:0px !important; }
}
This makes inline math look OK and other images acceptable, as opposed to inline math horrible and other images fine. Sorry for being off topic.
20 November, 2008 at 5:23 pm
Carnival of Mathematics #44 « Maxwell’s Demon
[…] generate Pythagorean triples at 360. To stretch your mathematical muscles a little more look for Terry Tao, considering polynomials on finite fields ranging over a finite group. Technical but […]
14 December, 2009 at 3:38 pm
Approximate bases, sunflowers, and nonstandard analysis « What’s new
[…] monomials each of degree at most , or alternatively as a function whose derivative vanishes; see this previous blog post for some discussion of this […]
8 May, 2010 at 1:48 pm
254B, Lecture Notes 4: Equidistribution of polynomials over finite fields « What’s new
[…] is also of importance (particularly in low characteristic), but the theory is more difficult; see these notes for some further […]
11 January, 2011 at 6:59 am
The inverse conjecture for the Gowers norm over finite fields in low characteristic « What’s new
[…] essentially no distinction between non-classical polynomials and their classical counterparts, as discussed previously on this blog). The need to deal with genuinely non-classical polynomials is the main new difficulty in this […]
21 September, 2015 at 11:14 am
Freddie Manners
Dear Prof. Tao,
I think the statement of Lemma 6 has a rogue exponent “n” in it — the previous sentence (“In dimension one…”) suggests we should be working with n=1, and the statement appears to be very much untrue without this assumption.
[Corrected, thanks – T.]
15 December, 2015 at 10:54 pm
Nonclassical polynomials, circles, and groups - Quorai
[…] this blog post for more background on nonclassical […]
27 May, 2022 at 2:14 pm
Notes on inverse theorem entropy | What's new
[…] degree polynomial phases from to , which one can normalize to equal at the origin, and then by the classification of such polynomials one can calculate that the entropy is of quasipolynomial size in . By using the recent work of […]