A plane in a list of numbers

A projective plane of order $n$ has $n^2+n+1$ points, the same number of lines, and $n+1$ points on each line. For $n = 3$ that is thirteen points, thirteen lines and four points a line — fifty-two statements of the form this point is on that line, all of which have to be consistent with two axioms.

Writing it out is a small chore. Writing it down is four numbers.

That the differences are distinct is the whole construction. Everything else follows from it in one line, and the line is worth having because it explains why difference is the operative word.

Why distinct differences give a plane #

Take a list $D$ of $n+1$ residues modulo $n^2+n+1$ whose $(n+1)n$ ordered differences are the non-zero residues, each exactly once. Such a list is a perfect difference set.

The points are the residues. The lines are the shifts $D + s$, one for each $s$.

Two points lie on exactly one line. Points $p$ and $q$ lie on the shift $D + s$ exactly when $p - s$ and $q - s$ are both in $D$ — that is, when $p - q$ is a difference of two members of $D$, with $s$ determined by which two. Since $p - q$ occurs as a difference exactly once, there is exactly one such pair and exactly one such $s$.

Two lines meet in exactly one point. By the same argument run backwards: shifts $D+s$ and $D+t$ share a point exactly when $s - t$ is a difference, which happens once.

That is the whole proof, and both halves are the difference condition read in the two directions. The plane’s two axioms are one arithmetic statement, and the symmetry between points and lines — which the seven-point plane has to state twice — is here a consequence of subtraction being antisymmetric.

The counting that forces the size #

The parameters are not free, and the arithmetic that fixes them is worth doing because it is the same count the schedule question runs.

A list of $k$ residues has $k(k-1)$ ordered differences. If those are to be the non-zero residues modulo $v$ exactly once, then $v - 1 = k(k-1)$, so $v = k^2 - k + 1$. Writing $k = n+1$ gives $v = n^2 + n + 1$ — the plane’s point count, forced by the difference condition alone.

So the size of the plane is a consequence of asking for distinct differences, not an input. That is the sense in which the construction is a compression rather than an encoding: the four numbers do not merely describe the plane of order three, they determine that it is the plane of order three.

What a difference set is not #

Three things are easy to assume about the list and none of them is true, and clearing them up is the fastest way to see what the condition actually constrains.

It is not unique. The plane of order three has other base blocks — $\{0, 1, 3, 9\}$ is one, and multiplying every member by a number coprime to thirteen gives another, usually different as a set. Multiplying by $3$ gives $\{0, 3, 9, 27\} = \{0, 3, 9, 1\}$, which is the same set; multiplying by $2$ gives $\{0, 2, 6, 5\}$, which is a genuinely different base block generating the same plane. The plane is the object and the list is a description of it, and several lists describe one plane.

It is not an ordering. The four numbers are a set; the order they are written in carries nothing, and the closed path in the figure is drawn only so that the set is visible.

And the shifts are not a labelling of anything geometric. Point $0$ and point $1$ are adjacent on the ring and have no special relationship in the plane; the ring is a picture of the cyclic group the construction uses, and the plane has no notion of one point being near another. A reader who takes the circle as geometry has taken the scaffolding for the building — which is the same caution the Fano plane’s usual drawing earns from the other direction, where one of its lines has to be bent into a circle and the bend means nothing either.

Where the lists come from #

The construction is only as good as the supply of difference sets, and the supply has one source.

Singer’s theorem, 1938. For every prime power $q$, a perfect difference set of size $q+1$ modulo $q^2+q+1$ exists.

The reason is a group action. The projective plane over the field with $q$ elements has $q^2+q+1$ points, and the multiplicative group of the field with $q^3$ elements acts on them — a field of $q^3$ elements is a three-dimensional space over the field of $q$ elements, its non-zero elements fall into $q^2+q+1$ classes under scaling, and those classes are the plane’s points. That a field of $q^3$ elements exists for every prime power is the fact the whole construction rests on, and it is the reason prime powers are where the planes are. Multiplication by a generator of the larger field’s multiplicative group permutes those classes in a single cycle of length $q^2+q+1$.

So the plane has a symmetry that cycles all its points, and a line under that symmetry becomes the shifts of one line. Reading the cycle’s positions as residues turns that line into a difference set.

