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]\displaystyle{ A }[/math] in [math]\displaystyle{ \mathbb{F}_3^n }[/math] of density about [math]\displaystyle{ 1/n }[/math] either has a `good' density increment on a subspace of codimension [math]\displaystyle{ d }[/math], or else the [math]\displaystyle{ (1/n) }[/math]-large spectrum of [math]\displaystyle{ A }[/math] intersects any [math]\displaystyle{ d }[/math]-dimensional subspace in at most about [math]\displaystyle{ 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]\displaystyle{ V \leq \mathbb{F}_3^n }[/math] we write

[math]\displaystyle{ V^{\perp} = \{ \gamma \in \widehat{\mathbb{F}_3^n} : \gamma(x) = 1 \ \forall x \in V \} }[/math]

for its annihilator (cf. the section on Bohr sets).

Proposition 1 Let [math]\displaystyle{ A \subset \mathbb{F}_3^n }[/math] be a set with density [math]\displaystyle{ \alpha }[/math], and let [math]\displaystyle{ 0 \leq \delta, \eta \leq 1 }[/math] be parameters. Set

[math]\displaystyle{ \Delta = \{ \gamma \in \widehat{G} : | \widehat{1_A}(\gamma) | \geq \delta \alpha \} \setminus \{ 0_{\widehat{\mathbb{F}_3^n}} \} }[/math].

Let [math]\displaystyle{ V \leq \mathbb{F}_3^n }[/math] be a subspace. Then

• either [math]\displaystyle{ A }[/math] has density at least [math]\displaystyle{ \alpha(1 + \eta) }[/math] on [math]\displaystyle{ V }[/math],
• or [math]\displaystyle{ |\Delta \cap V^{\perp}| \leq 3\eta \delta^{-2} }[/math]; in fact [math]\displaystyle{ \sum_{\gamma \in V^{\perp}} |\widehat{(1_A - \alpha)}(\gamma)|^2 \leq 3\eta \alpha^2 }[/math].

Proof: Let us write [math]\displaystyle{ \mu_V = \frac{|\mathbb{F}_3^n|}{|V|}1_V }[/math] for the indicator function of [math]\displaystyle{ V }[/math] normalized so that [math]\displaystyle{ \mathbb{E}_x \mu_V(x) = 1 }[/math]. If

[math]\displaystyle{ 1_A*\mu_V(x) \gt \alpha(1 + \eta) }[/math]

for some [math]\displaystyle{ x \in \mathbb{F}_3^n }[/math] then we are in the first case, so let us assume that [math]\displaystyle{ 1_A*\mu_V \leq \alpha(1+\eta) }[/math]. Write [math]\displaystyle{ f = 1_A - \alpha }[/math] for the balanced function of [math]\displaystyle{ A }[/math]. Then

[math]\displaystyle{ | \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]\displaystyle{ \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]\displaystyle{ \Delta }[/math] be as above, we have

[math]\displaystyle{ |\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]\displaystyle{ |\Delta| \leq \alpha^{-1} \delta^{-2} }[/math],

which should be compared to the bound on [math]\displaystyle{ | \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 the large spectrum [math]\displaystyle{ \Delta }[/math] cannot be too large; formally, the largest independent set has size at most [math]\displaystyle{ C\log(\alpha^{-1}) \delta^{-2} }[/math]. Unfortunately this statement becomes trivial with the parameters needed for the Bateman-Katz argument. (Nevertheless, there is a generalization of Chang's theorem due to Shkredov that gives a lower bound for the number of additive [math]\displaystyle{ (2m) }[/math]-tuples in the large spectrum of a set, which is used in 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]\displaystyle{ \Delta }[/math], or else there is a density increment. Specifically, if we have picked [math]\displaystyle{ \gamma_1, \ldots, \gamma_d }[/math] from [math]\displaystyle{ \Delta }[/math], then

[math]\displaystyle{ | \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]\displaystyle{ 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]\displaystyle{ \gamma_1, \ldots, \gamma_d }[/math], which is very important in Section 5 of the paper.