AFTD Auto-Formalizing Theoretical Domains

low_hole_reduction_overtake

theoremverified

Let 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) = recursive_line_hole_budget m n z z_RL - H - d, (d = 0 → z_2A ≤ z_2), and recursive_line_hole_budget m n z z_RL ≤ 2, then z_2A = z_2.

Statement

theorem low_hole_reduction_overtake
    (m n : ℕ) (z z_RL z_2 z_2A H d : ℤ)
    (hle : z_RL ≤ z_2)
    (h_overtake : z_2 ≤ z_2A)
    (hH : 0 ≤ H)
    (hd : 0 ≤ d)
    (h_budget : 2 * (z_2A - z_RL) = recursive_line_hole_budget m n z z_RL - H - d)
    (h_limited : d = 0 → z_2A ≤ z_2)
    (h_low : recursive_line_hole_budget m n z z_RL ≤ 2) :
    z_2A = z_2
Source
scout/2610-22875-overtake-and-the-recursive-line-equality-for-second-order-z.md:549
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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_two_mul_sub_ge_twoFor integers z_RL, z_2, and z_2A, if z_RL ≤ z_2 and z_2 < z_2A, then 2 ≤ 2 * (z_2A - z_RL).
  • low_hole_reduction_forces_zeroFor integers L, h, H, and d, if 0 ≤ H, 0 ≤ d, L = h - H - d, 2 ≤ L, and h ≤ 2, then h = 2 ∧ H = 0 ∧ d = 0.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

Read back from the Lean

For all natural numbers $m$ and $n$, and all integers $z$, $z_{RL}$, $z_2$, $z_{2A}$, $H$, and $d$, if: 1. $z_{RL} \le z_2$, 2. $z_2 \le z_{2A}$, 3. $0 \le H$, 4. $0 \le d$, 5. $2(z_{2A} - z_{RL}) = \text{recursive\_line\_hole\_budget}(m, n, z, z_{RL}) - H - d$, 6. $d = 0 \implies z_{2A} \le z_2$, and 7. $\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 is proved by contradiction. If z_2A ≠ z_2, then z_2 < z_2A, which together with z_RL ≤ z_2 forces 2 * (z_2A - z_RL) ≥ 2. Because the recursive line hole budget is at most 2 and equals 2 * (z_2A - z_RL) + H + d with H, d ≥ 0, the deficit d must equal 0. By hypothesis, d = 0 implies z_2A ≤ z_2, which contradicts z_2 < z_2A.

  1. z_2 < z_2A

    Assume for contradiction that z_2A ≠ z_2. Since z_2 ≤ z_2A by assumption, this inequality must be strict, giving z_2 < z_2A.

    lines 12–13

    uses lt_of_le_of_ne, Ne.symm

      by_contra hne
      have hgt : z_2 < z_2A := lt_of_le_of_ne h_overtake (Ne.symm hne)
  2. 2 ≤ 2 * (z_2A - z_RL)

    Since z_RL ≤ z_2 and z_2 < z_2A for integers, the difference z_2A - z_RL is at least 1, so twice this difference is at least 2.

    line 14

    uses low_hole_two_mul_sub_ge_two

      have h2 : 2 ≤ 2 * (z_2A - z_RL) := low_hole_two_mul_sub_ge_two z_RL z_2 z_2A hle hgt
  3. d = 0

    The budget equation expresses 2 * (z_2A - z_RL) as recursive_line_hole_budget m n z z_RL - H - d. With H ≥ 0, d ≥ 0, 2 ≤ 2 * (z_2A - z_RL), and the budget bounded by 2, low_hole_reduction_forces_zero forces the budget to be 2, H to be 0, and d to be 0.

    lines 15–17

    uses low_hole_reduction_forces_zero

      have hzero := low_hole_reduction_forces_zero (2 * (z_2A - z_RL))
        (recursive_line_hole_budget m n z z_RL) H d hH hd h_budget h2 h_low
      have hd0 : d = 0 := hzero.2.2
  4. A contradiction is reached, proving z_2A = z_2

    Because d = 0, the hypothesis h_limited yields z_2A ≤ z_2. Linear arithmetic closes the goal by showing this contradicts z_2 < z_2A.

    lines 18–19

      have hle' : z_2A ≤ z_2 := h_limited hd0
      linarith
lt_of_le_of_ne
In a partial order, if a ≤ b and a ≠ b, then a < b.
Ne.symm
Symmetry of inequality: if a ≠ b, then b ≠ a.
low_hole_two_mul_sub_ge_two
For integers, if z_RL ≤ z_2 and z_2 < z_2A, then 2 ≤ 2 * (z_2A - z_RL).
low_hole_reduction_forces_zero
If integers satisfy L = h - H - d with 0 ≤ H, 0 ≤ d, 2 ≤ L, and h ≤ 2, then h = 2, H = 0, and d = 0.

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 for given hole count and deficit. -/theorem low_hole_reduction_overtake    (m n : ℕ) (z z_RL z_2 z_2A H d : ℤ)    (hle : z_RL ≤ z_2)    (h_overtake : z_2 ≤ z_2A)    (hH : 0 ≤ H)    (hd : 0 ≤ d)    (h_budget : 2 * (z_2A - z_RL) = recursive_line_hole_budget m n z z_RL - H - d)    (h_limited : d = 0 → z_2A ≤ z_2)    (h_low : recursive_line_hole_budget m n z z_RL ≤ 2) :    z_2A = z_2 := by  by_contra hne  have hgt : z_2 < z_2A := lt_of_le_of_ne h_overtake (Ne.symm hne)  have h2 : 2 ≤ 2 * (z_2A - z_RL) := low_hole_two_mul_sub_ge_two z_RL z_2 z_2A hle hgt  have hzero := low_hole_reduction_forces_zero (2 * (z_2A - z_RL))    (recursive_line_hole_budget m n z z_RL) H d hH hd h_budget h2 h_low  have hd0 : d = 0 := hzero.2.2  have hle' : z_2A ≤ z_2 := h_limited hd0  linarith
See it in the graphDiscuss this resultChallenge it