Bruck–Ryser–Chowla theorem

The Bruck–Ryser–Chowla theorem is a result on the combinatorics of block designs that implies nonexistence of certain kinds of design. It states that if a (v, b, r, k, λ)-design exists with v = b (a symmetric block design), then:

if v is even, then k − λ is a square;
if v is odd, then the following Diophantine equation has a nontrivial solution:
x² − (k − λ)y² − (−1)^(v−1)/2 λ z² = 0.

The theorem was proved in the case of projective planes by Bruck & Ryser (1949). It was extended to symmetric designs by Chowla & Ryser (1950).

Projective planes[edit]

In the special case of a symmetric design with λ = 1, that is, a projective plane, the theorem (which in this case is referred to as the Bruck–Ryser theorem) can be stated as follows: If a finite projective plane of order q exists and q is congruent to 1 or 2 (mod 4), then q must be the sum of two squares. Note that for a projective plane, the design parameters are v = b = q² + q + 1, r = k = q + 1, λ = 1. Thus, v is always odd in this case.

The theorem, for example, rules out the existence of projective planes of orders 6 and 14 but allows the existence of planes of orders 10 and 12. Since a projective plane of order 10 has been shown not to exist using a combination of coding theory and large-scale computer search,^[1] the condition of the theorem is evidently not sufficient for the existence of a design. However, no stronger general non-existence criterion is known.

Connection with incidence matrices[edit]

The existence of a symmetric (v, b, r, k, λ)-design is equivalent to the existence of a v × v incidence matrix R with elements 0 and 1 satisfying

R R T = (k - λ) I + λ J

where $I$ is the v × v identity matrix and J is the v × v all-1 matrix. In essence, the Bruck–Ryser–Chowla theorem is a statement of the necessary conditions for the existence of a rational v × v matrix R satisfying this equation. In fact, the conditions stated in the Bruck–Ryser–Chowla theorem are not merely necessary, but also sufficient for the existence of such a rational matrix R. They can be derived from the Hasse–Minkowski theorem on the rational equivalence of quadratic forms.

References[edit]

^ Browne, Malcolm W. (20 December 1988), "Is a Math Proof a Proof If No One Can Check It?", The New York Times

Bruck, R.H.; Ryser, H.J. (1949), "The nonexistence of certain finite projective planes", Canadian Journal of Mathematics, 1: 88–93, doi:10.4153/cjm-1949-009-2, S2CID 123440808
Chowla, S.; Ryser, H.J. (1950), "Combinatorial problems", Canadian Journal of Mathematics, 2: 93–99, doi:10.4153/cjm-1950-009-8, S2CID 247194753
Lam, C. W. H. (1991), "The Search for a Finite Projective Plane of Order 10", American Mathematical Monthly, 98 (4): 305–318, doi:10.2307/2323798, JSTOR 2323798
van Lint, J.H., and R.M. Wilson (1992), A Course in Combinatorics. Cambridge, Eng.: Cambridge University Press.

External links[edit]

Weisstein, Eric W., "Bruck–Ryser–Chowla Theorem", MathWorld

[1] Browne, Malcolm W. (20 December 1988), "Is a Math Proof a Proof If No One Can Check It?", The New York Times

[1]

v t e Incidence structures
Representation	Incidence matrix Incidence graph
Fields	Combinatorics Block design Steiner system Geometry Incidence Projective plane Graph theory Hypergraph Statistics Blocking
Configurations	Complete quadrangle Fano plane Möbius–Kantor configuration Pappus configuration Hesse configuration Desargues configuration Reye configuration Schläfli double six Cremona–Richmond configuration Kummer configuration Grünbaum–Rigby configuration Klein configuration Dual
Theorems	Sylvester–Gallai theorem De Bruijn–Erdős theorem Szemerédi–Trotter theorem Beck's theorem Bruck–Ryser–Chowla theorem
Applications	Design of experiments Kirkman's schoolgirl problem