# Moser's cube problem

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Let $c'_n$ denote the largest subset of $[3]^n$ 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 $c'_n$. The first few values are (see OEIS A003142):
$c'_0 = 1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43.$
The best known lower bound for $c'_n$ is
$c'_n \gg 3^n/\sqrt{n}$,
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 $c_n$:
$c'_n \geq 3^{n-O(\sqrt{\log n})}$.