AFTD Auto-Formalizing Theoretical Domains

int_dense_marks_bracket

theoremverified

If every integer lies at distance less than D after a marked integer, every unmarked integer lies strictly between two marked integers whose total separation is at most D.

Statement

theorem int_dense_marks_bracket
    (D : ℕ) (F : ℤ → Prop)
    (hdense : ∀ v : ℤ, ∃ a : ℕ, a < D ∧ F (v-(a : ℤ)))
    (p : ℤ) (hp : ¬F p) :
    ∃ l r : ℕ, 0 < l ∧ 0 < r ∧ l+r ≤ D ∧ F (p-(l : ℤ)) ∧ F (p+(r : ℤ))
Source
Uniform full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

To bracket the unmarked integer p, we choose l as the smallest positive offset less than D such that p - l is marked, and r as the smallest positive offset at most D such that p + r is marked. Applying the density hypothesis to the shifted point (p - l) + D yields a marked point at some offset a < D. The minimality of l prevents this marked point from falling between p - l and p, forcing it to lie to the right of p at distance t = D - l - a. By the minimality of r, we have r ≤ t ≤ D - l, which immediately gives l + r ≤ D.

  1. The set S of offsets a < D such that p - a is marked is nonempty.

    Working classically, define S as the finite set of natural numbers a < D such that p - a is marked (i.e., F (p - a) holds). Applying the density hypothesis to p produces an offset a < D with F (p - a), so a belongs to S and S is nonempty.

    lines 10–14

      classical
      let S : Finset ℕ := (range D).filter (fun (a : ℕ) => F (p-(a : ℤ)))
      have hS : S.Nonempty := by
        obtain ⟨a, ha, hFa⟩ := hdense p
        exact ⟨a, mem_filter.mpr ⟨mem_range.mpr ha, hFa⟩⟩
  2. There is a minimal positive distance l < D such that p - l is marked.

    Let l be the minimum element of S. By membership in S (via min'_mem), l < D and F (p - l) holds. If l were 0, then p - l = p would be marked (simplifying with Nat.cast_zero and sub_zero), directly contradicting the assumption that p is unmarked. Hence l > 0.

    lines 15–22

    uses min'_mem, Nat.cast_zero, sub_zero

      let l : ℕ := S.min' hS
      have hlmem : l ∈ S := min'_mem _ hS
      have hlD : l < D := mem_range.mp (mem_filter.mp hlmem).1
      have hFl : F (p-(l : ℤ)) := (mem_filter.mp hlmem).2
      have hl₀ : 0 < l := by
        by_contra hn
        have he : l = 0 := by omega
        exact hp (by simpa only [he, Nat.cast_zero, sub_zero] using hFl)
  3. There is a minimal positive distance r ≤ D such that p + r is marked.

    Define T as the finite set of positive integers r ≤ D such that p + r is marked. Applying the density hypothesis to p + D yields an offset a < D such that p + D - a is marked. Setting r' = D - a gives a positive integer r' ≤ D with p + r' = p + D - a, so r' ∈ T and T is nonempty. We then choose r to be the minimum element of T (via min'_mem), which guarantees 0 < r and F (p + r).

    lines 23–32

    uses min'_mem

      let T : Finset ℕ := (range (D+1)).filter (fun (r : ℕ) => 0 < r ∧ F (p+(r : ℤ)))
      have hT : T.Nonempty := by
        obtain ⟨a, ha, hFa⟩ := hdense (p+(D : ℤ))
        have hroot : p+((D-a : ℕ) : ℤ) = p+(D : ℤ)-(a : ℤ) := by omega
        refine ⟨D-a, mem_filter.mpr ⟨mem_range.mpr (by omega), by omega, ?_⟩⟩
        simpa only [hroot] using hFa
      let r : ℕ := T.min' hT
      have hrmem : r ∈ T := min'_mem _ hT
      have hr₀ : 0 < r := (mem_filter.mp hrmem).2.1
      have hFr : F (p+(r : ℤ)) := (mem_filter.mp hrmem).2.2
  4. Applying density at (p - l) + D produces a marked integer at offset a < D satisfying l + a < D.

    Applying the density hypothesis to (p - l) + D yields an offset a < D such that (p - l) + D - a is marked. If we had l + a ≥ D, then the difference c = l + a - D would be a natural number strictly less than l (since a < D) and less than D. Furthermore, p - c = (p - l) + D - a would be marked, making c ∈ S. But by the minimality of l in S (min'_le), l ≤ c, contradicting c < l. Hence l + a < D.

    lines 33–42

    uses min'_le

      obtain ⟨a, ha, hFa⟩ := hdense (p-(l : ℤ)+(D : ℤ))
      have hla : l+a < D := by
        by_contra hn
        let c := l+a-D
        have hcD : c < D := by dsimp [c]; omega
        have hcl : c < l := by dsimp [c]; omega
        have hcroot : p-(c : ℤ) = p-(l : ℤ)+(D : ℤ)-(a : ℤ) := by dsimp [c]; omega
        have hcmem : c ∈ S := mem_filter.mpr ⟨mem_range.mpr hcD, by simpa only [hcroot] using hFa⟩
        have hmin : l ≤ c := min'_le S c hcmem
        omega
  5. The distances l and r satisfy l + r ≤ D, strictly bracketing p between marked integers.

    Define t = D - l - a. Since l + a < D, t is a strictly positive integer with t ≤ D. The identity p + t = (p - l) + D - a shows that p + t is marked, so t ∈ T. By the minimality of r in T (min'_le), r ≤ t = D - l - a ≤ D - l, which rearranges to l + r ≤ D. Together with 0 < l, 0 < r, F (p - l), and F (p + r), this establishes the existence of the desired bracket.

    lines 43–49

    uses min'_le

      let t := D-l-a
      have ht₀ : 0 < t := by dsimp [t]; omega
      have htD : t < D+1 := by dsimp [t]; omega
      have htroot : p+(t : ℤ) = p-(l : ℤ)+(D : ℤ)-(a : ℤ) := by dsimp [t]; omega
      have htmem : t ∈ T := mem_filter.mpr ⟨mem_range.mpr htD, ht₀, by simpa only [htroot] using hFa⟩
      have hrt : r ≤ t := min'_le T t htmem
      exact ⟨l, r, hl₀, hr₀, by dsimp [t] at hrt; omega, hFl, hFr⟩
min'_mem
The minimum element of a nonempty finite set belongs to that set.
Nat.cast_zero
The natural number 0 cast into an additive monoid with one (such as the integers) is 0.
sub_zero
Subtracting 0 from an element leaves it unchanged.
min'_le
The minimum element of a finite set is less than or equal to every element in the set.

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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem int_dense_marks_bracket    (D : ℕ) (F : ℤ → Prop)    (hdense : ∀ v : ℤ, ∃ a : ℕ, a < D ∧ F (v-(a : ℤ)))    (p : ℤ) (hp : ¬F p) :    ∃ l r : ℕ, 0 < l ∧ 0 < r ∧ l+r ≤ D ∧ F (p-(l : ℤ)) ∧ F (p+(r : ℤ)) := by  classical  let S : Finset ℕ := (range D).filter (fun (a : ℕ) => F (p-(a : ℤ)))  have hS : S.Nonempty := by    obtain ⟨a, ha, hFa⟩ := hdense p    exact ⟨a, mem_filter.mpr ⟨mem_range.mpr ha, hFa⟩⟩  let l : ℕ := S.min' hS  have hlmem : l ∈ S := min'_mem _ hS  have hlD : l < D := mem_range.mp (mem_filter.mp hlmem).1  have hFl : F (p-(l : ℤ)) := (mem_filter.mp hlmem).2  have hl₀ : 0 < l := by    by_contra hn    have he : l = 0 := by omega    exact hp (by simpa only [he, Nat.cast_zero, sub_zero] using hFl)  let T : Finset ℕ := (range (D+1)).filter (fun (r : ℕ) => 0 < r ∧ F (p+(r : ℤ)))  have hT : T.Nonempty := by    obtain ⟨a, ha, hFa⟩ := hdense (p+(D : ℤ))    have hroot : p+((D-a : ℕ) : ℤ) = p+(D : ℤ)-(a : ℤ) := by omega    refine ⟨D-a, mem_filter.mpr ⟨mem_range.mpr (by omega), by omega, ?_⟩⟩    simpa only [hroot] using hFa  let r : ℕ := T.min' hT  have hrmem : r ∈ T := min'_mem _ hT  have hr₀ : 0 < r := (mem_filter.mp hrmem).2.1  have hFr : F (p+(r : ℤ)) := (mem_filter.mp hrmem).2.2  obtain ⟨a, ha, hFa⟩ := hdense (p-(l : ℤ)+(D : ℤ))  have hla : l+a < D := by    by_contra hn    let c := l+a-D    have hcD : c < D := by dsimp [c]; omega    have hcl : c < l := by dsimp [c]; omega    have hcroot : p-(c : ℤ) = p-(l : ℤ)+(D : ℤ)-(a : ℤ) := by dsimp [c]; omega    have hcmem : c ∈ S := mem_filter.mpr ⟨mem_range.mpr hcD, by simpa only [hcroot] using hFa⟩    have hmin : l ≤ c := min'_le S c hcmem    omega  let t := D-l-a  have ht₀ : 0 < t := by dsimp [t]; omega  have htD : t < D+1 := by dsimp [t]; omega  have htroot : p+(t : ℤ) = p-(l : ℤ)+(D : ℤ)-(a : ℤ) := by dsimp [t]; omega  have htmem : t ∈ T := mem_filter.mpr ⟨mem_range.mpr htD, ht₀, by simpa only [htroot] using hFa⟩  have hrt : r ≤ t := min'_le T t htmem  exact ⟨l, r, hl₀, hr₀, by dsimp [t] at hrt; omega, hFl, hFr⟩
See it in the graphDiscuss this resultChallenge it