Brook-Reiser-Chowla teorem

Brooke [ - Reiser - Chowl teoremet er et resultat i flowchart - kombinatorik . Sætningen siger, at hvis en ( v , b , r , k , λ)-kredsløb eksisterer med v = b ( symmetrisk blokdiagram ), så:

hvis v er lige, så er k − λ et kvadrat;
hvis v er ulige, så har følgende diofantiske ligning en ikke-triviel løsning: $x^{2}-(k-\lambda )y^{2}-(-1)^{(v-1)/2}\lambda z^{2}=0$ .

Sætningen blev bevist for projektive fly af Brook og Reiser [1] . Sætningen blev udvidet til symmetriske kredsløb af Reiser og Chowl [2] .

Projektive planer

I det specielle tilfælde af symmetriske skemaer med , det vil sige projektive planer , kan sætningen (som i dette tilfælde er kendt som Bruck-Reiser-sætningen ) angives som følger: Hvis der findes et endeligt projektivt plan af orden q , og q er kongruent . til 1 eller 2 (mod 4), så skal q være summen af to kvadrater. Bemærk, at for det projektive plan, for skemaets parametre, . I dette tilfælde er v derfor altid ulige. $\lambda=1$ $v=b=q^{2}+q+1,r=k=q+1,\lambda =1$

Sætningen udelukker for eksempel eksistensen af orden 6 og 14 projektive planer, men tillader eksistensen af orden 10 og 12 planer nok til at skemaet eksisterer. Der kendes dog ikke noget ikke-eksistenskriterium.

Forholdet til incidensmatricer

Eksistensen af et symmetrisk ( v , b , r , k , λ)-skema svarer til eksistensen af en v × v incidensmatrix R med elementer 0 og 1, der opfylder betingelsen

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

hvor E er en v × v identitetsmatrix, og J er en v × v matrix, hvor alle elementer er lig med 1. I bund og grund er Brook-Reiser-Chowl-sætningen et udsagn om de nødvendige betingelser for eksistensen af en rationel v × v matrix R , der opfylder denne ligning. Faktisk er betingelserne i Brook-Reiser-Chowl-sætningen ikke kun nødvendige, men også tilstrækkelige til eksistensen af sådanne rationelle matricer R . De kan udledes af Minkowski-Hasse-sætningen om den rationelle ækvivalens af kvadratiske former.

Litteratur

Malcolm W. Browne. Er et matematisk bevis et bevis, hvis ingen kan tjekke det? // The New York Times. - 1988. - 1. december.
Bruck RH, Ryser HJ Ikke- eksistensen af visse endelige projektive planer // Canadian J. Math .. - 1949. - T. 1 . — S. 88–93 . - doi : 10.4153/cjm-1949-009-2 .
Chowla S., Ryser HJ Kombinatoriske problemer // 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 , no. 4 . — S. 305–318 . - doi : 10.2307/2323798 .
van Lint JH, Wilson R.M. Et kursus i kombinatorik. — Cambridge: Cambridge University Press, 1992.

Brook-Reiser-Chowla teorem

Projektive planer

Forholdet til incidensmatricer

Noter

Litteratur

Links