Extremal densities for forbidden configurations in $S$-smooth numbers

Resumo Técnico: Densidades Extremais para Configurações Proibidas em Números S-Regulares

1. O Problema

O artigo investiga um problema clássico de teoria combinatória dos números e teoria das densidades extremas, adaptado para o contexto dos números S-regulars (ou S-smooth).

• Definição de S-regulars: Seja $S = \{p_1, \dots, p_r\}$ um conjunto finito de primos distintos. O conjunto $M(S)$ consiste em todos os inteiros da forma $p_1^{a_1} \cdots p_r^{a_r}$ com $a_i \geq 0$.
• Configuração Proibida: O objetivo é encontrar o tamanho máximo de um subconjunto $A$ de $M(S) \cap [1, X]$ que não contenha nenhuma configuração do tipo $\{n, p_1n, \dots, p_rn\}$.
• Funções de Interesse:
  • $F_S(X)$: O tamanho máximo de tal subconjunto no intervalo $[1, X]$ restrito a $M(S)$.
  • $f_S(k)$: O tamanho máximo restrito aos primeiros $k$ números S-regulars.
  • $G_S(N)$: O problema análogo no intervalo completo $[1, N]$ (não restrito apenas a $M(S)$).

O problema generaliza resultados clássicos de Graham, Witsenhausen e Spencer (que estudaram o caso $S=\{2,3\}$ no intervalo inteiro) para semigrupos multiplicativos gerados por conjuntos arbitrários de primos.

2. Metodologia

O autor emprega uma combinação de técnicas de teoria dos números, geometria de números e combinatória:

• Geometria de Números e Simplesos Ponderados:
  O problema é mapeado para um espaço de coordenadas de expoentes. Um número $n = p_1^{a_1} \cdots p_r^{a_r}$ corresponde a um vetor $a = (a_1, \dots, a_r) \in \mathbb{Z}_{\geq 0}^r$. A condição de não conter $\{n, p_1n, \dots, p_rn\}$ equivale a evitar "cantos unitários" (unit corners) no simplex ponderado $\Sigma_S(u)$, definido por $\sum a_i \log p_i \leq u$.
• Coloração Modular (Limites Inferiores):
  Para estabelecer o limite inferior, o autor define uma coloração $\chi: \mathbb{Z}_{\geq 0}^r \to \mathbb{Z}/(r+1)\mathbb{Z}$ dada por $\chi(a) \equiv \sum i \cdot a_i \pmod{r+1}$.
  • Lema Chave: Todo canto unitário contém exatamente um ponto de cada cor.
  • Consequência: Removendo a classe de cor menos frequente, obtém-se um conjunto livre de cantos. Isso fornece uma densidade de pelo menos $r/(r+1)$.
• Identidades Combinatórias e Deslocamento (Limites Superiores):
  Para o limite superior, utiliza-se uma identidade que relaciona o tamanho do conjunto livre de cantos com o número de pontos nas faces do simplex (onde algum expoente é zero) e uma função de erro baseada em deslocamentos para trás. Isso demonstra que a densidade não pode exceder significativamente $r/(r+1)$.
• Decomposição e Soma de Séries:
  Para o problema no intervalo completo $[1, N]$, o autor decompõe os inteiros em $n = m \cdot d$, onde $d \in M(S)$ e $m$ é coprimo com o produto dos primos em $S$. Isso permite expressar a densidade global $\alpha_S$ como uma soma ponderada das diferenças finitas da função $f_S$.

3. Principais Contribuições e Resultados

A. Fórmula Assintótica para Números S-regulars (Teorema 1.1)
O resultado central estabelece que a densidade máxima de um subconjunto livre de configurações proibidas em $M(S)$ converge para $r/(r+1)$.
$$F_S(X) = \frac{r}{r+1}\Psi_S(X) + O_S((\log X)^{r-1})$$
Onde $\Psi_S(X)$ é a função de contagem dos números S-regulars.
Equivalentemente, para os primeiros $k$ números:
$$f_S(k) = \frac{r}{r+1}k + O_S(k^{(r-1)/r})$$
Isso confirma que a proporção de números que podem ser mantidos em um conjunto livre de cantos é exatamente $r/(r+1)$.

B. Densidade no Intervalo Completo e Constante $\alpha_S$ (Corolário 1.2)
O artigo deriva uma representação explícita para a densidade $\alpha_S$ no intervalo $[1, N]$:
$$G_S(N) = \alpha_S N + O_S((\log N)^r)$$
Onde a constante $\alpha_S$ é dada por:
$$\alpha_S = c_S \sum_{k \geq 1} \frac{\Delta f_S(k)}{d_k^{(S)}}$$
com $c_S = \prod_{p \in S} (1 - 1/p)$ e $\Delta f_S(k) \in \{0, 1\}$ indicando se o $k$-ésimo número S-regular pode ser adicionado a um conjunto ótimo sem criar uma configuração proibida.

C. Limites Computáveis e Recursão (Corolário 1.3 e Proposição 4.2)

• O autor fornece limites inferiores ($L_{S,N}$) e superiores ($U_{S,N}$) que são aninhados e convergem para $\alpha_S$.
• Desenvolve uma fórmula recursiva para calcular a "cauda recíproca" (soma dos inversos dos números S-regulars acima de um certo limite), permitindo o cálculo da densidade $\alpha_S$ com precisão arbitrária.

D. Soma Recíproca Racional Não Periódica (Proposição 1.4)
Um resultado surpreendente mostra que a soma $\sum c_k / d_k^{(S)}$ pode ser um número racional mesmo que a sequência binária $(c_k)$ (definida pela inclusão/exclusão nos conjuntos ótimos) não seja eventualmente periódica. Isso desafia a intuição de que somas racionais sobre sequências definidas por propriedades de números devem gerar sequências periódicas.

E. Caso Clássico $S = \{2, 3\}$
Para o caso histórico estudado por Graham e Spencer:

• Recupera-se a constante conhecida $\alpha = \alpha_{\{2,3\}}$.
• Obtém-se uma fórmula explícita para a cauda da série.
• Demonstra-se que não existe uma família aninhada de conjuntos ótimos ($A_1 \subseteq A_2 \subseteq \dots$). Ou seja, a estrutura dos conjuntos ótimos muda de forma não monótona à medida que $k$ aumenta, o que impede uma construção simples e recursiva direta para o conjunto ótimo global.

4. Significado e Impacto

• Generalização Teórica: O trabalho estende significativamente os resultados conhecidos sobre configurações proibidas multiplicativas de conjuntos de dois primos para conjuntos arbitrários de primos, estabelecendo a densidade universal $r/(r+1)$.
• Conexão entre Estrutura e Densidade: Ao conectar o problema de otimização combinatória (conjuntos livres de cantos) com a teoria analítica de números (funções de contagem e somas de séries), o artigo fornece ferramentas poderosas para estimar densidades em semigrupos multiplicativos.
• Computabilidade: A introdução de limites aninhados e fórmulas recursivas para a cauda da série torna o cálculo da densidade $\alpha_S$ efetivo, permitindo a determinação numérica de constantes que antes eram apenas existenciais.
• Comportamento Estrutural: A descoberta de que a sequência de decisões ótimas não é periódica, mesmo gerando somas racionais, adiciona uma camada de complexidade à compreensão da estrutura dos conjuntos extremos em teoria dos números.

Em suma, o artigo resolve assintoticamente o problema de densidade para S-regulars, fornece métodos práticos para calcular a densidade no intervalo inteiro e revela propriedades estruturais sutis sobre a natureza dos conjuntos ótimos.