Differenzenmenge

Eine Differenzenmenge der Ordnung n^[1] (englisch: perfect difference set^[2]) ist in der endlichen Geometrie eine Menge von ${\displaystyle n+1}$ natürlichen Zahlen^[3], aus der sich eine eindeutige projektive Ebene erzeugen lässt. James Singer konnte in den 1930er Jahren beweisen, dass jede endliche desarguessche Ebene von einer Differenzenmenge abstammt.^[2] Diese Tatsache ist eine der Aussagen des Satzes von Singer, der darüber hinaus besagt, dass jede endliche desarguessche projektive Geometrie einen Singer-Zyklus besitzt. Es wird vermutet, ist aber (2012) noch nicht bewiesen, dass genau die desarguesschen endlichen Ebenen von einer Differenzenmenge abstammen.^[1]

Es sei n eine natürliche Zahl. Eine Menge ${\displaystyle {\mathcal {D}}}$ von natürlichen Zahlen heißt eine Differenzenmenge der Ordnung n, falls gilt^[1]

1. ${\displaystyle {\mathcal {D}}}$ enthält genau ${\displaystyle n+1}$ Elemente,
2. jede natürliche Zahl ${\displaystyle m\in \{1,2,3,\ldots ,n^{2}+n\}}$ lässt sich auf genau eine Weise schreiben als ${\displaystyle m\equiv d_{1}-d_{2}\mod (n^{2}+n+1)}$ mit ${\displaystyle d_{1},d_{2}\in {\mathcal {D}}.}$

Die zweite Bedingung lässt sich formal abschwächen. Sei ${\displaystyle \Delta ({\mathcal {D}})=\{(d,d)|d\in {\mathcal {D}}\}}$ die Diagonale in ${\displaystyle {\mathcal {D}}^{2}}$. Dann ist die 2. Bedingung zunächst gleichwertig zu der abstrakter formulierten Bedingung

(2a) Die Abbildung ${\displaystyle \delta :{\mathcal {D}}^{2}\setminus \Delta ({\mathcal {D}})\rightarrow \{1,2,3,\ldots ,n^{2}+n\}:(d_{1},d_{2})\mapsto d_{1}-d_{2}\mod (n^{2}+n+1)}$ ist bijektiv.^[4]

Da für eine Menge ${\displaystyle {\mathcal {D}}}$, die der 1. Bedingung gemäß ${\displaystyle n+1}$ Elemente enthält, die Menge ${\displaystyle {\mathcal {D}}^{2}\setminus \Delta ({\mathcal {D}})}$ der Paare unterschiedlicher Zahlen immer ${\displaystyle (n+1)^{2}-(n+1)=n^{2}+n}$ Elemente enthält, ist die Definitionsmenge von ${\displaystyle \delta }$ immer gleichmächtig zur Zielmenge, daher sind für diese Abbildung Surjektivität, Injektivität und Bijektivität gleichwertige Forderungen und die 2. Bedingung kann durch

(2b) „Für ${\displaystyle d_{1},d_{2}\in {\mathcal {D}},d_{1}\neq d_{2}}$ sind die Differenzen ${\displaystyle d_{1}-d_{2}\mod (n^{2}+n+1)}$ paarweise verschiedene Zahlen (mit anderen Worten: ${\displaystyle \delta }$ ist injektiv).“ oder durch

(2c) „Jede natürliche Zahl ${\displaystyle m\in \{1,2,3,\ldots ,n^{2}+n\}}$ tritt modulo ${\displaystyle n^{2}+n+1}$ als Differenz ${\displaystyle d_{1}-d_{2}\;(d_{1},d_{2}\in {\mathcal {D}})}$ auf (mit anderen Worten: ${\displaystyle \delta }$ ist surjektiv).“

ersetzt werden.