That is the whole of it, and it says exactly where the construction’s limits are. Every known projective plane of order $n$ has $n$ a prime power, and the difference sets follow the same restriction — so the compression is available exactly where a plane is known to exist at all, and it produces nothing new.

What the compression does and does not settle #

It is worth separating three questions that look similar.

Storage. A plane of order $n$ has about $n^3$ incidences and a difference set has $n+1$ numbers. That is the same economy a generator’s parameters have against the pictures it draws: the rule is smaller than what it produces, and shifting is the rule. That is a genuine compression by a factor of $n^2$, and it is used: a design needed inside a computation is generated from its base block rather than stored.

Existence. A difference set gives a plane, and the converse is false. A plane whose points cannot be cycled by a single symmetry has no difference set, and such planes exist — several of the planes of order nine and sixteen are not cyclic. So the construction produces some planes and not all of them, and what it settles is a sufficient condition.

Non-existence. This is where the compression genuinely pays, and it is the reason difference sets are searched for. Deciding whether a plane of order $n$ exists is a search over $n^3$ incidences; deciding whether a cyclic one exists is a search over lists of $n+1$ residues. The second search is enormously smaller and has been run much further — cyclic planes have been ruled out for every non-prime-power order up to two thousand, while planes in general are only settled up to ten.

That gap is the honest summary. The compression converts an infeasible search into a feasible one at the cost of answering a weaker question, and the weaker answer is what almost all the computational evidence about projective planes actually is.

The ruled-out orders, and what rules them out #

Two obstructions apply and neither comes from the difference condition.

Bruck–Ryser. If a plane of order $n$ exists and $n \equiv 1$ or $2 \pmod 4$, then $n$ is a sum of two squares — so no plane of order $6$, $14$, $21$, $22$. That is the determinant argument pushed into a statement about quadratic forms, and it reaches the same two-square condition that belongs to the number theory here.

Exhaustive search, once. Order ten satisfies Bruck–Ryser — $10 = 1 + 9$ — and no plane exists, which was settled in 1989 by a computation of several thousand hours using the plane’s putative error-correcting code to prune. Nobody has repeated anything like it, and order twelve is open.

So the state of knowledge is: every plane anybody has is of prime-power order, no general reason is known why, one non-prime-power order has been ruled out by a congruence and one by brute force, and the next open case is twelve. The difference-set construction sits entirely on the positive side of that and contributes nothing to the negative side, which is the usual division of labour between a construction and an obstruction.

The same idea elsewhere #

A difference set is a specific case of a general pattern — a small object whose differences are controlled — and the pattern recurs wherever a structure is wanted with even coverage.

The Fano plane, from a field. The construction of the seven-point plane out of the two-element field and its construction from $\{0,1,3\}$ produce the same object, and Singer’s theorem is the statement that the two always agree. One description is algebraic and one is arithmetic, and the bridge between them is a symmetry that neither mentions.

Perfect rulers and sparse rulers. A Golomb ruler is a set of marks whose pairwise differences are all distinct; a perfect difference set is that condition made exactly tight modulo $v$. Rulers are used to place radio-telescope antennas so that every baseline length is measured once.

Sonar and radar arrays. A set of sensor positions whose pairwise separations are all distinct measures every separation exactly once, which is the same optimisation and is why some interferometer layouts are built from difference sets rather than from even spacing.

Optical orthogonal codes and frequency hopping. A sequence of frequencies whose shifts collide with themselves in at most one place is a difference set’s condition relaxed, and the same constructions supply them.

And the de Bruijn cycle. A cyclic sequence containing every word of a length exactly once is the same kind of object with substrings in place of differences — one short thing whose shifts cover everything without repetition, generated by a walk rather than by an addition.

The common shape is worth naming: a small set whose translates tile or cover a large one, with the covering exactly once. That condition is rigid enough to force the sizes, which is why all these objects come in restricted parameter families.

Running the construction by hand #

The plane of order three is small enough to build completely, and building it once shows what the shifts are doing.

The base block is $\{0, 1, 3, 9\}$ modulo thirteen. Its six positive differences are

