Bruck–Chowla–Ryser theorem

From Wikipedia, the free encyclopedia

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

k − λ is a square

when v is even, and the diophantine equation

x² − (k − λ)y² − (−1)^(v−1)/2 λ z² = 0

has a nontrivial solution when v is odd.

In the special case of a symmetric design with λ = 1, that is, a projective plane, the 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.

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, the condition of the theorem is evidently not sufficient for the existence of a design. However, no stronger general existence criterion is known.

The theorem was proved in the case of projective planes by Bruck and Ryser in 1949. It was extended to symmetric designs by Ryser and Chowla in 1950. 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-Chowla-Ryser 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-Chowla-Ryser 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.

[edit] References

• Bruck, R.H. and H.J. Ryser (1949) "The nonexistence of certain finite projective planes". Canadian J. Math. 1, 88–93.
• Chowla, S. and H.J. Ryser (1950) "Combinatorial problems". Canadian J. Math. 2, 93–99.
• Clement W.H. Lam (1991) "The Search for a Finite Projective Plane of Order 10", American Mathematical Monthly 98, (no. 4), 305–318.
• van Lint, J.H., and R.M. Wilson (1992), A Course in Combinatorics. Cambridge, Eng.: Cambridge University Press.
• Weisstein, Eric W. "Bruck-Ryser-Chowla Theorem." From MathWorld–A Wolfram Web