Brook-Reiser-Chowla teorem

Brooke [ - Reiser - Chowl satsen är ett resultat i flödesschemakombinatorik . Satsen säger att om en ( v , b , r , k , λ)-krets existerar med v = b ( symmetriskt blockdiagram ), då:

om v är jämnt är k − λ en kvadrat;
om v är udda, har följande diofantiska ekvation en icke-trivial lösning: $x^{2}-(k-\lambda )y^{2}-(-1)^{(v-1)/2}\lambda z^{2}=0$ .

Satsen bevisades för fallet med projektiva plan av Brook och Reiser [1] . Teoremet utvidgades till symmetriska kretsar av Reiser och Chowl [2] .

Projektiva plan

I specialfallet med symmetriska scheman med , det vill säga projektiva plan , kan satsen (som i detta fall är känd som Bruck-Reiser-satsen ) anges på följande sätt: Om ett ändligt projektivt plan av ordning q existerar och q är kongruent till 1 eller 2 (mod 4), då måste q vara summan av två kvadrater. Observera att för det projektiva planet, för schemats parametrar, . Så i det här fallet är v alltid udda. $\lambda=1$ $v=b=q^{2}+q+1,r=k=q+1,\lambda =1$

Teoremet utesluter till exempel förekomsten av projektiva plan ordning 6 och 14, men tillåter existensen av plan ordning 10 och 12. tillräckligt för att schemat ska existera. Inget icke-existenskriterium är dock känt.

Samband med incidensmatriser

Förekomsten av ett symmetriskt ( v , b , r , k , λ)-schema är ekvivalent med förekomsten av en v × v incidensmatris R med elementen 0 och 1 som uppfyller villkoret

RR^{T}=(k-\lambda )E+\lambda J

där E är en v × v identitetsmatris och J är en v × v matris där alla element är lika med 1. I huvudsak är Brook-Reiser-Chowl-satsen ett uttalande om de nödvändiga förutsättningarna för existensen av en rationell v × v matris R som uppfyller denna ekvation. Faktum är att villkoren i Brook-Reiser-Chowl-satsen inte bara är nödvändiga utan också tillräckliga för existensen av sådana rationella matriser R . De kan härledas från Minkowski-Hasses sats om kvadratiska formers rationella ekvivalens.

Litteratur

Malcolm W. Browne. Är ett matematiskt bevis ett bevis om ingen kan kontrollera det? // The New York Times. - 1988. - 1 december.
Bruck RH, Ryser HJ Oexistensen av vissa finita projektiva plan // Canadian J. Math .. - 1949. - T. 1 . — S. 88–93 . - doi : 10.4153/cjm-1949-009-2 .
Chowla S., Ryser HJ Kombinatoriska problem // Canadian J. Math .. - 1950. - T. 2 . — S. 93–99 . - doi : 10.4153/cjm-1950-009-8 .
CWH Lam. The Search for a Finite Projective Plane of Order 10 // American Mathematical Monthly . - 1991. - T. 98 , nr. 4 . — S. 305–318 . - doi : 10.2307/2323798 .
van Lint JH, Wilson R.M. En kurs i kombinatorik. — Cambridge: Cambridge University Press, 1992.

Länkar

Weisstein, Eric W. Bruck–Ryser–Chowla-teorem (engelska) på Wolfram MathWorld -webbplatsen .