## Friday, April 8, 2011

### Simplex

A linear surface is constructible through any n regions in Rn. According to the proof in the last post, the only reason a linear surface is not constructible through n+1 regions is that the regions are vertex regions of a simplex. To me that reinforces the importance of simplexes. The proof I supplied for the "Simplex Theorem" in the first post was insufficiently precise. Here is a better proof, preceded by supportive definition, lemma, and theorem. Subspace and region were defined in the first post. Here I define subregion.

If Sn is a subspace of Qn, and R is a region of Sn, then region P, in Qn, is a subregion of R iff R(b)=P(b) for each boundary b in Sn.

## Intermediate Region Lemma

If Sn is a subspace of linear space Qn, R is a region in Sn, b extends Qn to a linear space, and b divides R, then b divides a subregion of R in Qn.

Consider the section of Sn by b, Sn-1. Let P be the region in Sn-1 isomorphic to R. By transitivity of isomorphism, the section of Qn by b is isomorphic to an extension of Sn-1. Thus, the subregions of R are isomorphic to the subregions of P. Since at least R is a subregion of R, there is a subregion of P. Therefore, b divides a subregion of R.

## Intermediate Region Theorem

If linear space Sn extends to Qn, region R in Sn extends to regions {R0, R1, R2, ...} in Qn, Ra and Rb in {R0, R1, R2, ...} are on opposite sides of both b0 and b1, Qn extended by b2 is linear, and b2 divides Ra and Rb, then there exists Rc in {R0, R1, R2, ...}, such that b2 divides Rc, Rc is opposite one of b0 or b1 from Ra, and Rc is opposite the other of b0 or b1 from Rb.

Suppose b0 divides R into R1 and R2, and b1 divides R. By the lemma, b1 divides R1 or R2. First suppose b1 divides only one of R1 or R2. Suppose without loss of generality that b1 divides R1 into R3 and R4. Again without loss of generality, assume Ra is a subregion of R2 and Rb is a subregion of R4. Consider the section, Sn-1, of Sn by b2. Let P, P2, P4 in Sn-1 be isomorphic to R, R2, R4 in Sn, respectively. Since P is divided by two boundaries, isomorphic to b0 and b1, it has at least three subregions, two of which are P2 and P4, and the third is isomorphic to R3. Therefore, b2 divides R3. By the lemma, there is subregion Rc of R3 divided by b2, completing the proof for the case that b1 divides only one of R1 or R2. Next assume b1 divides R1 into R3 and R4, and b1 divides R2 into R5 and R6. Assume without loss of generality Ra is a subregion of R3 and Rb is a subregion of R6. Consider the section, Sn-1, of Sn by b2. Let P, P3, P6 in Sn-1 be isomorphic to R, R3, R6 in Sn, respectively. Since P is divided by two boundaries, isomorphic to b0 and b1, it has at least three subregions, two of which are P3 and P6, and the third is isomorphic to either R4 or R5. Therefore, b2 divides either R4 or R5. Assume without loss of generality that b2 divides R4. By the lemma, there is subregion Rc of R4 divided by b2, completing the proof.

## Simplex Theorem

If b divides the vertex regions of a simplex in linear space, Sn, then Sn extended by b is not linear.

If the vertexes of a simplex are divided by a boundary, b, then b divides the vertexes of the restriction of Sn to the simplex. Thus, I need only prove the theorem for Sn consisting of a simplex alone. Proceed by induction on the dimension of Sn. If n=1, no boundary divides the vertex regions because no boundary divides more than one region, and a simplex has two vertexes. Make the induction assumption that if the dimension is less than n, then any extension dividing vertex regions is not linear. Let V0, V1, ..., Vn be vertex regions of Sn opposite the empty region from boundaries b0, b1, ..., bn, respectively. Suppose for proof by contradiction, that V0, V1, ..., Vn are divided by b, and the extension by b is linear. For each bi in {b1, b2, ..., bn}, let Ri be the region of {b1, b2, ..., bn}-{bi} containing Vi. V0 is a subregion of Ri because none of {b1, b2, ..., bn}-{bi} separates Vi from V0. Since b divides Vi and V0, and Vi and V0 are subregions of Ri, the "Intermediate Region Theorem" applies. Thus, b divides a region Ui in Ri between bi and b0. Since only b0 and bi divide Ri, and the region opposite bi from Vi is empty, Ri has only three subregions, Vi, V0, and Ui. Consider Sn-1, the section by b0 of Sn with b0 removed. Since Sn-1 has n boundaries, it is a simplex. For each i in {1, 2, ..., n}, let Wi be the vertex region of Sn-1 opposite bi from the empty region, Pi be the region containing Ui and Vi as subregions, Uia and Uib be the subregions of Ui separated by b, Via and Vib be the subregions of Vi separated by b, Pia be the region with Uia and Via as subregions, and Pib be the region with Uib and Vib as subregions. Since the region opposite bi from Pi is V0, and b0 does not divide V0, Pi is isomorphic to Wi. Since b0 divides both Pia and Pib, b divides Wi. By the induction assumption, Sn-1 extended by b is not linear. On the other hand, Sn extended by b is linear by assumption. Thus by the "Section Theorem", Sn-1 extended by b is linear. This contradiction completes the proof.

