neverendingbooks

A projective plain (plane) of order ten

Published September 19, 2023 by lieven

A projective plane of order $n$ is a collection of $n^2+n+1$ lines and $n^2+n+1$ points satisfying:

every line contains exactly $n+1$ points
every point lies on exactly $n+1$ lines
any two distinct lines meet at exactly one point
any two distinct points lie on exactly one line

Clearly, if $q=p^k$ is a pure prime power, then the projective plane over $\mathbb{F}_q$, $\mathbb{P}^2(\mathbb{F}_q)$ (that is, all nonzero triples of elements from the finite field $\mathbb{F}_q$ up to simultaneous multiplication with a non-zero element from $\mathbb{F}_q$) is a projective plane of order $q$.

The easiest example being $\mathbb{P}^2(\mathbb{F}_2)$ consisting of seven points and lines

But, there are others. A triangle is a projective plane of order $1$, which is not of the above form, unless you believe in the field with one element $\mathbb{F}_1$…

And, apart from $\mathbb{P}^2(\mathbb{F}_{3^2})$, there are three other, non-isomorphic, projective planes of order $9$.

It is clear then that for all $n < 10$, except perhaps $n=6$, a projective plane of order $n$ exists.

In 1938, Raj Chandra Bose showed that there is no plane of order $6$ as there cannot be $5$ mutually orthogonal Latin squares of order $6$, when even the problem of two orthogonal squares of order $6$ (see Euler’s problem of the $36$ officers) is impossible.

Yeah yeah Bob, I know it has a quantum solution.

Anyway by May 1977, when Lenstra’s Festschrift ‘Een pak met een korte broek’ (a suit with shorts) was published, the existence of a projective plane of order $10$ was still wide open.

That’s when Andrew Odlyzko (probably known best for his numerical work on the Riemann zeta function) and Neil Sloane (probably best known as the creator of the On-Line Encyclopedia of Integer Sequences) joined forces to publish in Lenstra’s festschrift a note claiming (jokingly) the existence of a projective plane of order ten, as they were able to find a finite field of ten elements.

Here’s a transcript:

A PROJECTIVE PLAIN OF ORDER TEN

A. M. Odlyzko and N.J.A. Sloane

This note settles in the affirmative the notorious question of the existence of a projective plain of order ten.

It is well-known that if a finite field $F$ is given containing $n$ elements, then the projective plain of order $n$ can be immediately constructed (see M. Hall Jr., Combinatorial Theory, Blaisdell, Waltham, Mass. 1967 and D.R. Hughes and F.C. Piper, Projective Planes, Springer-Verlag, N.Y., 1970).

For example, the points of the plane are represented by the nonzero triples $(\alpha,\beta,\gamma)$ of elements of $F$, with the convention that $(\alpha,\beta,\gamma)$ and $(r\alpha, r\beta, r\gamma)$ represent the same point, for all nonzero $r \in F$.

Furthermore this plain even has the desirable property that Desargues’ theorem holds there.

What makes this note possible is our recent discovery of a field containing exactly ten elements: we call it the digital field.

We first show that this field exists, and then give a childishly simple construction which the reader can easily verify.

The Existence Proof

Since every real number can be written in the decimal system we conclude that

\[
\mathbb{R} = GF(10^{\omega}) \]

Now $\omega = 1.\omega$, so $1$ divides $\omega$. Therefore by a standard theorem from field theory (e.g. B. L. van der Waerden, Modern Algebra, Ungar, N.Y., 1953, 2nd edition, Volume 1, p. 117) $\mathbb{R}$ contains a subfield $GF(10)$. This completes the proof.

The Construction

The elements of this digital field are shown in Fig. 1.

They are labelled $Left_1, Left_2, \dots, Left_5, Right_1, \dots, Right_5$ in the natural ordering (reading from left to right).

Addition is performed by counting, again in the natural way. An example is shown in Fig. 2, and for further details the reader can consult any kindergarten student.

In all digital systems the rules for multiplication can be written down immediately once addition has been defined; for example $2 \times n = n+n$. The reader will easily verify the rest of the details.

Since this field plainly contains ten elements (see Fig. 1) we conclude that there is a projective plain of order ten.

So far, the transcript.

More seriously now, the non-existence of a projective plane of order ten was only established in 1988, heavily depending on computer-calculations. A nice account is given in

C. M. H. Lam, “The Search for a Finite Projective Plane of Order 10”.

Now that recent iPhones nearly have the computing powers of former Cray’s, one might hope for easier proofs.

Fortunately, such a proof now exists, see A SAT-based Resolution of Lam’s Problem by Curtis Bright, Kevin K. H. Cheung, Brett Stevens, Ilias Kotsireas, Vijay Ganesh

David Roberts, aka the HigherGeometer, did a nice post on this
No order-10 projective planes via SAT.

Comments closed

A suit with shorts

Published September 18, 2023 by lieven

I’m retiring in two weeks so I’m cleaning out my office.

So far, I got rid of almost all paper-work and have split my book-collection in two: the books I want to take with me, and those anyone can grab away.

Here’s the second batch (math/computer books in the middle, popular science to the right, thrillers to the left).

