Rotationen und Operatordiskrepanz

Betrachtet man die Definition der Diskrepanzen und die der Gleichverteilung genauer, so erkennt man, daß das Grundproblem das ist, die Größe ${\mathcal F} := \parallel \frac{1}{n} \cdot \sum_{n=1} f({\mathbf x}_i) - \int_X f({\mathbf x}){\mathit d}\mu \parallel$ bei festem Maß $\mu$ im Kompaktum X für eine geeignete Klasse $\Phi$ von Funktionen $f$ und für eine geeignete Norm möglichst klein zu machen. Klarerweise ist unser Kompaktum stets die $S^{d-1}$ mit dem Oberflächenmaß $\omega$, bzw. mit dem normierten Oberflächenmaß $\omega^*$
Verwendet man die Maximumsnorm und die Klasse der Indikatorfunktionen der sphärischen Kugelkappen auf $S^{d-1}$, so erhält man die Kugelkappendiskrepanz aus Paragraph 2.
In diesem Paragraphen wird die Operatordiskrepanz betrachtet, die entsteht, wenn der Fehler ${\mathcal F}$ in der $L^2$-Norm für die Funktionen der Klasse $\Phi = \{ t \in L^2(S^{d-1}): \quad \parallel f \parallel _2 = 1 \}$ möglichst gering werden soll.
Die hier vorgestellte Methode, die auch bei anderen Diskrepanzen verwendet werden kann, ist konstruktiv, liefert aber schwächere Ergebnisse als die Methoden von Beck. Wir wollen uns daher mit einer Skizze begnügen; die genaue Beschreibung findet man in [57] und [58].
Die Methode sucht nicht nach Punkten auf der Kugel, sondern nach Rotationen der Kugel. Klarerweise wird dann durch die Drehachsen eine Menge von Punkten auf der Kugel erzeugt.

Es sei G stets die SO(3), das ist die Gruppe aller Rotationen im 3-dimensionalen Raum. Wir entnehmen G eine symmetrische und gleichverteilte Folge von Rotationen. Dabei wird ''gleichverteilt'' im üblichen Sinn gebraucht, und unter ''symmetrisch'' verstehen wir, daß die Folge mit jeder Rotation $\gamma$ auch die inverse Rotation $\gamma^{-1}$ enthält.
Ist eine derartige Folge $\{\gamma_1,...,\gamma_{2n} \} = \{\gamma_1,..,\gamma_n,\gamma_1^{-1},...,\gamma_n^{-1} \}$ gegeben, so definieren wir uns für alle ${\mathit f} \in \Phi$ den Heckeoperator

$$Tf := \sum_{i=1}^n ( f(\gamma_i {\mathbf x}) + f(\gamma_i^{-1} {\mathbf x}) ).$$

Es sei nun:

$$\delta f := \frac{1}{2n} \cdot \sum_{i=1}^{2n} f(\gamma_i {... ...\cdot \int_{S^2} f({\mathbf x}){\mathit d}\omega({\mathbf x})$$

und für die Folge $\Gamma = \{\gamma_1,...,\gamma_n \}$ sei

$${\mathit O}(\Gamma) = {\mathit O}(\gamma_1,...,\gamma_n) = ... ...allel f \parallel = 1 }\{ \parallel \delta f \parallel _2 \}.$$

Dann verstehen unter $O_{2n}:= \inf_{\Gamma \in {\mathit G}}{\mathit O}(\Gamma)$ die Operatordiskrepanz, wobei wir das Infimum über alle möglichen Folgen $\Gamma$ bilden.
Wie die Autoren in [57] aufzeigen, ist läßt der Hecke-Operator, der die Operatornorm $\parallel T \parallel \quad = 2n$ hat, jeden Raum der sphärischen harmonischen Spektralanalyse invariant.
Der Raum $H_n$ der sphärischen harmonischen Spektralanalyse der Ordnung n ist definiert als der Eigenraum des Laplace-Operators $\Delta$ zu dem Eigenwert $n \cdot (n+1)$ und hat die Dimension $2n+1$; der Laplace-Operator $\Delta$ ( s.S.58) zerlegt den $L_2(S^2)$-Raum in die direkte Summe der $H_n$ [57, 67].
Die Legendre-Polynome $P_n$ werden erzeugt durch die Gleichung:

$$P_n(x) = \frac{1}{2^n \cdot n!} \cdot \frac{{\mathit d}}{{\mathit d} x^n} (x^2-1)^n$$

Sie bilden eine wichtige Funktionenfamilie der Räume $H_n$ und sind zueinander orthogonal.
Weiters gibt es eine Orthonormalbasis $\{{\mathit b}_{j,n}\}$ von $H_n$, die den Heckeoperator T diagonalisiert [57]. Ist $\rho_{j,n}$ der zum Basiselement ${\mathit b}_{j,n}$ zugehörigen Eigenwert, so gilt:

$$T({\mathit b}_{j,n}) = \rho_{j,n} \cdot {\mathit b}_{j,n}.$$

Dann ist Spur von $T^s = sp \quad T^s = \sum \rho^s_{j,n}$ (mit Summe über $\vert j \vert < n$).
Bezeichnet $W_s$ die Menge aller ''Wörter der Länge s'' in $\{\gamma_1,...,\gamma_{2n} \}$, so kann $T^s$ auch geschrieben werden als $T^s = \sum_{\gamma \in W_s} f(\gamma {\mathbf x})$. Diese Summe ist gleich $\sum_{\gamma \in W_s} r_{\gamma} \cdot (\sin(2n+1) \cdot (r_{\gamma}/2)) / (\sin(r_{\gamma}/2)$, wo $r_{\gamma}$ den Drehwinkel der Rotation $\gamma$ bezeichnet. Ist $m_s$ die Anzahl aller Wörter der Länge s, die die Identität buchstabieren, so folgt, da $r_{\gamma} = 0 \Leftrightarrow r = Id$, [57] :

$$\lim_{n \to \infty} \frac{1}{2n+1} \cdot \sum \rho^s_{j,n} = m_s.$$

Diese Grenzwertbeziehung ermutigt, durch $\int_{-\infty}^{+\infty} t^2 {\mathit d}\mu(t) = m_s$ für $s \geq 0$ ein Wahrscheinlichkeitsmaß zu definieren.
Bezeichnet $\mu_n$ das Spektralmaß von $T_{\vert H_n}$, so wird durch die angegebene Grenzwertbeziehung die Konvergenz der Maße in der schwach-*-Topologie aufgezeigt; d.h.: für jede stetige Funktion $f$ gilt: $\int f {\mathit d}\mu_n \to \int f {\mathit d}\mu$
Das Spektralmaß ist das Maß, das jedem Eigenwert eines Operators die Masse 1/(Dimension des Raumes) zuordnet; dabei werden die Eigenwerte gemäß ihrer Vielfachheit gezählt.
Daher gibt $\mu$ den Ort an, an dem der Großteil des Spektrums [=Großteil der ''Masse''] von T zu finden ist. Speziell besteht der Träger von $\mu$ (:= $supp \; \mu:=\{{\mathbf x} \in S^2: \mu({\mathbf x}) \neq 0\}$) aus Grenzwerten der Eigenwerte von T.
Weiters wird das Maß $\mu$ allein durch die natürliche Zahl $m_s$ definiert und hängt daher nur von der durch $\{\gamma_1...\gamma_n\}$ erzeugten Gruppe $\Gamma$ ab. Aus diesem Grund kann das Maß $\mu$ auch als Markovkette auf $\Gamma$ interpretiert werden [57].
Damit die Markovkette translationsinvariant wird und das Spektralmaß $\mu$ besitzt, muß die Wahrscheinlichkeit, von ${\mathit g} \in \Gamma$ nach $\gamma_i {\mathit g} [\in \Gamma]$ zu kommen, überall gleich 1/2n sein [57].
$m_s$ entpuppt sich in dieser Uminterpretation als die Anzahl der Wege der Länge s, die von einem Punkt g ausgehend zum selben Punkt g zurückführen.
Eine derartige Markovkette wurde von Kesten [46] untersucht. Er bewies, daß unter gewissen Bedingung das größte Trägerelement $\lambda = \max supp \;$mu $= \limsup_{n \to \infty} (m_s)^{1/s}$ von $\mu$ gleich 2n ist und sonst stets $\geq 2 \cdot \sqrt{2n-1}$ ausfällt.
Die gesuchte Diskrepanz $O_{2n}$ ist gleich dem zweitgrößten Eigenwert von T/2n [57]. Aus dem Satz von Kesten folgt daher:

$$O_{2n} \geq \sqrt{2n-1}/n$$

In umgekehrter Richtung gilt: $O(\gamma_1,..,\gamma_{2n} ) \ll (\log n)/(n^{1/2})$.
Ein Zusammenhang zwischen $O_{2n}$ und T/2n wird bereits deutlich, wenn man die Norm $\parallel \delta f \parallel$ betrachtet:

$$\parallel \delta f \parallel = \parallel \frac{1}{2n} \cd... ... f({\mathbf x}) {\mathit d}\omega({\mathbf x}) \parallel =$$

$$= \parallel \frac{1}{2n} \cdot \sum_{i=1}^{2n} f(\gamma_i {... ...ac{1}{2n} \cdot T \parallel \quad minus \quad \mathtt{Konst}.$$

Es wird in [58] auch gezeigt, daß man für jede Primzahl p mit $p \equiv 1(4)$ eine Menge $\Gamma = \{\gamma_1,...,\gamma_{(p+1)/2}, \gamma^{-1}_1,..,\gamma^{-1}_{(p+1)/2} \}$ finden kann, für die $O(\Gamma) = 2 \cdot \sqrt{p}$ ist.
Die zitierten Artikel enthalten auch Computerprogramme, mit denen optimale Rotationsanordnungen berechnet werden können. Tabellarische und, für spezielle Werte, auch graphische Ausdrucke geben einen Überblick über die optimalen Anordnungen.
Für die sphärische Kappendiskrepanz und die Diskrepanz des $L_2$-Mittels gilt:
Es sei:

$$B_N({\mathbf{\mathit C}}):= \char93 \{\gamma_i {\mathbf x} \in {\mathbf{\mathit C}} \}/n-\vert {\mathbf{\mathit C}} \vert$$

$$D(\gamma_1 {\mathbf x},...,\gamma_n {\mathbf x}) := \sup \vert B_N({\mathbf{\mathit C}}) \vert$$

$$T({\mathbf x}_1,...,{\mathbf x}_n) := (\int_{{\mathbf{\math... ...}})\vert^2 {\mathit d}\omega({\mathbf{\mathit C}}) )^{1/2}$$

Dann ist:

1. $D(\gamma_1 {\mathbf x},...,\gamma_n {\mathbf x}) \ll (\log n)^{2/3}/n^{1/3}$
2. $T({\mathbf x}_1,...,{\mathbf x}_n ) \ll n^{1/2} \cdot (\log n)$.

Die vergleichbaren Beck'schen Resultate lauten:

1. $D(\gamma_1 {\mathbf x},..,\gamma_n {\mathbf x}) \ll (\log n)^{1/2}/n^{3/4}$
2. $T({\mathbf x}_1,...,{\mathbf x}_n ) \ll n^{1/2}$,

sind also durchwegs schärfer, aber nicht konstruktiv.

Ein merkwürdiger Satz über die Verteilung von Punkten auf der $S^2$, ist folgender [25]:
Es gibt zwei Konstante $c_1,c_2 >0$, sodaß es
(i) für jede natürliche Zahl n und für jedes $\alpha$ mit $0 < \alpha < 2$ eine Anordnung von n Punkten auf $S^2$ gibt, in der jeder Punkt von mindestens $c_1 \cdot \log^* n$ anderen Distanz $> \alpha$ hat, und daß es
(ii) für jede natürliche Zahl n eine Anordnung von n Punkten auf $S^2$ gibt, in der jeder Punkt von mindestens $c_2 \cdot n^{1/3}$ anderen Punkten Abstand $\sqrt{2}$ hat.
[Haben zwei Punkte auf der $S^{d-1}$ den Abstand $\sqrt{2}$, so stehen die zugehörigen Ortvektoren orthogonal aufeinander.]
Mit $\log^* n$ wird dabei die kleinste natürliche Zahl r bezeichnet, sodaß man, bei Start in n, die log-Funktion r-mal iterieren muß, um einen Wert $\leq 1$ zu erhalten.
Bezeichnen wir mit $f^k$ die k-te Iteration der Funktion f, so ist also $\log^* n = \min \{ r \in {\rm I\mkern-3mu N}: (\log n)^r \leq 1 \}$. Diese Funktion ist Null für n = 1; für $2 \leq n \leq 15$ ist ihr Wert gleich 2; den Wert 3 nimmt sie an für $16 \leq n \leq 3814279$ , usw.

Die Beweisidee für (i) ist folgende :
Wir fixieren uns ein $\epsilon > 0$, sodaß der Durchmesser eines Breitenkreises vom Abstand $\epsilon$ von der Äquatorebene stets größer $\alpha$ ist [ $2 \cdot \sqrt{1-\epsilon^2} > \alpha$]. Die beiden Breitenkreise, die von der Äquatorebene den Abstand $\epsilon$ haben, begrenzen dann einen Parallelstreifen

$$S_{\epsilon} = \{(x_1,x_2,x_3) \in S^2 : \vert x_3 \vert \leq \epsilon\}.$$

Für jedes $k \geq 1$ wird nun eine Punktmenge ${\mathcal P}$ konstruiert, in der jeder Punkt von zumindest k anderen Abstand $\alpha$ besitzt.
Es sei für ein natürliches k eine derartige Menge ${\mathcal P} = \{P_1,..,P_{n(k)}\}$ gegeben, die sich zudem in einem kleinen $S_{\epsilon}$-Streifen [ $\epsilon(k)< \epsilon$] um den Äquator befinde. (für k=1 bestehe ${\mathcal P}$ aus zwei Punkten mit Abstand $\alpha$ auf dem Äquator.) Es sei U ein Punkt in der Nähe des Nordpols, von dem er den (beliebig) kleinen Abstand $\delta$ habe.
Wir lassen die Punktmenge ${\mathcal P}$ um die Achse -UU rotieren. Die Kugel wird dabei so um die Achse -UU gedreht, daß der Punkt $P_1$ auf einen Punkt $P_1'$, der von $P_1$ den Abstand $\vert P_1,P_1'\vert = \alpha$ besitzt, abgebildet wird. Diese Rotation bezeichen wir mit $\pi_1$. Analog dazu sei $\pi_i$ die Drehung um -UU, die $P_i$ auf $P'_i$ überführt. Auch hier sei $\vert P_i,P'_i\vert = \alpha$. Es sei ${\mathcal P}^{(0)} = {\mathcal P}$, ${\mathcal P}^{(1)} = \pi_1 ({\mathcal P}^{(0)})$. Sind die Mengen ${\mathcal P}^{(0)}$, ${\mathcal P}^{(1)}$,..., ${\mathcal P}^{(i-1)}$ bereits vorhanden, so wird ${\mathcal P}^{(i)}$ definiert durch [ $1 < i \leq n(k)$]:

$${\mathcal P}^{(i)} := \pi_i({\mathcal P}^{(0)} \cup {\mathcal P}^{(1)} \cup ... \cup {\mathcal P}^{(i-1)}).$$

Die so erhaltenen Mengen werden zuletzt noch in ${\mathcal P}^*$ vereinigt:

$${\mathcal P}^* := {\mathcal P}^{(0)} \cup {\mathcal P}^{(1)} \cup ... \cup {\mathcal P}^{(n(k))}.$$

Entscheidend für diese rekursive Konstruktion ist eine gute Wahl der Achse -UU. Mit einer geeigneten Wahl kann man nämlich erreichen, daß alle Drehungen $\rho_i$ existieren, daß die Mengen ${\mathcal P}^{(0)}$, ${\mathcal P}^{(1)}$,..., ${\mathcal P}^{(n(k))}$ paarweise disjunkt sind, und daß sich die Menge ${\mathcal P}^*$ auf einem $\epsilon (k+1)$-Streifen mit $\epsilon (k+1) < \epsilon$ um den Äquator befinden.
Aufgrund unserer Rekursion ist $\char93 {\mathcal P}^{(i)} = 2 \cdot \char93 {\mathcal P}^{(i-1)} = 2^{i-1} \cdot \char93 {\mathcal P}^{(0)}$, da bei Bildung von ${\mathcal P}^{(i)}$ jeder Punkt von ${\mathcal P}^{(i-1)}$ einen Bildpunkt [ $1 < i \leq n(k)$] erhält. Da alle Mengen paarweise disjunkt sind, enthält die Vereinigung von ${\mathcal P}^{(i-1)}$ und $\pi_i({\mathcal P}^{(i-1)} )$ genau $2 \cdot \char93 {\mathcal P}^{(i-1)}$ Punkte. Punkte. Setzen wir $n(k+1):= n(k) \cdot 2^{n(k)}$, so ist:

$$\char93 {\mathcal P}^* = \char93 \{{\mathcal P}^{(0)} \cu... ...(n(k))} \} = \sum_{i=0}^{n(k)} \char93 {\mathcal P}^{(i)} =$$

$$\char93 {\mathcal P}^{(0)} + \sum_{i=0}^{n(k)} (2^{i-1} \cd... ...= \char93 {\mathcal P}^{(0)} \cdot [1+2^{n(k)}-1] = n(k+1),$$

also $\char93 {\mathcal P}^* = n(k+1)$. Es ist $x \cdot 2^x = e^{\ln x + x \cdot \ln 2} < e^x$ ist für $x > 5.7$. Daher können wir mit vollständiger Induktion zeigen, daß gilt:

$$\log^* n(k+1) = k+1 \Leftrightarrow n(k+1) < e^{(k+1)}$$

Denn : $n(1) = 2 < e$; $n(2) = 8 < e^e = e\hat{ } e$ (Dabei sei $e^k$ die k-fache Potenz von e: $e\hat{ } e\hat{ } ...\hat{ }e$)
Ist $n(k) < e\hat{ } e\hat{ }...\hat{ }e$ (k mal), so ist:

$$n(k+1) = n(k) \cdot e^{n(k)} < n(k) \cdot e\hat{ } e\hat{ }... ...at{ }e < e\hat{ } e\hat{ }... \hat{ }e \hat{ }e = e^{(k+1)}$$

In der Menge ${\mathcal P}^*$ hat jeder Punkt von mindesten (k+1) anderen genau den Abstand $\alpha$, wie man durch Nachrechnen beweist.
Der Beweis der zweiten Aussage stützt sich auf einen analogen Satz der Ebene, dessen Konstruktion auf die Sphäre übertragen wird.