Bounds for Greedy $B_h$-sets

Resumen Técnico: Límites para conjuntos $B_h$ voraces (Greedy)

Planteamiento del Problema
El artículo investiga el comportamiento asintótico del algoritmo voraz (greedy) aplicado a la construcción de conjuntos $B_h$. Se define un conjunto $A$ de enteros no negativos como un conjunto $B_h$ si cada solución a la ecuación $a_1 + \dots + a_h = b_1 + \dots + b_h$ (donde $a_i, b_i \in A$) implica que los multiconjuntos $\{a_1, \dots, a_h\}$ y $\{b_1, \dots, b_h\}$ son idénticos. El objeto principal de estudio es el conjunto $B_h$ voraz, denotado como $G(h) = \{\gamma_0, \gamma_1, \gamma_2, \dots\}$, el cual se construye lexicográficamente estableciendo $\gamma_0 = 0, \gamma_1 = 1$, y definiendo $\gamma_{k+1}$ como el entero más pequeño tal que $\{\gamma_0, \dots, \gamma_{k+1}\}$ siga siendo un conjunto $B_h$.

El problema central abordado es determinar la tasa de crecimiento del $k$-ésimo elemento, $\gamma_k(h)$, como una función de $h$ para un $k$ fijo. Mientras que se conocen fórmulas exactas para $k \le 4$, el comportamiento para $k \ge 5$ ha permanecido mayormente inexplorado más allá de la enumeración computacional. El artículo busca establecer límites superiores e inferiores no triviales para $\gamma_k(h)$, específicamente apuntando al quinto elemento $\gamma_5(h)$ y límites generales para $k \ge 5$.

Metodología
El autor emplea una combinación de análisis combinatorio, acotación recursiva y enumeración detallada de casos:

