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.

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.

Formulierung des Satzes

Für eine Primzahlpotenz ${\displaystyle q}$ der Gestalt ${\displaystyle q=4n-1}$ 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}$.

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\}}$.

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.

Verwandtes Resultat

Auf Raymond Paley geht ein weiteres Resultat über Hadamard-Blockpläne zurück:

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