🔢 mathematics

Restricted partition functions and additive complements

Dit artikel beantwoordt positief een vraag uit 2016 van Dai en Chen door oneindige verzamelingen van positieve gehele getallen te construeren die een beperkte partitiefunctie met polynomiale groei opleveren, terwijl wordt gewaarborgd dat elk positief geheel getal ten minste één representatie heeft.

Oorspronkelijke auteurs: Yuchen Ding

Gepubliceerd 2026-06-17

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yuchen Ding

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een gigantische, oneindige gereedschapskist hebt vol met speciale bouwblokken. Elk blok heeft een specifieke grootte, bepaald door een getal in een lijst genaamd Set A. Je hebt ook een speciaal regelboek genaamd Set M dat je vertelt hoeveel van elk blok je mag gebruiken.

De wiskundige in dit artikel, Yuchen Ding, stelt een zeer specifieke vraag: Kunnen we deze twee lijsten (A en M) zo ontwerpen dat we elk positief heel getal (1, 2, 3, enz.) kunnen bouwen met deze blokken, maar zonder dat het aantal manieren om ze te bouwen uit de hand loopt?

Hier is een uitsplitsing van de concepten met behulp van alledaagse analogieën:

1. De Bouwblokken (Beperkte Partities)

Denk aan het getal $n$ (zoals 100) als een toren die je wilt bouwen.

Set A is je lijst met beschikbare blokgroottes (bijv. 1, 4, 16, 256...).
Set M is je regelboek voor "veelvouden". Het zegt: "Je kunt 0, 1 of 2 van de 4-blokken gebruiken, maar misschien 0, 5 of 10 van de 16-blokken."
Het Doel: Je wilt elk getal $n$ kunnen bouwen met deze regels.
Het Probleem: Als je te veel manieren hebt om hetzelfde getal te bouwen, wordt de wiskunde rommelig. De auteur wil bewijzen dat het aantal manieren om een toren te bouwen ( $p$ ) langzaam groeit—specifiek, "polynomiale groei".

De Analogie: Stel je voor dat je koekjes bakt.

Als je 100 verschillende recepten hebt voor een chocoladechipkoekje, is dat een hoop werk om bij te houden.
"Polynomiale groei" betekent dat naarmate je steeds grotere batches koekjes probeert te bakken, het aantal nieuwe, unieke recepten die je ontdekt niet direct explodeert naar miljoenen. Het groeit op een beheersbaar, voorspelbaar tempo.

2. Het "Gap"-probleem (Het Gat-probleem)

Voordat dit artikel bestond, kenden wiskundigen al manieren om lijsten te maken waarbij je elk getal kon bouwen, maar waarbij de "gap" tussen de groottes van de blokken niet enorm was.

De Vraag: Kunnen we een lijst maken waarbij de blokken extreem veel groter worden, heel snel? Stel je een lijst voor waar het eerste blok grootte 1 heeft, het volgende 100, het volgende 10.000 en het volgende 1.000.000.
De kloof tussen deze getallen is zo breed dat de wiskunde normaal gesproken vastloopt, wat het onmogelijk maakt om elk getal te bouwen of ervoor zorgt dat het aantal recepten explodeert.

3. De Oplossing: Het "Perfecte Paar"

Ding bewijst dat het antwoord JA is. Je kunt deze enorme gaten creëren en nog steeds elk getal bouwen met een beheersbaar aantal recepten.

Hij doet dit door een slimme truc te introduceren met betrekking tot Additieve Complementen.

De Metafoor: Stel je twee teams voor, Team B en Team S.
- Team B heeft leden die machten van 2 zijn (1, 2, 4, 8, 16...).
- Team S is een speciale groep getallen die de "gaten" opvult die door Team B zijn achtergelaten.
- Samen, als je één persoon van Team B en één van Team S neemt en hun "waarden" bij elkaar optelt, kun je elk getal op de getallenlijn vormen. Ze zijn "complementen".

Ding gebruikt een beroemd resultaat van de wiskundige Ruzsa om een Team S te vinden dat net schaars genoeg is om interessant te zijn, maar dicht genoeg om de gaten op te vullen.

4. Hoe de Constructie Werkt

Ding creëert zijn twee magische lijsten, A en M, gebaseerd op deze teams:

