Difference between revisions of "Moser's cube problem"

From Polymath Wiki
Jump to: navigation, search
(New page: Let <math>c'_n</math> denote the largest subset of <math>[3]^n</math> which does not contain any geometric line (which is the same as a combinatorial line, but has a second wildcard y whic...)
 
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>
  
The best known lower bound for <math>c'_n</math> is
+
Beyond this point, we only have some crude upper and lower bounds, e.g. <math>96 \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
  
 
: <math>c'_n \gg 3^n/\sqrt{n}</math>,
 
: <math>c'_n \gg 3^n/\sqrt{n}</math>,

Revision as of 03:31, 14 February 2009

Let [math]c'_n[/math] denote the largest subset of [math][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]c'_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 crude upper and lower bounds, e.g. [math]96 \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 [upper and lower bounds|significantly better bound] for [math]c_n[/math]:

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