Positivity of Nearly Linearly Recurrent Sequences

1. 문제 정의 (Problem Definition)

• 거의 선형 재귀 (NLRS):

  • 기존의 선형 재귀 수열 (LRS) 을 일반화한 개념입니다.
  • 수열 $u = (u_n)_{n=0}^\infty$가 다음 부등식을 만족할 때 NLRS 라고 정의합니다:
    $$\varepsilon_0 \le u_{n+d} - a_{d-1}u_{n+d-1} - \dots - a_0 u_n \le \varepsilon_1$$
    여기서 $a_i, \varepsilon_0, \varepsilon_1$은 유리수 상수이며 $a_0 \neq 0$입니다.
  • $\varepsilon_0 = \varepsilon_1 = 0$이면 기존 LRS 가 되고, $\varepsilon_0 = \varepsilon_1$이면 비동차 선형 재귀가 됩니다.
  • 이는 제어 이론의 선형 시불변 (LTI) 시스템이나 프로그램 분석의 **선형 제약 루프 (linear constraint loops)**의 특수한 경우로 볼 수 있습니다. 여기서 $\varepsilon$ 구간은 외부 제어나 노이즈 (disturbance) 를 모델링합니다.

• 양수성 문제 (Positivity Problem):

  • 주어진 재귀식과 초기 조건 ($u_0, \dots, u_{d-1}$) 을 만족하는 모든 수열 $u$에 대해, 모든 $n \in \mathbb{N}$에서 $u_n \ge 0$이 성립하는지 여부를 결정하는 문제입니다.
  • 기존 LRS 의 양수성 문제는 50 년 전부터 제기된 난제 (Skolem 문제와 밀접한 관련) 로, 5 차 이하에서는 결정 가능하지만 일반적으로는 미해결 상태입니다. NLRS 는 비결정성 (non-determinism, 즉 제어 입력 $r_n \in [\varepsilon_0, \varepsilon_1]$의 선택) 이 추가되어 더 어렵습니다.

2. 방법론 (Methodology)

논문은 2 차 NLRS 에 대한 결정 절차를 다음과 같은 단계로 구성합니다.

2.1 행렬 거듭제곱 형식화 (Matrix-Power Formulation)

• 재귀식을 벡터 재귀 $x_{n+1} = A x_n + r_n e_1$ ($r_n \in [\varepsilon_0, \varepsilon_1]$) 로 변환합니다. 여기서 $A$는 동반 행렬 (companion matrix) 입니다.
• 이 변환을 통해 NLRS 의 양수성 문제는 LTI 시스템의 비 도달성 (non-reachability) 문제로 귀결됩니다. 즉, 특정 반공간 (half-space) 에 도달하지 않는지 확인하는 문제입니다.
• Bang-Bang 원리 적용:
  • 수열 $u_n$이 음수가 되는지 확인하기 위해, 각 단계에서 제어 입력 $r_n$을 $[\varepsilon_0, \varepsilon_1]$ 구간 내에서 수열을 최소화하는 방향으로 선택합니다.
  • 최적 제어는 항상 구간의 끝점 ($\varepsilon_0$ 또는 $\varepsilon_1$) 에서 발생하므로, 모든 가능한 수열 중 가장 작은 값을 갖는 수열 $u^{(min)}_n$을 정의할 수 있습니다.
  • $u^{(min)}_n$이 양수이면 모든 수열이 양수입니다.

2.2 2 차 재귀에 대한 분석

• 행렬 $A$의 스펙트럼 (고유값) 에 따라 4 가지 경우로 나누어 분석합니다.
  1. 실수 스펙트럼: $A$의 어떤 거듭제곱이 양의 실수 스펙트럼을 가지는 경우. 이는 기존 LRS 이론 ($C_{pos}$ 클래스) 을 적용하여 결정 가능합니다.
  2. 스펙트럼 반지름 > 1: 고유값의 크기가 1 보다 큰 경우. 수열이 발산하거나 음수로 발산하여 양수성이 성립하지 않음을 보입니다.
  3. 스펙트럼 반지름 = 1: 고유값의 크기가 1 인 경우. 절대값의 합이 발산하여 양수성이 성립하지 않음을 보입니다.
  4. 스펙트럼 반지름 < 1: 고유값의 크기가 1 보다 작은 경우 (가장 어려운 경우).
     • 이 경우 $u^{(min)}_n$은 극한을 가집니다.
     • 핵심 난제: 이 극한값이 0 이 아닌지, 그리고 그 부호를 어떻게 결정할 것인가입니다.
     • 극한값은 무한급수 $\sum |a\lambda^n + \bar{a}\bar{\lambda}^n|$와 관련이 있습니다.

