User:Hermann Gruber

2009-02-18T20:17:01Z

Hermann Gruber: my user page

Hello,

this is my user page.

Contact:

[http://www.informatik.uni-giessen.de/staff/gruber/index.html Hermann Gruber at University of Giessen]

Moser's cube problem

2009-02-18T20:13:50Z

Hermann Gruber: fixed wikilink and corrected error in formula

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>

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

: <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#Asymptotics|significantly better bound]] for <math>c_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>.

Using [[DHJ(3)]], we have the upper bound

: <math>c'_n = o(3^n)</math>,

but no effective decay rate is known. It would be good to have a combinatorial proof of this fact (which is weaker than [[DHJ(3)]], but implies [[Roth's theorem]]).

== Variants ==

A 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]].

For k=5 (values 0,1,2,3,4) If A, B, C, D, and E denote the numbers of 0-s, 1-s, 2-s, 3-s, and 4-s then the first three points of a geometric line form a 3-term arithmetic progression in A+E+2(B+D)+3C. So, for k=5 we have a similar lower bound for the Moser’s problem as for DHJ k=3, i.e. <math>5^{n - O(\sqrt{\log n})}</math>.

Polymath Wiki - User contributions [en]

User:Hermann Gruber

Moser's cube problem