If you’re interested in some of these books (click for a larger image, if you want to zoom in) and are willing to pay the postage, leave a comment and I’ll try to send them if they survive the current ‘take-away’ phase.

Here are two books I definitely want to keep. On the left, an original mimeographed version of Mumford’s ‘Red Book’.

On the right, ‘Een pak met een korte broek’ (‘A suit with shorts’), a collection of papers by family and friends, presented to Hendrik Lenstra on the occasion of the defence of his Ph.D. thesis on Euclidean number-fields, May 18th 1977.

If the title intrigues you, a photo of young Hendrik in suit and shorts is included.

This collection includes hilarious ‘papers’ by famous people including

‘A headache-causing problem’ by Conway (J.H.), Paterson (M.S.), and Moscow (U.S.S.R.)
‘A projective plain of order ten’ by A.M. Odlyzko and N.J.A. Sloane
‘La chasse aux anneaux principaux non-Euclidiens dans l’enseignement’ by Pierre Samuel
‘On time-like theorems’ by Michiel Hazewinkel
‘She loves me, she loves me not’ by Richard K. Guy
‘Theta invariants for affine root systems’ by E.J.N. Looijenga
‘The prime of primes’ by F. Lenstra and A.J. Oort
(and many more, most of them in Dutch)

Perhaps I can do a couple of posts on some of these papers. It might break this clean-up routine.

One Comment

the L-game

Published September 17, 2023 by lieven

In 1982, the BBC ran a series of 10 weekly programmes entitled de Bono’s Thinking Course. In the book accompanying the series Edward de Bono recalls the origin of his ‘L-Game’:

Many years ago I was sitting next to the famous mathematician, Professor Littlewood, at dinner in Trinity College. We were talking about getting computers to play chess. We agreed that chess was difficult because of the large number of pieces and different moves. It seemed an interesting challenge to design a game that was as simple as possible and yet could be played with a degree of skill.

As a result of that challenge I designed the ‘L-Game’, in which each player has only one piece (the L-shape piece). In turn he moves this to any new vacant position (lifting up, turning over, moving across the board to a vacant position, etc.). After moving his L-piece he can – if he wishes – move either one of the small neutral pieces to any new position. The object of the game is to block your opponent’s L-shape so that no move is open to it.

It is a pleasant exercise in symmetry to calculate the number of possible L-game positions.

The $4 \times 4$ grid has $8$ symmetries, making up the dihedral group $D_8$: $4$ rotations and $4$ reflections.

An L-piece breaks all these symmetries, that is, it changes in form under each of these eight operations. That is, using the symmetries of the $4 \times 4$-grid we can put one of the L-pieces (say the Red one) on the grid as a genuine L, and there are exactly 6 possibilities to do so.

For each of these six positions one can then determine the number of possible placings of the Blue L-piece. This is best done separately for each of the 8 different shapes of that L-piece.

Here are the numbers when the red L is placed in the left bottom corner:

In total there are thus 24 possibilities to place the Blue L-piece in that case. We can repeat the same procedure for the remaining Red L-positions. Here are the number of possibilities for Blue in each case:

That is, there are 82 possibilities to place the two L-pieces if the Red one stands as a genuine L on the board.

But then, the L-game has exactly $18368 = 8 \times 82 \times 28$ different positions, where the factor

$8$ gives the number of symmetries of the square $4 \times 4$ grid.
Using these symmetries we can put the Red L-piece on the grid as a genuine $L$ and we just saw that this leaves $82$ possibilities for the Blue L-piece.
This leaves $8$ empty squares and so $28 = \binom{8}{2}$ different choices to place the remaining two neutral pieces.

The $2296 = 82 \times 28$ positions in which the red L-piece is placed as a genuine L can then be analysed by computer and the outcome is summarised in Winning Ways 2 pages 384-386 (with extras on pages 408-409).

Of the $2296$ positions only $29$ are $\mathcal{P}$-positions, meaning that the next player (Red) will loose. Here are these winning positions for Blue

Here, neutral piece(s) should be put on the yellow square(s). A (potential) remaining neutral piece should be placed on one of the coloured squares. The different colours indicate the remoteness of the $\mathcal{P}$-position:

Pink means remoteness $0$, that is, Red has no move whatsoever, so mate in $0$.
Orange means remoteness $2$: Red still has a move, but will be mated after Blue’s next move.
Purple stands for remoteness $4$, that is, Blue mates Red in $4$ moves, Red starting.
Violet means remoteness $6$, so Blue has a mate in $6$ with Red starting
Olive stands for remoteness $8$: Blue mates within eight moves.

Memorising these gives you a method to spot winning opportunities. After Red’s move image a board symmetry such that Red’s piece is a genuine L, check whether you can place your Blue piece and one of the yellow pieces to obtain one of the 29 $\mathcal{P}$-positions, and apply the reverse symmetry to place your piece.

If you don’t know this, you can run into trouble very quickly. From the starting position, Red has five options to place his L-piece before moving one of the two yellow counters.

All possible positions of the first option loose immediately.

For example in positions $a,b,c,d,f$ and $l$, Blue wins by playing

Here’s my first attempt at an opening repertoire for the L-game. Question mark means immediate loss, question mark with a number means mate after that number of moves, x means your opponent plays a sensible strategy.