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>.
:Suppose <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==

2010-07-08T19:49:31Z

Olof: Uniformizing notation

This is the wiki page for the mini-polymath2 project, which seeks solutions to Question 5 of the 2010 International Mathematical Olympiad.

The project will start at [http://www.timeanddate.com/worldclock/fixedtime.html?year=2010&month=7&day=8&hour=16&min=0&sec=0&p1=0 16:00 UTC July 8], and is hosted at the [http://polymathprojects.org/ polymath blog]. A discussion thread is hosted at [http://terrytao.wordpress.com Terry Tao's blog].

== Rules ==

This project will follow the [http://polymathprojects.org/general-polymath-rules/ usual polymath rules]. In particular:

* Everyone is welcome to participate, though people who have already seen an external solution to the problem should probably refrain from giving spoilers throughout the experiment.
* This is a team effort, not a race between individuals. Rather than work for extended periods of time in isolation from the rest of the project, the idea is to come up with short observations (or to carry an observation of another participant further) and then report back what one gets to the rest of the team. Partial results or even failures can be worth reporting.
* Participants are encouraged to update the wiki, or to summarise progress within threads, for the benefit of others.

== Threads ==

Discussion and planning:

* [http://terrytao.wordpress.com/2010/06/12/future-mini-polymath-project-2010-imo-q6/ Future mini-polymath project: 2010 IMO Q6?] June 12, 2010.
* [http://terrytao.wordpress.com/2010/06/21/organising-mini-polymath2/ Organising mini-polymath2] June 21, 2010.
* [http://terrytao.wordpress.com/2010/06/27/mini-polymath2-start-time/ Mini-polymath2 start time], June 27, 2010.
* [http://terrytao.wordpress.com/2010/07/08/mini-polymath2-discussion-thread/ Mini-polymath2 discussion thread], July 8 2010.

Research:

* [http://polymathprojects.org/2010/07/08/minipolymath2-project-imo-2010-q5/ Minipolymath2 project: IMO 2010 Q5], July 8 2010.

== The question ==

The question to be solved is Question 5 of the [http://www.imo-official.org/problems.aspx 2010 International Mathematical Olympiad]:

: '''Problem''' In each of six boxes <math>B_1, B_2, B_3, B_4, B_5, B_6</math> there is initially one coin. There are two types of operation allowed:
:
: ''Type 1:'' Choose a nonempty box <math>B_j</math> with <math>1 \leq j \leq 5</math>. Remove one coin from <math>B_j</math> and add two coins to <math>B_{j+1}</math>.
:
: ''Type 2:'' Choose a nonempty box <math>B_k</math> with <math>1 \leq k \leq 4</math>. Remove one coin from <math>B_k</math> and exchange the contents of (possibly empty) boxes <math>B_{k+1}</math> and <math>B_{k+2}</math>.
:
: Determine whether there is a finite sequence of such operations that results in boxes <math>B_1, B_2, B_3, B_4, B_5</math> being empty and box <math>B_6</math> containing exactly <math>2010^{2010^{2010}}</math> coins. (Note that <math>a^{b^c} := a^{(b^c)}</math>.)

== Observations and partial results ==

* If the left-most box <math>B_1</math> becomes empty, then it cannot ever become non-empty again. Furthermore, the left-most box can never have more than one coin; it can be touched exactly once.
* Define the ''worth'' W of a state to be <math>W = B_6 + 2 B_5 + 4 B_4 + 8 B_3 + 16 B_2 + 32 B_1</math>. Then the initial worth is 63, the final desired worth is <math>2010^{2010^{2010}}</math>, and the Type 1 move does not affect the worth. On the other hand, the Type 2 move increases the worth when <math>B_{j+2} - B_{j+1} \geq 4</math>.
* Once one has a large number of coins in one of the first four boxes, say <math>B_k</math>, one can apply the Type 2 move repeatedly to remove coins from <math>B_k</math> while swapping <math>B_{k+1}</math> and <math>B_{k+2}</math> repeatedly. This suggests that it is relatively easy to remove coins from the system; the difficulty is in adding coins to the system.
* The total number of coins in the system is bounded. Indeed, let <math>f(N,\Sigma)</math> be the maximum number of coins that one can end up with starting with N boxes with at most <math>\Sigma</math> coins in them. Thus for instance <math>f(1,\Sigma)=\Sigma</math>. By considering the times when one touches the left-most box, we can bound <math>f(N,\Sigma)</math> by at most <math>\Sigma</math> iterations of the map <math>n \mapsto f(N-1,n)+2</math> starting with <math>n=\Sigma</math>. This gives an Ackermann-type bound on <math>f(N,\Sigma)</math>. We need f(6,6) to be less than <math>2010^{2010^{2010}}</math>, but this bound is likely to be too large.

== Possible strategies ==

* Split the problem into two pieces. Part I: try to show the weaker result that the number of coins in the system can eventually be as large as <math>2010^{2010^{2010}}</math>. Part II: Show that once one has a lot of coins, one can move to the final state where <math>B_1=\ldots=B_5=0</math> and <math>B_6 = 2010^{2010^{2010}}</math>.
* Try to show that a quantity such as the worth increases or decreases in a controlled manner as one applies the Type 1 and Type 2 moves.
* We know that the first box can never contain more than one coin. What can we say about the second box, third box, etc.?
** There may be a recursive formula for the maximal size of box <math>B_j</math>, possibly requiring one to solve the five-box, four-box, etc. problems first.
* Work backwards?
* Try to completely solve the three-box problem (say) first: starting from <math>[X,Y,Z]</math>, what is the most number of coins one can generate?

== Compound moves ==

Here we use Type 1 move <math>[a,b] \mapsto [a-1,b+2]</math> and the Type 2 move <math>[a,b,c] \mapsto [a-1,c,b]</math> to create more advanced moves.

# We can create the move <math>[a,b] \mapsto [0,b+2a]</math> from repeated application of Type 1.
# We have <math>[1,a,b] \mapsto [0,0,a+2b]</math> by applying Type 2 once and then Type 1 b times.
#* Or, by using advanced move 1 first, the move <math>[1, a, b] \mapsto [1, 0, b+2a] \mapsto [0, b+2a, 0] \mapsto [0, 0, 2b+4a]</math>.
# We have <math>[a,0,0] \mapsto [0,2^a,0]</math> via <math>[a,0,0] \mapsto [a-1,2,0] \mapsto [a-1,0,4] \mapsto [a-2,4,0] \mapsto [a-2,0,8] \mapsto \ldots \mapsto [1, 0, 2^a] \mapsto [0,2^a,0]</math>.
# Using the previous move, we have <math>[a,b,0,0] \mapsto [a-2, 2^{b+2}, 0, 0]</math> via <math>[a,b,0,0] \mapsto [a,0,2^b,0] \mapsto [a,0,0,2^{b+1}] \mapsto [a-1,2,0,2^{b+1}] \mapsto [a-1,1,0,2^{b+2}] \mapsto [a-1,0,2^{b+2},0] \mapsto [a-2,2^{b+2},0,0]</math>.

The last move seems to be the key to the solutions so far discovered, since it allows one to introduce an exponential at only a linear cost.

== World records ==

To make the second box as big as possible:

* <math>[1,1,1] \mapsto [1,0,3] \mapsto [0,3,0]</math> places 3 coins in box 2.

To make the third box as big as possible:

* <math>[1,1,1] \mapsto [0,3,1] \mapsto [0,0,7]</math> places 7 coins in box 3. (Here we use advanced move 2).

To make the fourth box as big as possible

* <math>[1,1,1,1] \to [0,3,0,3] \to [0,2,2,3] \to [0,2,0,7] \to [0,1,7,0] \to [0,1,0,14]</math> <math> \to [0,0,14,0] \to [0,0,0,28]</math> gives 28 coins in box 4.

To make the sixth box as big as possible

* Using the fourth box move we have <math>[0,0,0,28,1,1]</math>. We can move <math>[28,1,1]</math> to <math>[27,0,7]</math> through Type 1; then using a variant of advanced move 3 we get <math>[0,0,7 * 2^{27}]</math>, leading to <math>7 \times 2^{27}</math> coins in the last box.

* A new record: we can get <math>2^{192}</math> in the 6th box by <math>[1,1,1,1,1,1]\to \to [0,0,7,1,1,1]\to [0,0,7,0,3,1] \to \to [0,0,1,0,3\times 2^6,1]\to[0,0,0,3\times 2^6,0,1]\to [0,0,0,0,0,2^{3\times 2^6}]</math> where <math>\to\to</math> are the special moves.

== Completed solutions ==

=== First solution ===
Fist, I introduce a move that follows from compound move 3:

(1) <math> [N,M,0,0] \to [N-1, 1, 0, 2^{M+1}] \to [N-2,2^{M+1}, 0, 0 ] </math>

We can get

(2) <math> [0,0, 140, 0, 0 ,0] </math> as follows:

:<math>[1,1,1,1,1,1] \to [0,2,2,2,2,3] \to [0,2,1,1,8,3] \to [0,2,1,1,0,19] \to [0,1,19,0,0,0]</math>
:<math>\to [0,1,1,36,0,0] \to [0,1,1,1,0,140] \to [0,0,140,0,0,0]</math>

By (1) combined with (2) we can get some number that is greater than <math>n:=2010^{2010^{2010}}</math> in the 4th spot

And swapping 5 with 6 enough times, we can adjust this number to have the value n/4. Moving everything to the right will give us the desired result.

=== Second solution ===
<math>[1,1,1,1,1,1] \to [0,3,1,1,1,1] \to [0,2,3,1,1,1] \to [0,2,1,5,1,1] \to [0,2,1,1,9,1]</math><math> \to [0,2,1,1,0,19] \to [0,2,1,0,19,0] \to [0,2,0,19,0,0] \to [0,1,19,0,0,0]</math>.

Make use of the compound move 4 here so that <math>\to [0,1,0,2^{2^{\cdots^2}},0,0] \to [0,0,2^{2^{\cdots^2}},0,0,0]=[0,0,N,0,0,0]</math> where there are 19 2's. Note that <math>2^{2^{2^2}}=2^16>2010</math>. Thus, <math>M=2^{2^{\cdots^2}}</math> with 12 2's is bigger than <math>K=2010^{2010^{2010}}</math>. Hence, we have <math>N>K>K/8</math> so that <math>[0,0,N,0,0,0] \to [0,0,N-1,0,0,0] \to \cdots \to [0,0,K/8,0,0,0] \to [0,0,0,K/4,0,0] \to [0,0,0,0,K/2,0] \to [0,0,0,0,0,K]</math>.