sidedness geometry

Simplex

2011-04-08T22:03:00.002-07:00

A linear surface is constructible through any n regions in Rⁿ. 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 Sⁿ is a subspace of Qⁿ, and R is a region of Sⁿ, then region P, in Qⁿ, is a subregion of R iff R(b)=P(b) for each boundary b in Sⁿ.

Intermediate Region Lemma

If Sⁿ is a subspace of linear space Qⁿ, R is a region in Sⁿ, b extends Qⁿ to a linear space, and b divides R, then b divides a subregion of R in Qⁿ.

Consider the section of Sⁿ by b, S^n-1. Let P be the region in S^n-1 isomorphic to R. By transitivity of isomorphism, the section of Qⁿ by b is isomorphic to an extension of S^n-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 Sⁿ extends to Qⁿ, region R in Sⁿ extends to regions {R₀, R₁, R₂, ...} in Qⁿ, R_a and R_b in {R₀, R₁, R₂, ...} are on opposite sides of both b₀ and b₁, Qⁿ extended by b₂ is linear, and b₂ divides R_a and R_b, then there exists R_c in {R₀, R₁, R₂, ...}, such that b₂ divides R_c, R_c is opposite one of b₀ or b₁ from R_a, and R_c is opposite the other of b₀ or b₁ from R_b.

Suppose b₀ divides R into R₁ and R₂, and b₁ divides R. By the lemma, b₁ divides R₁ or R₂. First suppose b₁ divides only one of R₁ or R₂. Suppose without loss of generality that b₁ divides R₁ into R₃ and R₄. Again without loss of generality, assume R_a is a subregion of R₂ and R_b is a subregion of R₄. Consider the section, S^n-1, of Sⁿ by b₂. Let P, P₂, P₄ in S^n-1 be isomorphic to R, R₂, R₄ in Sⁿ, respectively. Since P is divided by two boundaries, isomorphic to b₀ and b₁, it has at least three subregions, two of which are P₂ and P₄, and the third is isomorphic to R₃. Therefore, b₂ divides R₃. By the lemma, there is subregion R_c of R₃ divided by b₂, completing the proof for the case that b₁ divides only one of R₁ or R₂. Next assume b₁ divides R₁ into R₃ and R₄, and b₁ divides R₂ into R₅ and R₆. Assume without loss of generality R_a is a subregion of R₃ and R_b is a subregion of R₆. Consider the section, S^n-1, of Sⁿ by b₂. Let P, P₃, P₆ in S^n-1 be isomorphic to R, R₃, R₆ in Sⁿ, respectively. Since P is divided by two boundaries, isomorphic to b₀ and b₁, it has at least three subregions, two of which are P₃ and P₆, and the third is isomorphic to either R₄ or R₅. Therefore, b₂ divides either R₄ or R₅. Assume without loss of generality that b₂ divides R₄. By the lemma, there is subregion R_c of R₄ divided by b₂, completing the proof.

Simplex Theorem

If b divides the vertex regions of a simplex in linear space, Sⁿ, then Sⁿ 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 Sⁿ to the simplex. Thus, I need only prove the theorem for Sⁿ consisting of a simplex alone. Proceed by induction on the dimension of Sⁿ. 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 V₀, V₁, ..., V_n be vertex regions of Sⁿ opposite the empty region from boundaries b₀, b₁, ..., b_n, respectively. Suppose for proof by contradiction, that V₀, V₁, ..., V_n are divided by b, and the extension by b is linear. For each b_i in {b₁, b₂, ..., b_n}, let R_i be the region of {b₁, b₂, ..., b_n}-{b_i} containing V_i. V₀ is a subregion of R_i because none of {b₁, b₂, ..., b_n}-{b_i} separates V_i from V₀. Since b divides V_i and V₀, and V_i and V₀ are subregions of R_i, the "Intermediate Region Theorem" applies. Thus, b divides a region U_i in R_i between b_i and b₀. Since only b₀ and b_i divide R_i, and the region opposite b_i from V_i is empty, R_i has only three subregions, V_i, V₀, and U_i. Consider S^n-1, the section by b₀ of Sⁿ with b₀ removed. Since S^n-1 has n boundaries, it is a simplex. For each i in {1, 2, ..., n}, let W_i be the vertex region of S^n-1 opposite b_i from the empty region, P_i be the region containing U_i and V_i as subregions, U_ia and U_ib be the subregions of U_i separated by b, V_ia and V_ib be the subregions of V_i separated by b, P_ia be the region with U_ia and V_ia as subregions, and P_ib be the region with U_ib and V_ib as subregions. Since the region opposite b_i from P_i is V₀, and b₀ does not divide V₀, P_i is isomorphic to W_i. Since b₀ divides both P_ia and P_ib, b divides W_i. By the induction assumption, S^n-1 extended by b is not linear. On the other hand, Sⁿ extended by b is linear by assumption. Thus by the "Section Theorem", S^n-1 extended by b is linear. This contradiction completes the proof.

