Bruck–Ryser–Chowla-satsen
Bruck att – Ryser – Chowla -satsen är ett resultat av kombinatoriken för blockdesigner som antyder vissa typer av design inte finns. Den anger att om en ( v , b , r , k , λ)-design existerar med v = b (en symmetrisk blockdesign ), då:
- om v är jämnt är k − λ en kvadrat;
- om v är udda, så har följande diofantiska ekvation en icke-trivial lösning:
- x 2 − ( k − λ) y 2 − (−1) (v−1)/2 λ z 2 = 0.
Teoremet bevisades i fallet med projektiva plan av Bruck & Ryser (1949) . Den utökades till symmetriska mönster av Chowla & Ryser (1950) .
Projektiva plan
I specialfallet med en symmetrisk design med λ = 1, det vill säga ett projektivt plan , kan satsen (som i detta fall benämns Bruck–Ryser-satsen ) anges på följande sätt: Om ett ändligt projektivt ordningsplan q finns och q är kongruent med 1 eller 2 (mod 4), då måste q vara summan av två kvadrater. Observera att för ett projektivt plan är designparametrarna v = b = q 2 + q + 1, r = k = q + 1, λ = 1. V är alltså alltid udda i detta fall.
Teoremet utesluter till exempel förekomsten av projektiva plan av ordning 6 och 14 men tillåter existensen av plan av ordning 10 och 12. Eftersom ett projektivt plan av ordning 10 har visat sig inte existera med hjälp av en kombination av kodningsteori och storskalig datorsökning är satsens tillstånd uppenbarligen inte tillräckligt för att det ska finnas en design. Något starkare generellt icke-existenskriterium är dock känt.
Samband med incidensmatriser
Förekomsten av en symmetrisk ( v , b , r , k , λ)-design är ekvivalent med förekomsten av en v × v incidensmatris R med elementen 0 och 1 som uppfyller
- R R T = ( k − λ) I + λ J
där I är v × v identitetsmatrisen och J är v × v all-1 matrisen. I huvudsak är Bruck-Ryser-Chowla-satsen ett uttalande av de nödvändiga förutsättningarna för existensen av en rationell v × v - matris R som uppfyller denna ekvation. Faktum är att de villkor som anges i Bruck-Ryser-Chowla-satsen inte bara är nödvändiga, utan också tillräckliga för existensen av en sådan rationell matris R . De kan härledas från Hasse–Minkowskis sats om kvadratiska formers rationella ekvivalens .
- Bruck, RH; Ryser, HJ (1949), "The nonexistence of certain finite projective planes", Canadian Journal of Mathematics , 1 : 88–93, doi : 10.4153/cjm-1949-009-2
- Chowla, S .; Ryser, HJ (1950), "Kombinatoriska problem", Canadian Journal of Mathematics , 2 : 93–99, doi : 10.4153/cjm-1950-009-8
- Lam, CWH (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, JH och RM Wilson (1992), A Course in Combinatorics . Cambridge, eng.: Cambridge University Press.