Ensembles k-libres

Dans ce chapitre, nous nous intéressons aux ensembles k-libres, que nous pou- vons définir dans un monoïde quelconque, même si nous les étudierons ici unique- ment dans le cas des entiers naturels et des anneaux Z/nZ. Tout au long de l’étude, k et n seront des entiers naturels différents de 0. Lorsque nous dirons qu’un en- semble est optimal, cela signifiera qu’il est maximal au sens de la taille (cardinal), à ne pas confondre avec maximal au sens de l’inclusion.Un ensemble 1-libre étant nécessairement vide, on considèrera maintenant k ≥ 2. Au-delà de leur propre intérêt, ces ensembles apparaissent naturellement dans l’étude des ensembles k-Sidon (“k-fold Sidon set” en anglais).Ces ensembles ont été introduits par Lazebnik et Verstraëte (voir [3]) dans un travail sur le nombre de Turán généralisé. Remarquons pour commencer qu’un ensemble 1-Sidon est un ensemble de Sidon au sens usuel (x1 +x2 = x3 +x4 n’admet que les solutions triviales). Si on note D∗(A) = {a1 − a2, a1 6= a2 ∈ A}, l’ensemble des différences de A privé de 0, un 2-Sidon A est un ensemble de Sidon pour lequel D∗(A) est 2-libre (ou sans double). Plus généralement, si A est un ensemble k-Sidon, D∗(A) est k0-libre, pour tout 1 < k0 ≤ k. Bien que cette propriété ne soit pas suffisante en générale pour que A soit un ensemble k-Sidon (pour k = 3 par exemple, l’équation 3×1 = 2×3 + x4 n’admet également que des solutions triviales), c’est en utilisant seulement celle-ci que Cilleruelo et Timons ont prouvé dans [2] que pour tout entier k > 1, un ensemble k-Sidon A ⊂ J0, nK a au plus (n/k)1/2 + O((nk)1/4) éléments.

On sait seulement que le terme principal (n/k)1/2 est optimal pour k = 1. En effet, les ensembles de Sidon ont été très largement étudiés (cf. [5]), et on connaît en particulier trois constructions d’ensembles de Sidon maximaux au sens de la taille dans Z/nZ pour certains n. Bose et Chowla ont prouvé dans [1] l’existence d’un ensemble de Sidon de cardinal q + 1 dans Z/ (q2 + q + 1) Z (ensembles de Singer, voir aussi [7]) et de cardinal q dans Z/ (q2 − 1) Z (ensembles de Bose) où q est une puissance d’un nombre premier. La troisième construction optimale connue a été donnée par Ruzsa dans [6] pour Z/ (p2 − p) Z lorsque p est premier. Pour k = 2, si n = 22C’est donc en s’intéressant à ces ensembles que nous avons été amenés à étudier les ensembles k-libres. On parlera dans la section 3.2 du cas des entiers naturels, où des résultats étaient déjà connus. Mais pour ces différents problèmes où l’on cherche à optimiser la taille d’un ensemble sous des contraintes arithmétiques, il est important et utile d’étudier le cas des ensembles modulaires Z/nZ. C’est dans cette optique que l’on va s’intéresser aux ensembles k-libres optimaux dans Z/nZ, ce dont nous parlerons dans la section 3.3.

L’intérêt de cette partition est que les orbites que l’on considère ici sont indépen- dantes pour notre problème au sens où si x appartient à Ok(i), kx aussi. Ainsi, on se ramène à voir un ensemble k-libre comme un ensemble qui ne possède pas deux éléments consécutifs au sein de chacune de ces orbites.éléments. Pour voir cela, il suffit de considérer la parité du cardinal de l’orbite. En sommant ces quantités sur chacune des orbites, nous allons obte- nir rk(n). Cette méthode nous permet en outre de connaître tous les ensembles optimaux possibles.dans lesquelles on prend un élément sur deux, en commençant par le premier. Il s’agit clairement du prolongement des ensembles qu’on a pu considérer auparavant. B est donc un ensemble k-libre optimal dans N, de densité k/(k + 1).En suivant le même schéma, nous allons calculer la taille minimale d’un en- semble k-libre maximal au sens de l’inclusion. En effet, considérant toujours la partition en orbitespour qu’un ensemble B soit maximal au sens de l’inclusion des ensembles k-libres, cela signifie que sur chacune de ces orbites, B ne contient pas deux éléments consécutifs, il n’existe pas trois éléments consécutifs qui ne soient pas dans B (sinon, on pourrait rajouter par exemple le deuxième de ces trois éléments), l’un des deux premiers éléments de l’orbite est dans B et l’un des deux derniers éléments de l’orbite est dans B. Réciproquement, il est clair que si un ensemble vérifie ces quatre propriétés, il est k-libre, et si on lui ajoute un élément, il ne l’est plus.