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

Resumo Técnico: Lacunas de Semigrupos Numéricos Binários e de Polinômios Binários de Inclusão-Exclusão

Enunciado do Problema
Este trabalho aborda as propriedades estruturais dos "conjuntos de lacunas" (gapsets) de polinômios binários de inclusão-exclusão, denotados por $Q_{\{p,q\}}(x)$, e as distâncias entre elementos consecutivos no semigrupo numérico binário associado $\langle p, q \rangle$. O polinômio é definido como:
$$Q_{\{p,q\}}(x) := \frac{(1-x^{pq})(1-x)}{(1-x^p)(1-x^q)}$$
onde $p$ e $q$ são inteiros coprimos com $q \ge p \ge 3$. Quando $p$ e $q$ são primos, $Q_{\{p,q\}}$ reduz-se ao polinômio ciclotômico $\Phi_{pq}$.

O conjunto de lacunas $G(f)$ de um polinômio $f$ é definido como o conjunto das diferenças entre os expoentes dos coeficientes não nulos consecutivos. Pesquisas anteriores (por exemplo, Hong et al., Zhang, Cafure e Cesaratto) haviam estabelecido resultados específicos para as maiores lacunas de $\Phi_{pq}$ sob certas condições (por exemplo, $q \equiv \pm 1 \pmod p$), mas uma descrição completa de todo o conjunto de lacunas para o caso binário geral permanecia um problema em aberto. O artigo também busca caracterizar o conjunto de todas as distâncias possíveis entre elementos consecutivos no semigrupo $\langle p, q \rangle = \{ iq + jp \mid i, j \ge 0 \}$.

Metodologia
A contribuição técnica central do artigo é a análise de uma propriedade específica de permutações lineares de sistemas de resíduos. Seja $p$ um módulo e $u$ um inteiro coprimo a $p$. A permutação é dada por $n \mapsto \langle un \rangle_p$, onde $\langle x \rangle_p$ denota o menor resíduo não negativo de $x$ módulo $p$.

O autor define um "par dominante" $(a, b)$ com $a < b$ como um par que satisfaz uma das duas desigualdades:

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$

Para analisar esses pares, o artigo introduz uma representação do sistema de resíduos módulo $p$ derivada do algoritmo de Euclides aplicado a $p$ e ao inverso multiplicativo de $u$ (denotado $r_1$). O algoritmo de Euclides gera sequências $(r_i)$ e $(Z_i)$ via $r_{i-1} = Z_i r_i + r_{i+1}$.

O autor constrói uma representação específica para qualquer inteiro $n \in [0, p)$ na forma $n = R(z) = \sum z_i (-1)^{i-1} r_i$, onde $z$ é uma tupla de coeficientes restringida pelos parâmetros do algoritmo de Euclides. Esta representação permite a avaliação explícita de $\langle un \rangle_p$ em termos dos coeficientes $z_i$.

Principais Contribuições e Resultados

1. Caracterização de Pares Dominantes:
   O artigo prova que o conjunto das diferenças $\{b-a\}$ para pares dominantes é exatamente o conjunto:
   $$D_\Delta(p, u) = \{ r_{i-1} - z r_i \mid 0 \le z \le Z_i - 1, \ 1 \le i \le t \}$$
   onde $t$ é o número de passos no algoritmo de Euclides. Este resultado particiona as diferenças possíveis em conjuntos $D_i$ baseados no índice $i$ da sequência de Euclides.

2. Conjuntos de Lacunas de Semigrupos Numéricos:
   Ao definir $u$ como o inverso multiplicativo de $q$ módulo $p$, o autor conecta os pares dominantes ao semigrupo numérico $\langle p, q \rangle$.

   • Seja $S(p, q)$ o conjunto de inteiros representáveis em $[0, (p-1)(q-1)]$ e $N(p, q)$ o conjunto de inteiros não representáveis.
   • O conjunto das distâncias entre inteiros representáveis consecutivos, $S_\Delta(p, q) = \{ \ell_{j+1} - \ell_j \}$, e o conjunto das distâncias entre inteiros não representáveis consecutivos, $N_\Delta(p, q) = \{ n_{j+1} - n_j \}$, são completamente descritos.
   • Teorema 1: $S_\Delta(p, q) = N_\Delta(p, q)$, exceto se $q = p+1$, caso em que $S_\Delta(p, q) = N_\Delta(p, q) \cup \{2\}$. Ambos os conjuntos são iguais a $D_\Delta(p, x_1)$, onde $x_1 \equiv q^{-1} \pmod p$.

3. Conjuntos de Lacunas de Polinômios Binários de Inclusão-Exclusão:
   O artigo estabelece que as lacunas do polinômio $Q_{\{p,q\}}$ correspondem aos comprimentos de blocos de inteiros representáveis ou não representáveis consecutivos. Especificamente, o conjunto de lacunas $G(p, q)$ é dado por:
   $$G(p, q) = \{ \ell_{j+1} - \ell_j - 1 \mid \ell_{j+1} > \ell_j + 1 \}$$
   Teorema 2: O conjunto de lacunas é a união dos conjuntos $G_i$:
   $$G(p, q) = \bigcup_{i=1}^t G_i, \quad \text{onde } G_i = \{ r_{i-1} - z r_i - 1 \mid 0 \le z \le Z_i - 1 \}$$
   (Com uma ligeira modificação para o conjunto final $G_t$). Isso fornece uma descrição completa e construtiva de todas as lacunas possíveis.

4. Limites para o Número de Lacunas:
   Teorema 3: O artigo fornece limites precisos para a cardinalidade do conjunto de lacunas, $\#G(p, q)$.

   • Limite superior: $\#G(p, q) \le p - 1$.
   • Limite inferior: $\#G(p, q) \ge k$, onde $k$ é definido por $F_k < p \le F_{k+1}$ ($F_k$ sendo os números de Fibonacci).
     O autor observa que isso implica $\#G(p, q) > c \log p$ para alguma constante $c$.

Significado e Afirmativas
O artigo afirma fornecer uma "descrição completa" dos conjuntos de lacunas para a classe de polinômios binários de inclusão-exclusão, generalizando resultados anteriores que eram limitados a casos específicos (como $q \equiv \pm 1 \pmod p$) ou lacunas específicas (maiores ou segunda maiores).

O significado primário reside na redução do problema das lacunas polinomiais à análise de permutações lineares de sistemas de resíduos. O autor introduz uma representação do sistema de resíduos baseada no algoritmo de Euclides que torna as condições para pares dominantes "bastante transparentes". O artigo postula que esta representação é de interesse independente e pode ter aplicações futuras em outras áreas, embora não as especifique.

Os resultados unificam a compreensão das lacunas em polinômios ciclotômicos binários e em semigrupos numéricos binários, mostrando que o conjunto das distâncias entre elementos consecutivos no semigrupo é idêntico ao conjunto das diferenças em pares dominantes da permutação linear associada. O trabalho também quantifica a complexidade desses conjuntos de lacunas, mostrando que o número de lacunas distintas cresce logaritmicamente com o módulo $p$ no pior caso (entradas de Fibonacci) e é limitado linearmente por $p$ no melhor caso.