La fonction d’Erdős et Graham

Sur les bases additives dans les groupes abéliens

Introduction 

Dans toute la suite, (G, +) est un semi-groupe commutatif. De plus, on rappelle que si A est un sous-ensemble de G et h un entier, hA est l’ensemble formé des sommes de h éléments de A (non nécessairement distincts). Pour deux sous ensembles A et B de G, on note A ∼ B si leur différence symétrique est finie. On va s’intéresser à la notion de base additive. Bien qu’on en ait déjà parlé dans l’introduction générale du manuscrit, nous avons besoin ici de définir différents types de bases additives. Définition 1.1. On dit que l’ensemble A ⊂ G est – une base (asymptotique) faible d’ordre au plus h si A ∪ · · · ∪ hA ∼ G. – une base faible parfaite d’ordre au plus h si A ∪ · · · ∪ hA = G. – une base (asymptotique) d’ordre au plus h si hA ∼ G. – une base parfaite d’ordre au plus h si hA = G. Si h est le plus petit entier tel que hA ∼ G, on dit que A est une base d’ordre h et on note ord∗ G(A) = h. Si un tel h n’existe pas, on pose ord∗ G(A) = ∞. On définit évidemment l’ordre de la même façon pour les autres notions, et pour une base faible d’ordre h, on note ordG(A) = h. On peut facilement relier ces notions grâce à la remarque suivante. Dans le cas où G contient 0, A est une base faible si et seulement si A∪ {0} est une base, et on a ordG(A) = ord∗ G(A ∪ {0}). Bien entendu, les bases (faibles ou non) ne présentent 7 Chapitre 1 : Sur les bases additives dans les groupes abéliens un intérêt que lorsque G est infini. En revanche, les bases parfaites (faibles ou non) ont un sens dans un cadre fini également. Historiquement, les bases additives n’ont été étudiées que dans les cas G = N et G = Z (cf. [11] pour les entiers relatifs). En particulier, la question de savoir comment se comportait une base lorsqu’on lui enlevait un élément a donné lieu à de nombreux résultats, sur les fonctions E, X et S que nous introduirons dans les trois sous-sections qui suivent. Nous y donnerons certains résultats connus dans N, et expliquerons comment ces fonctions se comportent dans un groupe G infini. Pour un panorama plus exhaustif de cae thème de recherche, dans le cas des entiers naturels, on conseille la lecture de [13] ou [5]. Mais avant de chercher des propriétés sur les bases additives dans un groupe quelconque, il est naturel de se poser la question d’existence de bases d’ordre h, pour h ≥ 1. Le cas h = 1 est trivial. En effet, il suffit de considérer G tout entier ou G privé d’un nombre fini d’éléments selon ce qu’on veut obtenir. Dans le Théorème 1.1 ci-dessous, on montre un résultat plus fort que la simple existence d’une base d’ordre h. Il existe en fait une base minimale A d’ordre h, c’est-à-dire que pour tout a ∈ A, A \ {a} n’est plus une base d’ordre h (cela peut être une base d’ordre plus élevé). Dit autrement, chaque élément de A est nécessaire à ce que A soit une base d’ordre h. 

Théorème

soient G un groupe abélien infini et h un entier, h ≥ 2. Alors G admet une base parfaite minimale d’ordre h. La démonstration de ce théorème sera l’objet de la section 1.3. 

Élements exceptionnels 

La première question qu’on se pose est de savoir si lorsqu’on enlève un élément a de A une base additive, A \ {a} est toujours une base. Considérons un premier exemple simple pour se familiariser avec ces problèmes. On considère dans N la base additive suivante, d’ordre 2 (celle-ci est d’ailleurs parfaite) : A = {1} ∪ 2N. A \ {1} n’est plus une base, puisque cet ensemble n’engendre plus que les nombres pairs. Si on enlève un autre élément a, A \ {a} reste une base ; elle n’est plus parfaite d’ordre 2, mais ce n’est pas ce qui nous intéresse ici. 

Définition

 Soit a ∈ A, où A est une base de G. On dit que a est un élément exceptionnel si A \ {a} n’est plus une base de G. Dans le cas contraire, a est un élément régulier. On note A∗ l’ensemble des éléments réguliers de A.

Dans l’exemple précédent, A admet un seul élément exceptionnel. Grekos [6] a montré que le nombre d’éléments exceptionnels de A peut être majoré par h − 1, ce qui donne un sens à la définition suivante. E(h) = max hA∼N |A \ A ∗ |. (1.1) Plagne, dans [15], a obtenu l’équivalent suivant, lorsque h → ∞ : E(h) ∼ 2 s h log h . (1.2) Pour un groupe G quelconque, il n’est a priori pas clair que la fonction EG est bien définie, c’est-à-dire que le nombre d’éléments exceptionnels peut être majoré en fonction de h seulement. Le théorème suivant répond affirmativement à ce problème, et montre de plus que la borne obtenue est la meilleure possible. Théorème 1.2. (i) Pour tout G groupe abélien infini et pour tout h ≥ 1, EG(h) ≤ h − 1, (ii) il existe un groupe G infini qui vérifie EG(h) = h − 1 pour tout h ≥ 1, (iii) pour tout h ≥ 1, il existe un groupe G infini (qui dépend de h) pour lequel EG(h) = 0. Remarque. En fait, EG(1) = 0 pour tout G, donc seul le cas h ≥ 2 nous intéressera réellement dans les preuves. Comme on va le voir plus tard, les points (ii) et (iii) viendront de l’étude du cas G = Fp[t] l’anneau des polynômes sur le corps Fp, pour lequel on a EFp[t](h) =  » h − 1 p − 1 # . Le Théorème 1.2 sera démontré dans la section 1.4.

