On the structure of sumsets and representation functions with prescribed rates of growth

Abstract

Cette thèse explore la structure additive et les propriétés de représentation des ensembles en combinatoire additive, en se concentrant sur deux thèmes principaux :

-- Structure des ensembles somme : Soit $A \subseteq \mathbb{Z}_{\geq 0}$ un ensemble fini avec un élément minimum $0$, un élément maximum $m$, et $\ell$ éléments entre les deux. Définissons $(hA)^{(t)}$ comme l'ensemble des entiers ayant au moins $t$ représentations sous forme de somme de $h$ éléments de $A$. Nous prouvons que $(hA)^{(t)}$ est structuré lorsque \[ h \geq (1+o(1))\frac{1}{e} m\ell t^{1/\ell}, \] dans le régime $\ell \to \infty$, $t^{1/\ell} \to\infty$ et construisons des contre-exemples presque optimaux lorsque $h \ll m\ell t^{1/\ell}$. Des résultats similaires s'étendent aux sous-ensembles de $\mathbb{Z}^d$. De plus, nous interprétons les mouvements des pièces d'échecs comme des ensembles somme, montrant qu'un cavalier atteint une case générique plus efficacement qu'un roi, avec un facteur moyen de $24/13$.

-- Fonctions de représentation avec des taux de croissance prescrits : Étant donné des entiers positifs $b_1, \dots, b_h$ avec $\gcd(b_1, \dots, b_h) = 1$, nous étudions la fonction de représentation \[ r_{A,h}(n) = \#\{ (x_1, \dots, x_h) \in A^h : b_1 x_1 + \cdots + b_h x_h = n \}. \] Nous montrons que si $F(n) \leq r_{\mathbb{N},h}(n)$ est régulièrement croissante avec $\lim_{n \to \infty} F(n)/\log n = \infty$, il existe un ensemble $A \subseteq \mathbb{N}$ tel que $r_{A,h}(n) \sim F(n)$. Lorsque $F$ est croissante et que $F(2x) \ll F(x)$, nous construisons un ensemble $A$ satisfaisant $r_{A,h}(n) \asymp F(n)$, et fournissons une heuristique suggérant que si $\limsup_{n \to \infty} r_{A,h}(n)/\log n < 1$, alors $r_{A,h}(n) = 0$ pour une infinité de $n$.

S'appuyant sur les résultats de Vu et Wooley, nous étudions les fonctions de représentation pour les puissances $k$-ièmes $\mathbb{N}^k$ et les puissances $k$-ièmes des premiers $\mathbb{P}^k$. Pour $h \geq h_k = O(8^k k^2)$ et $F(n)$ régulièrement croissante satisfaisant $\lim_{n\to\infty} F(n)/\log n = \infty$, nous montrons l'existence d'un ensemble $A \subseteq \mathbb{N}^k$ tel que \[ r_{A,h}(n) \sim \mathfrak{S}_{k,h}(n) F(n), \] où $\mathfrak{S}_{k,h}(n)$ est la série singulière associée au problème de Waring. Dans le cas des puissances premières, nous obtenons des résultats analogues pour $F(n) = n^{\kappa}$. Pour $F(n) = \log n$, nous montrons que pour chaque $h \geq 2k^2(2\log k + \log\log k + O(1))$, il existe un ensemble $A \subseteq \mathbb{P}^k$ tel que $r_{A,h}(n) \asymp \log n$, ce qui montre l'existence de sous-bases minces pour les puissances premières.

This thesis investigates the additive structure and representation properties of sets in additive combinatorics, focusing on two main themes:

-- Structure of sumsets: Let $A \subseteq \mathbb{Z}_{\geq 0}$ be a finite set with minimum element $0$, maximum element $m$, and $\ell$ elements in between. Define $(hA)^{(t)}$ as the set of integers with at least $t$ representations as a sum of $h$ elements of $A$. We prove that $(hA)^{(t)}$ is structured when \[ h \geq (1+o(1))\frac{1}{e} m\ell t^{1/\ell}, \] in the regime $\ell \to \infty$, $t^{1/\ell} \to \infty$ and construct near-optimal counterexamples when $h \ll m\ell t^{1/\ell}$. Similar results extend to subsets of $\mathbb{Z}^d$. Additionally, we interpret chess piece movements as sumsets, showing that a knight reaches a generic square more efficiently than a king by a factor of $24/13$ on average.

-- Representation functions with prescribed rates of growth: Given positive integers $b_1, \dots, b_h$ with $\gcd(b_1, \dots, b_h) = 1$, we study the representation function \[ r_{A,h}(n) = \#\{ (x_1, \dots, x_h) \in A^h : b_1 x_1 + \cdots + b_h x_h = n \}. \] We show that if $F(n) \leq r_{\mathbb{N},h}(n)$ is regularly varying with $\lim_{n\to\infty} F(n)/\log n = \infty$, there exists $A \subseteq \mathbb{N}$ such that $r_{A,h}(n) \sim F(n)$. When $F$ is increasing and $F(2x)\ll F(x)$, we construct $A$ satisfying $r_{A,h}(n) \asymp F(n)$, and provide a heuristic suggesting that if $\limsup_{n\to\infty} r_{A,h}(n)/\log n < 1$, then $r_{A,h}(n) = 0$ for infinitely many $n$.

Building on results of Vu and Wooley, we investigate representation functions of $k$-th powers $\mathbb{N}^k$ and $k$-th powers of primes $\mathbb{P}^k$. For $h \geq h_k = O(8^k k^2)$ and regularly varying $F(n)$ satisfying $\lim_{n\to\infty} F(n)/\log n = \infty$, we show the existence of $A \subseteq \mathbb{N}^k$ such that \[ r_{A,h}(n) \sim \mathfrak{S}_{k,h}(n) F(n), \] where $\mathfrak{S}_{k,h}(n)$ is the singular series associated to Waring's problem. In the case of prime powers, we obtain analogous results for $F(n) = n^{\kappa}$. For $F(n) = \log n$, we show that for every $h \geq 2k^2(2\log k + \log\log k + O(1))$, there exists $A \subseteq \mathbb{P}^k$ such that $r_{A,h}(n) \asymp \log n$, showing the existence of thin subbases of prime powers.