Moser's cube problem: Difference between revisions
From Polymath Wiki
Jump to navigationJump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
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 [http://www.research.att.com/~njas/sequences/A003142 OEIS A003142]): | |||
: <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> | ||
Revision as of 09:59, 14 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 crude upper and lower bounds, e.g. [math]\displaystyle{ 96 \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].