La fonction d’Erdős et Graham

 On se demande maintenant, lorsque a est un élément régulier de A base d’ordre h, comment se comporte l’ordre de A \ {a}. Erdős et Graham [3] ont étudié cette question dans N et montré qu’on peut majorer l’ordre de A \ {a} en fonction de h seulement, ce qui donne un sens à la fonction X(h) = max hA∼N max a∈A∗ ord∗ (A \ {a}). (1.3) 9 Chapitre 1 : Sur les bases additives dans les groupes abéliens À l’heure actuelle, les meilleures minoration et majoration de X(h) sont dues à Plagne [14], qui a amélioré celles obtenues par Stöhr [16], Grekos [6] et Nash [12] notamment. On a  » h(h + 4) 3 # ≤ X(h) ≤ h(h + 1) 2 + & h − 1 3 ‘ . (1.4) Erdős et Graham [4] ont conjecturé qu’il existe une constante α telle que X(h) ∼ αh2 quand h → ∞, mais ce problème est toujours ouvert. Les inégalités (1.4) conduisent à X(1) = 1, X(2) = 4, X(3) = 7, mais la valeur de X(4) reste inconnue. On s’intéresse ici à ce problème dans le cas d’un groupe G quelconque, et on définit de même XG(h) = max hA∼G max a∈A∗ ord∗ G(A \ {a}). (1.5) Dans [3], Erdős et Graham utilisent une version différente de la fonction X, à savoir xG(h) = max{ord∗ G(A) : ∪ h i=1iA ∼ G et ord∗ G(A) < ∞} (1.6) = max{ord∗ G(A) : ∪ h i=1iA ∼ G et hA − Ai = G} avec G = N dans leur cas, et où hBi désigne le sous-groupe engendré par un ensemble B dans G. Dans la mesure où il nous sera préférable de travailler avec l’une ou l’autre de ces deux fonctions selon les cas, voyons dès à présent pourquoi elles sont égales (lorsqu’elles sont bien définies). Lemme 1.1. Pour tout groupe infini G, XG = xG. Démonstration. Soient h ≥ 1 et A une base d’ordre au plus h de G. Soit a ∈ A un élément régulier de A, alors B := A − a est également une base d’ordre au plus h et contient 0. Ainsi, B \ {0} est une base faible. De plus, ord∗ G(B \ {0}) = ord∗ G(A \ {a}), ce qui implique XG(h) ≤ xG(h). Pour l’autre sens, d’après les définitions de XG et xG, on a clairement h ≤ XG(h) et h ≤ xG(h). Si xG(h) = h, alors XG(h) = h = xG(h), puisque XG(h) ≤ xG(h). Ainsi, on peut supposer xG(h) > h (remarquons que c’est en fait toujours le cas, dès que h ≥ 2 d’après le Théorème 1.1). Soit B une base faible d’ordre au plus h de G satisfaisant h < ord∗ G(B) < ∞. Alors 0 6∈ B (sinon, ord∗ G(B) = ordG(B) ≤ h). Posons A = B ∪ {0}. A est donc une base d’ordre au plus h et 0 est un élément régulier de A car A \ {0} = B. En outre, ord∗ G(A \ {0}) = ord∗ G(B), ce qui donne bien xG(h) ≤ XG(h). L’étude de XG est nettement moins concluante que celle de EG. En effet, on ne sait même pas si XG(h) est fini pour tout G. Cependant, nous sommes capables de répondre à ce problème et donner des bornes pour XG(h) pour une large catégorie de groupes. Avant d’énoncer nos résultats, nous avons besoin de rappeler la définition de la fonction arithmétique Ω : Ω(n) = α1 + · · · + αk, (1.7) si n = p α1 1 · · · p αk k est la factorisation en produit de nombres premiers distincts de n. Rappelons de plus que nous désignons par m · A le sous-ensemble de G m · A = {ma : a ∈ A}. En adaptant l’idée d’Erdős et Graham, on obtient le théorème suivant. 

Théorème

Soit G un groupe abélien infini tel que pour tout entier 1 ≤ m ≤ h, le quotient G/m · G est fini, alors XG(h) ≤ h 2 + h · max 1≤m≤h Ω (|G/m · G|) + h − 1. (1.8) Parmi les groupes qui satisfont l’hypothèse du Théorème 1.3, on retrouve notamment les groupes abéliens de type fini, les groupes divisibles (i.e les groupes G tels que m · G = G pour tout m ∈ Z +, ce qui inclut R et Q) et Zp (les entiers p-adiques). Pour ce qui est de la minoration, on démontre que l’inégalité (1.4) se généralise aux groupes admettant Z comme quotient. 

Théorème

 Soit G un groupe abélien infini. Supposons qu’il existe un sous groupe H de G tel que G/H ∼= Z (isomorphisme algébrique), alors pour tout entier h ≥ 1, on a XG(h) ≥  » h(h + 4) 3 # . Cela pourrait laisser penser que XG(h) a une croissance quadratique. Nous montrons que ce n’est en fait pas le cas, en exhibant une classe de groupes pour lesquels XG(h) a une croissance linéaire.