# Apollonios-Kreisfüllung

Die Apollonios-Kreisfüllung$^{:S.374f}$ oder apollonische Kreispackung (englisch apollonian gasket oder apollonian circle packing, ACP) ist in der Geometrie eine Kreispackung, bei der in das Kreisbogendreieck zwischen drei sich paarweise berührenden Kreisen ein weiterer möglichst großer Kreis eingeschrieben und dieser Vorgang rekursiv fortgesetzt wird.
Die Namensgebung rührt vom Berührungsproblem des Apollonios$^{:S.241}$ her, das Apollonios von Perge formulierte. Das Problem beinhaltet unter anderem die Aufgabe, zu drei gegebenen Kreisen einen vierten zu finden, der die ersten drei berührt. Bei der Füllung berühren sich auch die vorgegebenen Kreise. Die Apollonios-Kreisfüllung ist eines der ersten jemals beschriebenen Fraktale. 2023 konnten zwei Studenten die anerkannte Lokal-Global-Vermutung über sie widerlegen.
* Apollonios-Kreisfüllungen
* (A) mit Radial­symmetrie
* (B) mit gefüllten Kreisen
* (C) primitiv ganzzahlig
* (D) mit unzutref­fender Lokal-Global-Vermutung
Es gibt Apollonios-Kreisfüllungen, in denen die Kehrwerte der Radien aller Kreise ganzzahlig sind wie in den Abbildungen (C) und (D). Auf diese Weise entsteht eine Verbindung zur Gruppen-$^{:S.2}$ und Zahlentheorie.

## Definitionen

Folgende Begriffe tauchen im Zusammenhang mit Apollonios-Kreisfüllungen auf:
* Die Krümmungen der Kreise sind die Kehrwerte ihrer Radien.
* Eine ganzzahlige Kreisfüllung (englisch integral packing) enthält ausschließlich Kreise mit ganzzahliger Krümmung.
* Ein Descartes-Quadrupel ist eine Gruppe von vier Zahlen {a,b,c,d}, die eine Lösung der descartschen Gleichung
       2·(a$^2$+b$^2$+c$^2$+d$^2$)−(a+b+c+d)$^2$=0 mit a+b+c+d>0$^{:S.2}$
    ist. Ein solches ganzzahliges Quadrupel besteht aus vier ganzen Zahlen.
* Das Stamm-Quadrupel (englisch root quadruple oder root packing) ist das Quadrupel mit den Krümmungen der vier größten Kreise in einer Füllung.$^{:S.16}$
* In einem primitiven ganzzahligen Descartes-Quadrupel sind die vier Zahlen teilerfremd.$^{:S.3}$
Die Ganzzahligkeit und Primitivität eines Stamm-Quadrupels überträgt sich auf die ihm entsprechende Apollonios-Kreisfüllung, die dann ebenso primitiv und ganzzahlig genannt wird.

## Eigenschaften
### Satz von Descartes

Der Satz von Descartes besagt, dass wenn {a,b,c,d} die Krümmungen von vier sich paarweise berührenden Kreisen sind, diese Krümmungen die descartsche Gleichung
    2·(a$^2$+b$^2$+c$^2$+d$^2$)−(a+b+c+d)$^2$=0