1. Límites Combinatorios: El artículo utiliza la observación de que el número de sumas de $h$ términos distintos de un conjunto de tamaño $k+1$ es $\binom{k+h}{k}$. Dado que estas sumas deben caer dentro del intervalo $[h\gamma_0, h\gamma_k]$, esto produce un límite inferior base para $\gamma_k(h)$.
2. Caracterización por "Mex": Un lema clave establece que $\gamma_{k+1} = \text{mex}(F^{(k)})$, donde $F^{(k)}$ es el conjunto de todos los enteros representables como $\frac{1}{r}\sum_{i=1}^k \gamma_i(m_i - m'_i)$ bajo restricciones específicas de multiplicidades $m_i, m'_i$. Esta caracterización permite al autor acotar $\gamma_{k+1}$ contando el número de valores "prohibidos" en $F^{(k)}$ que exceden cierto umbral.
3. Construcción del Límite Inferior ($\gamma_5$): Para probar el límite inferior para $\gamma_5(h)$, el autor define un conjunto específico de vectores de enteros $\Delta$ que representan combinaciones de coeficientes válidas para los primeros cuatro elementos. Al ordenar estos vectores lexicográficamente (basándose en un ordenamiento específico de tipo "odómetro") y analizar la imagen de estos vectores bajo el producto punto con $\langle \gamma_1, \gamma_2, \gamma_3, \gamma_4 \rangle$, el autor demuestra que las imágenes forman un intervalo contiguo. Esto asegura que el "mex" (el primer entero faltante) debe ser al menos el valor máximo de un subconjunto específico de estas imágenes.
4. Construcción del Límite Superior ($\gamma_k$): Para el límite superior, el autor utiliza un enfoque inductivo. Asumiendo un límite $\gamma_k(h) \le \alpha_k h^{k-1} + O(h^{k-2})$, el autor estima el tamaño del conjunto $F^{(k)}$ por encima de un umbral $\beta_k h^k$. Al estratificar el conjunto $F^{(k)}$ basándose en las multiplicidades del elemento más grande $\gamma_k$, y aplicando el conteo combinatorio de "estrellas y barras" (stars-and-bars), el autor deriva una relación de recurrencia para los coeficientes $\alpha_k$. La secuencia $\alpha_k$ se construye para ser no creciente y converger a cero.

Contribuciones Clave y Resultados

• Límite Inferior para $\gamma_5(h)$: El artículo establece un límite inferior no trivial para el quinto elemento del conjunto $B_h$ voraz:
  $$\gamma_5(h) \ge \frac{1}{8}h^4 + \frac{1}{2}h^3$$
  Este resultado se deriva de un análisis riguroso de las sumas prohibidas generadas por los primeros cuatro elementos.

• Límites Superiores para $\gamma_k(h)$ ($k \ge 5$): El artículo proporciona los primeros límites superiores no triviales para $\gamma_k(h)$ para $k \ge 5$. Específicamente, demuestra:
  $$\gamma_k(h) \le \alpha_k h^{k-1} + O(h^{k-2})$$
  donde las constantes $\alpha_k$ se definen recursivamente. El artículo calcula explícitamente:

  • $\alpha_5 \approx 0.467214$
  • $\alpha_6 \approx 0.382978$
  • $\alpha_7 \approx 0.269877$
  • Para $k \ge 7$, $\alpha_{k+1} = \frac{1}{2} \alpha_k + \frac{1}{2^k k!} \sum_{j=0}^{k-1} \binom{k-1}{j} \binom{k}{j} 2^j$.
    Se muestra que la secuencia $\alpha_k$ decae rápidamente, lo que implica que $\gamma_k(h)$ crece más lento de lo que las estimaciones no probadas anteriormente podrían sugerir.

• Conjetura sobre $\gamma_5(h)$: Basándose en datos computacionales para $h \le 47$, el autor conjetura una fórmula asintótica precisa:
  $$\gamma_5(h) = \frac{1}{3}h^4 + O(h^3)$$
  Esto sugiere que el límite inferior de $1/8$ no es ajustado, y que el coeficiente principal real es probablemente $1/3$.

• Límite Inferior General: El artículo reitera y contextualiza el límite inferior general $\gamma_k(h) \ge \frac{1}{k!}h^{k-1} + O(h^{k-2})$, confirmando que el algoritmo voraz produce conjuntos con la tasa de crecimiento correcta para un $k$ fijo.

Significancia y Reivindicaciones
El autor enmarca la significancia de este trabajo en tres áreas principales:

1. Necesidad Estética y Teórica: Los conjuntos $B_h$ son objetos fundamentales en la teoría de números combinatoria. El autor argumenta que comprender la salida del algoritmo voraz para estos conjuntos es un problema natural que merece respuestas, independientemente de aplicaciones inmediatas.
2. Viabilidad del Análisis Voraz: El artículo contrasta la dificultad de analizar el algoritmo voraz con las construcciones no voraces (como la construcción de Singer usando cuerpos finitos). Mientras que construir un conjunto $B_{100}$ con 11 elementos mediante cuerpos finitos requiere trabajar en $\mathbb{F}_{101}^{11}$ (lo cual es computacionalmente implausible), encontrar una fórmula para el décimo elemento del conjunto $B_{100}$ voraz se describe como "difícil pero plausible". Este trabajo representa el primer paso para hacer tal análisis riguroso para $k \ge 5$.
3. Comprensión del Algoritmo Voraz: La motivación principal es comprender mejor el algoritmo voraz para conjuntos $B_2$ (conjuntos de Sidon), que tienen aplicaciones en el mundo real (por ejemplo, reglas de Golomb, asignación de frecuencias). Dado que el algoritmo voraz es una heurística estándar para problemas aditivos, establecer límites para conjuntos $B_h$ contribuye a una comprensión más amplia de las estrategias voraces en la teoría de números aditiva.

El artículo concluye enumerando problemas abiertos, incluyendo la prueba de fórmulas cuasi-polinomiales para $\gamma_k$, la distribución uniforme de los elementos en clases de congruencia, y el ínfimo de $s$ para el cual la suma de las potencias recíprocas de los conjuntos $B_h$ voraces converge. El autor se mantiene modesto, señalando que, aunque los límites son no triviales, pueden no ser ajustados, y que los coeficientes exactos para $k \ge 5$ siguen siendo conjeturales.