AFTD Auto-Formalizing Theoretical Domains

low_hole_reduction_ruling_out_overtake

theoremverifiedformalization

Let m, n be natural numbers and let z, z_RL, z_2, z_2A be integers such that z_RL ≤ z_2 and z_2 ≤ z_2A. Suppose there exist integers H and d such that 0 ≤ H, 0 ≤ d, 2 * (z_2A - z_RL) = recursive_line_hole_budget m n z z_RL - H - d, and (d = 0 → z_2A ≤ z_2). If recursive_line_hole_budget m n z z_RL ≤ 2, then z_2A = z_2.

Statement

theorem low_hole_reduction_ruling_out_overtake
    (m n : ℕ) (z z_RL z_2 z_2A : ℤ)
    (hle : z_RL ≤ z_2)
    (h_overtake : z_2 ≤ z_2A)
    (h_witness : ∃ (H d : ℤ), 0 ≤ H ∧ 0 ≤ d ∧
      2 * (z_2A - z_RL) = recursive_line_hole_budget m n z z_RL - H - d ∧
      (d = 0 → z_2A ≤ z_2))
    (h_low : recursive_line_hole_budget m n z z_RL ≤ 2) :
    z_2A = z_2
Formalizes
scout/2610-22875-overtake-and-the-recursive-line-equality-for-second-order-z.md:539
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • recursive_line_hole_budgetThe recursive-line hole budget recursive_line_hole_budget m n z z_RL for natural numbers m, n and integers z, z_RL is defined as (m : ℤ) *…
  • low_hole_reduction_overtakeLet m, n be natural numbers and let z, z_RL, z_2, z_2A, H, d be integers. If z_RL ≤ z_2, z_2 ≤ z_2A, 0 ≤ H, 0 ≤ d, 2 * (z_2A - z_RL) =…

Read back from the Lean

For all natural numbers $m, n$ and all integers $z, z_{RL}, z_2, z_{2A}$, if: 1. $z_{RL} \le z_2$, 2. $z_2 \le z_{2A}$, 3. there exist integers $H$ and $d$ such that $0 \le H$, $0 \le d$, $2(z_{2A} - z_{RL}) = \text{recursive\_line\_hole\_budget}(m, n, z, z_{RL}) - H - d$, and $d = 0 \to z_{2A} \le z_2$, and 4. $\text{recursive\_line\_hole\_budget}(m, n, z, z_{RL}) \le 2$, then $z_{2A} = z_2$.

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 theorem rules out an overtake (establishing $z_{2A} = z_2$) whenever the recursive line hole budget is at most 2. The proof unpacks the existential hypothesis to obtain explicit witness integers $H$ and $d$ satisfying the required non-negativity and budget relations, and then directly applies the theorem `low_hole_reduction_overtake`.

  1. Fix witness integers $H$ and $d$ satisfying $0 \le H$, $0 \le d$, the hole budget relation, and the condition $d = 0 \implies z_{2A} \le z_2$.

    We unpack the existential hypothesis `h_witness`, obtaining explicit integers $H$ and $d$ along with their non-negativity and structural properties.

    line 11

      rcases h_witness with ⟨H, d, hH, hd, h_budget, h_limited⟩
  2. $z_{2A} = z_2$

    With the explicit witnesses $H$ and $d$ in hand, we invoke `low_hole_reduction_overtake`, supplying the inequalities $z_{RL} \le z_2$ and $z_2 \le z_{2A}$, the non-negativity of $H$ and $d$, the budget identity, the implication $d = 0 \implies z_{2A} \le z_2$, and the budget bound $\text{recursive\_line\_hole\_budget}(m, n, z, z_{RL}) \le 2$.

    lines 12–13

    uses low_hole_reduction_overtake

      exact low_hole_reduction_overtake m n z z_RL z_2 z_2A H d
        hle h_overtake hH hd h_budget h_limited h_low
low_hole_reduction_overtake
Given integers $z_{RL} \le z_2 \le z_{2A}$ and non-negative integers $H, d$ satisfying $2(z_{2A} - z_{RL}) = \text{recursive\_line\_hole\_budget}(m, n, z, z_{RL}) - H - d$ and $(d = 0 \implies z_{2A} \le z_2)$, if $\text{recursive\_line\_hole\_budget}(m, n, z, z_{RL}) \le 2$, then $z_{2A} = z_2$.

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

/-- Low-hole reduction ruling out overtake (Theorem 10). -/theorem low_hole_reduction_ruling_out_overtake    (m n : ℕ) (z z_RL z_2 z_2A : ℤ)    (hle : z_RL ≤ z_2)    (h_overtake : z_2 ≤ z_2A)    (h_witness : ∃ (H d : ℤ), 0 ≤ H ∧ 0 ≤ d ∧      2 * (z_2A - z_RL) = recursive_line_hole_budget m n z z_RL - H - d ∧      (d = 0 → z_2A ≤ z_2))    (h_low : recursive_line_hole_budget m n z z_RL ≤ 2) :    z_2A = z_2 := by  rcases h_witness with ⟨H, d, hH, hd, h_budget, h_limited⟩  exact low_hole_reduction_overtake m n z z_RL z_2 z_2A H d    hle h_overtake hH hd h_budget h_limited h_low
See it in the graphDiscuss this resultChallenge it