You are currently browsing the tag archive for the ‘density increment argument’ tag.
The following result is due independently to Furstenberg and to Sarkozy:
Theorem 1 (Furstenberg-Sarkozy theorem) Let
, and suppose that
is sufficiently large depending on
. Then every subset
of
of density
at least
contains a pair
for some natural numbers
with
.
This theorem is of course similar in spirit to results such as Roth’s theorem or Szemerédi’s theorem, in which the pattern is replaced by
or
for some fixed
respectively. There are by now many proofs of this theorem (see this recent paper of Lyall for a survey), but most proofs involve some form of Fourier analysis (or spectral theory). This may be compared with the standard proof of Roth’s theorem, which combines some Fourier analysis with what is now known as the density increment argument.
A few years ago, Ben Green, Tamar Ziegler, and myself observed that it is possible to prove the Furstenberg-Sarkozy theorem by just using the Cauchy-Schwarz inequality (or van der Corput lemma) and the density increment argument, removing all invocations of Fourier analysis, and instead relying on Cauchy-Schwarz to linearise the quadratic shift . As such, this theorem can be considered as even more elementary than Roth’s theorem (and its proof can be viewed as a toy model for the proof of Roth’s theorem). We ended up not doing too much with this observation, so decided to share it here.
The first step is to use the density increment argument that goes back to Roth. For any , let
denote the assertion that for
sufficiently large, all sets
of density at least
contain a pair
with
non-zero. Note that
is vacuously true for
. We will show that for any
, one has the implication
for some absolute constant . This implies that
is true for any
(as can be seen by considering the infimum of all
for which
holds), which gives Theorem 1.
It remains to establish the implication (1). Suppose for sake of contradiction that we can find for which
holds (for some sufficiently small absolute constant
), but
fails. Thus, we can find arbitrarily large
, and subsets
of
of density at least
, such that
contains no patterns of the form
with
non-zero. In particular, we have
(The exact ranges of and
are not too important here, and could be replaced by various other small powers of
if desired.)
Let be the density of
, so that
. Observe that
and
If we thus set , then
In particular, for large enough,
On the other hand, one easily sees that
and hence by the Cauchy-Schwarz inequality
which we can rearrange as
Shifting by
we obtain (again for
large enough)
In particular, by the pigeonhole principle (and deleting the diagonal case , which we can do for
large enough) we can find distinct
such that
so in particular
If we set and shift
by
, we can simplify this (again for
large enough) as
On the other hand, since
we have
for any , and thus
Averaging this with (2) we conclude that
In particular, by the pigeonhole principle we can find such that
or equivalently has density at least
on the arithmetic progression
, which has length
and spacing
, for some absolute constant
. By partitioning this progression into subprogressions of spacing
and length
(plus an error set of size
, we see from the pigeonhole principle that we can find a progression
of length
and spacing
on which
has density at least
(and hence at least
) for some absolute constant
. If we then apply the induction hypothesis to the set
we conclude (for large enough) that
contains a pair
for some natural numbers
with
non-zero. This implies that
lie in
, a contradiction, establishing the implication (1).
A more careful analysis of the above argument reveals a more quantitative version of Theorem 1: for (say), any subset of
of density at least
for some sufficiently large absolute constant
contains a pair
with
non-zero. This is not the best bound known; a (difficult) result of Pintz, Steiger, and Szemeredi allows the density to be as low as
. On the other hand, this already improves on the (simpler) Fourier-analytic argument of Green that works for densities at least
(although the original argument of Sarkozy, which is a little more intricate, works up to
). In the other direction, a construction of Rusza gives a set of density
without any pairs
.
Remark 1 A similar argument also applies with
replaced by
for fixed
, because this sort of pattern is preserved by affine dilations
into arithmetic progressions whose spacing
is a
power. By re-introducing Fourier analysis, one can also perform an argument of this type for
where
is the sum of two squares; see the above-mentioned paper of Green for details. However there seems to be some technical difficulty in extending it to patterns of the form
for polynomials
that consist of more than a single monomial (and with the normalisation
, to avoid local obstructions), because one no longer has this preservation property.
We now give a basic application of Fourier analysis to the problem of counting additive patterns in sets, namely the following famous theorem of Roth:
Theorem 1 (Roth’s theorem) Let
be a subset of the integers
whose upper density
is positive. Then
contains infinitely many arithmetic progressions
of length three, with
and
.
This is the first non-trivial case of Szemerédi’s theorem, which is the same assertion but with length three arithmetic progressions replaced by progressions of length for any
.
As it turns out, one can prove Roth’s theorem by an application of linear Fourier analysis – by comparing the set (or more precisely, the indicator function
of that set, or of pieces of that set) against linear characters
for various frequencies
. There are two extreme cases to consider (which are model examples of a more general dichotomy between structure and randomness). One is when
is aligned up almost completely with one of these linear characters, for instance by being a Bohr set of the form
or more generally of the form
for some multi-dimensional frequency and some open set
. In this case, arithmetic progressions can be located using the equidistribution theory of the previous set of notes. At the other extreme, one has Fourier-uniform or Fourier-pseudorandom sets, whose correlation with any linear character is negligible. In this case, arithmetic progressions can be produced in abundance via a Fourier-analytic calculation.
To handle the general case, one must somehow synthesise together the argument that deals with the structured case with the argument that deals with the random case. There are several known ways to do this, but they can be basically classified into two general methods, namely the density increment argument (or increment argument) and the energy increment argument (or
increment argument).
The idea behind the density increment argument is to introduce a dichotomy: either the object being studied is pseudorandom (in which case one is done), or else one can use the theory of the structured objects to locate a sub-object of significantly higher “density” than the original object. As the density cannot exceed one, one should thus be done after a finite number of iterations of this dichotomy. This argument was introduced by Roth in his original proof of the above theorem.
The idea behind the energy increment argument is instead to decompose the original object into two pieces (and, sometimes, a small additional error term): a structured component that captures all the structured objects that have significant correlation with
, and a pseudorandom component which has no significant correlation with any structured object. This decomposition usually proceeds by trying to maximise the “energy” (or
norm) of the structured component, or dually by trying to minimise the energy of the residual between the original object and the structured object. This argument appears for instance in the proof of the Szemerédi regularity lemma (which, not coincidentally, can also be used to prove Roth’s theorem), and is also implicit in the ergodic theory approach to such problems (through the machinery of conditional expectation relative to a factor, which is a type of orthogonal projection, the existence of which is usually established via an energy increment argument). However, one can also deploy the energy increment argument in the Fourier analytic setting, to give an alternate Fourier-analytic proof of Roth’s theorem that differs in some ways from the density increment proof.
In these notes we give both two Fourier-analytic proofs of Roth’s theorem, one proceeding via the density increment argument, and the other by the energy increment argument. As it turns out, both of these arguments extend to establish Szemerédi’s theorem, and more generally in counting other types of patterns, but this is non-trivial (requiring some sort of inverse conjecture for the Gowers uniformity norms in both cases); we will discuss this further in later notes.
Read the rest of this entry »
Recent Comments