int_dense_marks_bracket
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
- cycle_power_dyadic_class_no_island_of_full_class_coverA positive-exponent integer dyadic rooted-class model with tight weights, exact dyadic pair ownership, all ordinary distance coverage, and…
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.
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.
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⟩⟩
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.
uses
min'_mem,Nat.cast_zero,sub_zerolet 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)
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).
uses
min'_memlet 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
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.
uses
min'_leobtain ⟨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
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.
uses
min'_lelet 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