erfüllen. Die Krümmung eines umschreibenden Kreises geht hier mit negativem Vorzeichen ein. Wenn die Krümmungen der größten vier Kreise in der Füllung ganzzahlig sind, dann sind es deshalb auch die Krümmungen aller anderen Kreise in der Füllung. Im dritten Bild (C) oben hat der Umkreis die Krümmung 10 und die eingeschriebenen größten Kreise die Krümmungen 18, 23 und 27, womit auch alle anderen Kreise in der Füllung ganzzahlige Krümmungen aufweisen.
Wenn {a,b,c,d} ein Descartes-Quadrupel ist, dann ist es auch {a,b,c,d'} mit d'=2·(a+b+c)−d. Diese Krümmung hat derjenige Kreis, der durch Kreisspiegelung des Kreises mit Krümmung d an dem Kreis entsteht, der durch die drei Berührpunkte der Kreise mit Krümmungen a, b und c führt.$^{:S.15}$
Wenn {a,b,c,d} ein ganzzahliges Descartes-Quadrupel ist, dann folgt aus der descartschen Gleichung, dass (a+b+c+d)$^2$ eine gerade Zahl ist und somit auch die Summen a+b+c+d und −a+b+c+d gerade sind.

### Stamm-Quadrupel

Betrachtet wird ein primitives ganzzahliges Descartes-Quadrupel ⅅ=(a,b,c,d) mit a+b+c+d > 0.
ⅅ ist ein Stamm-Quadrupel, wenn$^{:S.15}$
    a ≤ 0 ≤ b ≤ c ≤ d und a+b+c ≥ d oder
    a ≤ 0 ≤ b ≤ c ≤ d und 0 < d ≤ 2(a+b+c)−d
Für jedes nicht negative ganzzahlige n ist (−n, n+1, n(n+1), n(n+1)+1) ein Stamm-Quadrupel.$^{:S.21}$ Hier kann der Kreis mit Krümmung n+1 wieder als Umkreis für eine Kreisfüllung (−n−1, n+2, (n+1)(n+2), (n+1)(n+2)+1) dienen und so weiter mit einem Ergebnis wie im Bild (B) oben. Diese Stamm-Quadrupel führen sämtlich auf #Symmetrische ganzzahlige Apollonios-Kreisfüllungen.
Alle Stamm-Quadrupel können mit der folgenden Methode gefunden werden.$^{:S.19}$ Dazu werden neue Variablen x, d$_1$, d$_2$ und m gemäß
    x = a, d$_1$ = a+b, d$_2$ = a+c, m = (a+b+c−d)/2
bzw.
    a = x, b = d$_1$−x, c = d$_2$−x und d = d$_1$+d$_2$−x−2m
eingeführt. Dann gilt:
* x$^2$+m$^2$ = d$_1$d$_2$
* ⅅ ist genau dann primitiv, wenn x, d$_1$ und d$_2$ teilerfremd sind.
* ⅅ ist genau dann ein Stamm-Quadrupel, wenn
       x < 0 ≤ 2m ≤ d$_1$ ≤ d$_2$
Wegen 2m ≤ d$_1$ und 2m ≤ d$_2$ ist 4m$^2$ ≤ d$_1$d$_2$ und daher 3m$^2$ ≤ d$_1$d$_2$−m$^2$ = x$^2$. Die unten stehende, in der Programmiersprache Python geschriebene Funktion stammquadrupel gibt für eine ganze Zahl a die zu −|a| passenden Stamm-Quadrupel.

### Restklassen und die Lokal-Global-Vermutung

In einer spezifischen primitiven ganzzahligen Apollonios-Füllung zeigt sich immer, dass die Krümmungen bei Division durch 24 mit Rest nicht alle möglichen Reste 0 bis 23 lassen, sondern nur sechs bis acht von diesen. Beispielsweise sind die Krümmungen der 15 größten Kreise in der Füllung 10–18–23–27 im Bild (C) oben
    −10, 18, 23, 27, 35, 47, 62, 63, 78, 83, 107, 110, 123, 135, 146.
Die Krümmung 10 des umschreibenden Kreises ist im Bild nicht angegeben und muss immer negativ genommen werden. Die Reste der Krümmungen bei Division durch 24 lauten
    14, 18, 23, 3, 11, 23, 14, 15, 6, 11, 11, 14, 3, 15, 2
was ohne Doppeltnennungen
    2, 3, 6, 11, 14, 15, 18, 23
entspricht. Die anderen 16 möglichen Reste, wie 1, 4 oder 5, können in der Füllung nicht vorkommen.
Denn in einer spezifischen primitiven ganzzahligen Apollonios-Füllung fallen die Krümmungen in sechs mögliche Restklassen­mengen modulo 24:$^{:S.6}$
    {(0, 1, 4, 9, 12, 16), (0, 5, 8, 12, 20, 21), (0, 4, 12, 13, 16, 21), (0, 8, 9, 12, 17, 20)
       (3, 6, 7, 10, 15, 18, 19, 22), (2, 3, 6, 11, 14, 15, 18, 23)}
Die Lokal-Global-Vermutung lautete, dass in einer Kreisfüllung (lokal) nur endlich viele Zahlen aus der jeweiligen Restklasse (global) nicht auftreten,$^{:S.41}$ was 2023 zwei Studenten widerlegen konnten.$^{:S.6}$ Ein Gegenbeispiel ist im Bild (D) oben gezeigt. Die Krümmungen der größten zehn Kreise sind dort
    −23, 48, 49, 52, 96, 105, 108, 193, 196, 208
und deren Reste modulo 24
    1, 0, 1, 4, 0, 9, 12, 1, 4, 16
womit alle Elemente der ersten oben genannten Restklassenmenge 𝕄=(0, 1, 4, 9, 12, 16) modulo 24 vertreten sind. Allerdings kommen unendlich viele Elemente aus jeder der Restklassen in 𝕄 nicht als Krümmung in der Füllung vor.$^{:S.4}$ Das ist nicht widersprüchlich, denn wenn man beispielsweise von allen positiven Ganzzahlen, die bei Division durch 24 den Rest eins lassen (das ist die Restklasse 1 modulo 24), die unendlich vielen Zahlen streicht, die den Rest 1 bei Division durch 48=2·24 lassen, bleiben immer noch unendlich viele Zahlen übrig.

### Asymptotisches Verhalten

Zu jeder Füllung F gibt es Konstanten c$_{0,1,2}$>0, die nur von F abhängen, sodass
* die Anzahl N(T) der Kreise mit einer Krümmung kleiner als T für T→∞ asymptotisch gleich c$_0$·T$^α$ ist,
* die Anzahl π(T) der Kreise mit einer primen Krümmung kleiner als T für T→∞ asymptotisch gleich c$_1$·T$^α$/log(T) ist,
* die Anzahl π$_2$(T) der Kreispaare mit Krümmungen, die kleiner als T sind und die einen Primzahlzwilling bilden, für T→∞ asymptotisch gleich c$_2$·T$^α$/log(T)$^2$ ist.
Darin ist α die Hausdorff-Dimension der Füllung.

### Hausdorff-Dimension

Die Hausdorff-Dimension der Füllung ist ungefähr
    α ≈ 1,3056867280498771846459862068510

## Spezialfälle
### Symmetrische ganzzahlige Apollonios-Kreisfüllungen

* Beispiele symmetrischer ganzzahliger Apollonios-Kreisfüllungen
* Kreisfüllung (−1, 2, 2, 3)
* Kreisfüllung (−3, 5, 8, 8)
* Kreisfüllung (−12, 25, 25,28)
* Kreisfüllung (−6, 10, 15, 19)
Die Tabelle enthält die Ausgaben von stammquadrupel(a) für a=0 bis a=14:
| (0, 0, 1, 1) | (−1, 2, 2, 3) | (−2, 3, 6, 7) | (−3, 4, 12, 13) |
| (−3, 5, 8, 8) | (−4, 5, 20, 21) | (−4, 8, 9, 9) | (−5, 6, 30, 31) |
| (−5, 7, 18, 18) | (−6, 7, 42, 43) | (−6, 10, 15, 19) | (−6, 11, 14, 15) |
| (−7, 8, 56, 57) | (−7, 9, 32, 32) | (−7, 12, 17, 20) | (−8, 9, 72, 73) |
| (−8, 13, 21, 24) | (−8, 12, 25, 25) | (−9, 10, 90, 91) | (−9, 11, 50, 50) |
| (−9, 14, 26, 27) | (−9, 18, 19, 22) | (−10, 11, 110, 111) | (−10, 14, 35, 39) |
| (−10, 18, 23, 27) | (−11, 12, 132, 133) | (−11, 13, 72, 72) | (−11, 16, 36, 37) |
| (−11, 21, 24, 28) | (−12, 13, 156, 157) | (−12, 21, 28, 37) | (−12, 17, 41, 44) |
| (−12, 16, 49, 49) | (−12, 21, 29, 32) | (−12, 25, 25, 28) | (−13, 14, 182, 183) |
| (−13, 15, 98, 98) | (−13, 18, 47, 50) | (−13, 23, 30, 38) | (−14, 15, 210, 211) |
| (−14, 18, 63, 67) | (−14, 19, 54, 55) | (−14, 22, 39, 43) | (−14, 27, 31, 34) |
Die rot markierten Quadrupel entsprechen Kreisfüllungen, die zu einem Durchmesser des Umkreises symmetrisch sind, auf dem der zweit- und drittgrößte Kreis der Füllungen liegen. Hier sind die viert- und fünftgrößten Kreise der Packung gleichgroß. Bei den grün markierten sind zwei der ersten vier größten Kreise in der Füllung gleich und die Symmetrieachse senkrecht zu ihrer Verbindungsachse. Bei den blau markierten Quadrupeln sind die Kreisfüllungen symmetrisch zu zwei zueinander senkrechten Symmetrieachsen.

### Apollonios-Kreisfüllung 0–0–1–1

Die über Apollonios-Kreisfüllungen geltenden Aussagen erlauben auch die Krümmung null der Kreise, die dann zu Geraden entarten. Die Packung 0–0–1–1 besitzt zwei „Kreise“ mit unendlich fernen Mittelpunkten; diese Kreise degenerieren zu zwei parallelen Geraden im Abstand zwei. Zwischen diesen liegen unendlich viele Kopien der Packung mit dem Stamm-Quadrupel. Sie ist die einzige unbeschränkte Apollonios-Kreisfüllung.$^{:S.3}$
Indem nur ein Stück zwischen den Berührpunkten von zwei benachbarten Kreisen mit Krümmung eins und den Geraden herausgetrennt wird, ihre Größe halbiert wird und nur die Kreise betrachtet werden, die eine der beiden Geraden berühren, bleiben Ford-Kreise zurück, die in der Zahlentheorie eine Rolle spielen.

## Apollonios-Gruppe

Die Apollonios-Gruppe A ist eine Gruppe, die von den vier selbstinversen Matrizen$^{:S.21}$
    ${\mathsf {S}}_{1}={\scriptstyle {\begin{pmatrix}-1&2&2&2\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}}},\,{\mathsf {S}}_{2}={\scriptstyle {\begin{pmatrix}1&0&0&0\\2&-1&2&2\\0&0&1&0\\0&0&0&1\end{pmatrix}}},\,{\mathsf {S}}_{3}={\scriptstyle {\begin{pmatrix}1&0&0&0\\0&1&0&0\\2&2&-1&2\\0&0&0&1\end{pmatrix}}},\,{\mathsf {S}}_{4}={\scriptstyle {\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\2&2&2&-1\end{pmatrix}}}$