• Ist ${\displaystyle {\mathcal {D}}}$ eine Differenzenmenge der Ordnung ${\displaystyle n}$, dann sind auch die ${\displaystyle n^{2}+n+1}$ verschiedenen Mengen ${\displaystyle {\mathcal {D}}+i=\{d+i\mod (n^{2}+n+1)|d\in {\mathcal {D}}\}}$ für beliebige ${\displaystyle i\in \{0,1,2,\ldots ,n^{2}+n\}}$ solche Differenzenmengen.
• Jede Differenzenmenge ${\displaystyle {\mathcal {D}}}$ der Ordnung ${\displaystyle n}$ enthält genau zwei verschiedene Elemente ${\displaystyle d_{1},d_{2}}$ mit ${\displaystyle d_{1}+1\equiv d_{2}\mod (n^{2}+n+1).}$ Dann ist ${\displaystyle {\mathcal {D}}-d_{1}=\{0,1,\ldots k_{n+1}\}}$ ebenfalls eine solche Differenzenmenge.

Singer verwendet Differenzenmengen, die 0 und 1 enthalten und deren Elemente alle in ${\displaystyle \{0,1,2,\ldots ,n^{2}+n-1\}}$ liegen, als Normalformen für Differenzenmengen und bezeichnet eine solche Differenzenmenge dann als reduzierte Differenzenmenge (englisch: reduced perfect difference set).^[2] Beutelspacher und Rosenbaum verwenden als Normalenform Mengen, die 1 und 2 enthalten und deren Elemente alle in ${\displaystyle \{1,2,3,\ldots ,n^{2}+n\}}$ liegen, ohne dafür eine gesonderte Bezeichnung einzuführen.^[1] Es gilt:

Falls eine Differenzenmenge der Ordnung ${\displaystyle n}$ existiert, dann existiert auch eine solche, die 0 und 1 enthält (also eine reduzierte Differenzenmenge), der Ordnung ${\displaystyle n}$.

Ist ${\displaystyle {\mathcal {D}}}$ eine Differenzenmenge der Ordnung ${\displaystyle n\geq 2}$, dann ist die folgendermaßen definierte Geometrie ${\displaystyle \mathop {\mathrm {P} } ({\mathcal {D}})}$ eine projektive Ebene der Ordnung ${\displaystyle n}$:^[1]

1. Die Punktmenge ist die Menge ${\displaystyle {\mathfrak {P}}=\{0,1,2,3,\ldots ,n^{2}+n\}\subseteq \mathbb {N} _{0}}$ von natürlichen Zahlen,
2. die Geradenmenge ${\displaystyle {\mathfrak {G}}}$ besteht aus den Teilmengen ${\displaystyle {\mathcal {D}}+i\subseteq {\mathfrak {P}},\quad i\in \{0,1,2,\ldots ,n^{2}+n\}}$,
3. die Inzidenzrelation ${\displaystyle I\subseteq ({\mathfrak {P}}\times {\mathfrak {G}})\cup ({\mathfrak {G}}\times {\mathfrak {P}})}$ von ${\displaystyle \mathop {\mathrm {P} } ({\mathcal {D}})}$ ist die mengentheoretische Enthaltenrelation zusammen mit ihrer Umkehrung: ${\displaystyle I={\in \cup \ni }.}$

Man sagt dann: Die so definierte projektive Ebene ${\displaystyle \mathop {\mathrm {P} } ({\mathcal {D}})=({\mathfrak {P}},{\mathfrak {G}},I)}$ „stammt von der Differenzenmenge ${\displaystyle {\mathcal {D}}}$“ ab.

Sei ${\displaystyle \kappa }$ eine Kollineation auf einer endlichen projektiven Geometrie. Wenn ${\displaystyle \kappa }$ die Punkte und Hyperebenen der Geometrie zyklisch permutiert, das heißt im Falle einer endlichen Ebene ${\displaystyle ({\mathfrak {P}},{\mathfrak {G}},I)}$ der Ordnung ${\displaystyle n}$: wenn für beliebige ${\displaystyle A\in {\mathfrak {P}},g\in {\mathfrak {G}}}$ gilt

