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 ${\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 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 ${\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 geht 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 sich beispielsweise die Existenz folgender Hadamard-Blockpläne:

Literatur

• Thomas Beth, Dieter Jungnickel, Hanfried Lenz: Design Theory. Bibliographisches Institut, Mannheim / Wien / Zürich 1985, ISBN 3-411-01675-2. 
• 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. 
• R. E. A. C. Paley: On orthogonal matrices. In: J. Math. Phys. Mass. Inst. Tech. Band 12, 1933, S. 311–320. 
• Peter Dembowski: Finite Geometries (= Ergebnisse der Mathematik und ihrer Grenzgebiete. Band 44). Springer Verlag, Berlin / Heidelberg / New York 1968. 
• 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
• Albrecht Beutelspacher: Einführung in die endliche Geometrie I. Blockpläne. Bibliographisches Institut, Mannheim / Wien / Zürich 1982, ISBN 3-411-01632-9.  MR0670590
• Daniel R. Hughes, Fred C. Piper: Design Theory. Cambridge University Press, Cambridge u. a. 1985, ISBN 0-521-25754-9. 

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
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.