Moser's cube problem: Difference between revisions

From Polymath Wiki
Jump to navigationJump to search
No edit summary
No edit summary
Line 9: Line 9:
: <math>c'_n \gg 3^n/\sqrt{n}</math>,
: <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 [upper and lower bounds|significantly better bound] for <math>c_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 [[upper and lower bounds|significantly better bound]] for <math>c_n</math>:


: <math>c'_n \geq 3^{n-O(\sqrt{\log n})}</math>.
: <math>c'_n \geq 3^{n-O(\sqrt{\log n})}</math>.

Revision as of 19:31, 13 February 2009

Let [math]\displaystyle{ c'_n }[/math] denote the largest subset of [math]\displaystyle{ [3]^n }[/math] which does not contain any geometric line (which is the same as a combinatorial line, but has a second wildcard y which goes from 3 to 1 whilst x goes from 1 to 3, e.g. xx2yy gives the geometric line 11233, 22222, 33211). The Moser cube problem is to understand the behaviour of [math]\displaystyle{ c'_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].