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

Resumen Técnico: Huecos de Semigrupos Numéricos Binarios y de Polinomios Binarios de Inclusión-Exclusión

Enunciado del Problema
Este trabajo aborda las propiedades estructurales de los "conjuntos de huecos" de los polinomios binarios de inclusión-exclusión, denotados $Q_{\{p,q\}}(x)$, y las distancias entre elementos consecutivos en el semigrupo numérico binario asociado $\langle p, q \rangle$. El polinomio se define como:
$$Q_{\{p,q\}}(x) := \frac{(1-x^{pq})(1-x)}{(1-x^p)(1-x^q)}$$
donde $p$ y $q$ son enteros coprimos con $q \ge p \ge 3$. Cuando $p$ y $q$ son primos, $Q_{\{p,q\}}$ se reduce al polinomio ciclotómico $\Phi_{pq}$.

El conjunto de huecos $G(f)$ de un polinomio $f$ se define como el conjunto de diferencias entre los exponentes de coeficientes no nulos consecutivos. Investigaciones anteriores (por ejemplo, Hong et al., Zhang, Cafure y Cesaratto) habían establecido resultados específicos para los mayores huecos de $\Phi_{pq}$ bajo ciertas condiciones (por ejemplo, $q \equiv \pm 1 \pmod p$), pero una descripción completa de todo el conjunto de huecos para el caso binario general permanecía como un problema abierto. El artículo también busca caracterizar el conjunto de todas las distancias posibles entre elementos consecutivos en el semigrupo $\langle p, q \rangle = \{ iq + jp \mid i, j \ge 0 \}$.

Metodología
La contribución técnica central del artículo es el análisis de una propiedad específica de las permutaciones lineales de sistemas residuales. Sea $p$ un módulo y $u$ un entero coprimo con $p$. La permutación viene dada por $n \mapsto \langle un \rangle_p$, donde $\langle x \rangle_p$ denota el residuo no negativo mínimo de $x$ módulo $p$.

El autor define un "par dominante" $(a, b)$ con $a < b$ como un par que satisface una de dos 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 analizar estos pares, el artículo introduce una representación del sistema residual módulo $p$ derivada del algoritmo euclidiano aplicado a $p$ y al inverso multiplicativo de $u$ (denotado $r_1$). El algoritmo euclidiano genera secuencias $(r_i)$ y $(Z_i)$ mediante $r_{i-1} = Z_i r_i + r_{i+1}$.

El autor construye una representación específica para cualquier entero $n \in [0, p)$ en la forma $n = R(z) = \sum z_i (-1)^{i-1} r_i$, donde $z$ es una tupla de coeficientes restringida por los parámetros del algoritmo euclidiano. Esta representación permite la evaluación explícita de $\langle un \rangle_p$ en términos de los coeficientes $z_i$.

Contribuciones y Resultados Clave

1. Caracterización de Pares Dominantes:
   El artículo demuestra que el conjunto de diferencias $\{b-a\}$ para pares dominantes es exactamente el conjunto:
   $$D_\Delta(p, u) = \{ r_{i-1} - z r_i \mid 0 \le z \le Z_i - 1, \ 1 \le i \le t \}$$
   donde $t$ es el número de pasos en el algoritmo euclidiano. Este resultado particiona las diferencias posibles en conjuntos $D_i$ basados en el índice $i$ de la secuencia euclidiana.

2. Conjuntos de Huecos de Semigrupos Numéricos:
   Al establecer $u$ como el inverso multiplicativo de $q$ módulo $p$, el autor conecta los pares dominantes con el semigrupo numérico $\langle p, q \rangle$.

   • Sea $S(p, q)$ el conjunto de enteros representables en $[0, (p-1)(q-1)]$ y $N(p, q)$ el conjunto de enteros no representables.
   • El conjunto de distancias entre enteros representables consecutivos, $S_\Delta(p, q) = \{ \ell_{j+1} - \ell_j \}$, y el conjunto de distancias entre enteros no representables consecutivos, $N_\Delta(p, q) = \{ n_{j+1} - n_j \}$, se describen completamente.
   • Teorema 1: $S_\Delta(p, q) = N_\Delta(p, q)$ a menos que $q = p+1$, caso en el cual $S_\Delta(p, q) = N_\Delta(p, q) \cup \{2\}$. Ambos conjuntos son iguales a $D_\Delta(p, x_1)$, donde $x_1 \equiv q^{-1} \pmod p$.

3. Conjuntos de Huecos de Polinomios Binarios de Inclusión-Exclusión:
   El artículo establece que los huecos del polinomio $Q_{\{p,q\}}$ corresponden a las longitudes de bloques de enteros representables o no representables consecutivos. Específicamente, el conjunto de huecos $G(p, q)$ viene dado por:
   $$G(p, q) = \{ \ell_{j+1} - \ell_j - 1 \mid \ell_{j+1} > \ell_j + 1 \}$$
   Teorema 2: El conjunto de huecos es la unión de conjuntos $G_i$:
   $$G(p, q) = \bigcup_{i=1}^t G_i, \quad \text{donde } G_i = \{ r_{i-1} - z r_i - 1 \mid 0 \le z \le Z_i - 1 \}$$
   (Con una ligera modificación para el conjunto final $G_t$). Esto proporciona una descripción completa y constructiva de todos los huecos posibles.

4. Límites en el Número de Huecos:
   Teorema 3: El artículo proporciona límites agudos para la cardinalidad del conjunto de huecos, $\#G(p, q)$.

   • Límite superior: $\#G(p, q) \le p - 1$.
   • Límite inferior: $\#G(p, q) \ge k$, donde $k$ se define mediante $F_k < p \le F_{k+1}$ ($F_k$ siendo los números de Fibonacci).
     El autor señala que esto implica $\#G(p, q) > c \log p$ para alguna constante $c$.

Significado y Afirmaciones
El artículo afirma proporcionar una "descripción completa" de los conjuntos de huecos para la clase de polinomios binarios de inclusión-exclusión, generalizando resultados anteriores que estaban limitados a casos específicos (como $q \equiv \pm 1 \pmod p$) o a huecos específicos (el mayor o el segundo mayor).

El significado principal radica en la reducción del problema de los huecos polinómicos al análisis de permutaciones lineales de sistemas residuales. El autor introduce una representación del sistema residual basada en el algoritmo euclidiano que hace que las condiciones para los pares dominantes sean "bastante transparentes". El artículo postula que esta representación es de interés independiente y puede tener aplicaciones futuras en otras áreas, aunque no las especifica.

Los resultados unifican la comprensión de los huecos en polinomios ciclotómicos binarios y semigrupos numéricos binarios, mostrando que el conjunto de distancias entre elementos consecutivos en el semigrupo es idéntico al conjunto de diferencias en los pares dominantes de la permutación lineal asociada. El trabajo también cuantifica la complejidad de estos conjuntos de huecos, mostrando que el número de huecos distintos crece logarítmicamente con el módulo $p$ en el peor de los casos (entradas de Fibonacci) y está acotado linealmente por $p$ en el mejor de los casos.