BK:Section 3

From Polymath Wiki
Jump to: navigation, search

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. 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 a translate of [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].

In other words, if the large spectrum of a set is somewhat concentrated in some subspace then one can find a density increment on a translate of the annihilator of that subspace.


Let us write [math]\mu_V = \frac{|\mathbb{F}_3^n|}{|V|}1_V[/math] for the scaled 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) \gt \alpha(1 + \eta)[/math]

for some [math]x \in \mathbb{F}_3^n[/math] then we are in the first case of the conclusion, 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],


[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 the large spectrum [math]\Delta[/math] cannot be too large; formally, the largest independent set has size at most [math]C\log(\alpha^{-1}) \delta^{-2}[/math]. Unfortunately this statement becomes trivial with the parameters needed for the Bateman-Katz argument ([math]\delta \sim \alpha \sim 1/n^{1+\epsilon}[/math]). Nevertheless, there is 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 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 Section 5 of the paper. (Note: for this type of conclusion to hold we need to know that the large spectrum [math]\Delta[/math] is quite large, which follows from the assumption that we may make in the [math]\mathbb{F}_3^n[/math] context that [math]A[/math] has no particularly large non-trivial Fourier coefficients.)

Relation to Lemma 2.8 in Sanders's paper