Moser's cube problem: Difference between revisions
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
: <math>c'_0 = 1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43.</math> | : <math>c'_0 = 1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43.</math> | ||
Beyond this point, we only have some | Beyond this point, we only have some upper and lower bounds, e.g. <math>120 \leq c'_5 \leq 129</math>; see [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg this spreadsheet] for the latest bounds. | ||
The best known asymptotic lower bound for <math>c'_n</math> is | The best known asymptotic lower bound for <math>c'_n</math> is | ||
| Line 12: | Line 12: | ||
: <math>c'_n \geq 3^{n-O(\sqrt{\log 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>. | |||
Revision as of 14:39, 15 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].
