Gaps of Binary Numerical Semigroups and of Binary Inclusion-Exclusion Polynomials

Résumé Technique : Gaps des Semigroupes Numériques Binaires et des Polynômes Binaires d'Inclusion-Exclusion

Énoncé du Problème
Ce travail traite des propriétés structurelles des « gapsets » des polynômes binaires d'inclusion-exclusion, notés $Q_{\{p,q\}}(x)$, et des distances entre éléments consécutifs dans le semigroupe numérique binaire associé $\langle p, q \rangle$. Le polynôme est défini par :
$$Q_{\{p,q\}}(x) := \frac{(1-x^{pq})(1-x)}{(1-x^p)(1-x^q)}$$
où $p$ et $q$ sont des entiers premiers entre eux avec $q \ge p \ge 3$. Lorsque $p$ et $q$ sont premiers, $Q_{\{p,q\}}$ se réduit au polynôme cyclotomique $\Phi_{pq}$.

Le gapset $G(f)$ d'un polynôme $f$ est défini comme l'ensemble des différences entre les exposants des coefficients non nuls consécutifs. Des recherches antérieures (par exemple Hong et al., Zhang, Cafure et Cesaratto) avaient établi des résultats spécifiques pour les plus grands gaps de $\Phi_{pq}$ sous certaines conditions (par exemple $q \equiv \pm 1 \pmod p$), mais une description complète de l'ensemble des gaps pour le cas binaire général restait un problème ouvert. L'article vise également à caractériser l'ensemble de toutes les distances possibles entre éléments consécutifs dans le semigroupe $\langle p, q \rangle = \{ iq + jp \mid i, j \ge 0 \}$.

Méthodologie
La contribution technique centrale de l'article est l'analyse d'une propriété spécifique des permutations linéaires de systèmes de résidus. Soit $p$ un module et $u$ un entier premier avec $p$. La permutation est donnée par $n \mapsto \langle un \rangle_p$, où $\langle x \rangle_p$ désigne le résidu non négatif le plus petit de $x$ modulo $p$.

L'auteur définit un « couple dominant » $(a, b)$ avec $a < b$ comme un couple satisfaisant l'une des deux inégalités suivantes :

1. $\max(\langle ua \rangle_p, \langle ub \rangle_p) < \min_{a < n < b} \langle un \rangle_p$
2. $\min(\langle ua \rangle_p, \langle ub \rangle_p) > \max_{a < n < b} \langle un \rangle_p$

Pour analyser ces couples, l'article introduit une représentation du système de résidus modulo $p$ dérivée de l'algorithme d'Euclide appliqué à $p$ et à l'inverse multiplicatif de $u$ (noté $r_1$). L'algorithme d'Euclide génère des suites $(r_i)$ et $(Z_i)$ via $r_{i-1} = Z_i r_i + r_{i+1}$.

L'auteur construit une représentation spécifique pour tout entier $n \in [0, p)$ sous la forme $n = R(z) = \sum z_i (-1)^{i-1} r_i$, où $z$ est un tuple de coefficients contraints par les paramètres de l'algorithme d'Euclide. Cette représentation permet l'évaluation explicite de $\langle un \rangle_p$ en fonction des coefficients $z_i$.

Contributions et Résultats Clés

1. Caractérisation des Couples Dominants :
   L'article démontre que l'ensemble des différences $\{b-a\}$ pour les couples dominants est exactement l'ensemble :
   $$D_\Delta(p, u) = \{ r_{i-1} - z r_i \mid 0 \le z \le Z_i - 1, \ 1 \le i \le t \}$$
   où $t$ est le nombre d'étapes dans l'algorithme d'Euclide. Ce résultat partitionne les différences possibles en ensembles $D_i$ basés sur l'indice $i$ de la suite d'Euclide.

2. Gapsets des Semigroupes Numériques :
   En fixant $u$ comme l'inverse multiplicatif de $q$ modulo $p$, l'auteur relie les couples dominants au semigroupe numérique $\langle p, q \rangle$.

   • Soit $S(p, q)$ l'ensemble des entiers représentables dans $[0, (p-1)(q-1)]$ et $N(p, q)$ l'ensemble des entiers non représentables.
   • L'ensemble des distances entre entiers représentables consécutifs, $S_\Delta(p, q) = \{ \ell_{j+1} - \ell_j \}$, et l'ensemble des distances entre entiers non représentables consécutifs, $N_\Delta(p, q) = \{ n_{j+1} - n_j \}$, sont entièrement décrits.
   • Théorème 1 : $S_\Delta(p, q) = N_\Delta(p, q)$ sauf si $q = p+1$, auquel cas $S_\Delta(p, q) = N_\Delta(p, q) \cup \{2\}$. Les deux ensembles sont égaux à $D_\Delta(p, x_1)$, où $x_1 \equiv q^{-1} \pmod p$.

3. Gapsets des Polynômes Binaires d'Inclusion-Exclusion :
   L'article établit que les gaps du polynôme $Q_{\{p,q\}}$ correspondent aux longueurs de blocs d'entiers représentables ou non représentables consécutifs. Spécifiquement, le gapset $G(p, q)$ est donné par :
   $$G(p, q) = \{ \ell_{j+1} - \ell_j - 1 \mid \ell_{j+1} > \ell_j + 1 \}$$
   Théorème 2 : Le gapset est l'union des ensembles $G_i$ :
   $$G(p, q) = \bigcup_{i=1}^t G_i, \quad \text{où } G_i = \{ r_{i-1} - z r_i - 1 \mid 0 \le z \le Z_i - 1 \}$$
   (Avec une légère modification pour l'ensemble final $G_t$). Cela fournit une description complète et constructive de tous les gaps possibles.

4. Bornes sur le Nombre de Gaps :
   Théorème 3 : L'article fournit des bornes précises sur la cardinalité du gapset, $\#G(p, q)$.

   • Bornes supérieure : $\#G(p, q) \le p - 1$.
   • Borne inférieure : $\#G(p, q) \ge k$, où $k$ est défini par $F_k < p \le F_{k+1}$ ($F_k$ étant les nombres de Fibonacci).
     L'auteur note que cela implique $\#G(p, q) > c \log p$ pour une certaine constante $c$.

Signification et Revendications
L'article revendique fournir une « description complète » des gapsets pour la classe des polynômes binaires d'inclusion-exclusion, généralisant des résultats antérieurs limités à des cas spécifiques (tels que $q \equiv \pm 1 \pmod p$) ou à des gaps spécifiques (le plus grand ou le deuxième plus grand).

La signification principale réside dans la réduction du problème des gaps polynomiaux à l'analyse des permutations linéaires de systèmes de résidus. L'auteur introduit une représentation du système de résidus basée sur l'algorithme d'Euclide qui rend les conditions pour les couples dominants « assez transparentes ». L'article postule que cette représentation présente un intérêt indépendant et pourrait avoir des applications futures dans d'autres domaines, bien qu'il ne les spécifie pas.

Les résultats unifient la compréhension des gaps dans les polynômes cyclotomiques binaires et les semigroupes numériques binaires, montrant que l'ensemble des distances entre éléments consécutifs dans le semigroupe est identique à l'ensemble des différences dans les couples dominants de la permutation linéaire associée. Le travail quantifie également la complexité de ces gapsets, montrant que le nombre de gaps distincts croît logarithmiquement avec le module $p$ dans le pire des cas (entrées de Fibonacci) et est borné linéairement par $p$ dans le meilleur des cas.