Constructibility

2011-03-15T19:40:00.000-07:00

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 Rⁿ are bounded by linear surfaces, so they are closed and convex.

Independent Boundary Theorem

If Sⁿ extended by b₀ is linear and Sⁿ extended by b₁ is linear, then there exists a linear superspace of Sⁿ extended by b₀ and b₁.

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

First Constructibility Lemma

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

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

Second Constructibility Lemma

If b₀ is a boundary for all of the regions divided by b₁ in a linear space Sⁿ, Sⁿ is isomorphic to linear surfaces in Rⁿ, b₀ is isomorphic to s₀ in Rⁿ, S^n-1 is the section of Sⁿ by b₁, b₀ in S^n-1 is isomorphic to linear subsurface l₀ in s₀, then there exists linear surface s₁ in Rⁿ isomorphic to b₁.

Choose R₀ in Rⁿ isomorphic to some R₀ divided by b₁. Construct s₁ arbitrarily close to s₀, through l₀, dividing R₀. I must show that the isomorphism between Sⁿ and Rⁿ maps the regions divided by b₁ to the regions divided by s₁. Suppose b₁ divides R₁ in Sⁿ isomorphic to R₁ in Rⁿ. By definition of section, R₀ and R₁ in Sⁿ on the same side of b₀ implies R₀ and R₁ in S^n-1 are on the same side of b₀. Let Qⁿ be Sⁿ with b₀ removed. Since b₀ bounds the regions divided by b₁, b₀ and b₁ divide the same regions in Qⁿ. Thus, b₀ in the section by b₁ is isomorphic to b₁ in the section by b₀. Therefore, R₀ and R₁ on the same side of b₀ in b₁ implies R₀ and R₁ are on the same side of b₁ in b₀. Let Pⁿ be Rⁿ with s₀ removed, then Pⁿ is isomorphic to Qⁿ. Thus, R₀ and R₁ on the same side of b₁ in b₀ implies R₀ and R₁ are on the same side of l₀ in s₀. By similarity of triangles, R₀ and R₁ on the same side of l₀ in s₀, R₀ and R₁ on the same side of s₀ in Rⁿ, s₁ arbitrarily close to s₀, and s₁ dividing R₀ implies s₁ divides R₁. A similar argument applies if R₀ and R₁ in Sⁿ are opposite b₀. Therefore, b₁ dividing R₁ implies s₁ divides R₁ isomorphic to R₁, so s₁ is isomorphic to b₁.

Third Constructibility Lemma

If there is no linear surface through regions {R₁, R₂, ...} in Rⁿ, and there is no linear surface tangent to more than n regions in {R₁, R₂, ...}, then there is a subset of n+1 regions {R₃, R₄, ...} from {R₁, R₂, ...} such that there is no linear surface through {R₃, R₄, ...}.

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

Fourth Constructibility Lemma

If there is no linear surface through n+1 regions {R₁, R₂, ...} in Rⁿ, then there is a simplex with {R₁, R₂, ...} in the vertex regions.

Fore each R in {R₁, R₂, ...} choose s through all of {R₁, R₂, ...} except R, closest to R. This is possible because it is always possible to construct a linear surface through n regions in Rⁿ. If s were not tangent to n regions from {R₁, R₂, ...}, there would be a linear surface through the same regions as s, but closer to R. Thus, s is tangent to n regions from {R₁, R₂, ...}. 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 {R₁, R₂, ...}. In this way construct simplex {t₁, t₂, ...} with {R₁, R₂, ...} in the vertex regions.

Constructibility Theorem

If Sⁿ is a linear sidedness space, then there exist non-coincidental linear surfaces in Rⁿ isomorphic to Sⁿ.

