AFTD Auto-Formalizing Theoretical Domains

satisfies_recurrence_2_1_exists

theoremverified

For every integer N ≥ 1, there exist recurrence coefficients a, b, c : Fin (N + 1) → ℝ satisfying condition (2.1).

Statement

theorem satisfies_recurrence_2_1_exists (N : ℕ) (hN : 1 ≤ N) :
    ∃ a b c : Fin (N + 1) → ℝ, satisfies_recurrence_2_1 N a b c
Source
arXiv:2611.01561, Section 2
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • satisfies_recurrence_2_1Real coefficients a, b, c : Fin (N + 1) → ℝ satisfy condition (2.1) if a 0 = 1, b 0 = 0, c 0 = 0, a N = 0, a i + b i + c i = 1 for all i,…

Read back from the Lean

For any natural number $N$ with $1 \le N$, there exist three functions $a, b, c : \mathrm{Fin}(N + 1) \to \mathbb{R}$ satisfying satisfies_recurrence_2_1 N a b c.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof proceeds by explicitly constructing candidate recurrence coefficients on {0, …, N}: a(i) = 1 for i < N and a(N) = 0; c(0) = 0 and c(i) = 1 for i > 0; and b(i) = 1 - a(i) - c(i). The partition of unity condition a(i) + b(i) + c(i) = 1 holds algebraically by the definition of b. The remaining boundary conditions and strict positivity requirements for a and c follow directly by evaluating the piecewise definitions using N ≥ 1.

  1. We propose explicit candidate coefficient functions a, b, c : Fin (N + 1) → ℝ.

    We define a(i) = 1 for i < N and a(N) = 0; c(0) = 0 and c(i) = 1 for i > 0; and b(i) = 1 - a(i) - c(i) for all i. Providing these three functions supplies the witnesses for the existential quantifier.

    lines 4–7

      let a : Fin (N + 1) → ℝ := fun i => if (i : ℕ) < N then 1 else 0
      let c : Fin (N + 1) → ℝ := fun i => if (i : ℕ) = 0 then 0 else 1
      let b : Fin (N + 1) → ℝ := fun i => 1 - a i - c i
      use a, b, c
  2. It suffices to verify the seven individual conditions in the definition of condition (2.1), noting that N > 0.

    Unfolding satisfies_recurrence_2_1 expands the goal into seven conditions: a(0) = 1, b(0) = 0, c(0) = 0, a(N) = 0, a(i) + b(i) + c(i) = 1 for all i, a(i) > 0 for i < N, and c(i) > 0 for i > 0. From the hypothesis N ≥ 1, linear arithmetic gives N > 0, which is recorded for evaluating the boundary conditions at 0. We then split the conjunction into seven independent goals.

    lines 8–10

      dsimp [satisfies_recurrence_2_1]
      have h0N : 0 < N := by omega
      refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩
  3. The four boundary conditions a(0) = 1, b(0) = 0, c(0) = 0, and a(N) = 0 hold.

    These four identities follow by evaluating the definitions: - Since 0 < N, the condition 0 < N holds in the definition of a, so a(0) = 1. - At index 0, b(0) = 1 - a(0) - c(0) = 1 - 1 - 0 = 0. - In the definition of c, 0 = 0 holds, so c(0) = 0. - At index N, N < N is false, so a(N) = 0.

    lines 11–14

      · simp [a, h0N]
      · simp [b, a, c, h0N]
      · simp [c]
      · simp [a]
  4. For every index i ∈ {0, …, N}, a(i) + b(i) + c(i) = 1.

    Expanding the definition b(i) = 1 - a(i) - c(i), the sum becomes a(i) + (1 - a(i) - c(i)) + c(i), which simplifies to 1 by elementary ring arithmetic.

    lines 15–17

      · intro i
        simp only [b]
        ring
  5. For every index i < N, a(i) > 0.

    Let i < N. By definition of a, since i < N, a(i) = 1, and 1 > 0.

    lines 18–19

      · intro i hi
        simp [a, hi]
  6. For every index i > 0, c(i) > 0.

    Let i > 0. Evaluating c(i) yields the conditional "if i = 0 then 0 else 1". The case i = 0 is impossible because i > 0. In the remaining case i ≠ 0, c(i) = 1, and 1 > 0.

    lines 20–24

      · intro i hi
        dsimp [c]
        split_ifs with h
        · omega
        · norm_num

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Sanity lemma: existence of coefficients satisfying condition (2.1) for every N ≥ 1. -/theorem satisfies_recurrence_2_1_exists (N : ℕ) (hN : 1 ≤ N) :    ∃ a b c : Fin (N + 1) → ℝ, satisfies_recurrence_2_1 N a b c := by  let a : Fin (N + 1) → ℝ := fun i => if (i : ℕ) < N then 1 else 0  let c : Fin (N + 1) → ℝ := fun i => if (i : ℕ) = 0 then 0 else 1  let b : Fin (N + 1) → ℝ := fun i => 1 - a i - c i  use a, b, c  dsimp [satisfies_recurrence_2_1]  have h0N : 0 < N := by omega  refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩  · simp [a, h0N]  · simp [b, a, c, h0N]  · simp [c]  · simp [a]  · intro i    simp only [b]    ring  · intro i hi    simp [a, hi]  · intro i hi    dsimp [c]    split_ifs with h    · omega    · norm_num
See it in the graphDiscuss this resultChallenge it