cycle_power_dyadic_prune_range_counterexample
There is a period-12 tight radius-16 class model with exact dyadic long-edge coverage and full ordinary coverage, whose original active counts are all at least four but whose outer-quarter pruned count at zero is two. Thus pruning need not lower the minimum active count by at most one. The original counts vary; this is not a counterexample to constant-count pruning or OP-205.
Statement
theorem cycle_power_dyadic_prune_range_counterexample : ∃ x : ℤ → ℕ → Bool, (∀ p j, x (p + 12) j = x p j) ∧ (∀ p, cycle_power_dyadic_class_weight 4 (x p) = (range 16).sum (fun a => (x p a).toNat)) ∧ (∀ j < 4, ∀ v : ℤ, (range (2 ^ j)).sum (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 16 - 2 ^ j)).toNat) = 1) ∧ (∀ d : ℕ, 1 ≤ d → d < 16 → ∀ v : ℤ, ∃ a ∈ range (16 - d), x (v - (a : ℤ)) a = true ∧ x (v - (a : ℤ)) (a + d) = true) ∧ (∀ v : ℤ, 4 ≤ (range 16).sum (fun a => (x (v - (a : ℤ)) a).toNat)) ∧ (range 8).sum (fun a => (cycle_power_dyadic_b_lift 2 (x (-(a : ℤ))) a).toNat) = 2
- Source
- Auxiliary route audit for OP-205 / RT-1, following arXiv:2610.15635 Section 3. Experiment 6286 minimizes the countermodel to the stronger extremal-count shortcut tried in this campaign session. No graph covering bound or research advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- cycle_power_dyadic_class_weightThe weighted number of pairs in a dyadic arc: the endpoint pair has weight two, and distances 2^m-2^j for 1≤j<m have weight one.
- cycle_power_dyadic_class_weight_leFor every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
The proof, explained
The counterexample is constructed by defining an explicit periodic configuration on ℤ/12ℤ with radius 16 and verifying all coverage, class weight, and pruning conditions by finite exhaustive computation (`decide`). This finite model has active window counts ranging from 4 to 16, satisfies exact dyadic coverage and full ordinary coverage up to distance 15, but has an outer-quarter pruned count of 2 at the origin. The model is then lifted to a 12-periodic configuration on ℤ via the canonical projection p ↦ (p : ZMod 12), where all properties transfer directly because coverage conditions depend only on coordinate differences.
There exists an explicit configuration on ℤ/12ℤ satisfying exact dyadic class weights, exact dyadic long-edge coverage, full ordinary distance coverage, active counts of at least 4, and outer-quarter pruned count 2 at 0. automation
We construct the configuration x : ZMod 12 → ℕ → Bool by explicitly specifying the active indices in {0, ..., 15} for each residue class modulo 12. Providing x as the witness, all five required properties—the exact dyadic class weight, exact dyadic long-edge coverage for scales j < 4, ordinary distance coverage for d ∈ {1, ..., 15}, active counts at least 4 across each 16-element window, and an outer-quarter pruned count of 2 at 0—are finite decidable propositions verified by exhaustive computation (decide).
let x : ZMod 12 → ℕ → Bool := fun p j => decide (j ∈ match p.val with | 0 => ({0, 1, 2, 3, 4, 9, 10, 11, 12, 13, 14, 15} : Finset ℕ) | 1 => {0, 15} | 2 => {0, 14, 15} | 3 => {0, 1, 13, 14, 15} | 4 => {0, 15} | 5 => range 16 | 6 => {0, 15} | 7 => {0, 1, 14, 15} | 8 => {0, 15} | 9 => {0, 1, 2, 12, 13, 14, 15} | 10 => {0, 15} | _ => {0, 14, 15}) refine ⟨x, ?_⟩ decide
Define the candidate configuration on ℤ by lifting the finite ℤ/12ℤ counterexample via projection modulo 12.
We instantiate the finite model on ℤ/12ℤ and its five verified properties using cycle_power_dyadic_prune_range_counterexample_finite. The configuration on ℤ is defined by composing with the canonical reduction p ↦ (p : ZMod 12), leaving six properties to verify for the lifted configuration.
uses
cycle_power_dyadic_prune_range_counterexample_finiteobtain ⟨x, hw, he, hc, hmin, hp⟩ := cycle_power_dyadic_prune_range_counterexample_finite refine ⟨fun p j => x (p : ZMod 12) j, ?_, ?_, ?_, ?_, ?_, ?_⟩
The configuration is 12-periodic on ℤ: x (p + 12) j = x p j.
Reducing p + 12 modulo 12 gives (p : ZMod 12) + (12 : ZMod 12). Since 12 = 0 in ℤ/12ℤ by computation (decide), this reduces to (p : ZMod 12) + 0 = (p : ZMod 12).
uses
Int.cast_add,Int.cast_ofNat,add_zero· intro p j simp only [Int.cast_add, Int.cast_ofNat] have hz : (12 : ZMod 12) = 0 := by decide rw [hz, add_zero]
The dyadic class weight of x p equals the total active count in the radius-16 window for each p ∈ ℤ.
The dyadic class weight and the window sum at p ∈ ℤ depend only on the fiber x (p : ZMod 12), so the equality follows immediately from the corresponding class weight property hw of the finite model.
· intro p exact hw (p : ZMod 12)
For each dyadic scale j < 4 and each vertex v ∈ ℤ, exactly one dyadic long edge covers v.
The dyadic coverage sum evaluates pairs at offsets v - a for a ∈ {0, ..., 2^j - 1}. Simplifying the integer subtraction and natural casts shows this sum is identical to the dyadic coverage sum at v : ZMod 12, which equals 1 by the finite model's property he.
uses
Int.cast_sub,Int.cast_natCast· intro j hj v simpa only [Int.cast_sub, Int.cast_natCast] using he ⟨j, hj⟩ (v : ZMod 12)
For every distance d ∈ {1, ..., 15} and vertex v ∈ ℤ, there is an active pair at distance d covering v.
Since 1 ≤ d < 16, linear integer arithmetic (omega) shows d - 1 < 15 and (d - 1) + 1 = d. The coverage property hc of the finite model provides an active pair at offset a < 16 - d for vertex v : ZMod 12, and projecting the integer offsets into ℤ/12ℤ shows the same offset a works on ℤ.
uses
Int.cast_sub,Int.cast_natCast· intro d hd hd16 v have hi : d - 1 < 15 := by omega have hd' : d - 1 + 1 = d := by omega obtain ⟨a, ha, h1, h2⟩ := hc ⟨d - 1, hi⟩ (v : ZMod 12) simp only [hd'] at ha h1 h2 exact ⟨a, ha, by simpa only [Int.cast_sub, Int.cast_natCast] using h1, by simpa only [Int.cast_sub, Int.cast_natCast] using h2⟩
For every vertex v ∈ ℤ, the active count across the radius-16 window is at least 4.
The window sum at v ∈ ℤ reduces modulo 12 to the window sum at v : ZMod 12, which is at least 4 by the minimum count property hmin of the finite model.
uses
Int.cast_sub,Int.cast_natCast· intro v simpa only [Int.cast_sub, Int.cast_natCast] using hmin (v : ZMod 12)
The outer-quarter pruned count at vertex 0 is 2.
The pruned count at 0 evaluates the lifted predicate at vertices -a for a ∈ {0, ..., 7}. Simplifying the negation and casts identifies this with the pruned count at 0 in ℤ/12ℤ, which equals 2 by property hp of the finite model.
uses
Int.cast_neg,Int.cast_natCast· simpa only [Int.cast_neg, Int.cast_natCast] using hp
cycle_power_dyadic_prune_range_counterexample_finite- There exists a configuration on ℤ/12ℤ satisfying exact dyadic class weights, exact dyadic long-edge coverage, full ordinary coverage up to distance 15, minimum active count at least 4, and outer-quarter pruned count 2 at 0.
Int.cast_add- The canonical cast from ℤ to a ring preserves addition: ↑(m + n) = ↑m + ↑n.
Int.cast_ofNat- Casting a natural number numeral from ℤ to a ring matches the numeral in the ring.
add_zero- Adding zero to an element leaves it unchanged: a + 0 = a.
Int.cast_sub- The canonical cast from ℤ to a ring preserves subtraction: ↑(m - n) = ↑m - ↑n.
Int.cast_natCast- Casting a natural number directly to a ring agrees with casting via ℤ: ↑(↑n : ℤ) = ↑n.
Int.cast_neg- The canonical cast from ℤ to a ring preserves negation: ↑(-n) = -↑n.
- The verification of the finite model cycle_power_dyadic_prune_range_counterexample_finite is performed entirely by computational evaluation via `decide` over the finite types ZMod 12, Fin 4, and Fin 15.
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 4000000 intheorem cycle_power_dyadic_prune_range_counterexample_finite : ∃ x : ZMod 12 → ℕ → Bool, (∀ p, cycle_power_dyadic_class_weight 4 (x p) = (range 16).sum (fun a => (x p a).toNat)) ∧ (∀ (j : Fin 4) (v : ZMod 12), (range (2 ^ (j : ℕ))).sum (fun a => (x (v - (a : ZMod 12)) a && x (v - (a : ZMod 12)) (a + 16 - 2 ^ (j : ℕ))).toNat) = 1) ∧ (∀ (d : Fin 15) (v : ZMod 12), ∃ a ∈ range (16 - ((d : ℕ) + 1)), x (v - (a : ZMod 12)) a = true ∧ x (v - (a : ZMod 12)) (a + ((d : ℕ) + 1)) = true) ∧ (∀ v : ZMod 12, 4 ≤ (range 16).sum (fun a => (x (v - (a : ZMod 12)) a).toNat)) ∧ (range 8).sum (fun a => (cycle_power_dyadic_b_lift 2 (x (-(a : ZMod 12))) a).toNat) = 2 := by let x : ZMod 12 → ℕ → Bool := fun p j => decide (j ∈ match p.val with | 0 => ({0, 1, 2, 3, 4, 9, 10, 11, 12, 13, 14, 15} : Finset ℕ) | 1 => {0, 15} | 2 => {0, 14, 15} | 3 => {0, 1, 13, 14, 15} | 4 => {0, 15} | 5 => range 16 | 6 => {0, 15} | 7 => {0, 1, 14, 15} | 8 => {0, 15} | 9 => {0, 1, 2, 12, 13, 14, 15} | 10 => {0, 15} | _ => {0, 14, 15}) refine ⟨x, ?_⟩ decidetheorem cycle_power_dyadic_prune_range_counterexample : ∃ x : ℤ → ℕ → Bool, (∀ p j, x (p + 12) j = x p j) ∧ (∀ p, cycle_power_dyadic_class_weight 4 (x p) = (range 16).sum (fun a => (x p a).toNat)) ∧ (∀ j < 4, ∀ v : ℤ, (range (2 ^ j)).sum (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 16 - 2 ^ j)).toNat) = 1) ∧ (∀ d : ℕ, 1 ≤ d → d < 16 → ∀ v : ℤ, ∃ a ∈ range (16 - d), x (v - (a : ℤ)) a = true ∧ x (v - (a : ℤ)) (a + d) = true) ∧ (∀ v : ℤ, 4 ≤ (range 16).sum (fun a => (x (v - (a : ℤ)) a).toNat)) ∧ (range 8).sum (fun a => (cycle_power_dyadic_b_lift 2 (x (-(a : ℤ))) a).toNat) = 2 := by obtain ⟨x, hw, he, hc, hmin, hp⟩ := cycle_power_dyadic_prune_range_counterexample_finite refine ⟨fun p j => x (p : ZMod 12) j, ?_, ?_, ?_, ?_, ?_, ?_⟩ · intro p j simp only [Int.cast_add, Int.cast_ofNat] have hz : (12 : ZMod 12) = 0 := by decide rw [hz, add_zero] · intro p exact hw (p : ZMod 12) · intro j hj v simpa only [Int.cast_sub, Int.cast_natCast] using he ⟨j, hj⟩ (v : ZMod 12) · intro d hd hd16 v have hi : d - 1 < 15 := by omega have hd' : d - 1 + 1 = d := by omega obtain ⟨a, ha, h1, h2⟩ := hc ⟨d - 1, hi⟩ (v : ZMod 12) simp only [hd'] at ha h1 h2 exact ⟨a, ha, by simpa only [Int.cast_sub, Int.cast_natCast] using h1, by simpa only [Int.cast_sub, Int.cast_natCast] using h2⟩ · intro v simpa only [Int.cast_sub, Int.cast_natCast] using hmin (v : ZMod 12) · simpa only [Int.cast_neg, Int.cast_natCast] using hp