View source

There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''.  (For all three notions there are obvious analogues defined on <math>[k]^n</math> for more general values of k, including k=2.)

For us, the most important (and most restrictive) notion is that of a ''combinatorial line'', which is a set of three points in <math>[3]^n</math>, formed by taking a string with one or more wildcards <math>\ast</math> in it, e.g., <math>112\!\ast\!\!1\!\ast\!\ast3\ldots</math>, and replacing those wildcards by <math>1, 2</math> and <math>3</math>, respectively.  In the example given, the resulting combinatorial line is: <math>\{ 11211113\ldots, 11221223\ldots, 11231333\ldots \}</math>.  Sets without any combinatorial lines are called ''line-free''.  The higher-dimensional analogue of a combinatorial line is a [[combinatorial subspace]]. More precisely, a d-dimensional combinatorial subspace is obtained by taking d disjoint subsets <math>W_1,\dots,W_d</math> of <math>[n],</math> fixing the values of all coordinates outside these subsets, and taking all points that equal the fixed values outside the <math>W_i</math> and are constant on each <math>W_i.</math> Sometimes one adds the restriction that the maximum of each <math>W_i</math> is less than the minimum of <math>W_{i+1}</math>. (In particular, the [[Hales-Jewett theorem]] or its [[DHJ(3)|density analogue]] can be straightforwardly generalized to yield a monochromatic subspace of this more stronger kind.)

The most general notion of a line is that of an ''algebraic line'', which is a set of three points of the form x, x+r, x+2r, where we identify <math>[3]^n</math> with <math>({\Bbb Z}/3{\Bbb Z})^n</math> and r is non-zero.  Every combinatorial line is an algebraic line, but not conversely.  For instance <math>\{23, 31, 12\}</math> is an algebraic line (but not a combinatorial or geometric line).  Sets without any algebraic lines are called ''cap-sets''.

Intermediate between these is the notion of a ''geometric line'': an arithmetic progression in <math>[3]^n</math>, which we now identify as a subset of <math>{\Bbb Z}^n</math>.  Every combinatorial line is geometric, and every geometric line is algebraic, but not conversely.  For instance, <math>\{ 31, 22, 13 \}</math> is a geometric line (and thus algebraic) but not a combinatorial line.  Sets without any geometric lines are called ''Moser sets'': see [[Moser's cube problem]].  One can view geometric lines as being like combinatorial lines, but with 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.