Math Games

The Fano Plane

Ed Pegg Jr., May 30, 2006

At a convention a few years ago, the Social Golfer Problem came up in a dinner conversation. Some number of golfers desire to golf in foursomes over a period of weeks, without any two people being in the same foursome twice. The Fano Plane was mentioned as one particular projective plane, and one of the non-math people at the table asked what the Fano plane was. I started sketching one on a napkin.

"I have a Fano Plane," said someone else. "I've been carrying it around with me for 17 years." Sure enough, he pulled out a Fano plane, and I felt outdone as he explained the significance to the people at the table. Since then, I've been seeing Fano planes everywhere.


Figure 1. The Fano Plane, and a Switching network

One application is switching networks. These are the devices that can connect any phone to any other phone. Suppose a switch can only connect up to three numbers, and seven numbers need to be connected. How many switches are required so that any number can call up any other number? By considering the lines of the Fano plane, a solution is obtained. This is the {1,2,4} 3-switching network. All of the switches are found by adding 0 to 6, mod 7. A fun task is to find the 13 4-switches that can connect 13 numbers. The 21 switches for a 5-switching network connecting 21 numbers is described by {1,2,5,15,17}. For 31 6-switches connecting 31 numbers, {1, 2, 4, 9, 13, 19} works. More cyclic switches are described at the La Jolla Difference Set Repository. Here's a partial glimpse at an 8-switch for 57 numbers. The red lines would all be one switch connecting 8 numbers, {1, 2, 4, 14, 33, 37, 44, 53}.


Figure 2. A cyclic 8-switch {1, 2, 4, 14, 33, 37, 44, 53}

One thing in the Fano plane that bothered me for years (for years, I say) is that it had a circle - and it was described as a line. For me, a line was a straight line, and I didn't trust curved or wriggly lines. This distrust kept me away from understanding projective planes, designs, and finite geometries for a awhile (for years). Recently, I just accepted the axioms, and my distrust vanished.

  1. Two distinct points are contained in a unique line.
  2. Two nonparallel lines intersect in a unique point.
  3. There exists four points such that no three are on the same line.
  4. In a projective plane, there are no parallel lines. A projective plane of order n has n2 + n + 1 points and lines, with n+1 points on each line, and n+1 lines on each point.
  5. In an affine plane, given a line l and a point p not on l, there exists exactly one line through p that is parallel to l. An affine plane of order n has n2 points and n2 + n lines, with n points on each line, and n + 1 lines on each point.
  6. In a finite geometry, there are a finite number of points. If the points are on a plane, the geometry is either affine or projective.
  7. In a configuration, there are k points on each line and r lines through each point.

Here is a more complicated projective plane. The small circles are the points, and the wriggly objects of a single color are the lines. The lines seem to intersect in lots of places, but the intersections only count at the points. With that caveat, you can see that any two points are on a unique line, and that any two lines intersect at a unique point. Each of the 21 points is on exactly 5 lines, and every one of the 21 lines goes through 5 points. This is an order 4 projective plane, as well as a (5,5) configuration.


Figure 3. An order 4 projective plane based on the {1,2,5,15,17}-21 difference set.

By looking at how the lines and points interact, an incidence graph can be drawn. Below, I've started with a Fano plane. In the graph next to it, points and lines are the vertices of the graph. A graph edge connects any line on a point, or point on a line. (More incidence graphs are shown in my Domino Graphs column.) This particular graph is the Heawood graph, which happens to be a cage graph. Geoff Exoo is an expert on cage graphs -- one of his discoveries is that the Heawood graph can be represented as queens on a chessboard.


Figure 4. The Fano Plane, its incidence graph, and a chessboard representation.

If a torus is 7-colored, as in the Szilassi polyhedron, the edges and vertices make the same Heawood graph. The 7-coloring can be demonstrated with a set of dominoes -- if the edges are wrapped, each of the numbers 0-6 is connected.


Figure 5. The Szilassi polyhedron, and a toroidal 7-coloring done with

A different Fano plane can help you win at Nim. In Nim, coins are in various stacks, and each of two players must remove some or all of the coins in single stack each turn. All 14 winning positions are pictured in the given Fano plane, by either the numbers on a line, or the number not on a line. The same positions are given by the corners and opposing faces of a die (plus 7, if the sum is odd).


Figure 6. The Fano plane, and a way to win at Nim.

I'm just getting started on Fano plane facts. Let me point to a few web pages:

  1. Physicist and columnist John Baez uses the Fano plane to multiply octonions.
  2. Jens-Peter Schliemann's game Fire and Ice has a Fano plane of Fano planes. A unique movement rule places an enemy piece on any vacated space.
  3. In an earlier column, Oskar van Deventer demonstrated tournament dice based on the Fano plane.
  4. Olivier Giraud uses the Fano plane to explain why one cannot hear the shape of a drum.


