On the Monotonicity of Higher-Fold Representation Functions

Technische Samenvatting: Over de Monotoniciteit van Hogere-orde Representatiefuncties

Probleemstelling
Het artikel onderzoekt de monotoniciteitseigenschappen van de geordende $h$-voudige representatiefunctie $R_{A,h}(n)$, gedefinieerd als het aantal geordende oplossingen aan $n = a_1 + \dots + a_h$, waarbij $a_i \in A$ en $A \subseteq \mathbb{N}$. De centrale vraag is of $R_{A,h}(n)$ strikt toenemend kan zijn voor een verzameling $A$ waarvan het complement $\mathbb{N} \setminus A$ oneindig is (een co-oneindige verzameling).

Historisch gezien bewezen Erdős, Sárközy en Sós dat voor $h=2$, strikte monotoniciteit impliceert dat $A$ co-eindig is (dat wil zeggen, het complement is eindig). Voor $h \ge 3$ vermoedde Dombi dat als $\mathbb{N} \setminus A$ oneindig is, $R_{A,h}(n)$ niet uiteindelijk strikt toenemend kan zijn. Dit vermoeden werd weerlegd door Shallit, die via automatentheorie een co-oneindige verzameling $A$ construeerde waarvoor $R_{B,3}(n)$ strikt toenemend is. Specifiek maakte Shallit gebruik van de verzameling $B = \{0\} \cup \{m \ge 1 : \text{de basis-4 expansie van } m \text{ begint met 1 of 2}\}$. Hoewel Shallit strikte monotoniciteit vaststelde voor $R_{B,h}(n)$ voor een vaste $h \ge 3$, bleef de precieze groeisnelheid van het verschil $R_{B,h}(n+1) - R_{B,h}(n)$ een open kwantitatieve vraag. Bovendien stelde Dombi een probleem over de existentie van dergelijke verzamelingen met asymptotische dichtheid $\alpha \neq 1/2$ (of specifiek $\alpha \neq 1$).

Methodologie
De auteurs maken gebruik van een combinatie van genererende functies, recursieformules afgeleid van de zelfgelijke structuur van de verzameling $B$, en convolutieargumenten om grenzen vast te stellen op de verschilfunctie $\Delta_h(n) = R_{B,h}(n+1) - R_{B,h}(n)$.

1. Recursieanalyse voor verzameling $B$:
   De verzameling $B$ wordt gedefinieerd door zijn indicatorreeks $c_n$, die een functionele vergelijking voldoet in de genererende functie $C(x) = \sum c_n x^n$:
   $$C(x) = (1+x+x^2+x^3)C(x^4) - x^3$$
   Door deze vergelijking te kwadrateren en te cuberen, leiden de auteurs recursieformules af voor de verschillen van de twee-voudige ($\beta_n$) en drie-voudige ($\alpha_n$) representatiefuncties.

   • Lemma 2.1 & 2.2: Deze lemma's vestigen recursieve formules voor $\beta_n$ en $\alpha_n$ gebaseerd op waarden bij indices $n/4$.
   • Grenzen op $\beta_n$: Lemma 3.1 bewijst dat het verschil voor de twee-voudige functie begrensd is: $-1 \le \beta_n \le 2$.
   • Grenzen op $\alpha_n$: Gebruikmakend van de grenzen op $\beta_n$ en de recursieformules, stelt Lemma 3.2 een lineaire ondergrens vast $\alpha_n \ge n/5 + 4$ voor $n \ge 78$, terwijl Lemma 3.3 een lineaire bovengrens biedt $\alpha_n \le 3n + 2$.

2. Convolutie-lift:
   Om de resultaten van $h=3$ uit te breiden naar willekeurige $h \ge 3$, gebruiken de auteurs de convolutie-identiteit:
   $$R_{p+q}(n) = \sum_{u=0}^n R_p(n-u)R_q(u)$$
   Dit leidt tot een relatie voor de verschillen:
   $$\Delta_{p+q}(n) = \sum_{u=0}^n \Delta_p(n-u)R_q(u) + R_p(0)R_q(n+1)$$
   Door $p=3$ en $q=h-3$ te kiezen, wordt het gedrag van $\Delta_h(n)$ gecontroleerd door het bekende gedrag van $\Delta_3(n)$ (d.w.z. $\alpha_n$) en de groei van $R_{h-3}(n)$.

