Invarianzprinzip

Nun wollen wir Diskrepanzkonzepte einführen, die abhängen vom Abstand der Punkte $\{P_1,..,P_n\}$ untereinander, und die darauf basieren, Mittelwerte von Abstandfunktionen und Abstandfunktionalen zu bilden.
Wir stellen uns dabei vor, in jedem der n ausgewählten Punkte $\{P_1,..,P_n\}$ befindet sich eine Energieeinheit. Wir suchen zunächst nach einer Auswahl $\{P_1,..,P_n\}$, die sich bei jeder Kraft, die nur zwischen je zwei Punkten interagiert, im Gleichgewicht befindet.

Leech [49] bewies, daß eine Anordnung, die sich bei jeder Kraft, die nur vom Abstand der Punkte untereinander abhängt, im Gleichgewicht befindet, eine hohe Symmetrie aufweisen muß:
Sie muß Rotationssymmetrie in Bezug auf jede Achse, die durch einen Punkt der Anordnung und den Kugelmittelpunkt hindurchgeht, aufweisen.

Die Anordnungspunkte können daher nur Eckpunkte von Polyedern sein, die der Sphäre einbeschrieben sind und bei denen alle Ecken auf Rotationsachsen liegen. Daher kommen als Lösungen nur in Betracht:

1. reguläre Polygone mit Ecken auf einem Großkreis
2. Platonische Körper, deren Dualkörper und Eckableitungen
3. bestimmte Polyeder, deren Eckenmenge durch Vereinigung von Ecken von Polyedern der ersten beiden Fälle entstehen.

[Unter einer Eckableitung ist hier die konvexe Hülle der Kantenmittelpunkte des Ausgangspolyeders zu verstehen.]
Es kann daher das gestellte Problem nur für n = 4, 6, 8, 10, 12, 14, 18, 20, 26, 30, 32, 42, 50, 62 gelöst werden [49].
Sind auf einer d-dimensionalen Kugel d+2 Punkte zu verteilen, so liegen sie meist optimal, wenn sie die Ecken eines Simplex bilden. Dieser Sachverhalt, der bereits bei den Lagerungsproblemen auftaucht, gilt auch für den Betrags des inneren Produktes [79]. Es ist dann:

$$\sum_{1 \leq i<j \leq d+2} \vert P_i \cdot P_j \vert ^{\alpha} \geq \frac{d+2}{2(d+1)^{\alpha-1}}$$ (2.17)

Nun soll der Begriff ''Abstand'' allgemeiner definiert werden. Dazu sei (wie in [2.3]) G = SO(3) die spezielle orthogonale Gruppe auf $S^{d-1}$, also die Gruppe der Drehungen der $S^{d-1}$. Für $\tau \in {\mathit G}$ sei $\int_{\mathit G} f {\mathit d}\tau$ das Haar'sche Integral der Funktion $f$. Dieses ist im wesentlichen gleich dem Integral über $S^{d-1}$ in Bezug auf das Oberflächenmaß ${\mathit d}\omega$.
Es sei N = (1,0,..,0) der ''Nordpol'' der $S^{d-1}$. $P_1$ und $P_2$ seien zwei Punkte der $S^{d-1}$ und ${\mathit g} = {\mathit g}(z)$ sei eine auf [0,1] definierte integrable Kernfunktion. Dann ist

$${\mathbf{\mathit d}}({\mathbf x}_1,{\mathbf x}_2):= {\mat... ...mathit G} \int_a^b {\mathit g}(z){\mathit d}z{\mathit d}\tau.$$ (2.18)

