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

Titel: Extremale Dichtheden voor Verboden Configuraties in S-Gladde Getallen

Auteur: Nikola Veselinov

---

1. Probleemstelling en Context

Het artikel onderzoekt een extremal combinatorisch probleem binnen de theorie van de getaltheorie, specifiek gericht op S-gladde getallen.

• Definitie: Laat $S = \{p_1, \dots, p_r\}$ een eindige verzameling van verschillende priemgetallen zijn. Een geheel getal $n$ heet S-glad als alle priemfactoren van $n$ tot $S$ behoren. De verzameling van alle S-gladde getallen wordt aangeduid als $M(S)$.
• Het Verboden Configuratie: Het doel is om de maximale grootte te vinden van een deelverzameling $A$ van de S-gladde getallen tot $X$ (of de eerste $k$ S-gladde getallen), zodanig dat $A$ geen verzameling van de vorm $\{n, p_1n, \dots, p_rn\}$ bevat.
• Vergelijking met Klassiek Geval: Dit generaliseert een klassiek probleem van Graham, Witsenhausen en Spencer (voor $S=\{2,3\}$) op het volledige interval $[1, N]$, waarbij men zoekt naar de maximale dichtheid van een verzameling zonder $\{x, 2x, 3x\}$.

De auteur definieert twee functies:

1. $F_S(X)$: De maximale grootte van een deelverzameling van $M(S) \cap [1, X]$ zonder de verboden configuratie.
2. $f_S(k)$: De maximale grootte van een deelverzameling van de eerste $k$ S-gladde getallen zonder de verboden configuratie.

2. Methodologie

De auteur combineert technieken uit de combinatorische getaltheorie, de theorie van gladde getallen en de meetkunde van roosters.

• Coördinatenovergang: Het probleem wordt getransformeerd van multiplicatieve getallen naar additieve roosters. Een S-glad getal $n = p_1^{a_1} \cdots p_r^{a_r}$ wordt geïdentificeerd met een vector $(a_1, \dots, a_r) \in \mathbb{Z}_{\ge 0}^r$.
• Gewogen Simplicia: De verzameling S-gladde getallen $\le X$ correspondeert met een gewogen roostersimplex $\Sigma_S(u)$, gedefinieerd door $\sum a_i \log p_i \le u$ (waar $u = \log X$).
• Unit Corners: De verboden configuratie $\{n, p_1n, \dots, p_rn\}$ correspondeert in deze roostervorm met een "unit corner" (een eenheidshoek): de verzameling $\{a, a+e_1, \dots, a+e_r\}$, waarbij $e_i$ de standaardbasisvectoren zijn. Het probleem wordt dus: vind de grootste deelverzameling van het simplex zonder zo'n hoek.
• Ondergrens (Modulaire Kleuring): Voor de ondergrens wordt een kleuring $\chi: \mathbb{Z}_{\ge 0}^r \to \mathbb{Z}/(r+1)\mathbb{Z}$ gebruikt, gedefinieerd als $\chi(a) \equiv \sum i \cdot a_i \pmod{r+1}$. Een unit corner bevat precies één punt van elke kleur. Door de kleinste kleurgroep te verwijderen, wordt elke hoek verbroken.
• Bovengrens (Identiteit voor Hoekvrije Mengen): Voor de bovengrens wordt een algebraïsche identiteit afgeleid die de grootte van een hoekvrije verzameling relateert aan de grootte van het simplex en de "achterwaartse verschuivingen" van de verzameling.
• Decompositie voor het Volledige Interval: Om het probleem op het volledige interval $[1, N]$ op te lossen (in plaats van alleen op $M(S)$), maakt de auteur gebruik van de unieke decompositie $n = m \cdot d$, waarbij $d \in M(S)$ en $(m, P_S) = 1$ (met $P_S$ het product van de priemgetallen in $S$). Dit splitst het probleem in disjuncte componenten.

3. Belangrijkste Resultaten

A. Asymptotische Formules (Stelling 1.1)

