On the Frobenius Number and Genus of a Collection of Semigroups Generalizing Repunit Numerical Semigroups

Resumo Técnico: Números de Frobenius e Gênero de Coleções de Semigrupos Numéricos Generalizados

1. O Problema

O artigo aborda o Problema de Frobenius (também conhecido como Problema do Troco ou Problema de Coin Change) no contexto de semigrupos numéricos. Dada uma sequência de inteiros positivos $A = (a_1, a_2, \dots, a_n)$ com $\gcd(A) = 1$, o semigrupo numérico gerado por $A$ é denotado por $\langle A \rangle$. O problema consiste em determinar dois invariantes fundamentais:

1. O Número de Frobenius ($F(A)$): O maior inteiro que não pertence a $\langle A \rangle$.
2. O Gênero ($g(A)$): O número de inteiros positivos que não pertencem a $\langle A \rangle$.

Embora existam fórmulas fechadas para $n=2$ (fórmula de Sylvester), para $n \geq 3$, Curtis provou que não existem fórmulas fechadas gerais do tipo polinomial. O foco deste trabalho é resolver o problema para classes específicas e generalizadas de semigrupos que incluem, mas não se limitam a, os semigrupos de Repunit, Mersenne, Thabit e Proth.

2. Metodologia

Os autores desenvolvem uma abordagem unificada baseada na teoria dos Conjuntos de Apéry e em problemas de minimização combinatória.

• Conjuntos de Apéry: Para um elemento $w \in \langle A \rangle$, o conjunto de Apéry é definido como $\text{Ap}(A, w) = \{s \in \langle A \rangle \mid s - w \notin \langle A \rangle\}$. O número de Frobenius e o gênero podem ser calculados diretamente a partir dos elementos máximos e da soma dos elementos deste conjunto (Lemmas 2.1 e 2.2).
• Generalização da Estrutura: O artigo define uma coleção geral de semigrupos, chamada Collection GCNS, gerada por sequências da forma:
  $$A = (a, h_1a + db_1, h_2a + db_2, \dots, h_ka + db_k)$$
  onde $b_1=1$, $b_{i+1} = s_i b_i + 1$ (com $s_i \geq s_{i-1}$), e $h_i = u b_i + 1$.
• Sequências Ordenadas (Orderly Sequences): Uma inovação metodológica crucial é o uso de sequências "ordenadas" (orderly). Uma sequência $B$ é ordenada se a solução do problema de mudança de moedas (minimizar o número de moedas para um valor $M$) pode ser encontrada sempre usando o algoritmo ganancioso (greedy). Os autores utilizam o Teorema do Ponto Único (One-Point Theorem) para provar que suas sequências $B$ são ordenadas sob certas condições.
• Representação Gananciosa: Devido à propriedade de ordenação, o conjunto de Apéry pode ser caracterizado pela "representação gananciosa" dos inteiros módulo $a$. Isso permite transformar o problema de encontrar o máximo do conjunto de Apéry em um problema de otimização linear discreta resolúvel algoritmicamente.
• Tratamento de $d$ Negativo: Uma contribuição técnica significativa é a capacidade de lidar com $d$ sendo um inteiro negativo, o que expande o escopo para semigrupos como os de Proth, onde os geradores têm a forma $m2^{n+i} + 1$ (equivalente a $d=-1$ em certas parametrizações).

3. Principais Contribuições e Resultados

A. Fórmulas Gerais para Collection GCNS (Teorema 2.12 e 2.13)
Os autores estabelecem fórmulas fechadas para $F(A)$ e $g(A)$ para a coleção generalizada GCNS, sob restrições específicas nos parâmetros ($ua + d + k - 2 \geq \sum s_i$ e $s_i < u + 1$).

• O número de Frobenius é dado por:
  $$F(A) = \sum_{i=1}^k x_i \cdot a + (a-1)(ua + d) - a$$
  onde $(x_1, \dots, x_k)$ é a representação gananciosa de $a-1$ na base $B$.
• O gênero é expresso como uma soma envolvendo as representações gananciosas de todos os inteiros de $0$a$a-1$.

B. Generalização de Semigrupos de Repunit e Mersenne (Seção 3)
Aplicando os resultados gerais ao caso onde $b_i = \frac{b^i-1}{b-1}$ e $u = b-1$, os autores recuperam e generalizam resultados conhecidos para semigrupos de Repunit ($S(b, n)$) e Mersenne ($S(n)$).

• Fornecem fórmulas explícitas para $F(A)$, $g(A)$ e o conjunto de números pseudo-Frobenius ($PF(A)$).
• Determinam que o tipo do semigrupo (cardinalidade de $PF(A)$) é$n-1$ para os casos de Repunit.

C. Generalização de Semigrupos de Thabit (Seção 4)
Para o caso $b_i = 2^i - 1$ e $u=1$, o trabalho generaliza os semigrupos de Thabit.

• Derivam fórmulas fechadas para $F(A)$ e $g(A)$ que dependem de $n$ e $d$.
• Determinam que o tipo do semigrupo é $n+1$ e descrevem a estrutura do conjunto $PF(A)$.

D. Solução Parcial para Semigrupos de Proth (Seção 5)
O artigo aborda o Problema Aberto 1.3 de Srivastava e Thakkar sobre semigrupos de Proth $P_m(n)$ gerados por $\{m2^{n+i} + 1\}$.

• Os autores fornecem uma caracterização completa do conjunto de Apéry para $P_m(n)$.
• Derivam fórmulas para o gênero $g(P_m(n))$.
• Para o número de Frobenius, eles resolvem o problema para casos específicos de $m$ (onde $m = 2^r + q$ com $q$ ímpar), fornecendo fórmulas explícitas baseadas na representação gananciosa de $(2^r+q)2^n$.
• Apresentam uma tabela (Tabela 1) com as representações gananciosas e as fórmulas correspondentes para $q < 50$, resolvendo parcialmente o problema aberto para uma vasta gama de casos.

E. Novas Classes de Semigrupos (Seção 6)
Os autores identificam e resolvem o problema de Frobenius para uma nova classe de semigrupos definida por $a = m(2^k-1) + 2^{k-1}-1$, fornecendo fórmulas fechadas para $F(A)$ e $g(A)$ que não estavam disponíveis anteriormente na literatura.

4. Significância e Impacto

• Unificação: O trabalho oferece uma estrutura teórica unificada que engloba diversas classes de semigrupos numéricos estudados anteriormente de forma isolada (Repunit, Mersenne, Thabit, Proth, etc.).
• Generalização: Ao permitir que o parâmetro $d$ seja negativo, o método expande a aplicabilidade para semigrupos gerados por sequências com termos decrescentes ou com estrutura diferente, como os de Proth.
• Resolução de Problemas Abertos: O artigo fornece uma solução parcial significativa para o problema aberto sobre semigrupos de Proth, oferecendo fórmulas explícitas onde antes havia apenas limites ou casos específicos.
• Eficiência Computacional: A demonstração de que as sequências subjacentes são "ordenadas" permite que o cálculo dos invariantes seja feito via algoritmos gananciosos, o que é computacionalmente eficiente em comparação com métodos de força bruta ou programação linear inteira geral.

Em suma, o artigo avança a teoria dos semigrupos numéricos ao estabelecer uma metodologia robusta baseada em conjuntos de Apéry e algoritmos gananciosos para uma ampla família de geradores, fornecendo soluções fechadas para problemas que eram anteriormente considerados difíceis ou apenas parcialmente resolvidos.