Positivity of Nearly Linearly Recurrent Sequences

This paper introduces the Positivity Problem for nearly linearly recurrent sequences, a generalization of linear recurrences, and presents a decision procedure for order-two cases supported by a novel transcendence result for infinite series.

The Gist

Imagine you are watching a ball bounce on a trampoline. In a perfect world, if you know exactly how hard you pushed it and how bouncy the trampoline is, you can predict exactly where the ball will be at every single moment in the future. This is a Linear Recurrence: a perfectly predictable pattern.

But in the real world, things aren't perfect. Maybe the wind blows a little, or the trampoline fabric is slightly uneven. The ball doesn't follow a single, perfect line; instead, it bounces within a "safe zone" or a "corridor" of possible paths.

This paper is about a new kind of math problem that deals with these imperfect, wobbly bounces. The authors call these "Nearly Linear Recurrent Sequences."

Here is the story of what they discovered, broken down into simple concepts:

1. The Problem: Will the Ball Stay Above Ground?

The main question the authors asked is the "Positivity Problem."

• The Setup: You have a rule for how a number (or a ball's height) changes over time. But this rule isn't exact; it has a little bit of wiggle room (a margin of error).
• The Question: No matter how the "wiggles" happen (even if they are the worst-case wiggles), will the number always stay positive (i.e., will the ball always stay above the ground)?

If the ball ever dips below zero, the system "fails." The goal is to build a computer program that can look at the rules and say, "Yes, it will always stay safe," or "No, eventually it will crash."

2. Why is this so hard?

For perfectly predictable systems (no wiggles), mathematicians have been trying to solve this for 50 years, and it's still a huge mystery for complex cases.

When you add the "wiggles" (the uncertainty), the problem becomes even harder. It's like trying to predict if a ship will stay afloat not just in calm water, but in a storm where the waves can push it in any direction within a certain limit. The number of possible paths becomes infinite.

3. The Breakthrough: Solving the "Two-Step" Dance

The authors managed to solve this problem specifically for systems that depend on the two previous steps (Order 2). Think of it like a dance where your next move depends on where you were two steps ago and one step ago.

They built a decision procedure (a step-by-step recipe) that a computer can follow to answer the question definitively.

4. The Secret Weapon: The "Magic Number"

How did they prove their recipe works? They used a very deep trick from the world of numbers called Transcendence.

Here is the analogy:
Imagine you are adding up an infinite list of numbers to get a final total.

• Algebraic Numbers are like numbers you can build with simple Lego bricks (like fractions or square roots).
• Transcendental Numbers are like numbers that are so unique and complex they cannot be built from any combination of simple Lego bricks (like $\pi$ or $e$).

The authors proved that the "worst-case total" of their bouncing ball problem results in a Transcendental Number.

• Why does this matter? Because if the total were a simple "Lego" number (algebraic), it might accidentally land exactly on zero (the ground). But since they proved the total is a "Transcendental" number, it cannot be zero. It must be either strictly positive or strictly negative.
• This means the computer doesn't need to check forever. It can just calculate the number with enough precision, see which side of zero it falls on, and stop.

5. The Tools They Used

To prove this "Magic Number" was transcendental, they used two heavy-duty mathematical tools:

1. The Subspace Theorem: Think of this as a super-advanced ruler that measures how close numbers can get to each other without actually touching.
2. Continued Fractions: A way of breaking down complex numbers into a sequence of simpler steps, like peeling an onion layer by layer, to see the hidden patterns.

6. What Does This Mean for the Future?

• For Computer Science: This helps verify that computer programs (which often have loops and conditions) won't crash or produce negative values when data is slightly uncertain.
• For Engineering: It helps control systems (like self-driving cars or drones) guarantee safety even when sensors aren't 100% perfect.
• The Limit: They solved it for the "two-step" dance. The "three-step" dance is much harder and is still a work in progress.

Summary

The authors took a messy, unpredictable problem (a bouncing ball with wind) and proved that for simple cases, we can mathematically guarantee it will never hit the ground. They did this by showing that the "worst-case scenario" results in a number so unique and complex that it can never accidentally equal zero. It's a victory for certainty in a world of uncertainty.

Technical Summary

1. Problem Definition

The paper addresses the Positivity Problem for Nearly Linear Recurrent Sequences (NLRS).

• Context: NLRS generalize classical Linear Recurrence Sequences (LRS) and appear in control theory (as Linear Time-Invariant systems with bounded disturbances) and program analysis (as linear constraint loops).
• Formal Definition: An NLRS of order $d$ is a sequence $(u_n)_{n=0}^\infty$ satisfying a system of inequalities:
  $$\varepsilon_0 \le u_{n+d} - a_{d-1}u_{n+d-1} - \dots - a_0 u_n \le \varepsilon_1$$
  where $a_i, \varepsilon_0, \varepsilon_1$ are rational constants ($a_0 \neq 0$).
  • If $\varepsilon_0 = \varepsilon_1 = 0$, it is a standard LRS.
  • If $\varepsilon_0 = \varepsilon_1$, it is an inhomogeneous LRS.
• The Positivity Problem: Given the recurrence coefficients and initial values $u_0, \dots, u_{d-1}$, determine whether every sequence satisfying the recurrence and initial conditions remains non-negative ($u_n \ge 0$ for all $n$).
• Significance: This is a generalization of the famous Positivity Problem for LRS (decidable for order $\le 5$, open in general) and a special case of the non-reachability problem for Linear Time-Invariant (LTI) systems.

2. Methodology

The authors develop a decision procedure specifically for order 2 NLRS. The methodology involves three main stages:

A. Matrix-Power Formulation and Reduction

The problem is reformulated using control theory concepts. The recurrence is expressed as a vector recurrence $x_{n+1} = A x_n + r_n e_1$, where $r_n \in [\varepsilon_0, \varepsilon_1]$ represents a control input.

• The positivity of the sequence $u_n$ corresponds to the system state remaining in a specific half-space.
• The authors apply the Bang-Bang Principle: To check if all sequences are positive, it suffices to check the "worst-case" sequence where the control $r_n$ is chosen at the boundaries ($\varepsilon_0$ or $\varepsilon_1$) to minimize the value at each step.
• This reduces the problem to analyzing a specific sequence $u^{(min)}_n$, which is the sum of a "zero-control" LRS and a sum involving absolute values of a "control" LRS.

B. Spectral Analysis

The decision procedure analyzes the eigenvalues (spectrum) of the companion matrix $A$ associated with the recurrence:

1. Positive Real Spectrum: If a power of $A$ has positive real eigenvalues, the problem is decidable using known properties of the class $\mathcal{C}_{pos}$ (sequences with positive real roots).
2. Spectral Radius $> 1$: The sequence diverges to $-\infty$ unless specific coefficients vanish, making positivity checkable via limit analysis.
3. Spectral Radius $= 1$: The sum of absolute values diverges, leading to non-positivity.
4. Spectral Radius $< 1$ (The Critical Case): The sequence converges. The limit is the sum of a rational/algebraic term and an infinite series of absolute values: $\sum |a\lambda^n + \bar{a}\bar{\lambda}^n|$.

C. Transcendence Theory

The core technical challenge lies in Case 4. To decide positivity, one must determine if the limit of the sequence is non-zero. The authors prove that the infinite sum $\alpha = \sum_{n=0}^\infty |a\lambda^n + \bar{a}\bar{\lambda}^n|$ is transcendental (not a root of any polynomial with integer coefficients) under the condition that $\lambda$ is not real and $|\lambda| < 1$.

• Proof Strategy:
  1. Approximation: They use the continued fraction expansion of the argument of $\lambda$ to construct a family of linear recurrences that the sequence of absolute values satisfies "almost everywhere."
  2. Subspace Theorem: They assume $\alpha$ is algebraic and apply Schlickewei's $p$-adic Subspace Theorem. This theorem is used to find a linear form $F$ that vanishes on the sequence of approximations.
  3. Contradiction: By eliminating variables, they derive a new linear form $L'$ whose value is bounded below by Baker's Theorem (on linear forms in logarithms). This lower bound contradicts the upper bound derived from the convergence speed of the series, proving $\alpha$ cannot be algebraic.
• Consequence: Since the limit is transcendental, it cannot be zero. Therefore, its sign can be determined by finite-precision numerical computation.

3. Key Contributions

1. Decision Procedure for Order 2: The paper provides the first decision procedure for the Positivity Problem for NLRS of order 2, even when coefficients are real algebraic numbers.
2. New Transcendence Result: Theorem 2 establishes that the infinite series of absolute values of a complex geometric progression (with $|\lambda|<1$) is transcendental. This result is of independent interest in number theory.
3. Synthesis of Fields: The work bridges Control Theory (LTI systems, bang-bang principle), Automata Theory (Positivity/Skolem problems), and Diophantine Approximation (Subspace Theorem, Baker's Theorem).

4. Results

• Main Theorem: The Positivity Problem for nearly linear recurrences of order 2 is decidable.
• Algorithm: The procedure involves:
  1. Checking the spectral radius of the system matrix.
  2. If the spectral radius is $<1$, computing the limit of the worst-case sequence numerically.
  3. Relying on the transcendence proof to guarantee that if the numerical approximation is non-zero, the true limit is non-zero and has the same sign.
• Limitations: The result is currently restricted to order 2. The paper notes that extending this to order 3 or handling more general reachability targets (e.g., point targets) remains an open challenge, likely due to the difficulty of finding rational separating hyperplanes in higher dimensions.

5. Significance

• Advancement on Open Problems: The classical Positivity Problem for LRS is a major open problem in theoretical computer science (decidable only for order $\le 5$). This paper solves a non-trivial generalization (NLRS) for order 2, showing that even with bounded non-determinism (disturbances), decidability can be achieved for low dimensions.
• Program Analysis: The results directly impact the termination analysis of linear constraint loops, a fundamental problem in software verification.
• Methodological Innovation: The use of transcendence results (specifically the Subspace Theorem) to solve algorithmic problems in dynamical systems represents a powerful new direction. It suggests that number-theoretic properties of the system's eigenvalues can be leveraged to overcome the undecidability barriers often found in reachability problems.
• Distinction from Related Work: Unlike previous works on robust LRS (which perturb initial values) or rounding errors (deterministic rounding), this work handles non-deterministic perturbations at every time step, making the problem significantly harder and requiring the novel "bang-bang" reduction to a single worst-case trajectory.