Figure 6. The Fano Plane and not hearing the shape of a drum (from Isospectral Billiards).

The Fano plane also plays a strong part in the Hoffman-Singleton graph, a feature of a previous column. With 15 Fano planes and 35 lines (all triplets from points 1-7), the (7,5)-cage is produced. Two lines are connected if they are parallel, with no point in common. A line and plane are connected if the line is on the plane.


Figure 7. The planes of the Hoffman-Singleton graph.

I went ahead and made a card deck out from the Hoffman-Singleton graph, and it works even better than I expected. That isn't my doing, I just had faith in one of the most beautifully symmetrical objects in mathematics. "Better than Set," according to one game reviewer. Can you find 3 connected cards in the picture below? As a harder puzzle, what is the face-down card? Write me if you can solve that.


Figure 8. Cards from the Hoffman-Singleton Game (available from mathpuzzle.com).

Burkard Polster, author of A Geometrical Picture Book, has a webpage showing how the Fano plane is a Generalized Triangle. His paper "Pretty Pictures of Geometries" is fascinating. A few days after I got my shipment of cards, I read his wonderful page on the Smallest Perfect Universe for the first time: 15 Fano planes, 35 lines (a non-complete set of triplets from points 1-15), and 15 points. I was terrified that I'd made the the wrong card set. Each Fano plane has 7 lines and 7 points. Each line is parallel to 16 other lines, intersects 18 other lines, is on 3 planes, and has 3 points. Each point is on 7 planes and 7 lines. In the Hoffman-Singleton deck, all lines and planes are connected equally -- a Projective Space deck doesn't quite have that. So, I made the right cards (whew!).

Figure 9. The 15 planes and 35 lines of the smallest projective space.
1 4 5
1 6 7
1 10 14
1 9 12
1 8 11
1 13 15
2 5 7
2 4 6
2 8 10
2 11 14
2 12 13
2 9 15
3 4 7
3 5 6
3 9 13
3 8 14
3 10 11
3 12 15
1 2 3
 
4 9 10
4 12 14
4 11 13
4 8 15
5 8 13
5 9 14
5 10 12
5 11 15
6 13 15
6 8 9
6 11 12
6 10 15
7 14 15
7 8 12
7 10 13
7 9 11

The smallest projective space has lots of nice properties, though. Any two points are on a unique line. Any three points not on a line define a unique plane. Any two intersecting lines define a unique plane. Any two planes intersect on a unique line. See the Smallest Perfect Universe page for much more.

The next time the Fano plane comes up in a dinner conversation, I'll be ready.


References:

John Baez, "The Fano Plane," http://math.ucr.edu/home/baez/octonions/node4.html.

H.S.M. Coxeter, G. Beck, The Real Projective Plane, Springer, 1992.

Olivier Giraud, "Finite Geometries and Diffractive orbits in Isospectral Billiards," 31 Mar 2005. http://arxiv.org/abs/nlin.CD/0503069.

Ed Pegg Jr, "Math Games: Domino Graphs," December 15, 2003. http://www.maa.org/editorial/mathgames/mathgames_12_15_03.html.

Ed Pegg Jr, "Math Games: The Hoffman-Singleton Game," November 1, 2004. http://www.maa.org/editorial/mathgames/mathgames_11_01_04.html.

Ed Pegg Jr, "Math Games: Tournament Dice," July 11, 2005. http://www.maa.org/editorial/mathgames/mathgames_07_11_05.html.

Burkard Polster, "Pretty pictures of geometries" Bull. Belg. Math. Soc. Simon Stevin 5, no. 2/3 (1998), 417–425. projecteuclid.org.

Burkard Polster, A Geometrical Picture Book, Springer, 1998.

Burkard Polster, The Smallest Perfect Universe. http://www.maths.monash.edu.au/~bpolster/perfect.html.

Paul Vaderlind, Richard K. Guy, Loren C. Larson, G. Alexanderson, R. Nelsen, The Inquisitive Problem Solver, MAA, 2002.

Eric W. Weisstein. "Affine Plane, Cage Graph, Configuration, Finite Geometry, Heawood Graph, Incidence Graph, Nim, Projective Plane, Social Golfer Problem, Szilassi Polyhedron, Torus Coloring." From MathWorld--A Wolfram Web Resource.


Math Games archives.

Comments are welcome. Please send comments to Ed Pegg Jr. at ed@mathpuzzle.com.

Ed Pegg Jr. is the webmaster of mathpuzzle.com. He works at Wolfram Research, Inc. as an associate editor of MathWorld. He is also a math consultant for the TV show Numb3rs.