On the Diophantine problem related to power circuits

Titolo: Sul Problema Diofanteo Relativo ai Circuiti di Potenza

Autore: Alexander Rybalov (Istituto di Matematica Sobolev, Omsk, Russia)

---

1. Il Problema e il Contesto

Il lavoro si concentra sulla decidibilità del problema diofanteo su una specifica struttura algebrica legata ai "circuiti di potenza" (power circuits).

• Contesto: I circuiti di potenza sono stati introdotti da Myasnikov, Ushakov e Won nel 2012 come strutture computazionali che supportano l'addizione e l'operazione $(x, y) \mapsto x \cdot 2^y$ sugli interi. Questi sono stati utilizzati per risolvere il problema della parola nel gruppo di Baumslag in tempo polinomiale, nonostante il gruppo abbia una funzione di Dehn non elementare.
• La Struttura: L'oggetto di studio è la struttura $\tilde{\mathbb{N}} = \langle \mathbb{N}_{>0}; +, x \cdot 2^y, \leq, 1 \rangle$, dove $\mathbb{N}_{>0}$ è l'insieme dei numeri naturali positivi.
• La Domanda Aperta: Myasnikov, Ushakov e Won avevano posto il problema della decidibilità del problema diofanteo su $\tilde{\mathbb{N}}$ (cioè, se esiste un algoritmo per determinare se un sistema di equazioni su questa struttura ammette soluzioni).
• Confronto con altri risultati:
  • Il problema diofanteo classico su $\langle \mathbb{N}; +, \cdot, 1 \rangle$ (Decimo Problema di Hilbert) è indeducibile (Matiyasevich).
  • La teoria del primo ordine su $\langle \mathbb{N}; +, x \mapsto 2^x, 1 \rangle$ è decidibile (Semenov), il che implica la decidibilità del suo problema diofanteo.
  • Il caso intermedio $\tilde{\mathbb{N}}$ (che include $x \cdot 2^y$ ma non la moltiplicazione generale) era incerto.

2. Metodologia

L'autore dimostra l'indeducibilità del problema diofanteo su $\tilde{\mathbb{N}}$ attraverso una riduzione dal problema diofanteo sui numeri interi maggiori di 1, denotato come $DP(\mathbb{N}_{>1})$.

La strategia si articola nei seguenti passaggi logici:

1. Riduzione Preliminare: Si dimostra che il problema diofanteo su $\mathbb{N}$ può essere ridotto a quello su $\mathbb{N}_{>k}$ per ogni $k$ (Lemma 2.1). Di conseguenza, poiché $DP(\mathbb{N})$ è indecidibile, anche $DP(\mathbb{N}_{>1})$ lo è (Corollario 2.2).
2. Definibilità Diofantea: L'obiettivo è mostrare che la moltiplicazione ($x \cdot y$) è definibile diofantinamente all'interno della struttura $\tilde{\mathbb{N}}$. Se la moltiplicazione è definibile, il problema diofanteo su $\tilde{\mathbb{N}}$ diventa equivalente a quello su $\mathbb{N}$, ereditandone l'indeducibilità.
3. Costruzione Gerarchica: L'autore costruisce la definizione della moltiplicazione definendo prima relazioni e funzioni più semplici:
   • Divisibilità ($x | y$): Definita usando la proprietà $m|n \iff 2^m-1 | 2^n-1$ e l'operazione $x \cdot 2^y$.
   • Ordinamento Stretto ($x < y$): Definito tramite l'esistenza di un $z$ tale che $x+z=y$.
   • Logaritmo Binario Intero ($\lfloor \log_2 x \rfloor$): Definito usando le disuguaglianze $2^y \leq x < 2^{y+1}$.
   • Quadrato ($x^2$): Questa è la parte più complessa. L'autore definisce un insieme di numeri della forma $kx(x+1)$, filtra questi numeri usando il logaritmo binario e condizioni di divisibilità specifiche ($x+2 | y+2x$ e $x+3 | y+3x$) per isolare esattamente il quadrato $x^2$ tra i candidati.
   • Moltiplicazione ($xy$): Una volta definito il quadrato, la moltiplicazione è ottenuta tramite l'identità algebrica:
     $$xy = \frac{(x+y)^2 - x^2 - y^2}{2}$$
     Poiché la struttura supporta l'addizione e la divisione per 2 (tramite le proprietà di $x \cdot 2^y$ e la definizione di divisibilità), l'operazione di moltiplicazione è totalmente definibile.

3. Risultati Principali

• Teorema 2.9: Il problema diofanteo sulla struttura $\tilde{\mathbb{N}} = \langle \mathbb{N}_{>0}; +, x \cdot 2^y, \leq, 1 \rangle$ è indecidibile.
  • Dimostrazione: Poiché la moltiplicazione è definibile diofantinamente su $\tilde{\mathbb{N}}$, qualsiasi sistema di equazioni diofantee su $\mathbb{N}_{>1}$ può essere trasformato in un sistema equivalente su $\tilde{\mathbb{N}}$. Dato che $DP(\mathbb{N}_{>1})$ è indecidibile, ne consegue che anche $DP(\tilde{\mathbb{N}})$ lo è.
• Corollario 2.10: La struttura $\tilde{\mathbb{N}}$ non è automatica.
  • Motivazione: È noto che ogni struttura automatica ha una teoria del primo ordine decidibile (e quindi un problema diofanteo decidibile). Poiché il problema diofanteo su $\tilde{\mathbb{N}}$ è indecidibile, la struttura non può essere automatica. Questo risolve negativamente una domanda aperta in [7, Problema 10.5].

4. Contributi Chiave

1. Risoluzione di una congettura aperta: Il paper chiude definitivamente la questione sulla decidibilità del problema diofanteo per i circuiti di potenza, dimostrando l'indeducibilità.
2. Costruzione tecnica innovativa: La dimostrazione che la moltiplicazione è definibile usando solo addizione, l'operazione $x \cdot 2^y$ e l'ordinamento è un risultato tecnico significativo. In particolare, la definizione della funzione quadrato ($x^2$) tramite l'uso combinato di logaritmi discreti e condizioni di divisibilità è un contributo originale.
3. Implicazioni sulla teoria delle strutture automatiche: Fornisce un controesempio importante, mostrando che una struttura legata a problemi computazionali complessi (gruppi con funzione di Dehn non elementare) non possiede la proprietà di essere "automatica".

5. Significato e Impatto

Questo lavoro ha un impatto significativo nella teoria della complessità computazionale e nella logica matematica:

• Limiti Computazionali: Dimostra che, nonostante i circuiti di potenza permettano algoritmi efficienti per il problema della parola in certi gruppi, la struttura algebrica sottostante è sufficientemente potente da codificare l'aritmetica completa (moltiplicazione), rendendo impossibile la risoluzione algoritmica generale delle equazioni su di essa.
• Connessione tra Algebra e Logica: Collega le proprietà dei gruppi finitamente presentati (come il gruppo di Baumslag) con la teoria dei modelli e la decidibilità dei problemi diofantei.
• Metodologia: La tecnica di definire la moltiplicazione attraverso l'isolamento del quadrato tramite condizioni di divisibilità e logaritmi offre nuovi strumenti per l'analisi di strutture aritmetiche estese.

In sintesi, Rybalov dimostra che l'aggiunta dell'operazione $x \cdot 2^y$ alla somma sugli interi positivi è sufficiente per ricreare la complessità della moltiplicazione generale, rendendo il problema diofanteo su tale struttura intrattabile.