If n=1, then construct by choosing boundaries dividing the same regions in R¹ as divided in S¹. This is possible because extensions to S¹ divide nonempty regions. If n>1, proceed by induction on the number of boundaries in Sⁿ. If there are no boundaries in Sⁿ, then the empty set of linear surfaces in Rⁿ is isomorphic. Assume there is a set of non-coincidental linear surfaces isomorphic to every sidedness space with one fewer boundary than Sⁿ. I must prove there is a set of non-coincidental linear surfaces isomorphic to Sⁿ. Assume the contrary. Remove one boundary, b, from Sⁿ. There is a set, {s₁, s₂, ...}, of non-coincidental linear surfaces isomorphic to Sⁿ with b removed. By assumption there is no linear surface dividing the regions, {R₁, R₂, ...}, isomorphic to the regions divided by b. If there exists a linear surface, s, through (tangent or dividing) all of {R₁, R₂, ...}, then by the "First Constructibility Lemma", s is tangent to at least n+1 of {R₁, R₂, ...}. 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 {R₁, R₂, ...}, or there is R in {R₁, R₂, ...} 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 Sⁿ 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 {R₁, R₂, ...} that s does not go through. Since the boundaries of {R₁, R₂, ...} are non-coincidental, no linear surface is tangent to more than n of {R₁, R₂, ...}. By the "Third Constructibility Lemma", there is a subset of n+1 of {R₁, R₂, ...}, say {R₃, R₄, ...}, that no linear surface goes through. By the "Fourth Constructibility Lemma", there is a simplex, say {s₃, s₄, ...} of n+1 linear surfaces with {R₃, R₄, ...} in the vertex regions. By the "only if" part of the "Linearity Theorem", and the "Independent Boundary Theorem", Sⁿ with b removed can be extended by boundaries isomorphic to {s₃, s₄, ...}, to spaces extensible by b. Thus, Sⁿ is extensible by a simplex with b dividing the vertex regions. This violates the "Simplex Theorem", so there is a linear surface, s₀, that together with {s₁, s₂, ...}, are isomorphic to Sⁿ. If {s₀, s₁, s₂, ...} are coincidental, then adjust s₀ by an arbitrarily small amount to find non-coincidental linear surfaces isomorphic to Sⁿ.

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.

Board Game

2010-04-24T16:13:00.000-07:00

The Chess board is divided into 64 regular squares. The Go board is also divided into regular squares. The Hex board is divided into regular hexagons. The Risk board is divided into irregular regions. What if dividing the board into regions was part of the game. Each player could take turns placing points or linear boundaries in a space.

I can imagine more than one possible goal in such a game. The goal could be to have the most regions containing only friendly points. Or, the goal could be to have the most regions with friendly point majorities. The game could be played by two or more people. It could be limited by number of moves or by time. It could be scored at the end, or the score could be averaged over number of moves or time. The game could be played in any number of dimensions. Two dimensions would be significantly easier than three, and four dimensions would be extremely difficult.

This game could only be played on a computer because pencil and paper could not produce precise enough lines. A computer could zoom in on detailed portions of the game space. Larger structures could be represented together with smaller ones by using spherical projection or something. I have no idea how higher dimensional game spaces could be displayed. I think each player would prepare for such a game by writing a program to make the moves understandable.

I would restrict the moves such that no played point lies on a boundary. I would also restrict boundary moves such that no two boundaries are parallel, and no more than n boundaries share a point in an n dimensional game. And, I would restrict point and boundary moves as follows. Taking played points and boundary intersection points as origins, I would restrict point moves and boundary moves such that no set of fewer than n+1 played points and/or boundary intersection points are linearly dependent in an n dimensional game. For example, a move which put 3 played points on the same line, or 2 played points and 2 intersection points on the same plane, would be illegal. One motivation for these restrictions is that moves would not have to be infinitely precise. Moves would have a little wiggle room without affecting the game play. This is important to accommodate rounding errors in the computer. In my opinion, another motivation for these restrictions is that it is more realistic. What are the chances of 3 unrelated points being on the same line in real life?

Counting Linear Regions

2010-02-05T08:40:00.000-08:00

The question "how many" has motivated me in what little math I have done. For example, how many tetrahedron overlaps are there? That led me to the question of how many equivalent linear spaces there are. I used a recursive formula to define linear space in the first entry on this blog. Now I will present the closed form for f(d,b), the number of nonempty regions in a linear space of d dimensions and b boundaries. For example,
f(3,b) = 1 + b + ∑_x=0..b−1x + ∑_y=0..b−1∑_x=0..y−1x
By definition,
f(d,b) =
f(d,b−1) + f(d−1,b−1) =
f(d,b−2) + f(d−1,b−2) + f(d−1,b−1) =
f(d,0) + f(d−1,0) + f(d−1,1) + f(d−1,2) + ... + f(d−1,b−1) =
1 + ∑_x=0..b−1f(d−1,x) =
1 + ∑_y=0..b−1(1+∑_x=0..y−1f(d−2,x)) =
1 + b + ∑_y=0..b−1∑_x=0..y−1f(d−2,x) =
Removing subscripts for brevity,
1 + b + ∑∑f(d−2,x) =
∑⁰1 + ∑¹1 + ∑²(1+∑f(d−3,x)) =
∑⁰1 + ∑¹1 + ∑²1+∑³f(d−3,x) =
∑⁰1 + ∑¹1 + ... + ∑^d−11 + ∑^df(0,x) =
∑⁰ + ∑¹ + ... + ∑^d−1 + ∑^d =
∑_{x>−1,x<d+1,x<b+1}∑^x
I have always liked figurate numbers. For example, the triangular numbers are 1, 3, 6, 10, 15, .... Consider points on a page. Each line has one more point than the last. Then the total number of points is ∑², the triangular number P₂(b−1). Now make a stack of pages with successive triangular numbers on them. The total number of points in the stack is ∑³, the tetrahedral number P₃(b−2). In general, ∑^d is the polytopic number P_d(b−d+1). The diagonals of Pascal's triangle of binomial coefficients are the polytopic numbers. Thus, ∑^d = P_d(b−d+1) = ^(b+1)!/_d!(b−d+1)!, and f(d,b) = ∑_{x>−1,x<d+1,x<b+1}^(b+1)!/_x!(b−x+1)!.

