Moser's cube problem: Difference between revisions

From Polymath Wiki
Jump to navigationJump to search
No edit summary
No edit summary
Line 18: Line 18:


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>.
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>.
== Variants ==
A straightforward 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]].

Revision as of 09:03, 16 February 2009

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

[math]\displaystyle{ 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]\displaystyle{ 120 \leq c'_5 \leq 129 }[/math]; see this spreadsheet for the latest bounds.

The best known asymptotic lower bound for [math]\displaystyle{ c'_n }[/math] is

[math]\displaystyle{ 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]\displaystyle{ c_n }[/math]:

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

A more precise lower bound is

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

where q is the nearest integer to [math]\displaystyle{ 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]\displaystyle{ c'_5 \geq 120 }[/math], which compares with the upper bound [math]\displaystyle{ c'_5 \leq 4 c'_3 = 129 }[/math].

Variants

A straightforward 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]\displaystyle{ \binom{n}{n/2} 2^n + \binom{n}{n/2-1} 2^{n-1} }[/math]

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