Bruck-Ryser-Chowla theorem

The Bruck – Ryser – Chowla theorem is a combinatorial statement about possible block plans , which specifies the necessary conditions for their existence.

The sentence says: If there is a symmetric block plan, then holds ${\displaystyle t-(v,k,\lambda )}$

• if v is even then is a square number ; ${\displaystyle k-\lambda }$
• if v is odd, then the Diophantine equation has a non-zero solution
  ${\displaystyle x^{2}=(k-\lambda )\cdot y^{2}+(-1)^{\frac {v-1}{2}}\cdot \lambda \cdot z^{2}}$
  ${\displaystyle (x,y,z)\in \mathbb {Z} ^{3}\setminus \{(0,0,0)\}.}$

The theorem was proved in 1949 for the special case of projective planes by Richard Bruck and Herbert John Ryser and in 1950 with Sarvadaman Chowla it was generalized to more general symmetrical block plans.

Finite projective planes

In the special case of a minimal symmetrical 2-block plan with - i.e. for finite projective planes - the sentence can be formulated as follows: ${\displaystyle \lambda =1}$

If a projective level of order exists and or holds, then is the sum of two square numbers (one of which can also vanish). ${\displaystyle q}$ ${\displaystyle q\equiv 1{\pmod {4}}}$ ${\displaystyle q\equiv 2{\pmod {4}}}$ ${\displaystyle q}$

If one understands a finite projective level of the order as a special symmetrical block plan, then are the parameters that describe the block plan ${\displaystyle q}$

${\displaystyle v=q^{2}+q+1;\quad k=q+1;\lambda =1}$.

In this more specific formulation for projective planes, the theorem is also cited as the theorem of Bruck and Ryser .

Conclusions and Examples

From the sentence it follows, for example, that there is no level for orders 6 and 14, but it does not exclude the existence of levels of orders and . It could be shown that no projective plane of order 10 exists. It follows that the conditions in Bruck-Ryser-Chowla's theorem are not a sufficient condition for the existence of block plans. ${\displaystyle 10=2\cdot 4+2=3^{2}+1^{2}}$ ${\displaystyle 12\equiv 0{\pmod {4}}}$

• The orders fulfill the necessary condition of the proposition for projective planes. In fact, there are levels with these orders because they are also prime powers. ${\displaystyle q=5=4+1;9=9+0;13=9+4}$
• The sentence makes no statement about levels of order , there is. Since 27 is a prime power, there is a level with this order. ${\displaystyle q=27=3^{3}}$ ${\displaystyle 27\equiv 3{\pmod {4}}}$

Excluded orders

The sequence of numbers that, due to the Bruck and Ryser theorem, cannot be orders of a projective plane, i.e. the numbers with that are not the sum of two square numbers , form the sequence A046712 in OEIS . ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle n\equiv 1,2{\pmod {4}}}$

The smallest orders excluded are: 6, 14, 21, 22, 30, 33, 38, 42, 46, 54, 57, 62, 66, 69, 70, 77, 78, 86, 93, 94, 102, 105 , 110, 114, 118, 126, 129, 133, 134, 138, 141, 142, 150, 154, 158, 161, 165, 166, 174, 177, 182, 186, 189, 190, 198, 201, 206 , 209, 210, 213, 214, 217, 222, 230, 237, 238, ...

literature

Technical article

• Richard H. Bruck, Herbert John Ryser: The nonexistence of certain finite projective planes . In: Canadian Journal of Mathematics . tape 1 . Canadian Mathematical Society, Feb. 1, 1949, pp. 88–93 , doi : 10.4153 / CJM-1949-009-2 ( abstract with link to the English PDF full text [accessed on February 8, 2012]).
• Sarvadaman Chowla, Herbert John Ryser: Combinatorial problems . In: Canadian Journal of Mathematics . tape 2 . Canadian Mathematical Society, 1950, pp. 93-99 .
• CWH Lam: The Search for a Finite Projective Plane of Order 10 . In: American Mathematical Monthly . tape 98 , no. 4 , 1991, pp. 305-318 (English, cecm.sfu.ca [accessed February 8, 2012]).

Textbooks that introduce the topic

• Jeffrey H. Dinitz, Douglas Robert Stinson: A Brief Introduction to Design Theory . In: JH Dinitz and DR Stinson (Eds.): Contemporary Design Theory: A Collection of Surveys . Wiley, New York 1992, ISBN 0-471-53141-3 , chap. 1 , p. 1-12 .
• Jacobus Hendricus van Lint , RM Wilson: A Course in Combinatorics . 2nd Edition. Cambridge University Press, Cambridge 2001, ISBN 0-521-80340-3 .
• Jiří Matoušek, Jaroslav Nešetřil: Discrete Mathematics . A journey of discovery. Springer, Berlin / Heidelberg / New York /… 2002, ISBN 3-540-42386-9 , 8: Finite projective planes and 11.1: Designs ( DNB 963555103/04 [accessed on February 8, 2012] English: Invitation to Discrete Mathematics . Translated by Hans Mielke, textbook that requires little previous knowledge - advanced school mathematics up to the 2nd semester of mathematics studies).
• Albrecht Beutelspacher : Introduction to finite geometry I . 2nd Edition. BI Wissenschaftsverlag, Mannheim 1983, ISBN 3-411-01632-9 , p. 176-185 .

Web links

• Eric W. Weisstein : Bruck – Ryser – Chowla theorem . In: MathWorld (English).
• block design . In: Encyclopaedia of Mathematics

References and comments

1. ↑ Bruck and Ryser (1949)
2. ↑ Chowla and Ryser (1950)
3. ↑ This means that different "blocks", which are called straight lines in geometry , always have exactly one ( ) common "point". ${\displaystyle t=2}$ ${\displaystyle \lambda =1}$
4. ↑ van Lint (1992)
5. ↑ Reinhard Zumkeller: Table n, a (n) for n = 1..10000 gives the first 10000 numbers excluded in this way, including their number in the sequence A046712: ASCII text file , accessed on February 9, 2012.