On the Monotonicity of Higher-Fold Representation Functions

Sintesi Tecnica: Sulla Monotonia delle Funzioni di Rappresentazione ad Ordine Superiore

Enunciato del Problema
Il saggio investiga le proprietà di monotonia della funzione di rappresentazione ordinata $h$-fold $R_{A,h}(n)$, definita come il numero di soluzioni ordinate a $n = a_1 + \dots + a_h$ con $a_i \in A$, dove $A \subseteq \mathbb{N}$. La questione centrale riguarda se $R_{A,h}(n)$ possa essere strettamente crescente per un insieme $A$ il cui complemento $\mathbb{N} \setminus A$ è infinito (un insieme co-infinito).

Storicamente, Erdős, Sárközy e Sós hanno dimostrato che per $h=2$, la monotonia stretta implica che $A$ sia cofinito (ovvero il complemento è finito). Per $h \ge 3$, Dombi ipotizzò che se $\mathbb{N} \setminus A$ è infinito, $R_{A,h}(n)$ non possa essere eventualmente strettamente crescente. Questa congettura è stata smentita da Shallit, il quale, utilizzando la teoria degli automi, ha costruito un insieme co-infinito $A$ in cui $R_{A,3}(n)$ è strettamente crescente. Nello specifico, Shallit ha utilizzato l'insieme $B = \{0\} \cup \{m \ge 1 : \text{l'espansione in base 4 di } m \text{ inizia con 1 o 2}\}$. Sebbene Shallit avesse stabilito la monotonia stretta per $R_{B,h}(n)$ per un $h \ge 3$ fissato, il preciso tasso di crescita della differenza $R_{B,h}(n+1) - R_{B,h}(n)$ rimaneva una questione quantitativa aperta. Inoltre, Dombi pose un problema riguardante l'esistenza di tali insiemi con densità asintotica $\alpha \neq 1/2$ (o specificamente $\alpha \neq 1$).

Metodologia
Gli autori impiegano una combinazione di funzioni generatrici, relazioni di ricorrenza derivate dalla struttura autosimile dell'insieme $B$ e argomenti di convoluzione per stabilire i limiti sulla funzione differenza $\Delta_h(n) = R_{B,h}(n+1) - R_{B,h}(n)$.

1. Analisi della Ricorrenza per l'Insieme $B$:
   L'insieme $B$ è definito dalla sua sequenza indicatrice $c_n$, che soddisfa un'equazione funzionale nella funzione generatrice $C(x) = \sum c_n x^n$:
   $$C(x) = (1+x+x^2+x^3)C(x^4) - x^3$$
   Elevando al quadrato e al cubo questa equazione, gli autori derivano relazioni di ricorrenza per le differenze delle funzioni di rappresentazione a due ordini ($\beta_n$) e a tre ordini ($\alpha_n$).

• Lemma 2.1 & 2.2: Questi lemmi stabiliscono formule ricorsive per $\beta_n$ e $\alpha_n$ basate sui valori agli indici $n/4$.
• Limiti su $\beta_n$: Il Lemma 3.1 dimostra che la differenza per la funzione a due ordini è limitata: $-1 \le \beta_n \le 2$.
• Limiti su $\alpha_n$: Utilizzando i limiti su $\beta_n$ e le relazioni di ricorrenza, il Lemma 3.2 stabilisce un limite inferiore lineare $\alpha_n \ge n/5 + 4$ per $n \ge 78$, mentre il Lemma 3.3 fornisce un limite superiore lineare $\alpha_n \le 3n + 2$.

2. Sollevamento per Convoluzione (Convolution Lift):
   Per estendere i risultati da $h=3$ a un $h \ge 3$ arbitrario, gli autori utilizzano l'identità di convoluzione:
   $$R_{p+q}(n) = \sum_{u=0}^n R_p(n-u)R_q(u)$$
   Ciò porta a una relazione per le differenze:
   $$\Delta_{p+q}(n) = \sum_{u=0}^n \Delta_p(n-u)R_q(u) + R_p(0)R_q(n+1)$$
   Impostando $p=3$ e $q=h-3$, il comportamento di $\Delta_h(n)$ è controllato dal comportamento noto di $\Delta_3(n)$ (ovvero $\alpha_n$) e dalla crescita di $R_{h-3}(n)$.

3. Costruzione dell'Insieme $C$:
   Per affrontare il problema della densità di Dombi, gli autori costruiscono un insieme $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$. Analizzano la funzione generatrice $G_C(x) = (1-x)^{-1} - D(x)$, dove $D(x)$ corrisponde alle potenze di 2 rimosse. La scarsità dell'insieme rimosso permette una stima esplicita della differenza $R_{C,h}(n+1) - R_{C,h}(n)$.

Contributi Chiave e Risultati

1. Ordine di Crescita Polinomiale (Teorema 1.1):
   Il saggio dimostra che per l'insieme $B$, la differenza $R_{B,h}(n+1) - R_{B,h}(n)$ cresce polinomialmente con ordine $n^{h-2}$. Nello specifico, per ogni intero $h \ge 3$, esistono costanti $c_h, C_h > 0$ tali che per ogni $n \ge 1$:
   $$c_h n^{h-2} \le R_{B,h}(n+1) - R_{B,h}(n) \le C_h n^{h-2}$$
   Questo risultato conferma che, nonostante $B$ abbia un complemento infinito con grandi lacune, la sua funzione di rappresentazione si comporta asintoticamente come l'insieme completo $\mathbb{N}$ (dove la differenza è $\binom{n+h-1}{h-2} \asymp n^{h-2}$).

2. Monotonia Stretta per Arbitrari $h \ge 3$:
   Gli autori provano rigorosamente che $R_{B,h}(n+1) > R_{B,h}(n)$ per ogni $n \ge 0$ e per ogni $h \ge 3$, migliorando il risultato di Shallit che si concentrava sull'esistenza di tali insiemi senza quantificare il tasso di crescita per ogni $h$.

3. Risoluzione del Problema della Densità di Dombi (Teorema 1.2):
   Il saggio costruisce un insieme co-infinito $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$ tale che:

• La densità asintotica esiste ed è uguale a 1: $\lim_{n \to \infty} C(n)/n = 1$.
• La funzione di rappresentazione $R_{C,h}(n)$ è strettamente crescente per ogni intero $h \ge 3$.
  Questo risponde al problema di Dombi fornendo un insieme con densità 1 (diverso dagli esempi di densità 1/2 precedentemente noti) che mantiene la monotonia stretta.

Significato
Il saggio affina la comprensione delle funzioni di rappresentazione additiva negli insiemi co-infiniti. Dimostra che l'ostruzione alla monotonia riscontrata nel caso $h=2$ non persiste per $h \ge 3$, anche quando l'insieme possiede un complemento infinito "grande". Stabilendo l'esatto ordine polinomiale della funzione differenza, gli autori mostri che l'insieme $B$ conserva la "regolarità" dell'insieme completo degli interi in termini di crescita della rappresentazione. Inoltre, la costruzione dell'insieme $C$ amplia il panorama noto di tali insiemi, mostrando che la monotonia stretta è compatibile con la densità asintotica 1, restringendo così il divario tra i comportamenti cofiniti e co-infiniti nella teoria additiva dei numeri.

Gli autori concludono ponendo problemi aperti riguardanti l'esistenza di tali insiemi per densità arbitrarie prescritte $d \in [0, 1)$ e per insiemi con specifici $\liminf$ e $\limsup$ di densità, suggerendo che la piena caratterizzazione delle condizioni di monotonia per le funzioni di rappresentazione rimanga un campo di ricerca attivo.