# Line

### From Polymath1Wiki

There are three types of lines in [3]^{n}: *combinatorial lines*, *geometric lines*, and *algebraic lines*. (For all three notions there are obvious analogues defined on [*k*]^{n} 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 [3]^{n}, formed by taking a string with one or more wildcards in it, e.g., , and replacing those wildcards by 1,2 and 3, respectively. In the example given, the resulting combinatorial line is: . 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 of [*n*], fixing the values of all coordinates outside these subsets, and taking all points that equal the fixed values outside the *W*_{i} and are constant on each *W*_{i}. Sometimes one adds the restriction that the maximum of each *W*_{i} is less than the minimum of *W*_{i + 1}. (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 [3]^{n} with and r is non-zero. Every combinatorial line is an algebraic line, but not conversely. For instance {23,31,12} 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 [3]^{n}, which we now identify as a subset of . Every combinatorial line is geometric, and every geometric line is algebraic, but not conversely. For instance, {31,22,13} 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.