erzeugt wird, mit denen sich sämtliche Elemente der Gruppe durch Matrizenmultiplikation berechnen. Wenn die Koeffizienten des Spaltenvektors q=(w,x,y,z)$^⊤$ ein Descartes-Quadrupel sind, dann ist es Mq mit M∈A ebenfalls.

## Verallgemeinerungen

Im n-dimensionalen Raum besteht eine Füllung aus n+2 paarweise berührenden n−1-Sphären, die sich in verschiedenen Punkten berühren.$^{:S.2}$ In der euklidischen Geometrie existieren ganzzahlige Packungen aus sich berührenden Sphären, die die verallgemeinerte Descartes-Gleichung$^{:S.512}$
    $\left(\sum _{i=1}^{n+2}r_{i}^{-1}\right)^{2}-n\sum _{i=1}^{n+2}r_{i}^{-2}=0$
befolgen, nur in zwei und drei Dimensionen; in höheren Dimensionen überlappen sich die Sphären.$^{:S.22}$$^{:S.3}$
Die Packung wurde auch in der höherdimensionalen sphärischen$^{:S.511}$ und hyperbolischen Geometrie untersucht.$^{:S.515}$ Es gibt auch dort ganzzahlige Packungen.$^{:S.7}$ Auf der rechten Seite obiger Gleichung ersetzt in sphärischer Geometrie ein negativer Wert$^{:S.11}$ die Null und in der hyperbolischen ein positiver.$^{:S.17}$$^{:S.3}$

## Geschichte

1643 entdeckte René Descartes den nach ihm benannten Satz, aber erst 1936 fiel es Frederick Soddy auf, dass es ganzzahlige Kreispackungen gibt, was er in Form des Gedichts „The Kiss Precise“ veröffentlichte; weitere Details dazu wurden 1937 bekannt. Der Name „apollonian packing“ geht auf Kasner und Supnick aus dem Jahr 1943 zurück und wurde 1982 von B. Mandelbrot populär gemacht, der einen Zusammenhang mit dem Werk von Apollonios von Perge um 200 v. Chr. feststellte.$^{:S.6}$