## Tuesday, March 15, 2011

### Constructibility

I am finally able to prove the theorems I left unproved in the first posting of this blog. I'll start with a new approach to the "Independent Boundary Theorem". Then I'll present a few lemmas for the "Constructibility Theorem", introduced as the "if" part of the "Linear Space Theorem" in the first posting. In the following, all regions in Rn are bounded by linear surfaces, so they are closed and convex.

## Independent Boundary Theorem

If Sn extended by b0 is linear and Sn extended by b1 is linear, then there exists a linear superspace of Sn extended by b0 and b1.

If n=1, and b0 and b1 divide different regions, then add points such that all regions identical, except for b0 and b1, to the regions divided by b0 and b1 are nonempty. If n=1, and b0 and b1 divide the same region, then add points such that 3 out of 4 of the regions identical, except for b0 and b1, to the region divided by b0 and b1 are nonempty. If n>1, Proceed by induction on number of boundaries. If Sn is empty, construct all 4 possible regions. Otherwise, choose b2 from Sn. Consider the section Sn-1 of Sn-{b2} by b2. By the "Section Theorem", Sn-1 is linear. Apply the induction hypothesis to get linear Sn-{b2}+{b0,b1}. Apply the induction hypothesis again to extend Sn-1 by the sections of b0 and b1 by b2. Choose sides of b2 for points in Sn-{b2}+{b0,b1} such that b2 divides regions isomorphic to Sn-1 extended by the sections of b0 and b1 by b2. Use the "Antisection Theorem" to prove that Sn+{b0,b1} is linear.

## First Constructibility Lemma

If linear surface s goes through (tangent or dividing) all regions {R1, R2, ...}, and no linear surface divides every region from {R1, R2, ...}, then s is tangent to at least n+1 of {R1, R2, ...}.

If s is tangent to fewer than n+1 of {R1, R2, ...}, then a linear surface dividing all of {R1, R2, ...} can be constructed by moving s an arbitrarily small amount into the regions from {R1, R2, ...} it is tangent to. This contradiction proves that s is tangent to at least n+1 of {R1, R2, ...}.

## Second Constructibility Lemma

If b0 is a boundary for all of the regions divided by b1 in a linear space Sn, Sn is isomorphic to linear surfaces in Rn, b0 is isomorphic to s0 in Rn, Sn-1 is the section of Sn by b1, b0 in Sn-1 is isomorphic to linear subsurface l0 in s0, then there exists linear surface s1 in Rn isomorphic to b1.

Choose R0 in Rn isomorphic to some R0 divided by b1. Construct s1 arbitrarily close to s0, through l0, dividing R0. I must show that the isomorphism between Sn and Rn maps the regions divided by b1 to the regions divided by s1. Suppose b1 divides R1 in Sn isomorphic to R1 in Rn. By definition of section, R0 and R1 in Sn on the same side of b0 implies R0 and R1 in Sn-1 are on the same side of b0. Let Qn be Sn with b0 removed. Since b0 bounds the regions divided by b1, b0 and b1 divide the same regions in Qn. Thus, b0 in the section by b1 is isomorphic to b1 in the section by b0. Therefore, R0 and R1 on the same side of b0 in b1 implies R0 and R1 are on the same side of b1 in b0. Let Pn be Rn with s0 removed, then Pn is isomorphic to Qn. Thus, R0 and R1 on the same side of b1 in b0 implies R0 and R1 are on the same side of l0 in s0. By similarity of triangles, R0 and R1 on the same side of l0 in s0, R0 and R1 on the same side of s0 in Rn, s1 arbitrarily close to s0, and s1 dividing R0 implies s1 divides R1. A similar argument applies if R0 and R1 in Sn are opposite b0. Therefore, b1 dividing R1 implies s1 divides R1 isomorphic to R1, so s1 is isomorphic to b1.

## Third Constructibility Lemma

If there is no linear surface through regions {R1, R2, ...} in Rn, and there is no linear surface tangent to more than n regions in {R1, R2, ...}, then there is a subset of n+1 regions {R3, R4, ...} from {R1, R2, ...} such that there is no linear surface through {R3, R4, ...}.

