On the Diophantine problem related to power circuits

1. O Problema

O artigo aborda a decidibilidade do Problema Diofantino sobre a estrutura $\tilde{\mathbb{N}} = \langle \mathbb{N}_{>0}; +, x \cdot 2^y, \le, 1 \rangle$.

• Contexto: As "circuitos de potência" (power circuits) foram introduzidos por Myasnikov, Ushakov e Won em 2012 para resolver o problema da palavra no grupo de Baumslag em tempo polinomial. Essas estruturas suportam adição e a operação $(x, y) \mapsto x \cdot 2^y$ sobre inteiros.
• A Questão Aberta: Os autores anteriores levantaram a questão de saber se o problema diofantino sobre $\tilde{\mathbb{N}}$ é decidível. Este problema é análogo ao Décimo Problema de Hilbert (sobre $\langle \mathbb{N}; +, \cdot, 1 \rangle$, que é indecidível), mas com uma operação de multiplicação por potência de 2 em vez da multiplicação geral.
• Motivação Adicional: A decidibilidade deste problema está diretamente ligada à questão de saber se a estrutura $\tilde{\mathbb{N}}$ é "automática". Estruturas automáticas possuem teorias de primeira ordem decidíveis; portanto, se o problema diofantino for indecidível, a estrutura não pode ser automática.

2. Metodologia

A prova de indecidibilidade segue uma estratégia de redução e definição diofantina:

1. Redução de Domínio: O autor primeiro estabelece que o problema diofantino sobre os inteiros naturais $\mathbb{N}$ pode ser reduzido ao problema sobre inteiros maiores que um ($\mathbb{N}_{>1}$). Isso é feito enumerando todas as atribuições possíveis de variáveis para os valores $\{0, \dots, k\}$ e transformando o sistema original em um conjunto finito de sistemas onde as variáveis são restringidas a $\mathbb{N}_{>k}$.
2. Definição de Relações e Funções: O núcleo da prova consiste em demonstrar que operações aritméticas fundamentais (divisibilidade, ordem estrita, logaritmo binário, quadrado e multiplicação) podem ser definidas diofantinamente dentro da estrutura $\tilde{\mathbb{N}}$.
   • Uma relação $R$ é definível diofantinamente se existir um sistema de equações sobre a estrutura tal que a relação seja verdadeira se e somente se o sistema tiver solução.
3. Construção da Multiplicação: O passo crucial é definir a multiplicação $xy$ para $x, y > 1$ usando apenas as operações disponíveis em $\tilde{\mathbb{N}}$ (adição, $x \cdot 2^y$, ordem e o elemento 1).
   • O autor utiliza a identidade algébrica $z = xy \iff 2z = (x+y)^2 - x^2 - y^2$.
   • Para isso, ele primeiro define o quadrado $x^2$ e o logaritmo binário $\lfloor \log_2 x \rfloor$.
   • A definição de $x^2$ é feita isolando o termo $x^2$ de um conjunto de candidatos gerados por divisibilidade e restrições de magnitude (usando o logaritmo).

3. Contribuições Chave (Lemas e Teoremas)

• Lema 2.1 & Corolário 2.2: Estabelecem que o problema diofantino sobre $\mathbb{N}_{>k}$ é indecidível para qualquer $k$, reduzindo-o ao problema clássico sobre $\mathbb{N}$.
• Lema 2.3: Prova que $m | n \iff 2^m - 1 | 2^n - 1$, permitindo definir a divisibilidade em termos de potências de 2.
• Lema 2.4: A relação de divisibilidade $x | y$ é definível diofantinamente em $\tilde{\mathbb{N}}$.
• Lema 2.5: A ordem estrita $x < y$ é definível (via existência de $z$ tal que $x+z=y$).
• Lema 2.6: O logaritmo binário inteiro $\lfloor \log_2 x \rfloor$ é definível, permitindo controlar a magnitude das variáveis.
• Lema 2.7: A função quadrado $sq(x) = x^2$ é definível. O autor constrói um conjunto de candidatos $S'(x)$ que contém $x^2$ e outros termos polinomiais, e usa condições de divisibilidade adicionais ($x+2 | y+2x$ e $x+3 | y+3x$) para eliminar os falsos positivos, isolando $x^2$.
• Lema 2.8: A multiplicação $mul(x, y) = xy$ é definível para $x, y > 1$, utilizando a identidade de soma de quadrados mencionada acima.
• Teorema 2.9 (Resultado Principal): O problema diofantino sobre $\tilde{\mathbb{N}}$ é indecidível.
  • Raciocínio: Como a multiplicação e a adição são definíveis em $\tilde{\mathbb{N}}$ para inteiros maiores que 1, e o problema diofantino sobre $\mathbb{N}_{>1}$ é indecidível, segue-se que o problema sobre $\tilde{\mathbb{N}}$ também o é.
• Corolário 2.10: A estrutura $\tilde{\mathbb{N}}$ não é automática. Isso responde negativamente à questão 10.5 do trabalho anterior de Myasnikov et al.

4. Resultados e Significância

• Resolução de uma Questão Aberta: O artigo resolve definitivamente a questão de decidibilidade levantada por Myasnikov, Ushakov e Won, provando que não existe um algoritmo para decidir se um sistema de equações sobre circuitos de potência tem solução.
• Implicações para Teoria de Modelos e Computação:
  • Demonstra que, embora a estrutura $\tilde{\mathbb{N}}$ seja poderosa o suficiente para simular a multiplicação (e, portanto, a aritmética completa de Peano em um subconjunto), ela não possui uma teoria de primeira ordem decidível.
  • Confirma que os circuitos de potência, apesar de permitirem algoritmos eficientes para o problema da palavra em grupos específicos (como o grupo de Baumslag), carregam uma complexidade computacional intrínseca (indecidibilidade diofantina) quando considerados como estruturas algébricas puras.
• Técnica de Prova: O trabalho oferece uma construção elegante para definir a multiplicação usando apenas adição e a operação de "escalonamento por potência de 2", superando a intuição de que a falta da multiplicação direta tornaria o sistema mais fraco (como no caso da teoria de Presburger com exponenciação, que é decidível). A chave foi a restrição ao domínio $\mathbb{N}_{>0}$ e o uso inteligente de propriedades de divisibilidade de números da forma $2^n-1$.

Em suma, Rybalov demonstra que a estrutura subjacente aos circuitos de potência é computacionalmente tão complexa quanto a aritmética padrão dos inteiros no que tange à resolução de equações diofantinas, tornando o problema indecidível.