Problems in additive number theory, VII: The structure of additive $h$-bases for $n$

Technische Samenvatting: Problemen in de Additieve Getaltheorie, VII: De Structuur van Additieve h-Basis voor n

Inleiding en Motivatie
Dit artikel, geschreven door Melvyn B. Nathanson, introduceert een nieuwe klasse van problemen in de additieve getaltheorie die betrekking hebben op de structuur van additieve $h$-basissen voor $n$. Het werk wordt geplaatst in de context van de evoluerende mogelijkheden van kunstmatige intelligentie in de wiskunde. Hoewel AI-systemen hebben aangetoond complexe problemen op te kunnen lossen die geschikt zijn voor proefschriften, missen ze momenteel het vermogen om "interessante" problemen te identificeren of nieuwe conjecturen te formuleren. Bijgevolg stelt dit artikel dat de formulering van nieuwe, oplosbare vragen een duidelijk voordeel blijft voor menselijke wiskundigen. De gepresenteerde problemen zijn ontworpen om oplosbaar te zijn door mensen en, in sommige gevallen, door huidige AI-systemen toegepast op rekenkunde.

Definities en Kader
Het artikel vestigt een rigoureus kader gebaseerd op de volgende definities:

• Additieve $h$-basis voor $n$: Een eindige verzameling gehele getallen $A$ is een additieve $h$-basis voor $n$ als de $h$-voudige sommenverzameling $hA$ (de verzameling van alle sommen van $h$ niet noodzakelijk verschillende elementen van $A$) het interval $[0, n]$ bevat.
• Interval $h$-basis voor $n$: Een verzameling $A$ is een interval $h$-basis voor $n$ als $hA$ een interval $[c, c+n]$ bevat voor een zekere gehele $c$.
• Maximale Intervallen: Voor een verzameling $A$ geeft $\ell_h(A)$ de grootste $n$ aan zodat $[0, n] \subseteq hA$, en $\ell^\sharp_h(A)$ geeft de grootste $n$ aan zodat $[c, c+n] \subseteq hA$ voor een zekere $c$.
• Vier Sleutelfuncties: Het artikel definieert vier functies gebaseerd op verzamelingen van grootte $k$:
  1. $n_h(k)$: De maximale $n$ zodat een verzameling $A \subseteq \mathbb{N}_0$ van grootte $k$ voldoet aan $[0, n] \subseteq hA$.
  2. $n^\sharp_h(k)$: De maximale $n$ zodat een verzameling $A \subseteq \mathbb{N}_0$ van grootte $k$ voldoet aan $[c, c+n] \subseteq hA$ voor een zekere $c$.
  3. $m_h(k)$: De maximale $n$ zodat een verzameling $A \subseteq \mathbb{Z}$ van grootte $k$ voldoet aan $[0, n] \subseteq hA$.
  4. $m^\sharp_h(k)$: De maximale $n$ zodat een verzameling $A \subseteq \mathbb{Z}$ van grootte $k$ voldoet aan $[c, c+n] \subseteq hA$ voor een zekere $c$.

Belangrijkste Bijdragen en Resultaten

1. Monotonie van Functies:
   Stelling 1 bewijst dat de rijen $(n_h(k))$, $(m_h(k))$, $(n^\sharp_h(k))$ en $(m^\sharp_h(k))$ strikt stijgend zijn voor $h, k \ge 2$. Het bewijs berust op de constructie van een verzameling $A'$ van grootte $k+1$ door een element toe te voegen aan een maximale verzameling $A$ van grootte $k$, waardoor het gedekte interval met ten minste één eenheid wordt uitgebreid.

2. Generalisatie van Sidon-verzamelingen:
   Om specifieke intervallenbasissen te construeren, introduceert het artikel het concept van $\Delta$-gescheiden verzamelingen van niveau $H$. Een verzameling is $\Delta$-gescheiden van niveau $\infty$ als het verschil tussen twee verschillende deelsomten ten minste $\Delta$ bedraagt.

   • Stelling 2 toont aan dat de verzameling machten $A(g) = \{g^i : i \in \mathbb{N}\}$ met $g = \Delta + 1$ $\Delta$-gescheiden is van niveau $\infty$. Dit biedt een methode om verzamelingen te construeren met sterk gescheiden sommenverzamelingen.

3. Constructie van Interval 2-Basis:
   Stelling 3 presenteert een constructief bewijs voor het bestaan van verzamelingen $A$ van grootte $2n+2$ zodat $2A$ een uniek interval $[c, c+n]$ bevat en geen andere intervallen (behalve deelintervallen van $[c, c+n]$). Alle elementen in $2A \setminus [c, c+n]$ zijn geïsoleerd. De constructie maakt gebruik van een rij gehele getallen die snel genoeg groeit om de scheiding van sommen buiten het doelinterval te waarborgen.