Drawing Abstractions

2008-10-19T12:05:00.000-07:00

This post shall contain observations of interest more to computer programmers than to mathematics enthusiasts.

My work experience is in creating models of hardware designs, and using the models to verify the designs by comparing the outputs of the two in response to various inputs. The difference between the models I write and the designs I verify is that the designs are synthesizable into real hardware. The models I write to verify the synthesizable designs contain more architectural than microarchitectural detail. The difference between architecture and microarchitecture is that the end user of the hardware does not have direct control over or direct access to the microarchitectural details. Corroboration between the model and design is merely anecdotal evidence of the correctness of the design. However, this sort of anecdotal verification is often essential to verify a hardware design.

The program described in the last post is a procedure to find mathematical abstractions. I can think of it as a model of some of the mathematical structures governed by theorems and definitions given in previous posts. Even though I would doubt the correctness of the theorems if I found it impossible to model the intended structures, my goal in modelling the structures is not to verify the theorems. In fact, success in modeling the structures would be only anecdotal support of the theorems. My goal in modeling the structures is to satisfy the curiosity which helped to motivate me to produce the theorems. In that way, I could more easily move on to related topics.

The challenge of modeling mathematical structures differs from the challenge of modeling hardware designs. Hardware designs are more concrete than the mathematical structures I am modeling. I have an intuitive sense of what a portion of the model must do in order to model the corresponding portion of the design. However, in my simplex overlap model, the sidednesses are represented by 1s and 0s, and sometimes I lack intuition as to whether some intermediate 1s and 0s are correct. This intuition about the correctness of intermediate results is essential to debugging a computer program. Other than by direct inspection of and reasoning about the program source code, the only way I know to debug a program is by taking it one step at a time, and checking the results after each step. For me, the direct inspection technique works better when it is used in conjunction with the intermediate result technique.

Often, the intermediate results in my simplex overlap program are the sidedness relations of linear spaces. At least for fewer than 4 dimensions, I do have an intuitive notion of what a linear space is. I can represent such a linear space by a drawing. Thus, to check that a sidedness relation does represent a linear space, I attempt to draw lines and points which satisfy the sidedness relation. Unfortunately, converting the sidedness relation to a drawing requires a lot of trial and error. This leads me to desire a program which could draw the lines and points automatically, given any linear sidedness relation. If the program failed on a particular sidedness relation, when it succeeded in much less time on equally complex sidedness relations, I would suspect that the sidedness relation it failed on was not in fact linear. In that way, I could detect faulty intermediate results in the simplex overlap program.

Another advantage of having drawings of intermediate linear space results in the simplex overlap program is that I could use those drawings to check other intermediate results which are not linear spaces. For example, the inside of a triangle overlap would be obvious from its drawing.

Yet another advantage of a program to convert the sidedness relations of a linear space into a drawing is that when I do find all of the tetrahedron overlaps, then I will be able to more easily publish drawings of them. I suspect the actual drawings will be more inspirational and convincing than a simple count of their number.

Now I will describe the program which converts sidedness relations to drawings. It starts out with random coordinates for the specified number of points and boundaries. The coordinates of a boundary are the coordinates of a point on the boundary, together with the coordinates of a unit normal to the boundary. Given a set of coordinates, the program calculates a score by taking the sum of the signed perpendicular distances of the points from the boundaries. The program attempts to increase this score by randomly changing one coordinate at a time. The program reverts the change if it does not improve the score. As the score improves, the way the coordinates are changed changes from pure random to a sort of Brownian motion.

I wonder whether this program to convert sidedness relations to coordinates would be easier to debug than the simplex overlap program it is intended to help debug. I suspect it would be easier to debug because coordinates are less abstract than sidedness relations. Coordinates are concrete in that they can be displayed on a computer screen in a graphical way. To me, graphics are less abstract than symbols.

Overlap Program Description

2008-08-27T23:45:00.000-07:00

By the Continuity Theorem (see previous posts), the migration operation spans all linear sidedness spaces, starting from any one. Similarly, migrations are sufficient to find all simplex overlaps of a given dimension. I need only check each migration from each overlap found so far, and find if it is equivalent to one found already. To simplify the equivalence check, I will impose an ordering on equivalent sections and remember only the first in order. The program to do this is described in the following.

