Satz von Paley

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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:
  1. 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.
  2. 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 \}.
  3. Die Inzidenzrelation I ist die Elementrelation, also I = \in .

Beispiele von Paley-Blockplänen[Bearbeiten]

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:

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[Bearbeiten]

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]

Verwandtes Resultat[Bearbeiten]

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

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

Aus diesem Resultat ergibt sich beispielsweise die Existenz folgender Hadamard-Blockpläne:

Hauptartikel: (35,17,8)-Blockplan
Hauptartikel: (51,25,12)-Blockplan

Literatur[Bearbeiten]

Einzelnachweise und Fußnoten[Bearbeiten]

  1.  Beutelspacher: S. 104–108.
  2.  Lüneburg: S. 75 ff.
  3.  Beth-Jungnickel-Lenz: S. 70 ff,262,264.
  4.  Hughes-Piper: S. 107 ff.
  5.  Jacobs-Jungnickel: S. 251 ff.
  6.  Dembowski: S. 97.
  7.  Hughes-Piper: S. 107, 180.
  8. Also q \equiv 3 \pmod 4.
  9.  Beth-Jungnickel-Lenz: 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.  Beutelspacher: S. 106. Und auch  Lüneburg: S. 79.
  13.  Jacobs-Jungnickel: S. 252.
  14.  Beth-Jungnickel-Lenz: S. 70-72.