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.
17 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 […]
10 March, 2023 at 8:59 am
A Host–Kra ${bf F}^omega_2$-system of order 5 that is not Abramov of order 5, and non-measurability of the inverse theorem for the $U^6({bf F}^n_2)$ norm; The structure of totally disconnected Host–Kra–Ziegler factors, and the inverse th
[…] is a one-bounded function with a lower bound on the Gowers uniformity norm. Then there exists a (non-classical) polynomial of degree at most such that […]
30 May, 2023 at 6:43 am
A Host–Kra F^omega_2-system of order 5 that isn't Abramov of order 5, and non-measurability of the inverse theorem for the U^6(F^n_2) norm; The construction of completely disconnected Host–Kra–Ziegler components, and the inverse theorem for the
[…] is a one-bounded perform with a decrease sure on the Gowers uniformity norm. Then there exists a (non-classical) polynomial of diploma at most such that […]