Balanced Incomplete Block Designs, Difference Sets, Klein's Quartic Curve, Projective Planes, and lots more!

I've been busy lately and unable to provide the answer for the Extreme Programming Code Review problem posted last time. I chose this problem, because when I was taking a graduate combinatorics class in college, the underlying problem had an almost mystic relation to a large number of other areas of combinatorics and geometry, as well as producing a simple, but beautiful and symmetric structure.

Mathematical history has many examples of similar, but harder arrangement problems. Catherine The Great supposedly kicked things off by posing to Euler, The 36 Officers Problem. Later, Kirkman proposed the 15 schoolgirl problem (my oh my, a Reverend and thoughts of schoolgirls eh?). These seemingly simple problems acted as a catalyst and resulted in great advances in the field of combinatorics, which has enormous applications in many fields. One application of course, is solving the problem I posed.

The problem says, given 7 people, arrange them into 7 teams of 3 each, such that no two people are ever on the same team twice. It is probably possible to construct this design using trial and error, but there are many other ways to do it.

Let us number the programmers 0 through 6, and start off with the team {0,1,3}. If we were to add 1 to each number, it is easy to see that the new team will consist of 3 new members, no two of which are in the first team. {1,2,4} And likewise, the same will be true for each new team, for all teams {x+0, x+1, x+3} up to x=0 to 6. The first two positions will always differ by 1, the second and third by 2, and the first and third by 3. If you read down the three columns, we're just rewritten the numbers 0 through 6 shifted by 1 or 2 places. Here's our list of teams, you can also verify them by visual inspection.

{0,1,3}
{1,2,4}
{2,3,5}
{3,4,6}
{4,5,0}
{5,6,1}
{6,7,2}

It turns out that this solution is also unique except for permuting order.

Combinatorics describes this as a t-(v,k,l) design. A t-(v,k,l) design is a set P of v points, a set of subsets of P called blocks (also called lines) B containing k points, and an incidence structure I in P * B which describes the relation of P and B (which elements of P are in which blocks). For any t points, exactly l blocks are incident.

Our problem says that there are p=7 points, and it says that for any t=2 points, they are contained in only l=1 block (team), and the blocks consist of k=3 points. Therefore, our problem is to construct a 2-(7,3,1) design. Such 2-designs are called Steiner Triple Systems and denoted STS(7). One result of combinatorics is that STS(v) exists if and only if v = 1 or 3 (mod 6).

So what's so special about this problem to get so worked up about? It turns out there are many connections with STS(7) and other areas of mathematics, in addition to which I mentioned in the header, there are also connections to coding theory, latin squares, octonions, simple groups, and geometry.

And now I will show you how this problem is connected to the Balsa Wood problem, as well as to very beautiful geometry.

Recall that there are 7 teams of 3-programmers, 7 programmers, no two programmers are on the same team twice. Remember back to the defination of a 2-(7,3,1) design, the programmers are called "points" and the teams are called "lines". If no two programmers are on the same team twice, that means 2 programmers (or points) uniquely determine a line, and also, that at most, two teams can only have 1 programmer in common, which says that any two lines intersect at one and only 1 point. Hmm...

• 7 points
• 7 lines
• 2 points determine a line
• 2 lines determine a point

What would happen if we wrote down those 7 programmers and connected the dots according to teams?



We form what's called a projective plane. This plane, the projective plane of order 2 called the Fano Plane has the interesting property that there are no parallel lines. It also has a 168-fold symmetry. (another interesting property, since each line has 3 points as well as each point is incident with 3 lines, you can interchange points and lines to no effect! The Fano Plane is its own dual.)

How can we use this to solve the Balsa Wood problem? I will give a partial solution, by showing the solution for 3 successive writes.

• if you are writing X and the ram is already in state X, do nothing
  
• if the ram is empty, and you're writing I, then place a 1 in bit position I
• if the ram contains 1 bit in position I and you are writing the number J, find a line (I,J,K) and place a 1 in bit position K
• if the ram contains 2 bits in positions I, K, and you are writing value X, write 2 more bits such that 3 of the bits will be colinear on a line, and X will be a point NOT on that line. That is, if X != I or != K, then find the line (I,J,K) and place a 1 bit in position J, as well as in position X. If X == I then write two bits on the other line containing K, and if X == K, then write two bits on the other line containing I.

Step 2 and 3 work because of the inherent property of projective planes. Step 2 works because 2 points uniquely determine a line. Step 3 works, because no matter what, there are three lines intersecting any point colinear with X, therefore, you can always place 2 1-bits on one of those lines.

The rules for reading are as follows:

• if the memory is blank, nothing has been written yet
• if exactly one bit is written in position I, then the value in the memory is I
• if exactly two bits are written in position I and K, then the value in the memory is J, where J is on the line containing I and K
• if exactly 4 bits are written in positions X, I, J, K, find the 3 positions which form a colinear line, the one which is "left out" by itself is the value in the memory.

I leave the construction of the final rule for writing and reading, as well as an argument as to its correctness to the reader. There is an alternate solution to this problem by using womcode techniques, which have applications to both error correcting codes and cryptography. Sadly, Rivest and Shamir seemed to have patented it, and the solution to the Balsa Wood problem actually violates the patent.

Another related problem to look up is the Transylvanian Lottery Problem, also solved with the Fano Plane.


-Ray