# Difference between revisions of "BK:Section 3"

m (→The nd-estimate) |
(→Comparison with other results about the large spectrum of a set) |
||

Line 30: | Line 30: | ||

which should be compared to the bound on <math>| \Delta \cap V^{\perp} |</math> given by the nd-estimate. | 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 | + | 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. (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 | 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 |

## Revision as of 00:24, 7 February 2011

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 [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) \gt \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 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. (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.