Start with a single entry list. Finding this initial overlap example is the most difficult part of the program. Create the example overlap by modifying an overlap with one fewer boundary than desired. First choose a boundary. Then choose a boundary in the section by it. In the one dimensional case, choose a region and divide it by a new boundary. In the next dimension up, divide regions by a new boundary close to the chosen one, passing through the new boundary in the previous dimension. Continue up to the original dimension.

One question is whether the above method could be used to find all overlaps without using migrations. This would be less efficient than using migrations as below, because the above method would find all possible sidedness relations. The migration method below finds all overlaps while going through only some of the possible sidedness relations.

Now fill out the list with a representative from each overlap equivalence class. For each overlap in the growing list, for each possible migration, consider the resultant overlap. If the overlap is not equivalent to any on the list, then add it to the end of the list.

Determine equivalence by keeping a list of sections which compare as the least of all permutations and inversions. By definition, the equivalence class is all permutations and inversions. A one to one mapping is a permutation. An inversion is a reversal of all bits in the sidedness relation indexed by a boundary.

First Principles

2008-01-04T22:38:00.000-08:00

This entry shall contain some philosophization. Philosophization, sidedness, get it?

What are some of the advantages and disadvantages of deriving mathematical results from first principles, instead of basing new results on published results? Both techniques are useful. I found it easier to get the information I needed to design a program to count tetrahedron overlaps by assuming points do not lie on lines instead of assuming they always lie on lines as in (widely published) incidence geometry. I do not doubt someone more familiar with incidence geometry would find it easier to use than I do. Both techniques, using first principles and using published results, encourage insight and interrelationships between different parts of mathematics. I already tied sidedness geometry to linear spaces, and I can imagine eventually learning enough about incidence geometry to find how sidedness and incidence geometries relate. The inspiration for trying to relate incidence and sidedness is that they are so obviously similar. So far these are advantages for both the first principle technique and the published result technique.

The difference between first principles and published results is that a hypothetical person who is intelligent, but hitherto illiterate, could understand an argument from first principles, but the same hypothetical person could never understand an argument based on published results. I am much closer to such an hypothetical person than a professional mathematician, so I admit a bias toward first principles. Perhaps the general public is closer to that hypothetical, intelligent but hitherto illiterate, person than a professional mathematician, and for that reason my bias is mitigated. However, I do find myself peculiarly deficient of memory when reason will suffice. For some reason, I associate this peculiarity of mine with creativity. Thus, in my mind, I consider first principles to be more creative than I imagine reasoning from published results would be.

Mathematics is all about abstraction, generality, and precision. That is, start with nothing, end up with everything, and make no mistakes along the way. With credentials like that, why don't we have more mathematicians in the white house? Both creativity and abstraction are, to borrow a phrase from Marvin Minsky, suitcase words, meaning many different things. Since I do not have a superior understanding of the complexities of abstraction, I must rely on my intuition that first principles are similar to abstraction. Since even I was able make a connection from first principles to linear space, I must assume connections to linear space are not the most general. However, my fantasy is that the number of overlaps is always prime. Now that would be a promising path from nothing to everything! As to precision, I draw from personal experience. In my profession, we discourage designers from verifying their own designs; we prefer for the verification to be done by someone else. Similarly, the correctness of my, and presumably other people's, proofs would be assisted by the attention of others. Since results derived from published results are more likely to be reviewed by others, a result from first principles has less chance for such review. While first principles are more abstract than published results, published results are more well reviewed than first principles, so neither has superior advantages.

Overlap Examples

2007-12-31T16:19:00.001-08:00

Here are the 11 triangle overlaps. The top left one differs from the disjoint one by a single migration. I call this kind of migration, where a point jumps across a boundary, a point migration.

Here are three tetrahedron overlaps. The right two differ from the disjoint one by single migrations. The middle one is a point migration since it is a point jumping across a boundary. The rightmost one is a segment migration since it is a segment jumping across another segment.

Tetrahedron Overlaps

2007-12-08T22:55:00.000-08:00

Linear Space Equivalence

Two linear spaces are equivalent iff they are isomorphic to the same finite set of nonparallel noncoincidental linear surfaces. Two finite sets of nonparallel noncoincidental linear surfaces are equivalent iff they are isomorphic to the same linear space. A finite set of nonparallel noncoincidental linear surfaces are said to be equivalent to a linear space iff they are isomorphic.

Migration

