Line - Revision history

Gowers at 13:01, 22 February 2009

2009-02-22T13:01:45Z

← Older revision		Revision as of 06:01, 22 February 2009
Line 1:		Line 1:
	There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''. (~~There~~ are obvious analogues ~~for all three notions~~ defined on <math>[k]^n</math> for more general values of k, including k=2.)		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.)		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.)

Gowers at 13:00, 22 February 2009

2009-02-22T13:00:56Z

← Older revision		Revision as of 06:00, 22 February 2009
Line 1:		Line 1:
	There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''. (~~These~~ notions ~~can also be~~ defined on <math>[k]^n</math> for more general values of k.)		There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''. (There are obvious analogues for all three notions 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.)		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.)

193.62.203.214: correct apparent typo in example of geometric line that is not a combinatorial line

2009-02-17T23:04:07Z

correct apparent typo in example of geometric line that is not a combinatorial line

← Older revision		Revision as of 16:04, 17 February 2009
Line 5:		Line 5:
	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''.		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, 23 \}</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.		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.

Teorth at 23:03, 16 February 2009

2009-02-16T23:03:06Z

← Older revision		Revision as of 16:03, 16 February 2009
Line 1:		Line 1:
	There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''.		There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''. (These notions can also be defined on <math>[k]^n</math> for more general values of k.)

	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.)		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.)

Teorth at 23:02, 16 February 2009

2009-02-16T23:02:29Z

← Older revision		Revision as of 16:02, 16 February 2009
Line 1:		Line 1:
	There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''.		There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''.

	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 can be straightforwardly generalized to yield a monochromatic subspace of this more stronger kind.)		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''.		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, 23 \}</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.		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, 23 \}</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.

Gowers: added to definition of combinatorial subspace

2009-02-16T22:00:07Z

added to definition of combinatorial subspace

← Older revision		Revision as of 15:00, 16 February 2009
Line 1:		Line 1:
	There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''.		There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''.

	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]].		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 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''.		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, 23 \}</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.		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, 23 \}</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.

Teorth at 22:19, 15 February 2009

2009-02-15T22:19:17Z

← Older revision		Revision as of 15:19, 15 February 2009
Line 1:		Line 1:
	There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''.		There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''.

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

	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''.		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, 23 \}</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.		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, 23 \}</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.

Teorth at 16:58, 14 February 2009

2009-02-14T16:58:49Z

← Older revision		Revision as of 09:58, 14 February 2009
Line 5:		Line 5:
	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''.		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, 23 \}</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]].		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, 23 \}</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.

Teorth: New page: There are three types of lines in $[3]^n$ : ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''. For us, the most important (and most restrictive) notion is th...

2009-02-14T16:58:07Z

New page: There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''. For us, the most important (and most restrictive) notion is th...

New page

There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''.

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 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, 23 \}</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]].