Satz von Paley

Der Satz von Paley, benannt nach dem englischen Mathematiker Raymond Paley, ist ein mathematischer Lehrsatz über die Konstruktion von Hadamard-Blockplänen mit Hilfe der Methoden der Gruppentheorie. Er liegt als solcher im Übergangsfeld von Kombinatorik, Geometrie und Algebra.^[1]^[2]^[3]^[4]^[5]

Blockpläne, welche nach dem Satz von Paley konstruierbar sind, werden manchmal auch als Paley-Blockpläne (engl. Paley designs) bzw. Paley-Hadamard-2-Blockpläne (engl. Paley-Hadamard 2-designs) bezeichnet.^[6]^[7]

Formulierung des Satzes

Für eine Primzahlpotenz $q$ der Gestalt $q=4n-1$ ^[8] zu einer natürlichen Zahl $n\geq 2$ gilt stets:

(I) Es existiert ein

2{\text{-}}(4n-1,2n-1,n-1)

-Blockplan, also ein symmetrischer Blockplan mit den Parametern

t=2

,

v=b=q

,

k=2n-1={\tfrac {q-1}{2}}

,

\lambda =n-1={\tfrac {q-3}{4}}

.

(II) Die zugehörige Inzidenzstruktur

{\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)

lässt sich dabei in folgender Weise konstruieren:

Den zu $q$ gehörenden Galois-Körper $K=\operatorname {GF} (q)$ wählt man als Punktmenge von ${\mathcal {I}}$ ; das heißt man wählt ${\mathfrak {p}}=K$ , also die Körperelemente als die Punkte der Inzidenzstruktur.
Für die Konstruktion des Blocksystems ${\mathfrak {B}}$ geht man aus von der multiplikativen Gruppe $K^{\times }$ des Galoiskörpers und betrachtet hier die Untergruppe $U\leq K^{\times }$ der Quadrate $\neq 0$ , also $U=\{u\in K^{\times }\mid \exists x\in K^{\times }:x^{2}=u\}$ . Dann setzt man ${\mathfrak {B}}=\{U+a\mid a\in K\}$ .
Die Inzidenzrelation $I$ ist die Elementrelation, also $I=\in$ .

Beispiele von Paley-Blockplänen

Die beiden kleinsten Beispiele von Paley-Blockplänen sind diejenigen für die beiden Primzahlen $q=7$ und $q=11$ .^[9]

So ergibt für $q=7$ auf $K=\operatorname {GF} (7)$ der $2{\text{-}}(7,3,1)$ -Blockplan, dessen geometrische Struktur der der Fano-Ebene entspricht. Die oben beschriebene Untergruppe der Quadrate von $\operatorname {GF} (7)$ ist $U=\{1,2,4\}$ .^[10]^[11]

Für $q=11$ ergibt sich auf $K=\operatorname {GF} (11)$ der $2{\text{-}}(11,5,2)$ -Blockplan. Die Untergruppe der Quadrate von $\operatorname {GF} (11)$ ist hier $U=\{1,3,4,5,9\}$ .

Weitere Beispiele ergeben sich aus anderen Artikeln der Kategorie:Blockplan:

Anmerkungen zum Beweis des Satzes

Der Beweis des Satzes von Paley lässt sich führen mit Hilfe der Ungleichung von Fisher und der Tatsache, dass eine spezielle Permutationsgruppe $\Gamma \leq S_{K}$ existiert, welche 2-fach homogen auf $K$ operiert.

Wie sich nämlich zeigt, lässt sich so das Blocksystem ${\mathfrak {B}}$ auch noch auf andere Weise beschrieben, nämlich als Menge der $\gamma$ -Bilder von $U$ über alle $\gamma \in \Gamma$ , also in der Form ${\mathfrak {B}}=\{\gamma (U)\mid \gamma \in \Gamma \}$ .

Man gewinnt die Permutationsgruppe $\Gamma$ dabei aus der obigen Untergruppe $U\leq K^{\times }$ , indem man diejenigen Permutationen $\gamma \colon K\to K$ betrachtet, welche die Form $x\mapsto \gamma (x)=ux+a$ haben, wobei $u\in U$ und $a\in K$ fest gewählte Elemente sind. All diese Permutationen, versehen mit der üblichen Verkettung, bilden dann $\Gamma$ .

Es lässt sich nun zeigen, dass die Untergruppe $U$ die Ordnung $k$ hat, während sich für die Permutationsgruppe $\Gamma$ die Ordnung $kq={\tfrac {q(q-1)}{2}}$ ergibt. Also hat $\Gamma$ ungerade Ordnung und enthält nach dem Satz von Lagrange kein Element der Ordnung 2. Daher ist $-1\notin U$ , woraus dann die 2-fache Homogenität von $\Gamma$ folgt.^[12]

Literatur

Thomas Beth, Dieter Jungnickel, Hanfried Lenz: Design Theory. Bibliographisches Institut, Mannheim / Wien / Zürich 1985, ISBN 3-411-01675-2.
Albrecht Beutelspacher: Einführung in die endliche Geometrie I. Blockpläne. Bibliographisches Institut, Mannheim / Wien / Zürich 1982, ISBN 3-411-01632-9. MR0670590
Peter Dembowski: Finite Geometries (= Ergebnisse der Mathematik und ihrer Grenzgebiete. Band 44). Springer Verlag, Berlin / Heidelberg / New York 1968.
Daniel R. Hughes, Fred C. Piper: Design Theory. Cambridge University Press, Cambridge u. a. 1985, ISBN 0-521-25754-9.
Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik (= de Gruyter Lehrbuch). 2., völlig neu bearbeitete und erweiterte Auflage. de Gruyter, Berlin u. a. 2004, ISBN 3-11-016727-1.
Heinz Lüneburg: Kombinatorik (= Elemente der Mathematik vom höheren Standpunkt aus. Band 6). Birkhäuser Verlag, Basel / Stuttgart 1971, ISBN 3-7643-0548-7. MR0335267
R. E. A. C. Paley: On orthogonal matrices. In: J. Math. Phys. Mass. Inst. Tech. Band 12, 1933, S. 311–320.

