Extremal densities for forbidden configurations in $S$-smooth numbers

1. Problemstellung

Das Paper untersucht ein extremales kombinatorisches Problem im Kontext der S-glatten Zahlen (S-smooth numbers).

• Definition: Sei $S = \{p_1, \dots, p_r\}$ eine endliche Menge von $r \ge 2$ verschiedenen Primzahlen. Die Menge $M(S)$ bezeichnet das multiplikative Halbgruppe, die von $S$ erzeugt wird (alle Zahlen der Form $p_1^{a_1} \cdots p_r^{a_r}$ mit $a_i \ge 0$).
• Verbotene Konfiguration: Gesucht ist die maximale Größe einer Teilmenge $A \subseteq M(S) \cap [1, X]$, die keine Menge der Form $\{n, p_1 n, \dots, p_r n\}$ enthält.
• Zielgrößen:
  • $F_S(X)$: Die maximale Größe einer solchen Teilmenge innerhalb des Intervalls $[1, X]$.
  • $f_S(k)$: Die maximale Größe einer solchen Teilmenge innerhalb der ersten $k$ S-glatten Zahlen.
  • $\alpha_S$: Die asymptotische Dichte der Lösung auf dem gesamten Intervall $[1, N]$ (im Gegensatz zu nur den S-glatten Zahlen).

Dies verallgemeinert klassische Probleme von Graham, Witsenhausen und Spencer, die den Fall $S=\{2,3\}$ (Verbot von $\{x, 2x, 3x\}$) betrachten.

2. Methodik

Der Autor kombiniert Techniken aus der analytischen Zahlentheorie, der kombinatorischen Zahlentheorie und der Gittergeometrie.

• Geometrische Interpretation: Das Problem wird in Exponentenkoordinaten transformiert. Eine S-glatte Zahl $n = p_1^{a_1} \cdots p_r^{a_r}$ entspricht einem Gitterpunkt $\mathbf{a} = (a_1, \dots, a_r) \in \mathbb{Z}_{\ge 0}^r$. Die Bedingung, keine Konfiguration $\{n, p_1 n, \dots, p_r n\}$ zu enthalten, entspricht dem Verbot von Einheits-Ecken (unit corners) $\{\mathbf{a}, \mathbf{a}+\mathbf{e}_1, \dots, \mathbf{a}+\mathbf{e}_r\}$ in einem gewichteten Gitter-Simplex $\Sigma_S(u)$, wobei $u = \log X$.
• Untere Schranke (Modulare Färbung): Es wird eine Färbung $\chi: \mathbb{Z}_{\ge 0}^r \to \mathbb{Z}/(r+1)\mathbb{Z}$ definiert durch $\chi(\mathbf{a}) \equiv \sum_{i=1}^r i \cdot a_i \pmod{r+1}$. Lemma 3.1 zeigt, dass jede Einheits-Ecke genau einen Punkt jeder der $r+1$ Farben enthält. Durch Weglassen der kleinsten Farbklasse erhält man eine konfliktfreie Menge.
• Obere Schranke (Identität für eckenfreie Mengen): Es wird eine kombinatorische Identität hergeleitet, die die Größe einer eckenfreien Menge $A$ mit der Größe des Simplex und den Rändern der Menge in Beziehung setzt. Dies führt zu einer exakten Formel mit einem Fehlerterm, der durch die Anzahl der Punkte auf den Hyperebenen des Simplex begrenzt wird.
• Verknüpfung mit dem Intervall $[1, N]$: Durch Zerlegung der Zahlen in $[1, N]$ nach ihrem „S-freien" Teil (Teiler, die nicht in $M(S)$ liegen) wird das Problem auf die S-glatten Zahlen zurückgeführt. Dies ermöglicht die Berechnung der globalen Dichte $\alpha_S$.
• Rekursive Berechnung: Die Reste (Tail) der reziproken Summen über S-glatten Zahlen werden durch eine rekursive Formel berechnet, die auf der Aufspaltung nach einer Primzahl basiert.

3. Wichtige Ergebnisse

A. Asymptotische Formeln für S-glatten Zahlen

