🔢 mathematics

Positivity of Nearly Linearly Recurrent Sequences

Questo articolo presenta un procedimento decisionale per il problema della positività delle ricorrenze quasi lineari di ordine due, basato su un nuovo risultato di trascendenza per le serie infinite.

Autori originali: Amaury Pouly, Mahsa Shirmohammadi, James Worrell

Pubblicato 2026-03-04

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Amaury Pouly, Mahsa Shirmohammadi, James Worrell

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di avere una macchina del tempo matematica che genera una sequenza di numeri, uno dopo l'altro, all'infinito.

In un mondo perfetto, questa macchina seguirebbe regole rigide e precise: ogni numero sarebbe la somma esatta dei precedenti moltiplicati per certi fattori. Questo è ciò che i matematici chiamano sequenza di ricorrenza lineare. È come un orologio svizzero: se sai come funziona, sai esattamente cosa succederà per sempre.

Ma nella vita reale, e in molti sistemi informatici o fisici, le cose non sono mai perfette. C'è sempre un po' di "rumore", un errore di misurazione, o un'imprevedibilità esterna. È qui che entrano in gioco gli autori di questo articolo: Amaury Pouly, Mahsa Shirmohammadi e James Worrell.

Il Problema: "Sarà sempre positivo?"

Immagina che la tua macchina del tempo debba generare una lista di numeri che rappresentano, ad esempio, il saldo del tuo conto in banca o la temperatura di un reattore nucleare. La domanda fondamentale è: sarà mai possibile che il numero diventi negativo?

Se il saldo diventa negativo, sei in rosso (problema!). Se la temperatura scende sotto zero in modo critico, il reattore si spegne (problema!).
I matematici vogliono sapere: possiamo essere sicuri che, nonostante il "rumore" o le imprecisioni, la sequenza rimarrà sempre positiva?

Questo è il "Problema della Positività". Per le macchine perfette (senza rumore), è un problema famoso e difficile, aperto da 50 anni. Ma per le macchine "imperfette" (quelle con il rumore), la situazione è ancora più complicata.

La Soluzione: Una "Bussola" Matematica

Gli autori si sono concentrati su un caso specifico: le macchine che generano numeri basandosi sui due precedenti (ordine 2). È come dire: "Il numero di oggi dipende da quello di ieri e da quello di dopodomani".

Hanno scoperto un modo per decidere, in modo definitivo, se la sequenza rimarrà sempre positiva o no. Ecco come funziona la loro idea, semplificata:

