Positivity of Nearly Linearly Recurrent Sequences

Titel: Positiviteit van Bijna Lineair Recurrente Sequenties

Auteurs: Amaury Pouly, Mahsa Shirmohammadi en James Worrell.

---

1. Probleemstelling

Het artikel introduceert en bestudeert het Positiviteitsprobleem voor Bijna Lineair Recurrente Sequenties (NLRS).

• Definitie van NLRS: Een bijna lineaire recurrente sequentie van orde $d$ is een rij van rationale getallen $(u_n)_{n=0}^\infty$ die voldoet aan een systeem van ongelijkheden:
  $$\varepsilon_0 \le u_{n+d} - a_{d-1}u_{n+d-1} - \dots - a_0 u_n \le \varepsilon_1$$
  waarbij $a_i$ en $\varepsilon_0 \le \varepsilon_1$ rationale constanten zijn ($a_0 \neq 0$).

  • Als $\varepsilon_0 = \varepsilon_1 = 0$, reduceert dit tot een klassieke lineaire recurrente rij (LRS).
  • Als $\varepsilon_0 = \varepsilon_1$, is het een inhomogene lineaire recurrente rij.
  • In het algemeen modelleren NLRS lineaire systemen met gebonden verstoringen (noise) of niet-determinisme.

• Het Positiviteitsprobleem: Gegeven een recurrente relatie (1) en initiële waarden $u_0, \dots, u_{d-1}$, moet worden bepaald of elke mogelijke rij $u$ die aan deze relatie voldoet, positief is voor alle $n$ (d.w.z. $u_n \ge 0$ voor alle $n \in \mathbb{N}$).

• Context:

  • Dit is een generalisatie van het Positiviteitsprobleem voor LRS (een open probleem dat al 50 jaar bestaat voor algemene orde, hoewel oplosbaar voor orde $\le 5$).
  • Het is een speciaal geval van het niet-bereikbaarheidsprobleem voor Lineaire Tijd-Invariante (LTI) systemen in de besturingstheorie.
  • Het is gerelateerd aan het bepalen van de terminatie van lineaire constraint-loops in programmeeranalyse.

---

2. Methodologie

De auteurs ontwikkelen een beslissingsprocedure (decision procedure) specifiek voor NLRS van orde 2. De aanpak combineert besturingstheorie, getaltheorie en transcendentietheorie.

A. Matrixformulering en Reductie

De recurrente relatie wordt herschreven als een vectorrecurrentie (LTI-systeem):
$$x_{n+1} = A x_n + r_n e_1$$
waarbij $A$ de companion-matrix is van de karakteristieke polynoom, $e_1$ een eenheidsvector is, en $r_n \in [\varepsilon_0, \varepsilon_1]$ een controlevariabele (niet-determinisme).

• De waarde $u_n$ wordt uitgedrukt als $e_d^\top x_n$.
• Het probleem wordt gereduceerd tot het controleren of de oplossing $x_n$ altijd in een halfruimte blijft ($e_d^\top x_n \ge 0$).
• Door het bang-bang principe (in lineaire besturingssystemen wordt een extremum bereikt door de controlevariabele op de randen van het interval te kiezen), kan de "slechtst mogelijke" rij worden geconstrueerd. Dit leidt tot een specifieke rij $u^{(min)}_n$ die het minimum vertegenwoordigt over alle mogelijke keuzes van $r_n$. Als deze rij positief is, dan zijn alle rijen positief.

B. Analyse van Orde 2

Voor orde 2 wordt de matrix $A$ geanalyseerd op basis van zijn spectrum (eigenwaarden $\lambda, \bar{\lambda}$):

1. Positief reëel spectrum: Als een macht van $A$ positieve reële eigenwaarden heeft, valt het probleem binnen de klasse $C_{pos}$ (waarvoor positiviteit bekend is oplosbaar).
2. Spectrale straal $> 1$: De rij divergeert naar $-\infty$ (niet positief).
3. Spectrale straal $= 1$: De som van absolute waarden divergeert, wat leidt tot negativiteit.
4. Spectrale straal $< 1$: Dit is het kritieke geval. De rij convergeert naar een limiet. Het probleem reduceert zich tot het bepalen van het teken van deze limiet.

