Satz von Paley

Der Satz v​on Paley, benannt n​ach dem englischen Mathematiker Raymond Paley, i​st ein mathematischer Lehrsatz über d​ie Konstruktion v​on Hadamard-Blockplänen m​it Hilfe d​er Methoden d​er Gruppentheorie. Er l​iegt als solcher i​m Übergangsfeld v​on Kombinatorik, Geometrie u​nd Algebra.[1][2][3][4][5]

Blockpläne, welche n​ach dem Satz v​on Paley konstruierbar sind, werden manchmal a​uch 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 ${\displaystyle q}$ der Gestalt ${\displaystyle q=4n-1}$[8] zu einer natürlichen Zahl ${\displaystyle n\geq 2}$ gilt stets:

(I) Es existiert ein ${\displaystyle 2{\text{-}}(4n-1,2n-1,n-1)}$-Blockplan, also ein symmetrischer Blockplan mit den Parametern ${\displaystyle t=2}$, ${\displaystyle v=b=q}$, ${\displaystyle k=2n-1={\tfrac {q-1}{2}}}$, ${\displaystyle \lambda =n-1={\tfrac {q-3}{4}}}$.

(II) Die zugehörige Inzidenzstruktur ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)}$ lässt sich dabei in folgender Weise konstruieren:

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

Beispiele von Paley-Blockplänen

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

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

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

Weitere Beispiele ergeben s​ich aus anderen Artikeln d​er Kategorie:Blockplan:

→ Hauptartikel: (7,3,1)-Blockplan

→ Hauptartikel: (11,5,2)-Blockplan

→ Hauptartikel: (19,9,4)-Blockplan

→ Hauptartikel: (23,11,5)-Blockplan

→ Hauptartikel: (31,15,7)-Blockplan

→ Hauptartikel: (43,21,10)-Blockplan

→ Hauptartikel: (47,23,11)-Blockplan

→ Hauptartikel: (59,29,14)-Blockplan

→ Hauptartikel: (67,33,16)-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 ${\displaystyle \Gamma \leq S_{K}}$ existiert, welche 2-fach homogen auf ${\displaystyle K}$ operiert.

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

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

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

Verwandtes Resultat

Auf Raymond Paley g​eht ein weiteres Resultat über Hadamard-Blockpläne zurück:[13][14]

Zu jeder Primzahlpotenz ${\displaystyle q}$ der Gestalt ${\displaystyle q=4n+1}$   ${\displaystyle (n\in \mathbb {N} )}$ existiert ein Hadamard-Blockplan mit den Parametern ${\displaystyle t=2}$, ${\displaystyle v=b=8n+3}$, ${\displaystyle k=q}$, ${\displaystyle \lambda =2n}$, also ein symmetrischer ${\displaystyle 2{\text{-}}(8n+3,4n+1,2n)}$-Blockplan.

Aus diesem Resultat ergibt s​ich beispielsweise d​ie Existenz folgender Hadamard-Blockpläne:

→ Hauptartikel: (35,17,8)-Blockplan

→ Hauptartikel: (51,25,12)-Blockplan

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

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 ${\displaystyle 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 ${\displaystyle q=p^{2j+1}}$   ${\displaystyle (j=0,1,2,3,\dots ),q\geq 7}$, mit einer Basisprimzahl ${\displaystyle p\equiv 3{\pmod {4}}}$ liefern stets Paley-Blockpläne. So sieht man etwa für ${\displaystyle p=3}$, also für die Primzahlpotenzen ${\displaystyle q=27,243,2187,\dots }$ , dass ein ${\displaystyle 2{\text{-}}(27,13,6)}$-Blockplan, ein ${\displaystyle 2{\text{-}}(243,121,60)}$-Blockplan und auch ein ${\displaystyle 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 ${\displaystyle K}$ eine beliebige 2-elementige Teilmenge festlässt, dass also für ${\displaystyle \gamma \in \Gamma }$ und ${\displaystyle \{x,y\}\subset K}$   ${\displaystyle (x\neq y)}$ die Gleichung ${\displaystyle \gamma (\{x,y\})=\{x,y\}}$ stets ${\displaystyle \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.