Einzelnachweise und Anmerkungen

↑ A. Beutelspacher: Einführung in die endliche Geometrie. 1982, S. 104–108.
↑ H. Lüneburg: Kombinatorik. 1971, S. 75 ff.
↑ T. Beth, D. Jungnickel, H. Lenz: Design Theory. 1985, S. 70 ff., 262, 264.
↑ D. R. Hughes, F. C. Piper: Design Theory. 1985, S. 107 ff.
↑ K. Jacobs, D. Jungnickel: Einführung in die Kombinatorik. 2004, S. 251 ff.
↑ P. Dembowski: Finite Geometries. 1968, S. 97.
↑ D. R. Hughes, F. C. Piper: Design Theory. 1985, S. 107, 180.
↑ Also $q\equiv 3{\pmod {4}}$ .
↑ T. Beth, D. Jungnickel, H. Lenz: Design Theory. 1985, S. 262, 264.
↑ Wegen der Unterschiede in der Darstellung in dem zugehörigen Hauptartikel beachte man den Hinweis auf den Singer-Zyklus.
↑ Auch alle Primzahlpotenzen der Gestalt $q=p^{2j+1}$ $(j=0,1,2,3,\dots ),q\geq 7$ , mit einer Basisprimzahl $p\equiv 3{\pmod {4}}$ liefern stets Paley-Blockpläne. So sieht man etwa für $p=3$ , also für die Primzahlpotenzen $q=27,243,2187,\dots$ , dass ein $2{\text{-}}(27,13,6)$ -Blockplan, ein $2{\text{-}}(243,121,60)$ -Blockplan und auch ein $2{\text{-}}(2187,1093,546)$ -Blockplan existiert. Siehe auch
Hauptartikel: (27,13,6)-Blockplan
↑ Der wesentliche Beweisschritt besteht hier darin zu zeigen, dass allein die identische Abbildung von $K$ eine beliebige 2-elementige Teilmenge festlässt, dass also für $\gamma \in \Gamma$ und $\{x,y\}\subset K$ $(x\neq y)$ die Gleichung $\gamma (\{x,y\})=\{x,y\}$ stets $\gamma ={id}_{K}$ nach sich zieht; s. A. Beutelspacher: Einführung in die endliche Geometrie. 1982, S. 106. Und auch H. Lüneburg: Kombinatorik. 1971, S. 79.
↑ K. Jacobs, D. Jungnickel: Einführung in die Kombinatorik. 2004, S. 252.
↑ T. Beth, D. Jungnickel, H. Lenz: Design Theory. 1985, S. 70–72.

[1] A. Beutelspacher: Einführung in die endliche Geometrie. 1982, S. 104–108.

[2] H. Lüneburg: Kombinatorik. 1971, S. 75 ff.

[3] T. Beth, D. Jungnickel, H. Lenz: Design Theory. 1985, S. 70 ff., 262, 264.

[4] D. R. Hughes, F. C. Piper: Design Theory. 1985, S. 107 ff.

[5] K. Jacobs, D. Jungnickel: Einführung in die Kombinatorik. 2004, S. 251 ff.

[6] P. Dembowski: Finite Geometries. 1968, S. 97.

[7] D. R. Hughes, F. C. Piper: Design Theory. 1985, S. 107, 180.

[8] Also $q\equiv 3{\pmod {4}}$ .

[9] T. Beth, D. Jungnickel, H. Lenz: Design Theory. 1985, S. 262, 264.

[10] Wegen der Unterschiede in der Darstellung in dem zugehörigen Hauptartikel beachte man den Hinweis auf den Singer-Zyklus.

[11] Auch alle Primzahlpotenzen der Gestalt $q=p^{2j+1}$ $(j=0,1,2,3,\dots ),q\geq 7$ , mit einer Basisprimzahl $p\equiv 3{\pmod {4}}$ liefern stets Paley-Blockpläne. So sieht man etwa für $p=3$ , also für die Primzahlpotenzen $q=27,243,2187,\dots$ , dass ein $2{\text{-}}(27,13,6)$ -Blockplan, ein $2{\text{-}}(243,121,60)$ -Blockplan und auch ein $2{\text{-}}(2187,1093,546)$ -Blockplan existiert. Siehe auch
Hauptartikel: (27,13,6)-Blockplan

[12] Der wesentliche Beweisschritt besteht hier darin zu zeigen, dass allein die identische Abbildung von $K$ eine beliebige 2-elementige Teilmenge festlässt, dass also für $\gamma \in \Gamma$ und $\{x,y\}\subset K$ $(x\neq y)$ die Gleichung $\gamma (\{x,y\})=\{x,y\}$ stets $\gamma ={id}_{K}$ nach sich zieht; s. A. Beutelspacher: Einführung in die endliche Geometrie. 1982, S. 106. Und auch H. Lüneburg: Kombinatorik. 1971, S. 79.

[13] K. Jacobs, D. Jungnickel: Einführung in die Kombinatorik. 2004, S. 252.

[14] T. Beth, D. Jungnickel, H. Lenz: Design Theory. 1985, S. 70–72.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]