Line

There are three types of lines in [math]\displaystyle{ [3]^n }[/math]: combinatorial lines, geometric lines, and algebraic lines. (There are obvious analogues for all three notions defined on [math]\displaystyle{ [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]\displaystyle{ [3]^n }[/math], formed by taking a string with one or more wildcards [math]\displaystyle{ \ast }[/math] in it, e.g., [math]\displaystyle{ 112\!\ast\!\!1\!\ast\!\ast3\ldots }[/math], and replacing those wildcards by [math]\displaystyle{ 1, 2 }[/math] and [math]\displaystyle{ 3 }[/math], respectively. In the example given, the resulting combinatorial line is: [math]\displaystyle{ \{ 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]\displaystyle{ W_1,\dots,W_d }[/math] of [math]\displaystyle{ [n], }[/math] fixing the values of all coordinates outside these subsets, and taking all points that equal the fixed values outside the [math]\displaystyle{ W_i }[/math] and are constant on each [math]\displaystyle{ W_i. }[/math] Sometimes one adds the restriction that the maximum of each [math]\displaystyle{ W_i }[/math] is less than the minimum of [math]\displaystyle{ W_{i+1} }[/math]. (In particular, the Hales-Jewett theorem or its 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]\displaystyle{ [3]^n }[/math] with [math]\displaystyle{ ({\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]\displaystyle{ \{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]\displaystyle{ [3]^n }[/math], which we now identify as a subset of [math]\displaystyle{ {\Bbb Z}^n }[/math]. Every combinatorial line is geometric, and every geometric line is algebraic, but not conversely. For instance, [math]\displaystyle{ \{ 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.