In space Sⁿ = (B,P,S,n), regions R₁ and R₂ are neighbors with respect to b₀∈B iff R₁(b) = R₂(b) and R₁(b₀) ≠ R₂(b₀), for b∈B₀, where B = B₀∪{b₀}. In space Sⁿ = (B,P,S,n), region R₂ is the opposite of region R₁ iff for b∈B, R₁(b) ≠ R₂(b) ⇔ R₁ has a nonempty neighbor with respect to b. Two spaces S₁ⁿ = (B,P₁,S,n) and S₂ⁿ = (B,P₂,S,n) are migrations of each other iff for each region R in S₁ⁿ and S₂ⁿ, one or both of the following is true. R is empty in S₁ⁿ ⇔ R is empty in S₂ⁿ. Or, R is empty ⇔ the opposite of R is not empty.

Example

Regions A, B, and C have empty opposites. Region A is the opposite of region E. Region E is the opposite of region D.

Migration Theorem

If S₁ⁿ and S₂ⁿ are migrations of each other then, S₁ⁿ is linear ⇔ S₂ⁿ is linear.

Without loss of generality, assume S₁ⁿ is linear, R is empty in S₂ⁿ,
and its opposite is not empty in S₂ⁿ. Suppose S₃ⁿ is any subspace of S₂ⁿ. If R is not a region of S₃ⁿ, then it is linear because its identical subspace in S₁ⁿ is linear. If R is a region of S₃ⁿ, then so is its opposite, so the number of nonempty regions in S₃ⁿ is unaltered, so it is linear, and the theorem is proved.

Continuity Theorem

There exists continuous L:R→{m linear surfaces in Rⁿ}, such that L(r) is nonparallel and nonconicidental for r ≠ r₀∈R, only if there exist r₁, r₂∈R, and linear spaces S₁ⁿ and S₂ⁿ, such that r₁<r₀<r₂, L(r₁)≡S₁ⁿ, L(r₂)≡S₂ⁿ, and S₁ⁿ and S₂ⁿ are migrations of each other.

As a set of linear surfaces changes continuously, its regions cannot suddenly become empty. Before becoming empty, a region must become infinitesimally small. As a region becomes infinitesimally small, so does its opposite. Thus, as a region becomes empty, its opposite becomes nonempty.

Simplex Overlap

A simplex overlap is two disjoint sets of boundaries, each of which is a simplex. The inside of a simplex overlap Sⁿ = (B,P,S,n) is a space S₁ⁿ = (B,P₁,S,n), such that P₁ is the union of the insides of the simplices. Two simplex overlaps, (M₁,M₂), and (N₁,N₂), where M₁, M₂, N₁, N₂ are the simplices of the overlaps, are equivalent iff there exists one to one mapping g:M₁∪M₂→N₁∪N₂, such that g(M₁) = N_i for some i∈{1,2}, and for each b∈M₁∪M₂ the section of the inside of (M₁,M₂) by b is equivalent to the section of the inside of (N₁,N₂) by g(b). There are 11 equivalence classes of triangle overlap. How many equivalence classes of tetrahedron overlap are there?

Sidedness Geometry

2007-11-11T12:40:00.000-08:00

Linear Space

Take points and boundaries as undefined. Define a sidedness relation S:B×P→{0,1}, where B is a finite set of boundaries and P is a finite set of points. Two points p₀, p₁ are said to be on the same side of a boundary b iff S(b,p₀) = S(b,p₁), and they are said to be opposite b iff S(b,p₀) ≠ S(b,p₁). Define a space as Sⁿ = (B,P,S,n), where S is a sidedness relation on B×P, and integer n>0 is called the dimension of the space. Define a region as R:B→{0,1}. Note that there are 2^m regions in a space with m boundaries. A point p∈P is said to be in region R iff S(b,p) = R(b) for each b∈B. A region is said to be empty iff no points are in it. Define a subspace of Sⁿ = (B,P,S,n) to be S₀ⁿ = (B₀,P,S₀,n) such that B₀⊂B, and S₀(b,p) = S(b,p) for each b∈B₀, and p∈P. A space Sⁿ is said to be linear iff in each subspace the number of nonempty regions is equal to f(n,m), where m is the number of boundaries in the subspace, f(1,m) = m+1, f(n,0) = 1, and f(n+1,m+1) = f(n+1,m)+f(n,m). A sidedness relation S:B×P→{0,1}, where B is a finite set of linear surfaces in Euclidean space Rⁿ and P⊂Rⁿ is a finite set of points not on the surfaces in B, is given by n_b∙(p-p_b)>0, where n_b is a normal to b∈B, p_b is a point on b, and p∈P. A set of n linear surfaces in Rⁿ determines an intersection point. A set of linear surfaces in Rⁿ is associated with a set of intersection points determined by all subsets of n linear surfaces. A finite set of linear surfaces in Rⁿ is noncoincidental iff no two surfaces in it are parallel, no n+1 surfaces in it share a point, and no linear surface goes through more than n intersection points. A space Sⁿ is isomorphic with a finite set of noncoincidental linear surfaces in Rⁿ iff there exist one to one mappings g:B→B, h:P→P, and s_b:{0,1}→{0,1}, such that S(b,p) = s_b(S(g(b),h(p))) for each b∈B and p∈P.

