You are currently browsing the tag archive for the ‘polynomials’ tag.
I’ve just uploaded to the arXiv my paper “Sendov’s conjecture for sufficiently high degree polynomials“. This paper is a contribution to an old conjecture of Sendov on the zeroes of polynomials:
Conjecture 1 (Sendov’s conjecture) Letbe a polynomial of degree
that has all zeroes in the closed unit disk
. If
is one of these zeroes, then
has at least one zero in
.
It is common in the literature on this problem to normalise to be monic, and to rotate the zero
to be an element
of the unit interval
. As it turns out, the location of
on this unit interval
ends up playing an important role in the arguments.
Many cases of this conjecture are already known, for instance
- When
(Brown-Xiang 1999);
- When
(Gauss-Lucas theorem);
- When
(Bojanov 2011);
- When
for a fixed
, and
is sufficiently large depending on
(Dégot 2014);
- When
for a sufficiently large absolute constant
(Chalebgwa 2020);
- When
(Rubinstein 1968; Goodman-Rahman-Ratti 1969; Joyal 1969);
- When
, where
is sufficiently small depending on
(Miller 1993; Vajaitu-Zaharescu 1993);
- When
(Chijiwa 2011);
- When
(Kasmalkar 2014).
In particular, in high degrees the only cases left uncovered by prior results are when is close (but not too close) to
, or when
is close (but not too close) to
; see Figure 1 of my paper.
Our main result covers the high degree case uniformly for all values of :
Theorem 2 There exists an absolute constantsuch that Sendov’s conjecture holds for all
.
In principle, this reduces the verification of Sendov’s conjecture to a finite time computation, although our arguments use compactness methods and thus do not easily provide an explicit value of . I believe that the compactness arguments can be replaced with quantitative substitutes that provide an explicit
, but the value of
produced is likely to be extremely large (certainly much larger than
).
Because of the previous results (particularly those of Chalebgwa and Chijiwa), we will only need to establish the following two subcases of the above theorem:
Theorem 3 (Sendov’s conjecture near the origin) Under the additional hypothesis, Sendov’s conjecture holds for sufficiently large
.
Theorem 4 (Sendov’s conjecture near the unit circle) Under the additional hypothesisfor a fixed
, Sendov’s conjecture holds for sufficiently large
.
We approach these theorems using the “compactness and contradiction” strategy, assuming that there is a sequence of counterexamples whose degrees going to infinity, using various compactness theorems to extract various asymptotic objects in the limit
, and somehow using these objects to derive a contradiction. There are many ways to effect such a strategy; we will use a formalism that I call “cheap nonstandard analysis” and which is common in the PDE literature, in which one repeatedly passes to subsequences as necessary whenever one invokes a compactness theorem to create a limit object. However, the particular choice of asymptotic formalism one selects is not of essential importance for the arguments.
I also found it useful to use the language of probability theory. Given a putative counterexample to Sendov’s conjecture, let
be a zero of
(chosen uniformly at random among the
zeroes of
, counting multiplicity), and let
similarly be a uniformly random zero of
. We introduce the logarithmic potentials
Theorem 5
- (i) If
, then
almost surely lie in the semicircle
and have the same distribution.
- (ii) If
, then
is uniformly distributed on the circle
, and
is almost surely zero.
In case (i) (and strengthening the hypothesis to
to control some technical contributions of “outlier” zeroes of
), we can use this information about
and (4) to ensure that the normalised logarithmic derivative
has a non-negative winding number in a certain small (but not too small) circle around the origin, which by the argument principle is inconsistent with the hypothesis that
has a zero at
and that
has no zeroes near
. This is how we establish Theorem 3.
Case (ii) turns out to be more delicate. This is because there are a number of “near-counterexamples” to Sendov’s conjecture that are compatible with the hypotheses and conclusion of case (ii). The simplest such example is , where the zeroes
of
are uniformly distributed amongst the
roots of unity (including at
), and the zeroes of
are all located at the origin. In my paper I also discuss a variant of this construction, in which
has zeroes mostly near the origin, but also acquires a bounded number of zeroes at various locations
inside the unit disk. Specifically, we take
[UPDATE, Feb 1, 2021: the strategy sketched out below has been successfully implemented to rigorously obtain the desired implication in this recent preprint of Giulio Bresciani.]
I recently came across this question on MathOverflow asking if there are any polynomials of two variables with rational coefficients, such that the map
is a bijection. The answer to this question is almost surely “no”, but it is remarkable how hard this problem resists any attempt at rigorous proof. (MathOverflow users with enough privileges to see deleted answers will find that there are no less than seventeen deleted attempts at a proof in response to this question!)
On the other hand, the one surviving response to the question does point out this paper of Poonen which shows that assuming a powerful conjecture in Diophantine geometry known as the Bombieri-Lang conjecture (discussed in this previous post), it is at least possible to exhibit polynomials which are injective.
I believe that it should be possible to also rule out the existence of bijective polynomials if one assumes the Bombieri-Lang conjecture, and have sketched out a strategy to do so, but filling in the gaps requires a fair bit more algebraic geometry than I am capable of. So as a sort of experiment, I would like to see if a rigorous implication of this form (similarly to the rigorous implication of the Erdos-Ulam conjecture from the Bombieri-Lang conjecture in my previous post) can be crowdsourced, in the spirit of the polymath projects (though I feel that this particular problem should be significantly quicker to resolve than a typical such project).
Here is how I imagine a Bombieri-Lang-powered resolution of this question should proceed (modulo a large number of unjustified and somewhat vague steps that I believe to be true but have not established rigorously). Suppose for contradiction that we have a bijective polynomial . Then for any polynomial
of one variable, the surface
has infinitely many rational points; indeed, every rational lifts to exactly one rational point in
. I believe that for “typical”
this surface
should be irreducible. One can now split into two cases:
- (a) The rational points in
are Zariski dense in
.
- (b) The rational points in
are not Zariski dense in
.
Consider case (b) first. By definition, this case asserts that the rational points in are contained in a finite number of algebraic curves. By Faltings’ theorem (a special case of the Bombieri-Lang conjecture), any curve of genus two or higher only contains a finite number of rational points. So all but finitely many of the rational points in
are contained in a finite union of genus zero and genus one curves. I think all genus zero curves are birational to a line, and all the genus one curves are birational to an elliptic curve (though I don’t have an immediate reference for this). These curves
all can have an infinity of rational points, but very few of them should have “enough” rational points
that their projection
to the third coordinate is “large”. In particular, I believe
- (i) If
is birational to an elliptic curve, then the number of elements of
of height at most
should grow at most polylogarithmically in
(i.e., be of order
.
- (ii) If
is birational to a line but not of the form
for some rational
, then then the number of elements of
of height at most
should grow slower than
(in fact I think it can only grow like
).
I do not have proofs of these results (though I think something similar to (i) can be found in Knapp’s book, and (ii) should basically follow by using a rational parameterisation of
with
nonlinear). Assuming these assertions, this would mean that there is a curve of the form
that captures a “positive fraction” of the rational points of
, as measured by restricting the height of the third coordinate
to lie below a large threshold
, computing density, and sending
to infinity (taking a limit superior). I believe this forces an identity of the form
for all . Such identities are certainly possible for some choices of
(e.g.
for arbitrary polynomials
of one variable) but I believe that the only way that such identities hold for a “positive fraction” of
(as measured using height as before) is if there is in fact a rational identity of the form
for some rational functions with rational coefficients (in which case we would have
and
). But such an identity would contradict the hypothesis that
is bijective, since one can take a rational point
outside of the curve
, and set
, in which case we have
violating the injective nature of
. Thus, modulo a lot of steps that have not been fully justified, we have ruled out the scenario in which case (b) holds for a “positive fraction” of
.
This leaves the scenario in which case (a) holds for a “positive fraction” of . Assuming the Bombieri-Lang conjecture, this implies that for such
, any resolution of singularities of
fails to be of general type. I would imagine that this places some very strong constraints on
, since I would expect the equation
to describe a surface of general type for “generic” choices of
(after resolving singularities). However, I do not have a good set of techniques for detecting whether a given surface is of general type or not. Presumably one should proceed by viewing the surface
as a fibre product of the simpler surface
and the curve
over the line
. In any event, I believe the way to handle (a) is to show that the failure of general type of
implies some strong algebraic constraint between
and
(something in the spirit of (1), perhaps), and then use this constraint to rule out the bijectivity of
by some further ad hoc method.
(This post is mostly intended for my own reference, as I found myself repeatedly looking up several conversions between polynomial bases on various occasions.)
Let denote the vector space of polynomials
of one variable
with real coefficients of degree at most
. This is a vector space of dimension
, and the sequence of these spaces form a filtration:
A standard basis for these vector spaces are given by the monomials : every polynomial
in
can be expressed uniquely as a linear combination of the first
monomials
. More generally, if one has any sequence
of polynomials, with each
of degree exactly
, then an easy induction shows that
forms a basis for
.
In particular, if we have two such sequences and
of polynomials, with each
of degree
and each
of degree
, then
must be expressible uniquely as a linear combination of the polynomials
, thus we have an identity of the form
for some change of basis coefficients . These coefficients describe how to convert a polynomial expressed in the
basis into a polynomial expressed in the
basis.
Many standard combinatorial quantities involving two natural numbers
can be interpreted as such change of basis coefficients. The most familiar example are the binomial coefficients
, which measures the conversion from the shifted monomial basis
to the monomial basis
, thanks to (a special case of) the binomial formula:
thus for instance
More generally, for any shift , the conversion from
to
is measured by the coefficients
, thanks to the general case of the binomial formula.
But there are other bases of interest too. For instance if one uses the falling factorial basis
then the conversion from falling factorials to monomials is given by the Stirling numbers of the first kind :
thus for instance
and the conversion back is given by the Stirling numbers of the second kind :
thus for instance
If one uses the binomial functions as a basis instead of the falling factorials, one of course can rewrite these conversions as
and
thus for instance
and
As a slight variant, if one instead uses rising factorials
then the conversion to monomials yields the unsigned Stirling numbers of the first kind:
thus for instance
One final basis comes from the polylogarithm functions
For instance one has
and more generally one has
for all natural numbers and some polynomial
of degree
(the Eulerian polynomials), which when converted to the monomial basis yields the (shifted) Eulerian numbers
For instance
These particular coefficients also have useful combinatorial interpretations. For instance:
- The binomial coefficient
is of course the number of
-element subsets of
.
- The unsigned Stirling numbers
of the first kind are the number of permutations of
with exactly
cycles. The signed Stirling numbers
are then given by the formula
.
- The Stirling numbers
of the second kind are the number of ways to partition
into
non-empty subsets.
- The Eulerian numbers
are the number of permutations of
with exactly
ascents.
These coefficients behave similarly to each other in several ways. For instance, the binomial coefficients obey the well known Pascal identity
(with the convention that vanishes outside of the range
). In a similar spirit, the unsigned Stirling numbers
of the first kind obey the identity
and the signed counterparts obey the identity
The Stirling numbers of the second kind obey the identity
and the Eulerian numbers obey the identity
This is a sequel to this previous blog post, in which we discussed the effect of the heat flow evolution
on the zeroes of a time-dependent family of polynomials , with a particular focus on the case when the polynomials
had real zeroes. Here (inspired by some discussions I had during a recent conference on the Riemann hypothesis in Bristol) we record the analogous theory in which the polynomials instead have zeroes on a circle
, with the heat flow slightly adjusted to compensate for this. As we shall discuss shortly, a key example of this situation arises when
is the numerator of the zeta function of a curve.
More precisely, let be a natural number. We will say that a polynomial
of degree (so that
) obeys the functional equation if the
are all real and
for all , thus
and
for all non-zero . This means that the
zeroes
of
(counting multiplicity) lie in
and are symmetric with respect to complex conjugation
and inversion
across the circle
. We say that this polynomial obeys the Riemann hypothesis if all of its zeroes actually lie on the circle
. For instance, in the
case, the polynomial
obeys the Riemann hypothesis if and only if
.
Such polynomials arise in number theory as follows: if is a projective curve of genus
over a finite field
, then, as famously proven by Weil, the associated local zeta function
(as defined for instance in this previous blog post) is known to take the form
where is a degree
polynomial obeying both the functional equation and the Riemann hypothesis. In the case that
is an elliptic curve, then
and
takes the form
, where
is the number of
-points of
minus
. The Riemann hypothesis in this case is a famous result of Hasse.
Another key example of such polynomials arise from rescaled characteristic polynomials
of matrices
in the compact symplectic group
. These polynomials obey both the functional equation and the Riemann hypothesis. The Sato-Tate conjecture (in higher genus) asserts, roughly speaking, that “typical” polyomials
arising from the number theoretic situation above are distributed like the rescaled characteristic polynomials (1), where
is drawn uniformly from
with Haar measure.
Given a polynomial of degree
with coefficients
we can evolve it in time by the formula
thus for
. Informally, as one increases
, this evolution accentuates the effect of the extreme monomials, particularly,
and
at the expense of the intermediate monomials such as
, and conversely as one decreases
. This family of polynomials obeys the heat-type equation
In view of the results of Marcus, Spielman, and Srivastava, it is also very likely that one can interpret this flow in terms of expected characteristic polynomials involving conjugation over the compact symplectic group , and should also be tied to some sort of “
” version of Brownian motion on this group, but we have not attempted to work this connection out in detail.
It is clear that if obeys the functional equation, then so does
for any other time
. Now we investigate the evolution of the zeroes. Suppose at some time
that the zeroes
of
are distinct, then
From the inverse function theorem we see that for times sufficiently close to
, the zeroes
of
continue to be distinct (and vary smoothly in
), with
Differentiating this at any not equal to any of the
, we obtain
and
and
Inserting these formulae into (2) (expanding as
) and canceling some terms, we conclude that
for sufficiently close to
, and
not equal to
. Extracting the residue at
, we conclude that
which we can rearrange as
If we make the change of variables (noting that one can make
depend smoothly on
for
sufficiently close to
), this becomes
Intuitively, this equation asserts that the phases repel each other if they are real (and attract each other if their difference is imaginary). If
obeys the Riemann hypothesis, then the
are all real at time
, then the Picard uniqueness theorem (applied to
and its complex conjugate) then shows that the
are also real for
sufficiently close to
. If we then define the entropy functional
then the above equation becomes a gradient flow
which implies in particular that is non-increasing in time. This shows that as one evolves time forward from
, there is a uniform lower bound on the separation between the phases
, and hence the equation can be solved indefinitely; in particular,
obeys the Riemann hypothesis for all
if it does so at time
. Our argument here assumed that the zeroes of
were simple, but this assumption can be removed by the usual limiting argument.
For any polynomial obeying the functional equation, the rescaled polynomials
converge locally uniformly to
as
. By Rouche’s theorem, we conclude that the zeroes of
converge to the equally spaced points
on the circle
. Together with the symmetry properties of the zeroes, this implies in particular that
obeys the Riemann hypothesis for all sufficiently large positive
. In the opposite direction, when
, the polynomials
converge locally uniformly to
, so if
,
of the zeroes converge to the origin and the other
converge to infinity. In particular,
fails the Riemann hypothesis for sufficiently large negative
. Thus (if
), there must exist a real number
, which we call the de Bruijn-Newman constant of the original polynomial
, such that
obeys the Riemann hypothesis for
and fails the Riemann hypothesis for
. The situation is a bit more complicated if
vanishes; if
is the first natural number such that
(or equivalently,
) does not vanish, then by the above arguments one finds in the limit
that
of the zeroes go to the origin,
go to infinity, and the remaining
zeroes converge to the equally spaced points
. In this case the de Bruijn-Newman constant remains finite except in the degenerate case
, in which case
.
For instance, consider the case when and
for some real
with
. Then the quadratic polynomial
has zeroes
and one easily checks that these zeroes lie on the circle when
, and are on the real axis otherwise. Thus in this case we have
(with
if
). Note how as
increases to
, the zeroes repel each other and eventually converge to
, while as
decreases to
, the zeroes collide and then separate on the real axis, with one zero going to the origin and the other to infinity.
The arguments in my paper with Brad Rodgers (discussed in this previous post) indicate that for a “typical” polynomial of degree
that obeys the Riemann hypothesis, the expected time to relaxation to equilibrium (in which the zeroes are equally spaced) should be comparable to
, basically because the average spacing is
and hence by (3) the typical velocity of the zeroes should be comparable to
, and the diameter of the unit circle is comparable to
, thus requiring time comparable to
to reach equilibrium. Taking contrapositives, this suggests that the de Bruijn-Newman constant
should typically take on values comparable to
(since typically one would not expect the initial configuration of zeroes to be close to evenly spaced). I have not attempted to formalise or prove this claim, but presumably one could do some numerics (perhaps using some of the examples of
given previously) to explore this further.
Let be a monic polynomial of degree
with complex coefficients. Then by the fundamental theorem of algebra, we can factor
as
for some complex zeroes (possibly with repetition).
Now suppose we evolve with respect to time by heat flow, creating a function
of two variables with given initial data
for which
On the space of polynomials of degree at most , the operator
is nilpotent, and one can solve this equation explicitly both forwards and backwards in time by the Taylor series
For instance, if one starts with a quadratic , then the polynomial evolves by the formula
As the polynomial evolves in time, the zeroes
evolve also. Assuming for sake of discussion that the zeroes are simple, the inverse function theorem tells us that the zeroes will (locally, at least) evolve smoothly in time. What are the dynamics of this evolution?
For instance, in the quadratic case, the quadratic formula tells us that the zeroes are
and
after arbitrarily choosing a branch of the square root. If are real and the discriminant
is initially positive, we see that we start with two real zeroes centred around
, which then approach each other until time
, at which point the roots collide and then move off from each other in an imaginary direction.
In the general case, we can obtain the equations of motion by implicitly differentiating the defining equation
in time using (2) to obtain
To simplify notation we drop the explicit dependence on time, thus
From (1) and the product rule, we see that
and
(where all indices are understood to range over ) leading to the equations of motion
at least when one avoids those times in which there is a repeated zero. In the case when the zeroes are real, each term
represents a (first-order) attraction in the dynamics between
and
, but the dynamics are more complicated for complex zeroes (e.g. purely imaginary zeroes will experience repulsion rather than attraction, as one already sees in the quadratic example). Curiously, this system resembles that of Dyson brownian motion (except with the brownian motion part removed, and time reversed). I learned of the connection between the ODE (3) and the heat equation from this paper of Csordas, Smith, and Varga, but perhaps it has been mentioned in earlier literature as well.
One interesting consequence of these equations is that if the zeroes are real at some time, then they will stay real as long as the zeroes do not collide. Let us now restrict attention to the case of real simple zeroes, in which case we will rename the zeroes as instead of
, and order them as
. The evolution
can now be thought of as reverse gradient flow for the “entropy”
(which is also essentially the logarithm of the discriminant of the polynomial) since we have
In particular, we have the monotonicity formula
where is the “energy”
where in the last line we use the antisymmetrisation identity
Among other things, this shows that as one goes backwards in time, the entropy decreases, and so no collisions can occur to the past, only in the future, which is of course consistent with the attractive nature of the dynamics. As is a convex function of the positions
, one expects
to also evolve in a convex manner in time, that is to say the energy
should be increasing. This is indeed the case:
Exercise 1 Show that
Symmetric polynomials of the zeroes are polynomial functions of the coefficients and should thus evolve in a polynomial fashion. One can compute this explicitly in simple cases. For instance, the center of mass is an invariant:
The variance decreases linearly:
Exercise 2 Establish the virial identity
As the variance (which is proportional to ) cannot become negative, this identity shows that “finite time blowup” must occur – that the zeroes must collide at or before the time
.
Exercise 3 Show that the Stieltjes transform
solves the viscous Burgers equation
either by using the original heat equation (2) and the identity
, or else by using the equations of motion (3). This relation between the Burgers equation and the heat equation is known as the Cole-Hopf transformation.
The paper of Csordas, Smith, and Varga mentioned previously gives some other bounds on the lifespan of the dynamics; roughly speaking, they show that if there is one pair of zeroes that are much closer to each other than to the other zeroes then they must collide in a short amount of time (unless there is a collision occuring even earlier at some other location). Their argument extends also to situations where there are an infinite number of zeroes, which they apply to get new results on Newman’s conjecture in analytic number theory. I would be curious to know of further places in the literature where this dynamics has been studied.
The equidistribution theorem asserts that if is an irrational phase, then the sequence
is equidistributed on the unit circle, or equivalently that
for any continuous (or equivalently, for any smooth) function . By approximating
uniformly by a Fourier series, this claim is equivalent to that of showing that
for any non-zero integer (where
), which is easily verified from the irrationality of
and the geometric series formula. Conversely, if
is rational, then clearly
fails to go to zero when
is a multiple of the denominator of
.
One can then ask for more quantitative information about the decay of exponential sums of , or more generally on exponential sums of the form
for an arithmetic progression
(in this post all progressions are understood to be finite) and a polynomial
. It will be convenient to phrase such information in the form of an inverse theorem, describing those phases for which the exponential sum is large. Indeed, we have
Lemma 1 (Geometric series formula, inverse form) Let
be an arithmetic progression of length at most
for some
, and let
be a linear polynomial for some
. If
for some
, then there exists a subprogression
of
of size
such that
varies by at most
on
(that is to say,
lies in a subinterval of
of length at most
).
Proof: By a linear change of variable we may assume that is of the form
for some
. We may of course assume that
is non-zero in
, so that
(
denotes the distance from
to the nearest integer). From the geometric series formula we see that
and so . Setting
for some sufficiently small absolute constant
, we obtain the claim.
Thus, in order for a linear phase to fail to be equidistributed on some long progression
,
must in fact be almost constant on large piece of
.
As is well known, this phenomenon generalises to higher order polynomials. To achieve this, we need two elementary additional lemmas. The first relates the exponential sums of to the exponential sums of its “first derivatives”
.
Lemma 2 (Van der Corput lemma, inverse form) Let
be an arithmetic progression of length at most
, and let
be an arbitrary function such that
for some
. Then, for
integers
, there exists a subprogression
of
, of the same spacing as
, such that
Proof: Squaring (1), we see that
We write and conclude that
where is a subprogression of
of the same spacing. Since
, we conclude that
for values of
(this can be seen, much like the pigeonhole principle, by arguing via contradiction for a suitable choice of implied constants). The claim follows.
The second lemma (which we recycle from this previous blog post) is a variant of the equidistribution theorem.
Lemma 3 (Vinogradov lemma) Let
be an interval for some
, and let
be such that
for at least
values of
, for some
. Then either
or
or else there is a natural number
such that
Proof: We may assume that and
, since we are done otherwise. Then there are at least two
with
, and by the pigeonhole principle we can find
in
with
and
. By the triangle inequality, we conclude that there exists at least one natural number
for which
We take to be minimal amongst all such natural numbers, then we see that there exists
coprime to
and
such that
If then we are done, so suppose that
. Suppose that
are elements of
such that
and
. Writing
for some
, we have
By hypothesis, ; note that as
and
we also have
. This implies that
and thus
. We then have
We conclude that for fixed with
, there are at most
elements
of
such that
. Iterating this with a greedy algorithm, we see that the number of
with
is at most
; since
, this implies that
and the claim follows.
Now we can quickly obtain a higher degree version of Lemma 1:
Proposition 4 (Weyl exponential sum estimate, inverse form) Let
be an arithmetic progression of length at most
for some
, and let
be a polynomial of some degree at most
. If
for some
, then there exists a subprogression
of
with
such that
varies by at most
on
.
Proof: We induct on . The cases
are immediate from Lemma 1. Now suppose that
, and that the claim had already been proven for
. To simplify the notation we allow implied constants to depend on
. Let the hypotheses be as in the proposition. Clearly
cannot exceed
. By shrinking
as necessary we may assume that
for some sufficiently small constant
depending on
.
By rescaling we may assume . By Lemma 3, we see that for
choices of
such that
for some interval . We write
, then
is a polynomial of degree at most
with leading coefficient
. We conclude from induction hypothesis that for each such
, there exists a natural number
such that
, by double-counting, this implies that there are
integers
in the interval
such that
. Applying Lemma 3, we conclude that either
, or that
In the former case the claim is trivial (just take to be a point), so we may assume that we are in the latter case.
We partition into arithmetic progressions
of spacing
and length comparable to
for some large
depending on
to be chosen later. By hypothesis, we have
so by the pigeonhole principle, we have
for at least one such progression . On this progression, we may use the binomial theorem and (4) to write
as a polynomial in
of degree at most
, plus an error of size
. We thus can write
for
for some polynomial
of degree at most
. By the triangle inequality, we thus have (for
large enough) that
and hence by induction hypothesis we may find a subprogression of
of size
such that
varies by most
on
, and thus (for
large enough again) that
varies by at most
on
, and the claim follows.
This gives the following corollary (also given as Exercise 16 in this previous blog post):
Corollary 5 (Weyl exponential sum estimate, inverse form II) Let
be a discrete interval for some
, and let
polynomial of some degree at most
for some
. If
for some
, then there is a natural number
such that
for all
.
One can obtain much better exponents here using Vinogradov’s mean value theorem; see Theorem 1.6 this paper of Wooley. (Thanks to Mariusz Mirek for this reference.) However, this weaker result already suffices for many applications, and does not need any result as deep as the mean value theorem.
Proof: To simplify notation we allow implied constants to depend on . As before, we may assume that
for some small constant
depending only on
. We may also assume that
for some large
, as the claim is trivial otherwise (set
).
Applying Proposition 4, we can find a natural number and an arithmetic subprogression
of
such that
and such that
varies by at most
on
. Writing
for some interval
of length
and some
, we conclude that the polynomial
varies by at most
on
. Taking
order differences, we conclude that the
coefficient of this polynomial is
; by the binomial theorem, this implies that
differs by at most
on
from a polynomial of degree at most
. Iterating this, we conclude that the
coefficient of
is
for
, and the claim then follows by inverting the change of variables
(and replacing
with a larger quantity such as
as necessary).
For future reference we also record a higher degree version of the Vinogradov lemma.
Lemma 6 (Polynomial Vinogradov lemma) Let
be a discrete interval for some
, and let
be a polynomial
of degree at most
for some
such that
for at least
values of
, for some
. Then either
or else there is a natural number
such that
for all
.
Proof: We induct on . For
this follows from Lemma 3 (noting that if
then
), so suppose that
and that the claim is already proven for
. We now allow all implied constants to depend on
.
For each , let
denote the number of
such that
. By hypothesis,
, and clearly
, so we must have
for
choices of
. For each such
, we then have
for
choices of
, so by induction hypothesis, either (5) or (6) holds, or else for
choices of
, there is a natural number
such that
for , where
are the coefficients of the degree
polynomial
. We may of course assume it is the latter which holds. By the pigeonhole principle we may take
to be independent of
.
Since , we have
for choices of
, so by Lemma 3, either (5) or (6) holds, or else (after increasing
as necessary) we have
We can again assume it is the latter that holds. This implies that modulo
, so that
for choices of
. Arguing as before and iterating, we obtain the claim.
The above results also extend to higher dimensions. Here is the higher dimensional version of Proposition 4:
Proposition 7 (Multidimensional Weyl exponential sum estimate, inverse form) Let
and
, and let
be arithmetic progressions of length at most
for each
. Let
be a polynomial of degrees at most
in each of the
variables
separately. If
for some
, then there exists a subprogression
of
with
for each
such that
varies by at most
on
.
A much more general statement, in which the polynomial phase is replaced by a nilsequence, and in which one does not necessarily assume the exponential sum is small, is given in Theorem 8.6 of this paper of Ben Green and myself, but it involves far more notation to even state properly.
Proof: We induct on . The case
was established in Proposition 5, so we assume that
and that the claim has already been proven for
. To simplify notation we allow all implied constants to depend on
. We may assume that
for some small
depending only on
.
By a linear change of variables, we may assume that for all
.
We write . First suppose that
. Then by the pigeonhole principle we can find
such that
and the claim then follows from the induction hypothesis. Thus we may assume that for some large
depending only on
. Similarly we may assume that
for all
.
By the triangle inequality, we have
The inner sum is , and the outer sum has
terms. Thus, for
choices of
, one has
for some polynomials of degrees at most
in the variables
. For each
obeying (7), we apply Corollary 5 to conclude that there exists a natural number
such that
for (the claim also holds for
but we discard it as being trivial). By the pigeonhole principle, there thus exists a natural number
such that
for all and for
choices of
. If we write
where is a polynomial of degrees at most
, then for
choices of
we then have
Applying Lemma 6 in the and the largeness hypotheses on the
(and also the assumption that
) we conclude (after enlarging
as necessary, and pigeonholing to keep
independent of
) that
for all (note that we now include that
case, which is no longer trivial) and for
choices of
. Iterating this, we eventually conclude (after enlarging
as necessary) that
whenever for
, with
nonzero. Permuting the indices, and observing that the claim is trivial for
, we in fact obtain (8) for all
, at which point the claim easily follows by taking
for each
.
An inspection of the proof of the above result (or alternatively, by combining the above result again with many applications of Lemma 6) reveals the following general form of Proposition 4, which was posed as Exercise 17 in this previous blog post, but had a slight misprint in it (it did not properly treat the possibility that some of the could be small) and was a bit trickier to prove than anticipated (in fact, the reason for this post was that I was asked to supply a more detailed solution for this exercise):
Proposition 8 (Multidimensional Weyl exponential sum estimate, inverse form, II) Let
be an natural number, and for each
, let
be a discrete interval for some
. Let
be a polynomial in
variables of multidegrees
for some
. If
for some
, or else there is a natural number
such that
Again, the factor of is natural in this bound. In the
case, the option (10) may be deleted since (11) trivially holds in this case, but this simplification is no longer available for
since one needs (10) to hold for all
(not just one
) to make (11) completely trivial. Indeed, the above proposition fails for
if one removes (10) completely, as can be seen for instance by inspecting the exponential sum
, which has size comparable to
regardless of how irrational
is.
Vitaly Bergelson, Tamar Ziegler, and I have just uploaded to the arXiv our joint paper “Multiple recurrence and convergence results associated to -actions“. This paper is primarily concerned with limit formulae in the theory of multiple recurrence in ergodic theory. Perhaps the most basic formula of this type is the mean ergodic theorem, which (among other things) asserts that if
is a measure-preserving
-system (which, in this post, means that
is a probability space and
is measure-preserving and invertible, thus giving an action
of the integers), and
are functions, and
is ergodic (which means that
contains no
-invariant functions other than the constants (up to almost everywhere equivalence, of course)), then the average
converges as to the expression
see e.g. this previous blog post. Informally, one can interpret this limit formula as an equidistribution result: if is drawn at random from
(using the probability measure
), and
is drawn at random from
for some large
, then the pair
becomes uniformly distributed in the product space
(using product measure
) in the limit as
.
If we allow to be non-ergodic, then we still have a limit formula, but it is a bit more complicated. Let
be the
-invariant measurable sets in
; the
-system
can then be viewed as a factor of the original system
, which is equivalent (in the sense of measure-preserving systems) to a trivial system
(known as the invariant factor) in which the shift is trivial. There is then a projection map
to the invariant factor which is a factor map, and the average (1) converges in the limit to the expression
where is the pushforward map associated to the map
; see e.g. this previous blog post. We can interpret this as an equidistribution result. If
is a pair as before, then we no longer expect complete equidistribution in
in the non-ergodic, because there are now non-trivial constraints relating
with
; indeed, for any
-invariant function
, we have the constraint
; putting all these constraints together we see that
(for almost every
, at least). The limit (2) can be viewed as an assertion that this constraint
are in some sense the “only” constraints between
and
, and that the pair
is uniformly distributed relative to these constraints.
Limit formulae are known for multiple ergodic averages as well, although the statement becomes more complicated. For instance, consider the expression
for three functions ; this is analogous to the combinatorial task of counting length three progressions in various sets. For simplicity we assume the system
to be ergodic. Naively one might expect this limit to then converge to
which would roughly speaking correspond to an assertion that the triplet is asymptotically equidistributed in
. However, even in the ergodic case there can be additional constraints on this triplet that cannot be seen at the level of the individual pairs
,
. The key obstruction here is that of eigenfunctions of the shift
, that is to say non-trivial functions
that obey the eigenfunction equation
almost everywhere for some constant (or
-invariant)
. Each such eigenfunction generates a constraint
tying together ,
, and
. However, it turns out that these are in some sense the only constraints on
that are relevant for the limit (3). More precisely, if one sets
to be the sub-algebra of
generated by the eigenfunctions of
, then it turns out that the factor
is isomorphic to a shift system
known as the Kronecker factor, for some compact abelian group
and some (irrational) shift
; the factor map
pushes eigenfunctions forward to (affine) characters on
. It is then known that the limit of (3) is
where is the closed subgroup
and is the Haar probability measure on
; see this previous blog post. The equation
defining
corresponds to the constraint (4) mentioned earlier. Among other things, this limit formula implies Roth’s theorem, which in the context of ergodic theory is the assertion that the limit (or at least the limit inferior) of (3) is positive when
is non-negative and not identically vanishing.
If one considers a quadruple average
(analogous to counting length four progressions) then the situation becomes more complicated still, even in the ergodic case. In addition to the (linear) eigenfunctions that already showed up in the computation of the triple average (3), a new type of constraint also arises from quadratic eigenfunctions , which obey an eigenfunction equation
in which
is no longer constant, but is now a linear eigenfunction. For such functions,
behaves quadratically in
, and one can compute the existence of a constraint
between ,
,
, and
that is not detected at the triple average level. As it turns out, this is not the only type of constraint relevant for (5); there is a more general class of constraint involving two-step nilsystems which we will not detail here, but see e.g. this previous blog post for more discussion. Nevertheless there is still a similar limit formula to previous examples, involving a special factor
which turns out to be an inverse limit of two-step nilsystems; this limit theorem can be extracted from the structural theory in this paper of Host and Kra combined with a limit formula for nilsystems obtained by Lesigne, but will not be reproduced here. The pattern continues to higher averages (and higher step nilsystems); this was first done explicitly by Ziegler, and can also in principle be extracted from the structural theory of Host-Kra combined with nilsystem equidistribution results of Leibman. These sorts of limit formulae can lead to various recurrence results refining Roth’s theorem in various ways; see this paper of Bergelson, Host, and Kra for some examples of this.
The above discussion was concerned with -systems, but one can adapt much of the theory to measure-preserving
-systems for other discrete countable abelian groups
, in which one now has a family
of shifts indexed by
rather than a single shift, obeying the compatibility relation
. The role of the intervals
in this more general setting is replaced by that of Folner sequences. For arbitrary countable abelian
, the theory for double averages (1) and triple limits (3) is essentially identical to the
-system case. But when one turns to quadruple and higher limits, the situation becomes more complicated (and, for arbitrary
, still not fully understood). However one model case which is now well understood is the finite field case when
is an infinite-dimensional vector space over a finite field
(with the finite subspaces
then being a good choice for the Folner sequence). Here, the analogue of the structural theory of Host and Kra was worked out by Vitaly, Tamar, and myself in these previous papers (treating the high characteristic and low characteristic cases respectively). In the finite field setting, it turns out that nilsystems no longer appear, and one only needs to deal with linear, quadratic, and higher order eigenfunctions (known collectively as phase polynomials). It is then natural to look for a limit formula that asserts, roughly speaking, that if
is drawn at random from a
-system and
drawn randomly from a large subspace of
, then the only constraints between
are those that arise from phase polynomials. The main theorem of this paper is to establish this limit formula (which, again, is a little complicated to state explicitly and will not be done here). In particular, we establish for the first time that the limit actually exists (a result which, for
-systems, was one of the main results of this paper of Host and Kra).
As a consequence, we can recover finite field analogues of most of the results of Bergelson-Host-Kra, though interestingly some of the counterexamples demonstrating sharpness of their results for -systems (based on Behrend set constructions) do not seem to be present in the finite field setting (cf. this previous blog post on the cap set problem). In particular, we are able to largely settle the question of when one has a Khintchine-type theorem that asserts that for any measurable set
in an ergodic
-system and any
, one has
for a syndetic set of , where
are distinct residue classes. It turns out that Khintchine-type theorems always hold for
(and for
ergodicity is not required), and for
it holds whenever
form a parallelogram, but not otherwise (though the counterexample here was such a painful computation that we ended up removing it from the paper, and may end up putting it online somewhere instead), and for larger
we could show that the Khintchine property failed for generic choices of
, though the problem of determining exactly the tuples for which the Khintchine property failed looked to be rather messy and we did not completely settle it.
One of the first non-trivial theorems one encounters in classical algebraic geometry is Bézout’s theorem, which we will phrase as follows:
Theorem 1 (Bézout’s theorem) Let
be a field, and let
be non-zero polynomials in two variables
with no common factor. Then the two curves
and
have no common components, and intersect in at most
points.
This theorem can be proven by a number of means, for instance by using the classical tool of resultants. It has many strengthenings, generalisations, and variants; see for instance this previous blog post on Bézout’s inequality. Bézout’s theorem asserts a fundamental algebraic dichotomy, of importance in combinatorial incidence geometry: any two algebraic curves either share a common component, or else have a bounded finite intersection; there is no intermediate case in which the intersection is unbounded in cardinality, but falls short of a common component. This dichotomy is closely related to the integrality gap in algebraic dimension: an algebraic set can have an integer dimension such as or
, but cannot attain any intermediate dimensions such as
. This stands in marked contrast to sets of analytic, combinatorial, or probabilistic origin, whose “dimension” is typically not necessarily constrained to be an integer.
Bézout’s inequality tells us, roughly speaking, that the intersection of a curve of degree and a curve of degree
forms a set of at most
points. One can consider the converse question: given a set
of
points in the plane
, can one find two curves of degrees
with
and no common components, whose intersection contains these points?
A model example that supports the possibility of such a converse is a grid that is a Cartesian product of two finite subsets
of
with
. In this case, one can take one curve to be the union of
vertical lines, and the other curve to be the union of
horizontal lines, to obtain the required decomposition. Thus, if the proposed converse to Bézout’s inequality held, it would assert that any set of
points was essentially behaving like a “nonlinear grid” of size
.
Unfortunately, the naive converse to Bézout’s theorem is false. A counterexample can be given by considering a set of
points for some large perfect square
, where
is a
by
grid of the form described above, and
consists of
points on an line
(e.g. a
or
grid). Each of the two component sets
can be written as the intersection between two curves whose degrees multiply up to
; in the case of
, we can take the two families of parallel lines (viewed as reducible curves of degree
) as the curves, and in the case of
, one can take
as one curve, and the graph of a degree
polynomial on
vanishing on
for the second curve. But, if
is large enough, one cannot cover
by the intersection of a single pair
of curves with no common components whose degrees
multiply up to
. Indeed, if this were the case, then without loss of generality we may assume that
, so that
. By Bézout’s theorem,
either contains
, or intersects
in at most
points. Thus, in order for
to capture all of
, it must contain
, which forces
to not contain
. But
has to intersect
in
points, so by Bézout’s theorem again we have
, thus
. But then (by more applications of Bézout’s theorem)
can only capture
of the
points of
, a contradiction.
But the above counterexample suggests that even if an arbitrary set of (or
) points cannot be covered by the single intersection of a pair of curves with degree multiplying up to
, one may be able to cover such a set by a small number of such intersections. The purpose of this post is to record the simple observation that this is, indeed, the case:
Theorem 2 (Partial converse to Bézout’s theorem) Let
be a field, and let
be a set of
points in
for some
. Then one can find
and pairs
of coprime non-zero polynomials for
such that
Informally, every finite set in the plane is (a dense subset of) the union of logarithmically many nonlinear grids. The presence of the logarithm is necessary, as can be seen by modifying the example to be the union of logarithmically many Cartesian products of distinct dimensions, rather than just a pair of such products.
Unfortunately I do not know of any application of this converse, but I thought it was cute anyways. The proof is given below the fold.
One of the basic problems in analytic number theory is to obtain bounds and asymptotics for sums of the form
in the limit , where
ranges over natural numbers less than
, and
is some arithmetic function of number-theoretic interest. (It is also often convenient to replace this sharply truncated sum with a smoother sum such as
, but we will not discuss this technicality here.) For instance, the prime number theorem is equivalent to the assertion
where is the von Mangoldt function, while the Riemann hypothesis is equivalent to the stronger assertion
It is thus of interest to develop techniques to estimate such sums . Of course, the difficulty of this task depends on how “nice” the function
is. The functions
that come up in number theory lie on a broad spectrum of “niceness”, with some particularly nice functions being quite easy to sum, and some being insanely difficult.
At the easiest end of the spectrum are those functions that exhibit some sort of regularity or “smoothness”. Examples of smoothness include “Archimedean” smoothness, in which
is the restriction of some smooth function
from the reals to the natural numbers, and the derivatives of
are well controlled. A typical example is
One can already get quite good bounds on this quantity by comparison with the integral , namely
with sharper bounds available by using tools such as the Euler-Maclaurin formula (see this blog post). Exponentiating such asymptotics, incidentally, leads to one of the standard proofs of Stirling’s formula (as discussed in this blog post).
One can also consider “non-Archimedean” notions of smoothness, such as periodicity relative to a small period . Indeed, if
is periodic with period
(and is thus essentially a function on the cyclic group
), then one has the easy bound
In particular, we have the fundamental estimate
This is a good estimate when is much smaller than
, but as
approaches
in magnitude, the error term
begins to overwhelm the main term
, and one needs much more delicate information on the fractional part of
in order to obtain good estimates at this point.
One can also consider functions which combine “Archimedean” and “non-Archimedean” smoothness into an “adelic” smoothness. We will not define this term precisely here (though the concept of a Schwartz-Bruhat function is one way to capture this sort of concept), but a typical example might be
where is periodic with some small period
. By using techniques such as summation by parts, one can estimate such sums using the techniques used to estimate sums of periodic functions or functions with (Archimedean) smoothness.
Another class of functions that is reasonably well controlled are the multiplicative functions, in which whenever
are coprime. Here, one can use the powerful techniques of multiplicative number theory, for instance by working with the Dirichlet series
which are clearly related to the partial sums (essentially via the Mellin transform, a cousin of the Fourier and Laplace transforms); for this post we ignore the (important) issue of how to make sense of this series when it is not absolutely convergent (but see this previous blog post for more discussion). A primary reason that this technique is effective is that the Dirichlet series of a multiplicative function factorises as an Euler product
One also obtains similar types of representations for functions that are not quite multiplicative, but are closely related to multiplicative functions, such as the von Mangoldt function (whose Dirichlet series
is not given by an Euler product, but instead by the logarithmic derivative of an Euler product).
Moving another notch along the spectrum between well-controlled and ill-controlled functions, one can consider functions that are divisor sums such as
for some other arithmetic function , and some level
. This is a linear combination of periodic functions
and is thus technically periodic in
(with period equal to the least common multiple of all the numbers from
to
), but in practice this periodic is far too large to be useful (except for extremely small levels
, e.g.
). Nevertheless, we can still control the sum
simply by rearranging the summation:
and thus by (1) one can bound this by the sum of a main term and an error term
. As long as the level
is significantly less than
, one may expect the main term to dominate, and one can often estimate this term by a variety of techniques (for instance, if
is multiplicative, then multiplicative number theory techniques are quite effective, as mentioned previously). Similarly for other slight variants of divisor sums, such as expressions of the form
or expressions of the form
where each is periodic with period
.
One of the simplest examples of this comes when estimating the divisor function
which counts the number of divisors up to . This is a multiplicative function, and is therefore most efficiently estimated using the techniques of multiplicative number theory; but for reasons that will become clearer later, let us “forget” the multiplicative structure and estimate the above sum by more elementary methods. By applying the preceding method, we see that
Here, we are (barely) able to keep the error term smaller than the main term; this is right at the edge of the divisor sum method, because the level in this case is equal to
. Unfortunately, at this high choice of level, it is not always possible to always keep the error term under control like this. For instance, if one wishes to use the standard divisor sum representation
where is the Möbius function, to compute
, then one ends up looking at
From Dirichlet series methods, it is not difficult to establish the identities
and
This suggests (but does not quite prove) that one has
in the sense of conditionally convergent series. Assuming one can justify this (which, ultimately, requires one to exclude zeroes of the Riemann zeta function on the line , as discussed in this previous post), one is eventually left with the estimate
, which is useless as a lower bound (and recovers only the classical Chebyshev estimate
as the upper bound). The inefficiency here when compared to the situation with the divisor function
can be attributed to the signed nature of the Möbius function
, which causes some cancellation in the divisor sum expansion that needs to be compensated for with improved estimates.
However, there are a number of tricks available to reduce the level of divisor sums. The simplest comes from exploiting the change of variables , which can in principle reduce the level by a square root. For instance, when computing the divisor function
, one can observe using this change of variables that every divisor of
above
is paired with one below
, and so we have
except when is a perfect square, in which case one must subtract one from the right-hand side. Using this reduced-level divisor sum representation, one can obtain an improvement to (2), namely
This type of argument is also known as the Dirichlet hyperbola method. A variant of this argument can also deduce the prime number theorem from (3), (4) (and with some additional effort, one can even drop the use of (4)); this is discussed at this previous blog post.
Using this square root trick, one can now also control divisor sums such as
(Note that has no multiplicativity properties in
, and so multiplicative number theory techniques cannot be directly applied here.) The level of the divisor sum here is initially of order
, which is too large to be useful; but using the square root trick, we can expand this expression as
which one can rewrite as
The constraint is periodic in
with period
, so we can write this as
where is the number of solutions in
to the equation
, and so
The function is multiplicative, and can be easily computed at primes
and prime powers
using tools such as quadratic reciprocity and Hensel’s lemma. For instance, by Fermat’s two-square theorem,
is equal to
for
and
for
. From this and standard multiplicative number theory methods (e.g. by obtaining asymptotics on the Dirichlet series
), one eventually obtains the asymptotic
and also
and thus
Similar arguments give asymptotics for on other quadratic polynomials; see for instance this paper of Hooley and these papers by McKee. Note that the irreducibility of the polynomial will be important. If one considers instead a sum involving a reducible polynomial, such as
, then the analogous quantity
becomes significantly larger, leading to a larger growth rate (of order
rather than
) for the sum.
However, the square root trick is insufficient by itself to deal with higher order sums involving the divisor function, such as
the level here is initially of order , and the square root trick only lowers this to about
, creating an error term that overwhelms the main term. And indeed, the asymptotic for such this sum has not yet been rigorously established (although if one heuristically drops error terms, one can arrive at a reasonable conjecture for this asymptotic), although some results are known if one averages over additional parameters (see e.g. this paper of Greaves, or this paper of Matthiesen).
Nevertheless, there is an ingenious argument of Erdös that allows one to obtain good upper and lower bounds for these sorts of sums, in particular establishing the asymptotic
for any fixed irreducible non-constant polynomial that maps
to
(with the implied constants depending of course on the choice of
). There is also the related moment bound
for any fixed (not necessarily irreducible) and any fixed
, due to van der Corput; this bound is in fact used to dispose of some error terms in the proof of (6). These should be compared with what one can obtain from the divisor bound
and the trivial bound
, giving the bounds
for any fixed .
The lower bound in (6) is easy, since one can simply lower the level in (5) to obtain the lower bound
for any , and the preceding methods then easily allow one to obtain the lower bound by taking
small enough (more precisely, if
has degree
, one should take
equal to
or less). The upper bounds in (6) and (7) are more difficult. Ideally, if we could obtain upper bounds of the form
for any fixed , then the preceding methods would easily establish both results. Unfortunately, this bound can fail, as illustrated by the following example. Suppose that
is the product of
distinct primes
, each of which is close to
. Then
has
divisors, with
of them close to
for each
. One can think of (the logarithms of) these divisors as being distributed according to what is essentially a Bernoulli distribution, thus a randomly selected divisor of
has magnitude about
, where
is a random variable which has the same distribution as the number of heads in
independently tossed fair coins. By the law of large numbers,
should concentrate near
when
is large, which implies that the majority of the divisors of
will be close to
. Sending
, one can show that the bound (8) fails whenever
.
This however can be fixed in a number of ways. First of all, even when , one can show weaker substitutes for (8). For instance, for any fixed
and
one can show a bound of the form
for some depending only on
. This nice elementary inequality (first observed by Landreau) already gives a quite short proof of van der Corput’s bound (7).
For Erdös’s upper bound (6), though, one cannot afford to lose these additional factors of , and one must argue more carefully. Here, the key observation is that the counterexample discussed earlier – when the natural number
is the product of a large number of fairly small primes – is quite atypical; most numbers have at least one large prime factor. For instance, the number of natural numbers less than
that contain a prime factor between
and
is equal to
which, thanks to Mertens’ theorem
for some absolute constant , is comparable to
. In a similar spirit, one can show by similarly elementary means that the number of natural numbers
less than
that are
-smooth, in the sense that all prime factors are at most
, is only about
or so. Because of this, one can hope that the bound (8), while not true in full generality, will still be true for most natural numbers
, with some slightly weaker substitute available (such as (7)) for the exceptional numbers
. This turns out to be the case by an elementary but careful argument.
The Erdös argument is quite robust; for instance, the more general inequality
for fixed irreducible and
, which improves van der Corput’s inequality (8) was shown by Delmer using the same methods. (A slight error in the original paper of Erdös was also corrected in this latter paper.) In a forthcoming revision to my paper on the Erdös-Straus conjecture, Christian Elsholtz and I have also applied this method to obtain bounds such as
which turn out to be enough to obtain the right asymptotics for the number of solutions to the equation .
Below the fold I will provide some more details of the arguments of Landreau and of Erdös.
Recent Comments