Difference between revisions of "Moser's cube problem"

From Polymath Wiki
Jump to: navigation, search
(Variants)
Line 27: Line 27:
 
== Variants ==
 
== Variants ==
  
A straightforward lower bound for Moser’s cube k=4 (values 0,1,2,3) is:
+
A lower bound for Moser’s cube k=4 (values 0,1,2,3) is:
 
q entries are 1 or 2; or q-1 entries are 1 or 2 and an odd number of entries are 0.  This gives a lower bound of
 
q entries are 1 or 2; or q-1 entries are 1 or 2 and an odd number of entries are 0.  This gives a lower bound of
  

Revision as of 13:03, 18 February 2009

Define a Moser set to be a subset of [math][3]^n[/math] which does not contain any geometric line, and let [math]c'_n[/math] denote the size of the largest Moser set in [math][3]^n[/math]. The first few values are (see OEIS A003142):

[math]c'_0 = 1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43.[/math]

Beyond this point, we only have some upper and lower bounds, e.g. [math]120 \leq c'_5 \leq 129[/math]; see this spreadsheet for the latest bounds.

The best known asymptotic lower bound for [math]c'_n[/math] is

[math]c'_n \gg 3^n/\sqrt{n}[/math],

formed by fixing the number of 2s to a single value near n/3. Is it possible to do any better? Note that we have a significantly better bound for [math]c_n[/math]:

[math]c'_n \geq 3^{n-O(\sqrt{\log n})}[/math].

A more precise lower bound is

[math]c'_n \geq \binom{n+1}{q} 2^{n-q}[/math]

where q is the nearest integer to [math]n/3[/math], formed by taking all strings with q 2s, together with all strings with q-1 2s and an odd number of 1s. This for instance gives the lower bound [math]c'_5 \geq 120[/math], which compares with the upper bound [math]c'_5 \leq 4 c'_3 = 129[/math].

Using DHJ(3), we have the upper bound

[math]c'_n = o(3^n)[/math],

but no effective decay rate is known. It would be good to have a combinatorial proof of this fact (which is weaker than DHJ(3), but implies Roth's theorem).

Variants

A lower bound for Moser’s cube k=4 (values 0,1,2,3) is: q entries are 1 or 2; or q-1 entries are 1 or 2 and an odd number of entries are 0. This gives a lower bound of

[math]\binom{n}{n/2} 2^n + \binom{n}{n/2-1} 2^{n-1}[/math]

which is comparable to [math]4^n/\sqrt{n}[/math] by Stirling's formula.

For k=5 (values 0,1,2,3,4) If A, B, C, D, and E denote the numbers of 0-s, 1-s, 2-s, 3-s, and 4-s then the first three points of a geometric line form a 3-term arithmetic progression in A+E+2(B+D)+3C. So, for k=5 we have a similar lower bound for the Moser’s problem as for DHJ k=3, i.e. [math]5^{n - O(\sqrt{\log n})}[/math].