AFTD Auto-Formalizing Theoretical Domains

recursive_one_player_extension_barrier

theoremverifiedformalization

Let r be a natural number and let α : ℕ → ℝ be a sequence satisfying 0 ≤ α r and α r < 1. Under the one-player extension recurrence α (k + 1) = 1 / (2 - α k) for all k ≥ r, the approximation guarantee for any m ≥ r satisfies α m = 1 - 1 / ((m : ℝ) - c), where c = (r : ℝ) - 1 / (1 - α r).

Statement

theorem recursive_one_player_extension_barrier
    (r : ℕ) (α : ℕ → ℝ) (hαr : 0 ≤ α r ∧ α r < 1)
    (hrec : ∀ k, r ≤ k → α (k + 1) = 1 / (2 - α k))
    (m : ℕ) (hm : r ≤ m) :
    let c : ℝ := (r : ℝ) - 1 / (1 - α r)
    α m = 1 - 1 / ((m : ℝ) - c)
Formalizes
arXiv:2611.06076 Proposition 2.3
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

Read back from the Lean

Let $r$ be a natural number and $\alpha : \mathbb{N} \to \mathbb{R}$ be a sequence of real numbers such that $0 \le \alpha(r) < 1$. Suppose that for every natural number $k \ge r$, the recurrence $\alpha(k + 1) = \frac{1}{2 - \alpha(k)}$ holds. Then for any natural number $m \ge r$, setting $c = r - \frac{1}{1 - \alpha(r)}$, we have $\alpha(m) = 1 - \frac{1}{m - 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

Under the recurrence α (k + 1) = 1 / (2 - α k), the quantity 1 / (1 - α m) grows linearly with m, as established by recursive_one_player_extension_reciprocal. Rearranging this relation shows that the denominator (m : ℝ) - c is equal to 1 / (1 - α m). Substituting this into the desired formula reduces the claim to simplifying the double reciprocal 1 / (1 / (1 - α m)) to 1 - α m, from which the result follows by elementary ring arithmetic.

  1. (m : ℝ) - c = 1 / (1 - α m), where c = (r : ℝ) - 1 / (1 - α r)

    Applying recursive_one_player_extension_reciprocal gives the linear relation 1 / (1 - α m) = 1 / (1 - α r) + ((m : ℝ) - (r : ℝ)). Rearranging this equality algebraically by ring arithmetic establishes that (m : ℝ) - ((r : ℝ) - 1 / (1 - α r)) equals 1 / (1 - α m).

    lines 8–10

    uses recursive_one_player_extension_reciprocal

      have h := recursive_one_player_extension_reciprocal r α hαr.2 hrec m hm
      have hc : (m : ℝ) - ((r : ℝ) - 1 / (1 - α r)) = 1 / (1 - α m) := by
        rw [h]; ring
  2. It suffices to show α m = 1 - 1 / (1 / (1 - α m))

    Unfolding the definition of c = (r : ℝ) - 1 / (1 - α r) in the target equality and substituting the expression for (m : ℝ) - c replaces the denominator with 1 / (1 - α m).

    lines 11–12

      show α m = 1 - 1 / ((m : ℝ) - ((r : ℝ) - 1 / (1 - α r)))
      rw [hc]
  3. 1 / (1 / (1 - α m)) = 1 - α m

    Applying one_div_div rewrites the double division 1 / (1 / (1 - α m)) as (1 - α m) / 1, which simp evaluates to 1 - α m.

    lines 13–14

    uses one_div_div

      have hinv : 1 / (1 / (1 - α m)) = 1 - α m := by
        rw [one_div_div]; simp
  4. α m = 1 - (1 - α m), concluding the proof

    Rewriting with the simplified double reciprocal transforms the goal into α m = 1 - (1 - α m), which is an identity verified by ring arithmetic.

    line 15

      rw [hinv]; ring
recursive_one_player_extension_reciprocal
Under the recurrence α (k + 1) = 1 / (2 - α k) with initial condition α r < 1, the reciprocal sequence satisfies 1 / (1 - α m) = 1 / (1 - α r) + (m - r) for all m ≥ r.
one_div_div
For elements a, b of a division monoid, the reciprocal of a / b is b / a: 1 / (a / b) = b / a.

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

/-- Proposition 2.3: Limitation of recursive one-player extension for multiplayer approximate Nash equilibria. -/theorem recursive_one_player_extension_barrier    (r : ℕ) (α : ℕ → ℝ) (hαr : 0 ≤ α r ∧ α r < 1)    (hrec : ∀ k, r ≤ k → α (k + 1) = 1 / (2 - α k))    (m : ℕ) (hm : r ≤ m) :    let c : ℝ := (r : ℝ) - 1 / (1 - α r)    α m = 1 - 1 / ((m : ℝ) - c) := by  have h := recursive_one_player_extension_reciprocal r α hαr.2 hrec m hm  have hc : (m : ℝ) - ((r : ℝ) - 1 / (1 - α r)) = 1 / (1 - α m) := by    rw [h]; ring  show α m = 1 - 1 / ((m : ℝ) - ((r : ℝ) - 1 / (1 - α r)))  rw [hc]  have hinv : 1 / (1 / (1 - α m)) = 1 - α m := by    rw [one_div_div]; simp  rw [hinv]; ring
See it in the graphDiscuss this resultChallenge it