Difference between revisions of "BK:Section 3"

From Polymath1Wiki
Jump to: navigation, search
m (Section 3: the "nd-estimate" moved to BK:Section 3: Easier to refer to)
m (The nd-estimate)
Line 11: Line 11:
 
:'''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  
 
:'''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>.
 
:<math>\Delta = \{ \gamma \in \widehat{G} : | \widehat{1_A}(\gamma) | \geq \delta \alpha \} \setminus \{ 0_{\widehat{\mathbb{F}_3^n}} \}</math>.
:Suppose <math>V \leq \mathbb{F}_3^n</math> be a subspace. Then
+
: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>,
 
:* 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>.
 
:* 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>.

Revision as of 16:04, 6 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 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 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.

Relation to Lemma 2.8 in Sanders's paper