${\displaystyle {\begin{array}{rrclcl}(1)\quad &{\mathfrak {P}}&=&\{\kappa ^{i}(A)&|&i\in \{1,2,3,\ldots ,n^{2}+n+1\}\}\quad {\mathrm {und} }\\(2)\quad &{\mathfrak {G}}&=&\{\kappa ^{i}(g)&|&i\in \{1,2,3,\ldots ,n^{2}+n+1\}\}\end{array}}}$

dann heißt die von ${\displaystyle \kappa }$ erzeugte Kollineationsgruppe ${\displaystyle \langle \kappa \rangle }$ ein Singer-Zyklus der Geometrie, speziell der Ebene.^[5]

Der Satz von Dembowski-Hughes-Parker besagt, dass eine Gruppe von Kollineationen einer projektiven Geometrie genau dann auf der Punktmenge transitiv operiert, wenn sie auf der Menge der Hyperebenen transitiv operiert.^[6] Daraus folgt, dass die geforderten Eigenschaften (1) und (2) für zyklische Kollineationsgruppen auf einer Ebene äquivalent sind.

Die folgenden Aussagen werden als Satz von Singer bezeichnet:

1. Jede endliche, desarguessche, projektive Geometrie besitzt einen Singer-Zyklus. Dieser kann so gewählt werden, dass er sogar nur aus Projektivitäten besteht.^[7]
2. Eine endliche projektive Ebene besitzt genau dann einen Singer-Zyklus, wenn sie isomorph zu einer von einer Differenzenmenge abstammenden Ebene ist.^[8]

Ist ${\displaystyle \mathop {\mathrm {P} } ({\mathcal {D}})=({\mathfrak {P}},{\mathfrak {G}},I)}$ eine solche Ebene in ihrer oben beschriebenen Darstellung durch die Differenzenmenge ${\displaystyle {\mathcal {D}}}$, dann ist

${\displaystyle \kappa :{\mathfrak {P}}=\{0,1,2,3,\ldots ,n^{2}+n\}\rightarrow {\mathfrak {P}};\quad x\mapsto x+1\mod (n^{2}+n+1)}$

eine Kollineation der Ordnung ${\displaystyle n^{2}+n+1}$, die somit einen Singer-Zyklus erzeugt.

Jede desarguessche projektive Geometrie endlicher Ordnung ist isomorph zu einem ${\displaystyle d}$-dimensionalen projektiven Raum ${\displaystyle \mathbb {P} ^{d}(K)}$ über einem endlichen Körper ${\displaystyle K=\mathbb {F} _{q}}$. Der Koordinatenvektorraum ${\displaystyle V}$ von ${\displaystyle \mathbb {P} ^{d}(K)}$ ist als ${\displaystyle K}$-Vektorraum isomorph zu dem endlichen Körper ${\displaystyle L=\mathbb {F} _{q^{d+1}}}$. Die multiplikative Gruppe ${\displaystyle (L^{\ast },\cdot )}$ ist zyklisch, also existiert ein erzeugendes („primitives“) Element ${\displaystyle \xi \in L}$ dieser Gruppe, mit dem ${\displaystyle \langle \xi \rangle =L^{\ast }}$ gilt. Die Abbildung

${\displaystyle \Xi :K^{d+1}\rightarrow K^{d+1}:\quad v\mapsto \xi \cdot v}$

ist ein ${\displaystyle K}$-Vektorraumautomorphismus. Nach Wahl einer Punktbasis in ${\displaystyle \mathbb {P} ^{d}(K)}$ kann dieser Automorphismus als Koordinatendarstellung einer Projektivität angesehen werden. Da ${\displaystyle \Xi }$ transitiv auf ${\displaystyle V^{\ast }\cong \left(K^{d+1}\right)^{\ast }}$ operiert, operiert auch die dadurch dargestellte Projektivität transitiv auf der Punktmenge von ${\displaystyle \mathbb {P} ^{d}(K)}$ und erzeugt daher einen Singer-Zyklus dieser projektiven Geometrie.