4. Equivalentie van Niet-negatieve en Gehele Basissen:
   Stelling 5 stelt vast dat $n^\sharp_h(k) = m^\sharp_h(k)$. Dit resultaat geeft aan dat het toestaan van negatieve gehele getallen in de basisverzameling de maximale lengte van een interval dat door een $h$-voudige sommenverzameling kan worden gedekt, niet vergroot, mits het interval kan worden verschoven. Het bewijs omvat het verschuiven van een verzameling met negatieve gehele getallen naar een verzameling niet-negatieve gehele getallen zonder de lengte van het gedekte interval te veranderen.

5. Diametergrenzen:
   Stelling 6 biedt een bovengrens voor de diameter van een verzameling $A \subseteq \mathbb{N}_0$ die de maximale intervallengte $n_h(k)$ bereikt. Specifiek geldt: als $\ell_h(A) = n_h(k)$, dan is $\text{diam}(A) \le n_h(k)$. Het bewijs betoogt dat als het grootste element groter zou zijn dan $n_h(k)$, het overbodig zou zijn voor het dekken van het interval $[0, n_h(k)]$, wat in strijd zou zijn met de maximaliteit van $n_h(k)$.

Open Problemen en Methodologie
Het artikel lost de primaire computationele problemen niet op, maar formuleert ze als uitdagingen voor toekomstig onderzoek. De methodologie omvat:

• Patroonherkenning: Het opsommen van specifieke waarden voor kleine $h$ en $k$ (bijvoorbeeld $L_{\mathbb{N}_0, h}(k)$) om verborgen patronen te identificeren.
• Constructieve Bewijzen: Het gebruik van snel groeiende rijen (machten van gehele getallen) om specifieke sommenverzamelingen te isoleren.
• Verschuivingsargumenten: Het gebruik van het delingsalgoritme om intervallen te verschuiven en problemen over $\mathbb{Z}$ te relateren aan die over $\mathbb{N}_0$.

Het artikel identificeert verschillende specifieke problemen, waarvan er vele met een asterisk (*) zijn gemarkeerd om de potentiële moeilijkheid voor AI aan te geven:

• Probleem 1 & 2: Het beschrijven van de verzamelingen van mogelijke waarden voor $\ell_h(A)$ en $\ell^\sharp_h(A)$ voor vaste $h$ en $k$.
• Probleem 3: Het berekenen van de rijen van de vier functies en het ontwikkelen van algoritmen om te beslissen of een gegeven geheel getal $w$ tot hun bereik behoort.
• Probleem 4: Het analyseren van de verschilrijen van deze functies.
• Probleem 5: Het bepalen of de opname van negatieve getallen de grootte van het maximale interval $[0, n]$ strikt vergroot.
• Problemen 7–9: Het onderzoeken van de mogelijkheid om verzamelingen te construeren waarbij de sommenverzameling intervallen bevat op specifieke, ver uit elkaar liggende locaties.
• Probleem 10: Het bepalen van de gelijkheid van de vier functies (bijvoorbeeld: is $n_h(k) = m_h(k)$?).

Betekenis en Reikwijdte
Het artikel claimt betekenis voornamelijk in de formulering van deze nieuwe vragen. Het erkent dat de functie $n_h(k)$ uitvoerig is bestudeerd in oudere Duitse literatuur (met verwijzing naar auteurs zoals Bloom, Hofmeister en Rohrbach), en dat oplossingen mogelijk bestaan in historische tijdschriften. Het artikel heeft echter tot doel het onderzoek te moderniseren door:

1. Systematisch de vier gerelateerde functies te definiëren ($n_h, n^\sharp_h, m_h, m^\sharp_h$).
2. Het concept van $\Delta$-gescheiden verzamelingen in te voeren om intervallenbasissen met specifieke structurele eigenschappen te construeren.
3. Deze problemen expliciet te kaderen als benchmarks voor AI-capaciteiten in wiskundige ontdekking.

Het werk is bescheiden in zijn claims, waarbij wordt opgemerkt dat het "nieuwe vragen" introduceert in plaats van definitieve oplossingen te bieden voor het asymptotische gedrag van deze functies. Het benadrukt dat terwijl de tellende functie $n_h(k)$ de focus van eerder onderzoek is geweest, de andere tellende functies en de structurele eigenschappen van intervallenbasissen grotendeels onbestudeerd blijven. Het artikel concludeert met de suggestie dat analoge problemen bestaan voor andere verzamelingen (kwadraten, priemgetallen) en andere configuraties (rekenkundige rijen), waardoor een breed programma voor toekomstig onderzoek wordt achtergelaten.