für positives g eine Metrik auf $S^{d-1}$ [78]. Die Integrationsgrenzen werden dabei auf folgende Weise erhalten:
Wir unterwerfen die Punkte $P_1$ und $P_2$ der Drehung $\tau$. Von den gedrehten Vektoren $\tau P_1$ und $\tau P_2$ nehmen wir jeweils die erste Koordinate und ordnen der Größe nach. Das können wir so anschreiben: $a = \min \{ \tau P_1 \cdot N, \tau P_2 \cdot N \}$ und $b = \max \{ \tau P_1 \cdot N, \tau P_2 \cdot N \}$. Das Funktional ${\mathbf{\mathit d}}$ ist unabhängig von $\tau$, denn für jedes $\tau_1 \in {\mathit G}$ sind die Grenzen der inneren Integration:
$a = \tau_1 \tau P_1 \cdot N = \tau' P_1 \cdot N$ und $b = \tau_1 \tau P_2 \cdot N = \tau' P_2 \cdot N$.
Da über ganz G = SO integriert wird, ist

$${\mathbf{\mathit d}}(\tau_1 {\mathbf x}_1,\tau_1 {\mathbf x}_2 ) = {\mathbf{\mathit d}}({\mathbf x}_1,{\mathbf x}_2).$$

Für ${\mathit g} \equiv 1$ ist $\int_a^b {\mathit g}(z){\mathit d}z = b-a = \vert \tau P_1 \cdot N - \tau P_2 \cdot N\vert$. Da die Drehung eine lineare Transformation ist, gilt:

$$\vert \tau P_1 \cdot N - \tau P_2 \cdot N \vert = \vert ... ... \cdot N \vert = \vert (P_1 - P_2 ) \cdot \tau^{-1} N \vert$$

$\tau$ bewegt sich durch ganz G und daher können wir von N aus jeden Punkt der $S^{d-1}$ durch eine Drehung erreichen. Somit können wir $\tau^{-1} N$ durch einen Punkt ${\mathbf u}$ der $S^{d-1}$ und das Haar'schen Integrals durch das Oberflächenintegral ersetzen.
Für ${\mathit g} \equiv 1$ ergibt sich daher, wenn ${\mathbf x}$ einen Punkt der $S^{d-1}$ bezeichnet:

$${\mathbf{\mathit d}} (P_1,P_2) = \int_{S^{d-1}} \vert (P_1-P_2) \cdot {\mathbf u}\vert {\mathit d}\omega({\mathbf u}) =$$

$$\parallel P_1-P_2 \parallel_2 \cdot \int_{S^{d-1}} \vert... ...P_1-P_2 \parallel_2 \vert {\mathit d}\omega({\mathbf u}) =$$

$$\parallel P_1-P_2 \parallel_2 \cdot \int_{S^{d-1}} \ver... ...hbf x} \cdot {\mathbf u}\vert {\mathit d}\omega({\mathbf u}).$$

Das Integral kann man durch folgende Überlegung berechnen :
Das inneren Produkt zweier Vektoren ist bekanntlich gleich dem Produkt des Betrages des ersten Vektors mit dem Betrag der Projektion des zweiten Vektors auf den ersten.
Es sei ${\mathcal H}$ die Hyperebene, die normal zum ersten Vektor steht und die den Ursprung der $S^{d-1}$ enthält. Wir halten nun den Vektor ${\mathbf x}$ in ${\mathbf x} \cdot {\mathbf u}$ fest und bewegen ${\mathbf u}$ über ganz $S^{d-1}$ . Dann überstreicht die vektorielle Projektion von ${\mathbf u}$ die (d-1)-dimensionale Kugel, die von ${\mathcal H}$ aus $B^d$ herausgeschnitten wird, aus Symmetriegründen zweimal vollständig.
Daher hat das obige Integral den Wert $2 \cdot \kappa_{d-1}$:

$$\int_{S^{d-1}} \vert {\mathbf x} \cdot {\mathbf u}\vert d\omega({\mathbf u}) = 2\kappa_{d-1},$$ (2.19)

Faßt man die soeben durchgeführten Überlegungen zusammen, so erkennt man, daß durch die Kernfunktion ${\mathit g} \equiv 1$ der euklidischen Abstand erzeugt wird, wenn man von einer multiplikativen Konstanten absieht.

Damit können wir definieren:
Es sei ${\mathcal P}:=\{P_1,...,P_n\}$ eine n-elementige Menge von Punkten der $S^{d-1}$ und ${\mathbf{\mathit d}}$ sei ein Abstand im Sinne von (2). Unter einer Potenzsumme verstehen wir dann das Funktional:

$${\huge E}_{\alpha}({\mathcal P}):= \sum_{i<j} {\mathbf{\mathit d}}(P_i,P_j)^{\alpha}$$

bzw.

$${\huge E}_{\alpha}:= \max_{{\mathcal P}}{\huge E}_{\alpha}({\mathcal P})$$

Für sehr große, natürliche $\alpha$ nähert sich die optimale Verteilung der Potenzsumme der optimalen Verteilung des Unterdeckungsproblemes [ s. I.6].
Ähnliche Potenzsummen kann man auf jedem konvexen Körper definieren; der Körper, bei dem diese Summen für den euklidischen Abstand am größten werden können, ist stets die Kugel, wie Groemer [36] gezeigt hat.

Ist ${\mathbf{\mathit C}}(t):=\{{\mathbf y} \in S^{d-1}: {\mathbf y} \cot N \leq t \}$ die Kappe um N mit Radius t, so gilt für $\alpha = 1$ das ''Invarianzprinzip'' [78]:

$${\huge E}_1({\mathcal P})+ \int_{-1}^{+1} {\mathit g}(t) \c... ...2 {\mathit d}\tau \Bigr) {\mathit d}\omega(t) = K \cdot n^2$$ (2.20)

Die Konstante K ist dabei gleich $1/2 \cdot \omega_{d-1} \cdot \int \int {\mathbf{\mathit d}}({\mathbf x},{\mathbf y}) {\mathit d}\omega({\mathbf x}) {\mathit d}\omega({\mathbf y})$, wobei jedesmal über $S^{d-1}$ zu integrieren ist, $\omega^*$ ist wiederum das normierte Oberflächenmaß auf $S^{d-1}$.

Der Beweis benötigt man das Lemma ([78]; [1]):
Für reelle Zahlenfolgen $p_1 \leq ... \leq p_u$ und $q_1 \leq ... \leq q_v$ gilt:

$$\sum_{i,j} \int_{p_i}^{q_j} {\mathit g}(z){\mathit d}z - \... ...z - \sum_{i<j} \int_{q_i}^{q_j} {\mathit g}(z){\mathit d}z =$$

$$\int_{-\infty}^{+\infty} {\mathit g}(x) \cdot {\mathcal G}(x) \cdot ( {\mathcal G}(x) - (u-v) ){\mathit d}x$$

mit ${\mathcal G}(x) := \char93 \{ p_i \leq x \} - \char93 \{q_j \leq x \}$.

Für u = v und ${\mathit g} \equiv 1$ ist $\int_{-\infty}^{+\infty} {\mathcal G}^2 dx \geq \int_{-\infty}^{+\infty} \vert {\mathcal G} \vert ^2 dx = \sum_{i=1}^n \vert P_i,Q_i \vert$. Zum Beweis des Satzes setzen wir $u = v = n$ und geben uns zwei Punktfolgen ${\mathcal P}_p = \{P_1,..,P_n \}$ und ${\mathcal P}_q = \{ Q_1,..,Q_n \}$ vor. Dann wählen wir drei Transformationen $\tau,\phi_1,\phi_2 \in {\mathit G}$ und setzen

$p_i := \tau f_1 P_i \cdot N$ und $q_i := \tau f_2 Q_j \cdot N$.

Damit schreibt sich die rechte Seite von (4) an als:

$$2 \cdot K \cdot n^2 = \int_{\mathit G} \int_{\mathit G} ... ...hi_1 P_i,\phi_2 Q_j ) {\mathit d}\phi_1{\mathit d}\phi_2 .$$

Jetzt rufen wir uns (2) in Erinnerung. Die Anwendung des Lemmas auf $\sum_{i,j}{\mathbf{\mathit d}}(\phi_1 P_i,\phi_2 Q_j)$ ergibt dann:

$$\sum_{i,j} {\mathbf{\mathit d}}(\phi_1 P_i,\phi_2 Q_j ) = ... ...q_j}{\mathit g}(z) {\mathit d}z {\mathit d}\tau = [Lemma] =$$