• Die Menge ${\displaystyle {\mathcal {D}}_{2}=\{1,2,4\}}$ ist eine Differenzenmenge der Ordnung 2, denn die sämtlichen Differenzen von verschiedenen Elementen ${\displaystyle d_{1},d_{2}\in {\mathcal {D}}_{2}}$ lauten (modulo 7):

${\displaystyle {\begin{array}{rcl|rcl|rcl}1-2&\equiv &6&1-4&\equiv &4&2-4&\equiv &5\\2-1&\equiv &1&4-1&\equiv &3&4-2&\equiv &2\end{array}}}$

Die 7 Geraden der projektiven Ebene zu dieser Differenzenmenge lauten, vergleiche auch die Abbildung rechts:

${\displaystyle {\begin{array}{rcl|rcl|rcl}{\mathcal {D}}_{2}+0&=&\{1,2,4\}&{\mathcal {D}}_{2}+1&=&\{2,3,5\}&{\mathcal {D}}_{2}+2&=&\{3,4,6\}\\{\mathcal {D}}_{2}+3&=&\{4,5,0\}&{\mathcal {D}}_{2}+4&=&\{5,6,1\}&{\mathcal {D}}_{2}+5&=&\{6,0,2\}\\{\mathcal {D}}_{2}+6&=&\{0,1,3\}&\end{array}}}$

Die Ebene ist isomorph zur Fano-Ebene.

• Die Mengen ${\displaystyle {\mathcal {D}}_{3}=\{1,2,4,10\}}$ bzw. ${\displaystyle {\mathcal {D}}_{4}=\{1,2,5,15,17\}}$ sind Differenzenmengen der Ordnung 3 bzw. 4.
• Die Menge ${\displaystyle {\mathcal {D}}_{5}=\{0,1,3,8,12,18\}}$ ist eine reduzierte Differenzenmenge der Ordnung 5.
• Da zu den Ordnungen 6, 10, 12 und 14 keine projektiven Ebenen existieren, gibt es auch keine Differenzenmengen dieser Ordnungen.
• Der Satz von Bruck-Ryser-Chowla liefert notwendige Bedingungen an die Ordnungen projektiver Ebenen. Natürliche Zahlen, die nach diesem Satz ausgeschlossen sind (Folge A046712 in OEIS), können auch nicht Ordnungen einer Differenzenmenge sein.

• Albrecht Beutelspacher, Ute Rosenbaum: Projektive Geometrie. Von den Grundlagen bis zu den Anwendungen (= Vieweg Studium: Aufbaukurs Mathematik). 2., durchgesehene und erweiterte Auflage. Vieweg, Wiesbaden 2004, ISBN 3-528-17241-X (Inhaltsverzeichnis [abgerufen am 1. April 2012]). 
• Daniel Hughes, Fred Piper: Projective planes (= Graduate texts in mathematics. Band 6). Springer, Berlin/Heidelberg/New York 1973, ISBN 3-540-90044-6. 
• James Singer: A theorem in projective geometry and some applications to number theory. In: Transactions of the American Mathematical Society. Band 43, Nr. 3, 1938, S. 377–385 (Volltext, PDF [abgerufen am 1. April 2012]). 

1. ↑ ^{a b c d e} Beutelspacher & Rosenbaum (2004)
2. ↑ ^{a b c} Singer (1938)
3. ↑ Im vorliegenden Artikel wird die 0 stets zu den natürlichen Zahlen ${\displaystyle \mathbb {N} _{0}=\{0,1,2,3,\ldots \}}$ gezählt.
4. ↑ Man beachte dazu, dass ${\displaystyle \delta }$ aufgrund der Eigenschaften der Modulo-Funktion mod stets eine Abbildung ist.
5. ↑ Zu Ehren von James Singer siehe Literatur, Beutelspacher & Rosenbaum (2004), 2.8
6. ↑ Hughes & Piper (1973)
7. ↑ Beutelspacher & Rosenbaum (2004), Kapitel 6
8. ↑ Beutelspacher & Rosenbaum (2004), Sätze 2.8.4, 2.8.5