3. Constructie van verzameling $C$:
   Om Dombi's probleem betreffende de asymptotische dichtheid aan te pakken, construeren de auteurs een verzameling $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$. Zij analyseren de genererende functie $G_C(x) = (1-x)^{-1} - D(x)$, waarbij $D(x)$ overeenkomt met de verwijderde machten van 2. De schaarste van de verwijderde verzameling maakt een expliciete schatting van het verschil $R_{C,h}(n+1) - R_{C,h}(n)$ mogelijk.

Belangrijkste Bijdragen en Resultaten

1. Polynomiale Groeiorde (Theorem 1.1):
   Het artikel bewijst dat voor de verzameling $B$ het verschil $R_{B,h}(n+1) - R_{B,h}(n)$ polynomiaal groeit met orde $n^{h-2}$. Specifiek, voor elke geheel getal $h \ge 3$, bestaan er constanten $c_h, C_h > 0$ zodat voor alle $n \ge 1$:
   $$c_h n^{h-2} \le R_{B,h}(n+1) - R_{B,h}(n) \le C_h n^{h-2}$$
   Dit resultaat bevestigt dat, ondanks dat $B$ een oneindig complement met grote gaten heeft, de representatiefunctie zich asymptotisch gedraagt als die van de volledige verzameling $\mathbb{N}$ (waar het verschil $\binom{n+h-1}{h-2} \asymp n^{h-2}$ is).

2. Strikte Monotoniciteit voor willekeurige $h \ge 3$:
   De auteurs bewijzen rigoureus dat $R_{B,h}(n+1) > R_{B,h}(n)$ voor alle $n \ge 0$ en alle $h \ge 3$, waarmee zij de resultaten van Shallit verbeteren, die zich richtten op de existentie van dergelijke verzamelingen zonder de groeisnelheid voor alle $h$ te kwantificeren.

3. Oplossing van Dombi's Dichtheidsprobleem (Theorem 1.2):
   Het artikel construeert een co-oneindige verzameling $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$ waarvoor:

   • De asymptotische dichtheid bestaat en gelijk is aan 1: $\lim_{n \to \infty} C(n)/n = 1$.
   • De representatiefunctie $R_{C,h}(n)$ strikt toenemend is voor elke gehele $h \ge 3$.
     Dit beantwoordt Dombi's probleem door een verzameling te leveren met dichtheid 1 (anders dan de voorheen bekende voorbeelden met dichtheid 1/2) die eveneens strikte monotoniciteit behoudt.

Betekenis
Het artikel verfijnt het begrip van additieve representatiefuncties in co-oneindige verzamelingen. Het toont aan dat de obstructie voor monotoniciteit die in het geval $h=2$ wordt gevonden, niet persisteert voor $h \ge 3$, zelfs wanneer de verzameling een "groot" oneindig complement heeft. Door de exacte polynomiale groeiorde van de verschilfunctie vast te stellen, tonen de auteurs aan dat de verzameling $B$ de "gladheid" van de volledige verzameling gehele getallen behoudt wat betreft de groei van de representaties. Verder breidt de constructie van verzameling $C$ het bekende landschap van dergelijke verzamelingen uit, door te laten zien dat strikte monotoniciteit compatibel is met een asymptotische dichtheid van 1, waardoor de kloof tussen co-efiene en co-oneindige eigenschappen in de additieve getaltheorie wordt verkleind.

De auteurs concluderen door openstaande problemen te formuleren met betrekking tot de existentie van dergelijke verzamelingen voor willekeurig voorgeschreven dichtheden $d \in [0, 1)$ en voor verzamelingen met specifieke liminf- en limsup-dichtheden, wat suggereert dat de volledige karakterisering van monotoniciteitscondities voor representatiefuncties een actief onderzoeksgebied blijft.