La Macchina e il Rumore: Immagina che la tua sequenza sia guidata da un "pilota automatico" (la regola matematica) ma che ci sia un "passeggero" che spinge leggermente il volante a destra o a sinistra in modo casuale (il rumore o l'incertezza).
Il Peggior Scenario: Per essere sicuri che la sequenza sia sempre positiva, dobbiamo guardare il peggior scenario possibile. Dobbiamo chiederci: "Se il passeggero spinge il volante nel modo peggiore possibile per farci andare in negativo, ce la facciamo comunque a rimanere positivi?"
La Somma Infinita: Analizzando questo scenario peggiore, gli autori hanno trasformato il problema in una somma infinita. Immagina di sommare una serie di piccole onde che salgono e scendono. La domanda diventa: "Questa somma infinita è zero o no?"
Il Trucco Magico (I Numeri Trascendenti): Qui arriva la parte più affascinante. Per rispondere, gli autori hanno dovuto dimostrare che questa somma infinita non può essere zero.
- Come fanno a saperlo? Usano una proprietà molto profonda dei numeri chiamata trascendenza.
- Pensa ai numeri come a due famiglie: i "numeri razionali/algebrici" (come 2, 1/3, o la radice quadrata di 2, che sono come "numeri familiari" che obbediscono a regole semplici) e i "numeri trascendenti" (come $\pi$ o $e$ , che sono "numeri ribelli" che non obbediscono a nessuna regola semplice).
- Gli autori hanno dimostrato che la loro somma infinita è un numero trascendente. È come dire: "Questo numero è così strano e unico che non può mai essere zero".
- Se sai che un numero è trascendente, sai che non è zero. E se non è zero, puoi calcolarlo con una calcolatrice abbastanza precisa per vedere se è positivo o negativo.

L'Analogia della "Fuga dal Labirinto"

Immagina di essere in un labirinto (lo spazio dei possibili stati della macchina).

L'obiettivo: Uscire dal labirinto senza mai toccare le pareti nere (i numeri negativi).
Il nemico: Un vento variabile che ti spinge in direzioni imprevedibili.
La scoperta: Gli autori hanno trovato una mappa che dice: "Se il vento è abbastanza forte, uscirai dal labirinto toccando le pareti nere. Se è debole, rimarrai al sicuro".
La parte "trascendente" è come avere una bussola che ti dice con certezza assoluta: "Non puoi fermarti esattamente al centro della stanza (zero), sei sempre o leggermente a destra o leggermente a sinistra".

Perché è importante?

Questo risultato è un passo enorme perché:

Sicurezza Informatica: Aiuta a verificare che i programmi dei computer (specialmente quelli che controllano robot o sistemi critici) non vadano mai in crash o in stati pericolosi, anche se ci sono piccoli errori di calcolo.
Teoria dei Sistemi: Risolve un problema aperto da decenni per una classe specifica di sistemi, aprendo la strada a soluzioni per problemi più complessi.
Matematica Pura: Hanno usato strumenti molto sofisticati (come il "Teorema del Sottospazio" e la teoria dei numeri) per risolvere un problema pratico, dimostrando che la matematica astratta ha applicazioni concrete nella vita reale.

In Sintesi

Gli autori hanno creato un algoritmo (una ricetta passo-passo) che dice: "Data una macchina che genera numeri con un po' di rumore, possiamo calcolare se rimarrà sempre positiva".
Per farlo, hanno dovuto dimostrare che una certa somma infinita di numeri è "troppo strana" per essere zero. È come se avessero detto: "Non preoccuparti di contare ogni singolo granello di sabbia; basta sapere che la spiaggia è fatta di un tipo di sabbia che non può mai formare un cerchio perfetto di zero".

È un lavoro che unisce la logica dei computer, la fisica dei sistemi di controllo e la magia dei numeri, tutto per rispondere a una domanda semplice: "Andremo sempre bene?" E la risposta, in questo caso, è: "Sì, possiamo saperlo con certezza".

1. Il Problema: Positività delle Sequenze Quasi-Lineari Ricorrenti (NLRS)

Il lavoro si concentra sul Problema della Positività per le Sequenze Quasi-Lineari Ricorrenti (NLRS).
Una NLRS di ordine $d$ è definita come una sequenza di numeri razionali $(u_n)_{n=0}^\infty$ che soddisfa un sistema di disuguaglianze:
$\varepsilon_0 \le u_{n+d} - a_{d-1}u_{n+d-1} - \dots - a_0 u_n \le \varepsilon_1$
dove $a_i$ e $\varepsilon_0 \le \varepsilon_1$ sono costanti razionali ( $a_0 \neq 0$ ).

Generalizzazione: Se $\varepsilon_0 = \varepsilon_1 = 0$ , la definizione si riduce a una classica Sequenza Ricorrente Lineare (LRS). Se $\varepsilon_0 = \varepsilon_1$ , diventa una ricorrenza lineare non omogenea.
Contesto: Le NLRS possono essere viste come sistemi lineari tempo-invarianti (LTI) soggetti a disturbi limitati o come loop a vincoli lineari nell'analisi dei programmi. La non-deterministicità (la possibilità di scegliere il termine di disturbo $r_n \in [\varepsilon_0, \varepsilon_1]$ ad ogni passo) rende l'analisi algoritmica estremamente complessa.
Obiettivo: Dato un sistema di ricorrenza (1) e valori iniziali $u_0, \dots, u_{d-1}$ , determinare se tutte le sequenze che soddisfano la ricorrenza e i valori iniziali rimangono non negative ( $u_n \ge 0$ ) per ogni $n \in \mathbb{N}$ .

Questo problema è una generalizzazione del Problema della Positività per le LRS (noto come aperto per ordini superiori a 5) e un caso particolare del problema di non-raggiungibilità per sistemi LTI.

2. Metodologia e Formulazione Matematica

Gli autori riducono il problema della positività delle NLRS a un problema di raggiungibilità per sistemi dinamici lineari.

Formulazione Matriciale: La ricorrenza (1) viene riscritta come un sistema di vettori:
$x_{n+1} = A x_n + r_n e_1$
dove $A$ è la matrice compagna della ricorrenza, $e_1$ è il vettore base, e $r_n \in [\varepsilon_0, \varepsilon_1]$ è un controllo non deterministico. La condizione di positività richiede che la proiezione $e_d^\top x_n \ge 0$ per ogni possibile scelta della sequenza di controlli.
Principio "Bang-Bang": Per determinare se la sequenza rimane positiva, è sufficiente considerare il caso peggiore. Il minimo valore di $u_n$ si ottiene scegliendo i controlli agli estremi dell'intervallo $[\varepsilon_0, \varepsilon_1]$ in base al segno della sequenza di controllo associata. Questo porta a definire una sequenza minima $u^{(min)}_n$ .
Riduzione a Serie Infinita: Per il caso di ordine 2, l'analisi dello spettro della matrice $A$ (autovalori $\lambda, \bar{\lambda}$ ) permette di esprimere il limite della sequenza minima come una combinazione di termini esponenziali e una serie infinita della forma:
$S = \sum_{n=0}^\infty |a \lambda^n + \bar{a} \bar{\lambda}^n|$
La decidibilità del problema dipende dalla capacità di determinare il segno di questa somma infinita.

3. Contributi Chiave e Risultati Principali

Il risultato centrale del paper è un procedimento decisionale per il Problema della Positività per NLRS di ordine 2.

Teorema 1 (Decidibilità): Il problema è decidibile per ricorrenze di ordine 2, anche quando i coefficienti sono numeri algebrici reali.
Strategia di Risoluzione:
- Se lo spettro di $A$ ha potenze a parte reale positiva, il problema è risolvibile tramite proprietà di chiusura delle classi di LRS positive.
- Se il raggio spettrale è $\ge 1$ , si dimostra che la sequenza diverge verso $-\infty$ (quindi non è positiva).
- Se il raggio spettrale è $< 1$ , la sequenza converge a un limite. Il problema si riduce a determinare se questo limite è zero o meno.
Teorema 2 (Risultato di Trascendenza): Il contributo tecnico più significativo è la dimostrazione che la serie infinita $S = \sum_{n=0}^\infty |a \lambda^n + \bar{a} \bar{\lambda}^n|$ $S = \sum_{n = 0}^{\infty} ∣ a λ^{n} + \overset{a}{ˉ} \overset{ˉ}{λ}^{n} ∣$ (con $|\lambda|<1$ $∣ λ ∣ < 1$ e $\lambda^n \notin \mathbb{R}$ $λ^{n} \in / R$ ) è trascendente.
- Poiché i coefficienti del sistema sono algebrici, se la somma fosse zero, dovrebbe essere algebrica. Dimostrando che è trascendente, si conclude che la somma non può essere zero.
- Questo permette di determinare il segno della somma tramite calcoli numerici a precisione finita, risolvendo il problema decisionale.

4. Tecniche Matematiche Avanzate

La dimostrazione del Teorema 2 combina strumenti profondi della teoria dei numeri e dell'approssimazione diofantea:

Approssimazione Diofantea e Frazioni Continue: Si analizza l'argomento $\theta$ di $\lambda = |\lambda|e^{2\pi i \theta}$ . Usando le frazioni continue di $\theta$ , si costruisce una famiglia di ricorrenze lineari di ordine crescente che approssimano la sequenza $|a\lambda^n + \bar{a}\bar{\lambda}^n|$ .
Teorema del Sottospazio di Schlickewei: Si utilizza una versione $p$ -adica del Teorema del Sottospazio (generalizzazione del Teorema di Roth). Si assume per assurdo che la somma $\alpha$ sia algebrica. Si costruisce una forma lineare $L$ che si annulla molto rapidamente su una sequenza di vettori costruiti dalle ricorrenze.
Teorema di Baker (Forme Lineari nei Logaritmi): Si applica il Teorema di Baker per ottenere un limite inferiore per la distanza da zero di certe forme lineari.
Contraddizione: Si dimostra che la velocità di convergenza della forma lineare verso zero (derivata dall'assunzione di algebricità) contraddice il limite inferiore fornito dal Teorema di Baker. Di conseguenza, l'assunzione che $\alpha$ sia algebrica è falsa; $\alpha$ è trascendente e quindi non nullo.

5. Significato e Implicazioni

Avanzamento nella Teoria dei Sistemi: Il lavoro risolve un caso specifico ma fondamentale del problema di non-raggiungibilità per sistemi LTI con controlli limitati, collegando l'analisi dei sistemi dinamici alla teoria dei numeri trascendentali.
Metodologia Innovativa: L'uso di risultati di trascendenza per risolvere problemi di decidibilità in sistemi dinamici è un approccio potente. Il paper dimostra come strumenti di approssimazione diofantea possano essere applicati a problemi di controllo e verifica formale.
Limiti e Lavori Futuri:
- Il metodo attuale funziona per l'ordine 2. Estenderlo all'ordine 3 presenta sfide significative.
- Il paper distingue tra varianti del problema: la versione "universale" (tutte le sequenze sono positive) è risolta qui. La versione "esistenziale" (esiste una sequenza positiva) richiede tecniche diverse (principio bang-bang non applicabile) e rimane aperta per ordini superiori.
- Il lavoro apre la strada all'analisi di sistemi LTI con poli di controllo più generali (poliedri multidimensionali), sebbene la presenza di iperpiani di separazione non razionali possa complicare l'estensione.

In sintesi, il paper fornisce una soluzione completa per la positività delle NLRS di ordine 2, fondendo analisi complessa, teoria dei numeri e teoria del controllo, e stabilisce un nuovo paradigma per affrontare problemi di raggiungibilità in sistemi con disturbi limitati.