Latin Squares and Finite Geometries

A Latin square is a square array in which each symbol appears once per row and column, and finite geometries are highly structured incidence systems on finitely many points and lines.

Definition

A Latin square of order n is an n-by-n array filled with n symbols so that each symbol occurs exactly once in every row and every column; a finite projective plane is an incidence structure of points and lines in which any two points lie on a unique line and any two lines meet in a unique point.

Scope

This topic treats Latin squares and mutually orthogonal Latin squares, their equivalence with nets and transversal designs, and finite projective and affine planes built from finite fields. It includes the classical Euler conjecture on orthogonal squares and the deep connection between mutually orthogonal Latin squares and finite projective planes.

Core questions

• How many mutually orthogonal Latin squares of a given order can exist?
• For which orders do complete sets of orthogonal squares, and hence projective planes, exist?
• How do finite fields construct planes and orthogonal squares?
• What incidence axioms define affine and projective geometries over finite sets?

Key concepts

• Latin square
• Mutually orthogonal Latin squares
• Transversal designs and nets
• Finite projective plane
• Affine plane
• Galois (finite) fields

Key theories

MOLS and projective planes

A complete set of n-1 mutually orthogonal Latin squares of order n exists if and only if a finite projective plane of order n exists, tying Latin-square combinatorics to finite geometry.

Refutation of Euler's conjecture

Euler conjectured no pair of orthogonal Latin squares exists for orders congruent to 2 modulo 4; Bose, Shrikhande, and Parker disproved this in 1960 for all such orders except 2 and 6.

Clinical relevance

Latin squares provide row-column experimental designs that control two sources of variation simultaneously, orthogonal arrays support factorial experiments and software testing, and finite geometries generate codes and designs.

History

Euler studied orthogonal Latin squares in 1782 through his thirty-six officers problem; his conjecture stood until the 1960 disproof by Bose, Shrikhande, and Parker, the so-called Euler spoilers.

Key figures

• Leonhard Euler
• R. C. Bose
• E. T. Parker

Seminal works

• colbourn2007

Frequently asked questions

What does it mean for two Latin squares to be orthogonal?

When the two squares are superimposed, each ordered pair of symbols occurs exactly once, so the squares jointly distinguish every cell of the grid.

Is a Sudoku grid a Latin square?

A completed Sudoku is a Latin square of order nine with the extra constraint that each three-by-three box also contains every symbol once.