Linear Space Theorem

A finite set of noncoincidental linear surfaces in Rⁿ exists if and only if isomorphic linear space Sⁿ exists.

First I will prove that a finite set of linear surfaces in Rⁿ exists only if isomorphic linear space Sⁿ exists. Each point in R divides one of a finite set of regions spanning R, so the number of regions in R is f(1,m) = m+1, where m is the number of points dividing R. Thus, the "only if" part of the theorem is true for n = 1. There exist any number of points in Rⁿ on either side of a linear surface, so f(n,1) = 2, for all n. Thus, the "only if" part of the theorem is true for m = 1. Suppose the "only if" part of the theorem is true for n < i. Also suppose that if n = i, then the "only if" part of the theorem is true for m < j. I must show that the "only if" part of the theorem is true for n = i and m = j. Let L be a set of j-1 noncoincidental linear surfaces in Rⁱ, and let l be a linear surface in Rⁱ, noncoincidental with L. By supposition, L divides Rⁱ into f(i,j-1) regions. The intersections of l with the surfaces in L are isomorphic with linear surfaces in R^i-1. By supposition, l divides f(i-1,j-1) of the regions formed by L in Rⁱ. Therefore, there are f(i,j-1)+f(i-1,j-1) = f(i,j) regions formed by L∪{l} in Rⁱ, and the "only if" part of the theorem is proved. The "if" part I will prove below after proving some supportive theorems.

Section

A boundary b is said to extend S₀ⁿ = (B₀,P₀,S₀,n) to S₁ⁿ = (B₁,P₁,S₁,n) iff S₀ⁿ is a subspace of S₁ⁿ, and B₁ = B₀∪{b}. If b extends S₀ⁿ = (B₀,P₀,S₀,n) to S₁ⁿ, then b divides region R₀ in S₀ⁿ into regions R_1a and R_1b in S₁ⁿ iff R_1a and R_1b are not empty, R_1a ≠ R_1b, and R_1a(b₀) = R_1b(b₀) = R₀(b₀) for each b₀∈B₀. If b extends S₀ⁿ = (B₀,P₀,S₀,n), then S₁^n-1 is the section of S₀ⁿ by b iff S₁^n-1 is isomorphic with S₁ⁿ = (B₀,P⊂P₀,S₀,n), where p∈P iff p is in a region divided by b.

Section Theorem

If S^n-1 is a section of S₀ⁿ by b, b extends S₀ⁿ to S₁ⁿ, S₀ⁿ is linear, and S₁ⁿ is linear, then S^n-1 is linear.

The number of regions in S^n-1 is the number of regions divided by b. The number of regions divided by b is the number of regions in S₀ⁿ subtracted from the number of regions in S₁ⁿ. Since S₀ⁿ and S₁ⁿ are linear, the number of regions in S^n-1 is f(n,m+1)-f(n,m) = (f(n,m)+f(n-1,m))-f(n,m) = f(n-1,m). The same reasoning applies to each subspace of S^n-1, because each subspace of S^n-1 is the section of a subspace of S₀ⁿ by b. Therefore, S^n-1 is linear.

Antisection Theorem

If S^n-1 is a section of S₀ⁿ by b, b extends S₀ⁿ to S₁ⁿ, S^n-1 is linear, and S₀ⁿ is linear, then S₁ⁿ is linear.

The number of regions in S^n-1 is the number of regions divided by b. The number of regions in S₁ⁿ is the number of regions divided by b added to the number of regions in S₀ⁿ. Since S^n-1 and S₀ⁿ are linear, the number of regions in S₁ⁿ is f(n-1,m)+f(n,m) = f(n,m+1). The same reasoning applies to each subspace of S₁ⁿ, because each subspace of S₁ⁿ is the extension of a subspace of S₀ⁿ by b. Therefore, S₁ⁿ is linear.

Simplex

A simplex in linear space Sⁿ is any n+1 boundaries in Sⁿ. Note that because n linear surfaces are linearly independent in Rⁿ, and the "only if" part of the Linear Space Theorem is true, f(n,n) = 2ⁿ. By definition of linear space, f(1,2) = 2²-1, and if f(n-1,n) = 2ⁿ-1, then f(n,n+1) = f(n,n)+f(n-1,n) = 2ⁿ+2ⁿ-1 = 2ⁿ⁺¹-1, so the number of nonempty regions in a simplex is 2ⁿ⁺¹-1. Consider the empty region of a simplex in space Sⁿ. Reverse any one sidedness of the empty region, and call the resultant region a vertex region of the simplex. Since there are n+1 boundaries in a simplex, there are n+1 vertex regions in it. Reverse all of the sidednesses of the empty region and call the resultant region the inside of the simplex. Since there is only one empty region in a simplex, there is only one inside in it.

