Singer Difference Setsv0.6.1

Singer Difference Sets

Mark 0, 1, and 3 on a clock with seven hours. Every distance from 1 to 6 hours appears exactly once between two of the marks. Sets like this look like they need a long search. In 1938 James Singer showed how to write one down directly for every prime power, using finite fields and projective planes.

Start with lesson 1: Differences on a circle

The path

Part I: The puzzle

  1. Differences on a circleWhat a difference set is, and why searching for one by hand quickly becomes hopeless.
  2. Rotations that never overlap too muchTranslates of a difference set meet in exactly λ points, which is the clue that leads to geometry.

Part II: Projective planes

  1. A geometry with seven pointsThe Fano plane, whose seven lines are the seven rotations of {0, 1, 3}.
  2. Projective planes in generalThe axioms, the counts, and why a cyclic projective plane is exactly a planar difference set.

Part III: Finite fields

  1. Which clocks are fieldsThe field axioms, and why ℤ/nℤ is a field exactly when n is prime.
  2. Every field with p elements is ℤ/pℤCharacteristic and the prime subfield: there is only one field of each prime order.
  3. Fields with pᵏ elements, built from polynomialsPolynomials over GF(p) modulo an irreducible polynomial, where irreducibles play the role of primes.
  4. One element to generate them allPrimitive elements, log tables, and a fast test for primitive polynomials.
  5. Fields inside fieldsSubfields, the Frobenius map, and why GF(q) sits inside GF(q³).

Part IV: Planes from fields

  1. Vectors over a finite fieldGF(q)³ as a finite grid of vectors, and counting the lines and planes through the origin.
  2. Coordinates for a projective planePG(2, q): points and lines as subspaces of GF(q)³.
  3. The field hiding inside the planeGF(q³) is GF(q)³, so every point of PG(2, q) is a power of α.
  4. The Singer cycleMultiplying by α rotates the whole plane, so PG(2, q) is cyclic.

Part V: Singer's algorithm

  1. Writing down a difference setThe trace-zero line gives a Singer set directly, with no search.
  2. Many sets, few shapesMultipliers, equivalence, and the distinct Singer sets for each q.

Part VI: The frontier

  1. Beyond the planeSinger sets in every dimension, and the q = 2 case that becomes the shift-register sequence engineers call an m-sequence.
  2. Is every planar difference set a Singer set?The completeness conjecture: Singer's construction may find every planar difference set there is.

Part VII: Applications

  1. A card game from a planeWhy every two cards of Spot It share exactly one symbol, and how a difference set deals the deck.
  2. Pictures without a lensCoded-aperture telescopes: a mask of holes whose shadows can be unscrambled.
  3. Finding an echoCodes that look like noise but line up with themselves in only one place.
  4. Majority rulesAn error-correcting code that fixes bits by a simple vote, broadcast to car radios.
  5. Always meetRadios that wake on a few slots and still always hear each other, whatever their clocks say.
  6. A ruler with no repeatsMarks whose distances are all different, for antennas and radio channels.

Playgrounds