$$\int_{\mathit G} \bigl( \int_{-\infty}^{+\infty} {\mathit ... ..._i}^{q_j}{\mathit g}(z) {\mathit d}z \bigr) {\mathit d}\tau =$$

$$\int_{\mathit G} \int_{-1}^{+1} {\mathit g}(z) {\mathcal G}... ...\int_{q_i}^{q_j}{\mathit g}(z) {\mathit d}z {\mathit d}\tau =$$

$$\int_{\mathit G} \int_{-1}^{+1} {\mathit g}(z) \cdot ( {\ma... ...hit d}}(p_i,p_j) + \sum_{i<j} {\mathbf{\mathit d}}(q_i,q_j),$$

da ${\mathbf{\mathit d}}$ unabhängig von der Wahl der Transformationen ist.
Dabei ist

$${\mathcal G}(z,\tau):= \char93 \{ p_i \cdot N \leq z\} - \char93 \{q_i \cdot N \leq z \} =$$

$$\char93 \{ \tau \phi_1 P_i \cdot N \leq z\} - \char93 \{\tau \phi_2 P_i \cdot N \leq z \} =$$

$$\char93 \{ {\mathcal P}_p \cup \phi_1 ({\mathbf{\mathit C... ...hi_2 ({\mathbf{\mathit C}}(z)) \} =: \char93 _p - \char93 _q.$$

Daraus ergibt sich: $2 \cdot K \cdot n^2 = \frac{n^2}{\omega_{d-1}} \cdot \int \!\! \int_{S^{d-1}} ... ...bf x},{\mathbf y}) {\mathit d}\omega({\mathbf x}){\mathit d}\omega({\mathbf y})$ =

$$\int \!\! \int_{S^{d-1}} \sum_{i,j}{\mathbf{\mathit d}}(\ph... ...it d}}(p_i,p_j) + \sum_{i<j} {\mathbf{\mathit d}}(q_i,q_j)$$

Ist $n^* = n \cdot \omega^* ({\mathbf{\mathit C}}(z))$, so ist $\int_{\mathit G}(\char93 _p-n^*) {\mathit d}\phi_1 = 0$, da $n^*$ gleich dem Erwartungswert von $\char93 _p$ ist. Daher ist der Rest gleich:

$$\int_{-1}^{+1} \int_{\mathit G} \! \! \int_{\mathit G} {\m... ...r93 _q )^2 {\mathit d}\phi_1 {\mathit d}\phi_2 {\mathit d}z =$$

$$\int_{-1}^{+1} \int_{\mathit G} {\mathit g}(z) \cdot (\c... ...cdot (\char93 _q - n^* )^2 {\mathit d}\phi_2 {\mathit d}z -$$

$$-2 \cdot \int_{-1}^{+1} \int_{\mathit G} {\mathit g}(z) \cd... ... \cdot (\char93 _q - n^* ) {\mathit d}\phi_2 {\mathit d}z =$$

$$= \int_{-1}^{+1} \int_{\mathit G} {\mathit g}(z) \cdot (... ...cdot (\char93 _q - n^* )^2 {\mathit d}\phi_2 {\mathit d}z .$$

Daher ist $2 \cdot K \cdot n^2$ gleich der Summe der Diskrepanzen von ${\mathcal P}_p$ und ${\mathcal P}_q$ in Bezug zu ${\mathit g}(x)$. Setzen wir nun ${\mathcal P}_p = {\mathcal P}_q$ [dh. $P_i = Q_j$ für $1 \leq i \leq n$] und dividieren wir beide Seiten der Gleichung durch zwei, so erhalten wir die Behauptung $\diamondsuit$
Wenn wir das Integral auf der linken Seite der Gleichung (5) durch die Abschätzungen (2.4) und (2.8) ersetzen, so sehen wir, daß es Konstanten $c_0$, $c_1$ und $c_2$ gibt, die nur abhängig sind von der Dimension d, sodaß gilt:

$$c_1 \cdot n^{1-1/(d-1)} < c_0 \cdot n^2 - E_1 < c_2 \cdot n^{1-1/(d-1)}$$