Der Hauptresultat (Satz 1.1) liefert das asymptotische Verhalten für $X \to \infty$:
$$F_S(X) = \frac{r}{r+1} \Psi_S(X) + O_S((\log X)^{r-1})$$
wobei $\Psi_S(X)$ die Anzahl der S-glatten Zahlen $\le X$ ist.
Entsprechend gilt für die ersten $k$ S-glatten Zahlen:
$$f_S(k) = \frac{r}{r+1} k + O_S(k^{(r-1)/r})$$
Dies zeigt, dass die maximale dichte Teilmenge etwa $\frac{r}{r+1}$ der gesamten Menge der S-glatten Zahlen ausmacht. Der Fehlerterm ist scharf.

B. Die Dichte-Konstante $\alpha_S$

Für das Problem auf dem vollen Intervall $[1, N]$ wird die Existenz einer Dichte $\alpha_S$ bewiesen:
$$G_S(N) = \alpha_S N + O_S((\log N)^r)$$
Eine explizite Darstellung von $\alpha_S$ wird hergeleitet:
$$\alpha_S = c_S \sum_{k \ge 1} \frac{\Delta f_S(k)}{d_k^{(S)}}$$
wobei $c_S = \prod_{p \in S} (1 - 1/p)$, $d_k^{(S)}$ die $k$-te S-glatte Zahl ist und $\Delta f_S(k) \in \{0, 1\}$ die Differenz der Extremalfunktion.

C. Berechenbarkeit und Schranken

Korollar 1.3 zeigt, dass $\alpha_S$ durch eine Folge von verschachtelten Intervallen $[L_{S,N}, U_{S,N}]$ beliebig genau berechnet werden kann. Die Breite des Intervalls entspricht dem Rest der reziproken Summe über die S-glatten Zahlen größer als $d_N^{(S)}$. Eine rekursive Formel (Proposition 4.2) erlaubt die effiziente Berechnung dieses Rests.

D. Nicht-periodische rationale Summen

Ein bemerkenswertes Ergebnis (Proposition 1.4) ist, dass rationale Summen der Form $\sum c_k / d_k^{(S)}$ (mit $c_k \in \{0,1\}$) nicht notwendigerweise von einer schließlich periodischen Folge $(c_k)$ erzeugt werden müssen. Dies widerlegt die Intuition, dass Rationalität in diesem Kontext immer Periodizität impliziert.

E. Der klassische Fall $S=\{2,3\}$

Für $S=\{2,3\}$ (die Graham-Spencer-Witsenhausen-Konstante $\alpha$) werden explizite Formeln für den Restterm hergeleitet. Zudem wird gezeigt, dass es keine verschachtelte Familie optimaler Mengen $A_1 \subseteq A_2 \subseteq \dots$ gibt, die für jedes $k$ die maximale Größe $f(k)$ erreicht. Dies bedeutet, dass die Struktur der optimalen Mengen nicht monoton wächst; man muss Elemente entfernen, um neue hinzuzufügen.

4. Signifikanz und Beitrag

• Verallgemeinerung: Das Paper löst das Problem der verbotenen Konfigurationen für beliebige endliche Primzahlmengen $S$, nicht nur für $S=\{2,3\}$.
• Präzision: Die Bestimmung des Hauptterms $\frac{r}{r+1}$ und des genauen Fehlerterms ist ein signifikanter Fortschritt gegenüber früheren Existenzbeweisen.
• Algorithmische Zugänglichkeit: Die Herleitung von $\alpha_S$ als konvergierende Reihe mit expliziten, berechenbaren Restschranken macht die Bestimmung dieser Konstanten für beliebige $S$ praktisch durchführbar.
• Strukturelle Einsichten: Die Ergebnisse zur Nicht-Existenz verschachtelter optimaler Mengen (für $S=\{2,3\}$) und zur Nicht-Periodizität rationaler Summen erweitern das theoretische Verständnis der Struktur solcher extremaler Mengen und der Eigenschaften von S-glatten Zahlen.
• Verbindung von Disziplinen: Die Arbeit verbindet erfolgreich Gittergeometrie (Simplexe), modulare Arithmetik (Färbungen) und analytische Zahlentheorie (Zählfunktionen glatter Zahlen).

Zusammenfassend liefert das Paper eine vollständige asymptotische und algorithmische Beschreibung extremaler Dichten für verbotene multiplikative Konfigurationen in S-glatten Zahlen und liefert neue, tiefe Einsichten in die Struktur dieser Mengen.