C. Transcendentie en het Subspace Theorema

In het kritieke geval (orde 2, spectrale straal $< 1$) wordt de limiet uitgedrukt als een oneindige som:
$$\alpha = \sum_{n=0}^\infty |a \lambda^n + \bar{a} \bar{\lambda}^n|$$
De kern van de methode is het bewijzen dat deze som $\alpha$ transcendent is (d.w.z. geen wortel van een polynoom met gehele coëfficiënten).

• Als $\alpha$ transcendent is, kan het niet nul zijn.
• Omdat $\alpha$ transcendent is, kan het teken ervan worden bepaald door numerieke benadering met voldoende precisie.
• Bewijsstrategie voor transcendentie:
  1. Gebruik van verlengde breuken van het argument $\theta$ van $\lambda$ om een familie van lineaire recurrente relaties te construeren die de termen $|u_n|$ "bijna" voldoen.
  2. Constructie van een lineaire vorm $L$ en een rij vectoren $\Lambda_n$ die zeer snel naar nul convergeren.
  3. Toepassing van het p-adic Subspace Theorema (van Schlickewei) om aan te tonen dat als $\alpha$ algebraïsch zou zijn, dit zou leiden tot een contradictie met ondergrenzen voor lineaire vormen in logaritmen (Baker's Theorema).

---

3. Belangrijkste Bijdragen en Resultaten

• Hoofdstelling (Theorema 1): Het Positiviteitsprobleem voor bijna lineaire recurrente sequenties van orde 2 is beslisbaar (decidable).
  • De procedure werkt zelfs als de constanten in de recurrente relatie algebraïsche reële getallen zijn.
• Nieuw Transcendentie-resultaat (Theorema 2): Voor algebraïsche getallen $\lambda, a$ met $|\lambda| < 1$ en $\lambda^n \notin \mathbb{R}$, is de som $\sum |a\lambda^n + \bar{a}\bar{\lambda}^n$ transcendent.
  • Dit resultaat is van onafhankelijk wiskundig belang en vormt de technische kern van de bewijzen.
• Technische Innovatie: De combinatie van de Subspace Theorema (uit Diophantische benadering) met de analyse van LTI-systemen en lineaire constraint-loops.

---

4. Betekenis en Toekomstperspectief

• Uitbreiding van bestaande theorie: Dit werk generaliseert het klassieke Positiviteitsprobleem voor LRS naar systemen met niet-determinisme/verstoringen. Het toont aan dat zelfs met deze extra complexiteit, beslisbaarheid mogelijk blijft voor lage dimensies.
• Verband met andere domeinen:
  • Besturingstheorie: Het biedt een oplossing voor een speciaal geval van het niet-bereikbaarheidsprobleem voor LTI-systemen met een lineaire controlepolytoop.
  • Programma-analyse: Het draagt bij aan het probleem van terminatiebewijzen voor lineaire constraint-loops.
• Beperkingen en Toekomstig Werk:
  • De huidige procedure is beperkt tot orde 2. Uitbreiding naar orde 3 wordt gezien als een aanzienlijke uitdaging.
  • Het artikel onderscheidt verschillende varianten van het positiviteitsprobleem (geïnitieerd vs. niet-geïnitieerd, universeel vs. existentieel). De huidige methode werkt voor de geïnitieerde, universele variant.
  • Voor de existentiële variant (bestaat er een positieve rij?) werkt de "bang-bang" methode niet, wat andere technieken vereist.
  • De auteurs vermoeden dat hun transcendentie-benadering kan worden gegeneraliseerd voor LTI-systemen met algemene polyedrische controleverzamelingen, maar dat het behandelen van complexere doelen (zoals punt-doelen) moeilijker zal zijn vanwege het ontbreken van rationele of algebraïsche beschrijvingen van scheidende hypervlakken.

Conclusie: Het artikel levert een doorbraak door een beslissingsprocedure te bieden voor een niet-triviaal veralgemeend positiviteitsprobleem, gebruikmakend van diepe resultaten uit de transcendentietheorie om de onbepaaldheid van oneindige sommen op te lossen.