De auteur bewijst een scherpe asymptotische formule voor de maximale grootte van de deelverzamelingen:
$$F_S(X) = \frac{r}{r+1} \Psi_S(X) + O_S((\log X)^{r-1})$$
waarbij $\Psi_S(X)$ het aantal S-gladde getallen $\le X$ is.
Dit impliceert ook voor de functie op de eerste $k$ getallen:
$$f_S(k) = \frac{r}{r+1} k + O_S(k^{(r-1)/r})$$
Dit betekent dat de extremale dichtheid binnen de S-gladde getallen exact $\frac{r}{r+1}$ is.

B. Dichtheidsconstante voor het Volledige Interval (Corollarium 1.2)

Voor het probleem op het volledige interval $[1, N]$ (aangeduid als $G_S(N)$) wordt bewezen dat er een constante $\alpha_S$ bestaat zodanig dat:
$$G_S(N) = \alpha_S N + O_S((\log N)^r)$$
De constante wordt expliciet uitgedrukt als een reeks over de S-gladde getallen:
$$\alpha_S = c_S \sum_{k \ge 1} \frac{\Delta f_S(k)}{d_k^{(S)}}$$
waarbij $c_S = \prod_{p \in S} (1 - 1/p)$ en $\Delta f_S(k) \in \{0, 1\}$ de incrementen van de extremale functie zijn.

C. Berekenbare Grenzen (Corollarium 1.3)

Op basis van de bovenstaande reeks worden genesterde, berekenbare intervallen $[L_{S,N}, U_{S,N}]$ gedefinieerd die $\alpha_S$ bevatten. De breedte van deze intervallen is exact de "staart" van de reciproque som over de S-gladde getallen. Dit maakt het mogelijk om $\alpha_S$ met willekeurige precisie te berekenen.

D. Reciproke Sommen en Periodiciteit (Propositie 1.4)

Een opmerkelijk theoretisch resultaat is dat een rationele som van de vorm $\sum c_k / d_k^{(S)}$ (waar $c_k \in \{0,1\}$) niet noodzakelijkerwijs voortkomt uit een uiteindelijk periodieke binaire rij. De auteur construeert een voorbeeld waarbij de som rationaal is, maar de rij $(c_k)$ geen eindige periode heeft.

E. Het Klassieke Geval $S=\{2, 3\}$

Voor het specifieke geval van 3-gladde getallen (getallen van de vorm $2^a 3^b$):

• De constante $\alpha_{\{2,3\}}$ wordt herleid tot de bekende Graham-Spencer-Witsenhausen constante.
• Er wordt een expliciete recursieve formule voor de staart van de som afgeleid.
• Er wordt bewezen dat er geen genestelde familie van optimale verzamelingen bestaat (d.w.z. een rij $A_1 \subset A_2 \subset \dots$ waarbij elke $A_k$ optimaal is voor de eerste $k$ getallen). Dit toont aan dat de structuur van optimale oplossingen complex is en niet monotoon opgebouwd kan worden.

4. Significatie en Bijdrage

• Generalisatie: Het artikel generaliseert een klassiek probleem uit de extremale verzamelingstheorie naar de context van multiplicatieve semigruppen (S-gladde getallen) voor een willekeurige eindige verzameling priemgetallen.
• Precisie: Het levert niet alleen de leidende term van de asymptotiek, maar ook een nauwkeurige foutterm en een expliciete representatie van de dichtheidsconstante.
• Berekenbaarheid: Door de link te leggen tussen de extremale functie en reciproque sommen, biedt het een methode om de dichtheidsconstanten numeriek te benaderen met willekeurige nauwkeurigheid.
• Structuurinzicht: De resultaten over de niet-periodiciteit van binaire rijen en de afwezigheid van genestelde optimale families in het geval $S=\{2,3\}$ bieden nieuw inzicht in de structurele eigenschappen van deze extremale verzamelingen, wat verder gaat dan alleen het tellen van elementen.

Samenvattend biedt dit werk een volledig wiskundig raamwerk voor het begrijpen van de dichtheid van verzamelingen die multiplicatieve patronen vermijden binnen de S-gladde getallen, met sterke verbindingen tussen combinatoriek, analyse en getaltheorie.