2.3 초월성 (Transcendence) 결과 활용

• 주요 기술적 기여: 해당 무한급수의 합이 **초월수 (transcendental number)**임을 증명하여, 이 값이 0 이 될 수 없음을 보여줍니다.
• 증명 기법:
  1. 연분수 (Continued Fractions): 고유값 $\lambda$의 위상각 $\theta$에 대한 연분수 전개를 이용하여, $|a\lambda^n + \bar{a}\bar{\lambda}^n|$이 거의 선형 재귀를 따르는 구간들을 식별합니다.
  2. 부분공간 정리 (Subspace Theorem): Schlickewei 의 $p$-adic 부분공간 정리를 적용합니다. 이는 디오판토스 근사 이론의 강력한 도구입니다.
  3. 모순 유도: 만약 이 합이 대수적 수 (algebraic number) 라고 가정하면, 선형 형태의 하한 (Baker 의 정리 기반) 과 급수의 수렴 속도가 모순을 일으킴을 보입니다. 따라서 합은 초월수이며, 0 이 될 수 없습니다.
• 결정 절차: 극한값이 0 이 아니므로, 충분히 높은 정밀도의 수치 계산을 통해 극한값의 부호를 결정할 수 있습니다. 극한값이 양수라면 충분히 큰 $n$ 이후의 모든 항이 양수이므로, 초기 유한 개의 항만 검사하면 됩니다.

3. 주요 결과 (Key Results)

• 주요 정리 (Theorem 1): 2 차 NLRS 에 대한 양수성 문제는 **결정 가능 (decidable)**합니다.
  • 이 절차는 재귀식의 계수가 실수 대수수 (real algebraic numbers) 일 때도 적용됩니다.
• 초월성 정리 (Theorem 2): $|\lambda| < 1$이고 $\lambda^n \in \mathbb{R}$이 아닌 대수적 수 $\lambda, a$에 대해, $\alpha := \sum_{n=0}^\infty |a\lambda^n + \bar{a}\bar{\lambda}^n|$는 초월수입니다.
  • 이 결과는 독립적으로도 중요한 의미를 가지며, NLRS 의 양수성 증명에 필수적인 도구로 작용했습니다.

4. 의의 및 기여 (Significance)

• 이론적 확장: 기존의 LRS 양수성 문제를 비결정적 요소 (제어 입력) 가 포함된 NLRS 로 확장하여, 2 차 시스템에 대해 해결책을 제시했습니다.
• 교차 학문적 연결: 제어 이론 (LTI 시스템), 프로그램 분석 (루프 종료성), 그리고 수론 (초월수 이론, 디오판토스 근사) 을 긴밀하게 연결했습니다.
• 알고리즘적 접근: 비결정적 시스템의 도달성 문제를 해결하기 위해, 단순히 수치적 시뮬레이션만으로는 불가능한 경우를 수론적 도구 (부분공간 정리) 를 통해 해결하는 새로운 패러다임을 제시했습니다.
• 한계 및 향후 연구:
  • 현재 결과는 2 차 시스템에 국한되어 있습니다. 3 차 이상으로 확장하는 것은 큰 도전 과제로 남아있습니다.
  • "존재적 (existential)" 변형 (어떤 양수 수열이 존재하는가?) 에 대해서는 Bang-Bang 원리가 적용되지 않아 다른 기법이 필요할 것으로 예상됩니다.

요약

이 논문은 비결정적 요소를 가진 2 차 거의 선형 재귀 수열의 양수성 문제를 해결하기 위해, Bang-Bang 원리를 통해 최적 제어 경로를 식별하고, **디오판토스 근사 이론 (부분공간 정리)**을 활용하여 관련 무한급수의 합이 0 이 될 수 없음을 증명함으로써 결정 절차를 확립했습니다. 이는 제어 시스템의 안전성 검증 및 프로그램 분석 분야에서 중요한 이론적 진전입니다.