View source for BK:Section 3

Parent page: [[Improving the bounds for Roth's theorem]]

One of the take-away results from Section 3 of the Bateman-Katz paper is Proposition 3.1, an important part of which is in some places referred to as the "nd-estimate". The rough reason for this terminology is that it says that a set <math>A</math> in <math>\mathbb{F}_3^n</math> of density about <math>1/n</math> either has a `good' density increment on a subspace of codimension <math>d</math>, or else the <math>(1/n)</math>-large spectrum of <math>A</math> intersects any <math>d</math>-dimensional subspace in at most about <math>nd</math> points. We shall say later on why this is significant.

==The nd-estimate==

Here is the precise result, stated in slightly different terms to the paper in order to illustrate how it relates to other results. For a subspace <math>V \leq \mathbb{F}_3^n</math> we write 
:<math>V^{\perp} = \{ \gamma \in \widehat{\mathbb{F}_3^n} : \gamma(x) = 1 \ \forall x \in V \}</math>
for its annihilator (cf. [[Basic facts about Bohr sets|the section on Bohr sets]]).

:'''Proposition 1''' Let <math>A \subset \mathbb{F}_3^n</math> be a set with density <math>\alpha</math>, and let <math>0 \leq \delta, \eta \leq 1</math> be parameters. Set 
:<math>\Delta = \{ \gamma \in \widehat{G} : | \widehat{1_A}(\gamma) | \geq \delta \alpha \} \setminus \{ 0_{\widehat{\mathbb{F}_3^n}} \}</math>.
:Let <math>V \leq \mathbb{F}_3^n</math> be a subspace. Then
:* either <math>A</math> has density at least <math>\alpha(1 + \eta)</math> on <math>V</math>,
:* or <math>|\Delta \cap V^{\perp}| \leq 3\eta \delta^{-2}</math>; in fact <math>\sum_{\gamma \in V^{\perp}} |\widehat{(1_A - \alpha)}(\gamma)|^2 \leq 3\eta \alpha^2</math>.
'''Proof''':
Let us write <math>\mu_V = \frac{|\mathbb{F}_3^n|}{|V|}1_V</math> for the indicator function of <math>V</math> normalized so that <math>\mathbb{E}_x \mu_V(x) = 1</math>. If 
:<math>1_A*\mu_V(x) > \alpha(1 + \eta)</math>
for some <math>x \in \mathbb{F}_3^n</math> then we are in the first case, so let us assume that <math>1_A*\mu_V \leq \alpha(1+\eta)</math>. Write <math>f = 1_A - \alpha</math> for the balanced function of <math>A</math>. Then
:<math> | \Delta \cap V^{\perp} | \delta^2 \alpha^2 \leq \sum_{\gamma \in V^{\perp}} |\widehat{f}(\gamma)|^2 = \sum_{\gamma \in \widehat{\mathbb{F}_3^n}} |\widehat{f}(\gamma)|^2 |\widehat{\mu_V}(\gamma)|^2.</math>
By Parseval's identity, this equals
:<math> \mathbb{E}_{x \in \mathbb{F}_3^n} f*\mu_V(x)^2 = \mathbb{E}_{x \in \mathbb{F}_3^n} 1_A*\mu_V(x)^2 - \alpha^2 \leq \alpha^2(2\eta + \eta^2),</math>
which proves the result.

==Comparison with other results about the large spectrum of a set==
The main ingredient in deriving the nd-estimate is Parseval's identity. This identity also has the following useful consequence: letting <math>\Delta</math> be as above, we have
:<math>|\Delta| \delta^2 \alpha^2 \leq \sum_{\gamma \in \widehat{\mathbb{F}_3^n}} |\widehat{1_A}(\gamma)|^2 = \mathbb{E}_x 1_A(x)^2 = \alpha</math>,
whence
:<math>|\Delta| \leq \alpha^{-1} \delta^{-2}</math>,
which should be compared to the bound on <math>| \Delta \cap V^{\perp} |</math> given by the nd-estimate.

There is another useful result about the large spectrum of a set known as Chang's theorem. Informally, this says that the largest size of a linearly independent set in large spectrum <math>\Delta</math> cannot be too large. Unfortunately, with the parameters needed for the Bateman-Katz paper, Chang's theorem reduces to a trivial statement. (Nevertheless, there is [http://arxiv.org/abs/math/0605689 a generalization of Chang's theorem due to Shkredov] that gives a lower bound for the number of additive <math>(2m)</math>-tuples in the large spectrum of a set, which is used in [[BK:Section 4|Section 4]] of the Bateman-Katz paper.)

By contrast, the nd-estimate is something like a statement in the opposite direction: it says that there are quite a lot of linearly independent characters in <math>\Delta</math>, or else there is a density increment. Specifically, if we have picked <math>\gamma_1, \ldots, \gamma_d</math> from <math>\Delta</math>, then
:<math>| \Delta \cap \langle \gamma_1, \ldots, \gamma_d \rangle | \leq 3\eta \delta^{-2}</math>
unless we get a density increment on a (particular) subspace of codimension at most <math>d</math>.
For suitable parameter choices, this says that there are a lot of characters in the large spectrum that are linearly independent of <math>\gamma_1, \ldots, \gamma_d</math>, which is very important in [[BK:Section 5|Section 5]] of the paper.

==Relation to Lemma 2.8 in Sanders's paper==