Small sumsets and Sidon sets, the study of two extremal cases
Ensembles de petite somme et ensembles de Sidon, étude de deux extrêmes
Résumé
Notre projet se situe dans le domaine de la combinatoire additive. Il s’agit plus précisément de déterminer la taille maximale d’un sous-ensemble A d’un groupe fini G qui ne contient pas de triplets (a,a+d,a+2d) d’éléments distincts. On dit alors que A est sans progression arithmétique. Une telle progression (PA3) est en fait un exemple à la fois simple et naturel de structure additive que l’on s’attend à trouver dans un ensemble « assez gros ». Toute la difficulté consiste à déterminer ce que « assez gros » signifie ici. La recherche de la taille maximale d’un ensemble sans progression arithmétique est un problème désormais classique en combinatoire additive. Elle a donné lieu à des travaux célèbres des meilleurs spécialistes du domaine. On distingue deux aspects du problème : la détermination d’une taille au-delà de laquelle on est assuré que A possède des PA3, ce qui donne une majoration de la taille maximale d’un ensemble sans PA3, et la construction de gros ensembles sans PA3, ce qui en donne une minoration. Nous insisterons plus particulièrement sur la construction d’ensembles sans PA3 dans les groupes finis Z_q^n avec q petit. On commencera par une optimisation numérique des ensembles de base utilisés dans les constructions déjà connues et une généralisation à d’autres entiers q. On cherchera également à adapter une construction de Ruzsa à ce contexte. Cela permettra d‘aborder les difficultés de manière progressive en commençant par des manipulations combinatoires sur un groupe de base de petit cardinal autorisant donc une approche numérique.
Our project lies in the field of additive combinatorics. More precisely, we seek the maximal size of a progression free subset of a finite group G, meaning a subset with no three distinct elements of the form a, a+d, a+2d (called a 3AP for 3 arithmetic progression). A 3AP is a simple and natural pattern that we expect to find in a 'large enough' set and we shall try to precise what 'large enough' means here. Trying to determine the maximal size of a progression free set is now a classical problem in additive combinatorics, on which many of the best experts have worked. There are two different aspects in this problem : to determine a minimal size for A which assures the existence of 3AP in A, this gives an upper bound for the maximal size of a progression free set; to build some large progression free sets, this gives a lower bound for this maximal size. We will insist on the constructive part in the context of groups Z_q^n with small q. We shall also try to adapt a construction by Ruzsa to this context. The progression of this work should be from some combinatorial constructions, allowing numerical approach, to more theoretical concepts.
Origine | Fichiers produits par l'(les) auteur(s) |
---|