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