Simplex Theorem

There exists no boundary dividing all vertex regions of a simplex.

Suppose there does exist boundary b dividing all n+1 vertex regions of simplex b₁, b₂, ... b_n+1. Consider the section of b₁, b₂, ... b_n by b. That section is a simplex with vertices sectioned from the vertices opposite b₁, b₂, ... b_n. Since the vertex region opposite b_n+1 is opposite one of b₁, b₂, ... b_n from each of the sectioned vertex regions, it is not sectioned to any one region of the sectioned simplex. This contradicts the supposition of b, so no such b exists, and the theorem is proved.

Independent Boundary Theorem

If Sⁿ extended by b₀ is linear, and Sⁿ extended by b₁ is linear, then there exists a linear superspace of Sⁿ extended by b₀ and Sⁿ extended by b₁.

(This proof attempt is wrong. I am working on a correction.) For S¹ it is true because b₀ and b₁ divide different regions, so points on one or the other side of b₀ in the region it divides will all be on one side of b₁. Suppose it is true for S^n-1. I must prove it for Sⁿ. Suppose Sⁿ is not linear if it is extended by both b₀ and b₁ together, but Sⁿ is linear if it is extended by b₀ or b₁ individually. Discard boundaries from Sⁿ until the reduced Sⁿ is linear when extended by both b₀ and b₁. This is possible because b₀ and b₁ alone in Sⁿ is a linear space. Let b₂ be the last boundary discarded from Sⁿ. Consider the section by b₂, S^n-1. By the Section Theorem, S^n-1 is linear because Sⁿ is linear and Sⁿ extended by b₂ is linear. Similarly, S^n-1 extended by the section of b₀, or by the section of b₁, is linear. Thus, by supposition, S^n-1 extended by the sections of both b₀ and b₁ is linear. By the Antisection Theorem, since Sⁿ extended by b₀ and b₁ is linear, and S^n-1 extended by the sections of b₀ and b₁ is linear, Sⁿ extended by b₀, b₁, and b₂ is linear. This contradicts the supposition, so the theorem is proved.

"If" Part of Linear Space Theorem

If linear space Sⁿ exists, then a finite set of linear surfaces in Rⁿ isomorphic with Sⁿ exist.

(This proof attempt, in particular the struckout text, is wrong. I am working on a correction.) Suppose no R₀ⁿ exits with boundaries and sidednesses isomorphic to some linear space S₀ⁿ. Let S₁ⁿ be boundaries of S₀ⁿ which are isomorphic with the boundaries and sidednesses of some R₁ⁿ. Until impossible, extend S₁ⁿ by boundaries from S₀ⁿ such that S₁ⁿ is still isomorphic with an extension of R₁ⁿ. By supposition, there exists boundary b₀ in S₀ⁿ such that b₀ is not in S₁ⁿ. Let R₁, R₂, ... R_n+1 be the n+1 regions of S₁ⁿ divided by b₀ such that no b₀ exists which divides those regions in R₁ⁿ. Let p₁ and q₁ be in R₁, opposite b₀, and similarly for (p₂,q₂), ... (p_n+1,q_n+1). Construct b₁, b₂, ... b_n+1 such that p₁ and q₁ are in one vertex region of the simplex formed by b₁, b₂, ... b_n+1, and (p₂,q₂), ... (p_n+1,q_n+1) are in the other vertex regions. The prior construction is possible because, given n+1 points in Rⁿ a simplex can be constructed with those points as vertices; a point can be chosen in each of R₁, R₂, ... R_n+1; the vertex region of each point at least partially overlaps the region the point is in; and without loss of generality, we may assume p_i and q_i are in the portion of R_i which overlaps the vertex region. Extend R₁ⁿ by b₁, b₂, ... b_n+1 to R₂ⁿ. Since R₂ⁿ obeys the "only if" part of the Linear Space Theorem, S₁ⁿ can be similarly extended to S₂ⁿ such that S₂ⁿ is isomorphic to R₂ⁿ. Since S₁ⁿ can be extended by b₀, and b₀ divides different regions from b₁, b₂, ... b_n+1, S₂ⁿ can be extended by b₀ to S₃ⁿ because of the Independent Boundary Theorem. Now, b₀ goes through each of the vertex regions of b₁, b₂, ... b_n+1 in S₃ⁿ. This violates the Simplex Theorem. Therefore the supposition was false, and there does exist R₀ⁿ with boundaries and sidednesses isomorphic with S₀ⁿ.