Any linear surface goes through an empty set of regions, so {R1, R2, ...} must be nonempty. Choose {R5, R6, ...} and R from {R1, R2, ...} such that there is a linear surface through {R5, R6, ...}, but no linear surface through {R, R5, R6, ...}. Choose linear surface s0, closest to R that goes through {R5, R6, ...}. Because s0 cannot be moved closer to R without changing whether it goes through {R5, R6, ...}, and s0 is tangent to no more than n regions from {R5, R6, ...}, s0 is tangent to exactly n regions from {R5, R6, ...}. Let {R3, R4, ...} be the n regions from {R5, R6, ...} that s0 is tangent to, together with R. Suppose there is linear surface s1 that goes through all of {R3, R4, ...}. Move s0 towards s1 such that their intersection remains fixed. Since s0 is closest to R through {R5, R6, ...}, it must leave one of {R5, R6, ...} before it gets closer to R, and it must get closer to R to get closer to s1. The only regions s0 can leave immediately are the ones it is tangent to. Thus, s0 must leave one of {R3, R4, ...}. Since s0 only moves towards s1 and the regions are convex, s0 never returns to that region it leaves. Therefore s1 does not go through all of {R3, R4, ...}, and there is no linear surface through all of {R3, R4, ...}.

## Fourth Constructibility Lemma

If there is no linear surface through n+1 regions {R1, R2, ...} in Rn, then there is a simplex with {R1, R2, ...} in the vertex regions.

Fore each R in {R1, R2, ...} choose s through all of {R1, R2, ...} except R, closest to R. This is possible because it is always possible to construct a linear surface through n regions in Rn. If s were not tangent to n regions from {R1, R2, ...}, there would be a linear surface through the same regions as s, but closer to R. Thus, s is tangent to n regions from {R1, R2, ...}. For each s, choose t arbitrarily close to s, not through the regions s is tangent to, and still not through R. Thus, t separates R from the other regions in {R1, R2, ...}. In this way construct simplex {t1, t2, ...} with {R1, R2, ...} in the vertex regions.

## Constructibility Theorem

If Sn is a linear sidedness space, then there exist non-coincidental linear surfaces in Rn isomorphic to Sn.

If n=1, then construct by choosing boundaries dividing the same regions in R1 as divided in S1. This is possible because extensions to S1 divide nonempty regions. If n>1, proceed by induction on the number of boundaries in Sn. If there are no boundaries in Sn, then the empty set of linear surfaces in Rn is isomorphic. Assume there is a set of non-coincidental linear surfaces isomorphic to every sidedness space with one fewer boundary than Sn. I must prove there is a set of non-coincidental linear surfaces isomorphic to Sn. Assume the contrary. Remove one boundary, b, from Sn. There is a set, {s1, s2, ...}, of non-coincidental linear surfaces isomorphic to Sn with b removed. By assumption there is no linear surface dividing the regions, {R1, R2, ...}, isomorphic to the regions divided by b. If there exists a linear surface, s, through (tangent or dividing) all of {R1, R2, ...}, then by the "First Constructibility Lemma", s is tangent to at least n+1 of {R1, R2, ...}. By the induction assumption, the boundaries of the regions are non-coincidental, so s is tangent to no more than n regions unless it is a boundary for all of the regions it goes through. Thus, s is a boundary for all of {R1, R2, ...}, or there is R in {R1, R2, ...} that s does not go through (neither tangent nor dividing). If s is a boundary, then since n>1, the boundary isomorphic to s in the section of Sn by b is constructible by the induction assumption. By the "Second Constructibility Lemma", if s is a boundary for the regions, then b is constructible. This contradiction shows that for each linear surface s there is some R in {R1, R2, ...} that s does not go through. Since the boundaries of {R1, R2, ...} are non-coincidental, no linear surface is tangent to more than n of {R1, R2, ...}. By the "Third Constructibility Lemma", there is a subset of n+1 of {R1, R2, ...}, say {R3, R4, ...}, that no linear surface goes through. By the "Fourth Constructibility Lemma", there is a simplex, say {s3, s4, ...} of n+1 linear surfaces with {R3, R4, ...} in the vertex regions. By the "only if" part of the "Linearity Theorem", and the "Independent Boundary Theorem", Sn with b removed can be extended by boundaries isomorphic to {s3, s4, ...}, to spaces extensible by b. Thus, Sn is extensible by a simplex with b dividing the vertex regions. This violates the "Simplex Theorem", so there is a linear surface, s0, that together with {s1, s2, ...}, are isomorphic to Sn. If {s0, s1, s2, ...} are coincidental, then adjust s0 by an arbitrarily small amount to find non-coincidental linear surfaces isomorphic to Sn.

Note that the proof extends an arbitrary set of linear surfaces with a new surface. Thus, every isomorphic set of linear surfaces can be extended to every superspace. In other words, to obtain a set of linear surfaces isomorphic to a given abstract linear space, linear surfaces can be added to the set in any order, and any linear surface that divides the correct regions suffices. To me this means linear spaces are very easy to construct. On the other hand, I could claim that linear spaces are very rigid. For example, no change in the position of a linear surface sufficient to close a line of sight is possible without changing which equivalence class the linear space is in.