Set A (De Blokken): Hij neemt de getallen van Team B en verandert ze in machten van 2 (bijv. $2^1, 2^2, 2^4, 2^8...$ ). Dit creëert de "enorme gaten" die vereist zijn door de vraag.
Set M (De Regels): Hij creëert regels gebaseerd op Team S. De regels laten je toe om kleine stukjes van Team S te combineren om de coëfficiënten te vormen (het "hoeveelheid" deel).

De Magie: Omdat Team B en Team S perfecte complementen zijn, kun je elk getal altijd afbreken in een som die aan deze specifieke regels voldoet. Omdat Team S zorgvuldig is gekozen, explodeert het aantal manieren om dit te doen niet; het blijft binnen een "polynomiale" limiet (een beheersbaar groeitempo).

5. Waarom Dit Belangrijk Is (Volgens het Artikel)

Dit artikel beantwoordt een specifieke vraag gesteld door Dai en Chen in 2016.

De Vraag: "Bestaan er twee oneindige verzamelingen waarbij de blokken oneindig ver uit elkaar liggen, maar waarbij we nog steeds elk getal kunnen bouwen met een beheersbaar aantal combinaties?"
Het Antwoord: Ja. Ding construeerde een specifiek voorbeeld waarbij de gaten tussen de blokken zo snel groeien dat de ratio van hun logaritmen naar oneindig gaat, en toch werkt het systeem perfect.

Een Opmerking over het "AI"-Ingrediënt

De auteur, Yuchen Ding, vermeldt expliciet dat hij een AI-tool (ChatGPT) heeft gebruikt tijdens het onderzoeksproces.

Wat de AI deed: Het suggereerde om naar verzamelingen te kijken die machten van 2 bevatten en wees hem op een specif evenement doorstelling van Ruzsa over "lacunaire sequenties" (sequenties met grote gaten).
Wat de Auteur deed: De auteur verifieerde de wiskunde, controleerde de logica, organiseerde het bewijs opnieuw en schreef de definitieve tekst. Hij neemt de volledige verantwoordelijkheid voor de juistheid van het werk.

Samenvatting

Yuchen Ding heeft een puzzel over het bouwen van getallen opgelost. Hij heeft aangetoond dat je een set bouwblokken kunt hebben die extreem ver uit elkaar staan (zoals een ladder met sporten die steeds verder uit elkaar liggen), en een set regels voor het gebruik ervan, zodanig dat:

Je elk heel getal kunt bouwen.
Het aantal manieren om ze te bouwen niet uit de hand loopt.

Het is alsoer bewijzen dat je een ladder kunt hebben met sporten die een mijl uit elkaar liggen, maar dat je er toch vloeiend op kunt klimmen, gebruikmakend van een specifieke, beheersbare set klimtechnieken.

Technische Samenvatting: Beperkte Partitiefuncties en Additieve Complementen

Probleemstelling
Het artikel behandelt een specifieke vraag in de additieve getaltheorie betreffende beperkte partitiefuncties. Laat $\mathbb{N}$ de verzameling positieve gehele getallen zijn en $\mathbb{N}_0 = \mathbb{N} \cup \{0\}$ . Voor deelverzamelingen $A, M \subseteq \mathbb{N}$ telt de beperkte partitiefunctie $p(n, A, M)$ het aantal representaties van een geheel getal $n$ in de vorm:
$n = \sum_{a \in A} m_a a$
waarbij $m_a \in M \cup \{0\}$ voor alle $a \in A$ , en slechts eindig veel $m_a$ ongelijk zijn aan nul. De functie $p$ wordt gezegd een polynomiale groei te hebben als er constanten $c > 0$ en $n_0$ bestaan zodat $p(n, A, M) \leq n^c$ voor alle $n \geq n_0$ .

Het centrale probleem, geponeerd door Dai en Chen in 2016 (Vraag 1), vraat of er twee oneindige verzamelingen $A = \{a_n\}_{n=1}^\infty$ en $M$ van positieve gehele getallen bestaan zodanig dat:

De verzameling $A$ extreem ijl is, voldoend aan $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ .
$p(n, A, M) > 0$ voor alle voldoende grote $n$ (dat wil zeggen, elk groot geheel getal is representeerbaar).
De partitiefunctie $p(n, A, M)$ een polynomiale groei vertoont.

Vorig werk van Alon (2012) en Dai en Chen (2016) had de existentie van dergelijke verzamelingen met polynomiale groei vastgesteld onder minder strikte ijltheidsvoorwaarden of met specifieke exponentbounds (bijv. $p(n) < n^{2+o(1)}$ ), maar de casus van super-logaritmische ijltheid bleef open.

