Sunday, October 19, 2008

Drawing Abstractions

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.

Wednesday, August 27, 2008

Overlap Program Description

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.

Friday, January 4, 2008

First Principles

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.