$$1-0 = 1, \quad 3-1 = 2, \quad 3-0 = 3, \quad 9-3 = 6, \quad 9-1 = 8, \quad 9-0 = 9,$$

and the six negatives of those are $12, 11, 10, 7, 5, 4$. Together that is $1$ through $12$, each exactly once.

The thirteen lines are the shifts: $\{0,1,3,9\}$, $\{1,2,4,10\}$, $\{2,3,5,11\}$, and so on round to $\{12,0,2,8\}$.

Which line holds the points $2$ and $7$? Their difference is $7 - 2 = 5$, and $5$ appears in the difference list exactly once, as $1 - 9$. So the line must carry $7$ where the base block carries $1$, which means the shift is $s = 7 - 1 = 6$. The line is $\{0,1,3,9\} + 6 = \{6, 7, 9, 2\}$, and it holds both.

And there is no second one, because $5$ occurred once. That is the whole uniqueness argument, done on one pair.

Which point do the lines $\{0,1,3,9\}$ and $\{2,3,5,11\}$ share? The shifts differ by $2$, which appears once as $3 - 1$. So the shared point is $3$ in the first and $1 + 2 = 3$ in the second — the same point, and only that one.

The argument is a sentence and the arithmetic is fiddly, which is the whole reason the figures check every pair rather than exhibiting one. Following a single pair by hand is evidence; seventy-eight pairs of points and seventy-eight pairs of lines, verified each time the picture is drawn, is the claim.

A circle that is not geometry #

The ring is a picture of a cyclic group and not of a plane. The points sit on a circle because the construction cycles them, and nothing about their positions means anything geometrically — two points next to each other on the ring are no more related than any other pair, which is the opposite of what a circle usually conveys.

The base block is drawn as a closed path and it is not one. The four points $0, 1, 3, 9$ are a line of the plane, and a line is a set rather than a circuit; the path is drawn to make the set visible and its edges have no meaning at all.

The checks are exhaustive at these sizes only. Every pair of points and every pair of lines is verified for the three planes drawn, which is complete for those and says nothing about Singer’s theorem, which is a statement about every prime power.

And the figure shows a plane that exists. Everything hard about this subject is on the other side — the orders where no plane is known — and there is no figure of an absent plane. What a figure of order six would have to show is a search failing, which is a picture of nothing happening for a long time.

The compression is not visible either. The point of the construction is that four numbers carry fifty-two incidences, and the figure draws all thirteen shifts side by side, which is the expansion rather than the compression. A drawing of the four numbers alone would be four numbers, and would look like nothing at all — which is, in a sense, the honest picture of what a base block is.

Still open here: why prime powers, and nothing else #

The question this whole anchor sits under is the oldest open one in the area and it is easy to state.

Is there a projective plane whose order is not a prime power? Every known plane has prime-power order; the only general obstruction is Bruck–Ryser, which rules out about half the non-prime-power orders and is silent about the rest; and one further order, ten, has been eliminated by a computation nobody wants to repeat.

The difference-set version is sharper and equally open: is there a cyclic plane of non-prime-power order? That has been checked to two thousand and there is a conjecture, due to Hall, that the answer is no. Neither question has a method behind it, which is why the evidence is a search.

The other direction is about how much a plane can be compressed below a difference set. A plane of order $n$ needs $n+1$ residues to generate it this way; whether a shorter description exists — some other symmetry with a smaller fundamental domain — is not a question with a general answer, and the planes with the largest symmetry groups are exactly the ones this construction produces.

A structure, and the least that determines it #

The habit is about looking for the smallest thing a structure is generated by.

The plane of order three is fifty-two incidences and four numbers. The compression works because the object has a symmetry that acts transitively on its points, so one line and the symmetry generate everything — and finding that symmetry is the whole of the work, done once by Singer for all prime powers.

Where an object has a transitive symmetry, its description collapses to one orbit representative plus the group, and the search space for such objects collapses with it. That is why the negative results about planes are nearly all about cyclic ones: a search that is hopeless over incidences becomes routine over base blocks.

The price is stated in the section above and is worth repeating, because the compression is seductive. A search over the compressed descriptions answers a question about the compressed objects, and whether that is the question wanted depends entirely on whether every object has a compression — which here, demonstrably, it does not.