Methodologie
De auteur, Yuchen Ding, hanteert een constructie gebaseerd op additieve complementen en binaire expansies. De kernstrategie omvat:

Definiëren van Additieve Complementen: Twee verzamelingen $B, S \subseteq \mathbb{N}_0$ worden complete additieve complementen genoemd als $B + S = \mathbb{N}_0$ .
Constructie van de Verzamelingen $A$ en $M$ : Het artikel construeert $A$ $A$ en $M$ $M$ op basis van een paar additieve complementen $B$ $B$ en $S$ $S$ die voldoen aan een specifieke telconditie. Specifiek:
- $A = \{2^b : b \in B\}$
- $M = \{ \sum_{d \in D} 2^d : D \subset S, 0 < |D| < \infty \}$ (eindige sommen van machten van 2 uit $S$ ).
Injectieve Afbeelding: Het bewijs vestigt een injectieve afbeelding van de representaties van $n$ die door $p(n, A, M)$ worden geteld naar eindige deelverzamelingen van de productruimte $S \times B$ . Door gebruik te maken van de uniciteit van binaire expansies, toont de auteur aan dat elke representatie van $n$ overeenkomt met een verzameling paren $(s, b)$ waarvoor $s+b \leq \log_2 n$ .
Begrenzen van de Groei: Het aantal dergelijke representaties wordt begrensd door het aantal paren $(s, b) \in S \times B$ waarvoor $s+b \leq N$ (waarbij $N \approx \log_2 n$ ). Deze telling wordt aangetoond begrensd te zijn door $S(N)B(N)$ . Als $B(x)S(x) \ll x$ , vertoont de resulterende partitiefunctie polynomiale groei.

Belangrijkste Bijdragen en Resultaten
Het artikel geeft een bevestigend antwoord op Vraag 1 van Dai en Chen via de volgende resultaten:

Stelling 1: Laat $B$ en $S$ complete additieve complementen zijn die voldoen aan de telconditie $B(x)S(x) \ll x$ . Als $A$ en $M$ als hierboven gedefinieerd zijn, dan is $p(n, A, M) > 0$ voor elk $n \in \mathbb{N}$ en heeft $p(n, A, M)$ polynomiale groei.
Corollary 1 (Resolutie van Vraag 1): Door een resultaat van Ruzsa (1972) betreffende additieve complementen van machten van twee aan te roepen, construeert de auteur specifieke verzamelingen $A$ $A$ en $M$ $M$ die voldoen aan de voorwaarden van Stelling 1.
- Laat $B = \{0\} \cup \{2^k : k \geq 0\}$ .
- Laat $S$ een deelverzameling van $\mathbb{N}$ zijn afgeleid van de stelling van Ruzsa zodanig dat $S(x) \ll x / \log x$ en $B+S = \mathbb{N}_0$ (na het toevoegen van eindig veel elementen).
- De resulterende verzameling $A$ heeft elementen $a_n = 2^{2^{n-2}}$ voor $n \geq 2$ .
- Deze constructie levert $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ op, wat aan de eis van extreme ijltheid voldoet.
- Aangezien $B(x) \ll \log x$ en $S(x) \ll x / \log x$ , geldt het product $B(x)S(x) \ll x$ , wat de polynomiale groei van $p(n, A, M)$ waarborgt.

Betekenis
Het artikel claimt een vraag uit 2016 van Dai en Chen in het positief te hebben beantwoord. Het demonstreert dat het mogelijk is om beperkte partitiefuncties te construeren die surjectief zijn (alle positieve gehele getallen representeren) en polynomiale groei vertonen, zelfs wanneer de toegestane delen $A$ aanzienlijk ijler zijn dan eerder bekende voorbeelden (specifiek, waarbij aan een limietconditie wordt voldaan waarbij de logaritmische kloof tussen opeenvolgende elementen sneller groeit dan elke macht van $\log n$ ).

Het werk generaliseert eerdere resultaten door de groeisnelheid van beperkte partitiefuncties direct te koppelen aan de tel-eigenschappen van additieve complementen. De auteur merkt op dat de constructie aanvankelijk werd verkend met behulp van generatieve AI (ChatGPT), die de specifieke vorm van de verzamelingen en de connectie met de stelling van Ruzsa suggereerde, hoewel de wiskundige verificatie, reorganisatie en het uiteindelijke bewijs het onafhankelijke werk van de auteur zijn.