AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_prune_range_counterexample

theoremverified

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

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.

  1. 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).

    lines 20–35

      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
  2. 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.

    lines 51–52

    uses cycle_power_dyadic_prune_range_counterexample_finite

      obtain ⟨x, hw, he, hc, hmin, hp⟩ := cycle_power_dyadic_prune_range_counterexample_finite
      refine ⟨fun p j => x (p : ZMod 12) j, ?_, ?_, ?_, ?_, ?_, ?_⟩
  3. 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).

    lines 53–56

    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]
  4. 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.

    lines 57–58

      · intro p
        exact hw (p : ZMod 12)
  5. 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.

    lines 59–60

    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)
  6. 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 ℤ.

    lines 61–67

    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⟩
  7. 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.

    lines 68–69

    uses Int.cast_sub, Int.cast_natCast

      · intro v
        simpa only [Int.cast_sub, Int.cast_natCast] using hmin (v : ZMod 12)
  8. 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.

    line 70

    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.

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 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
See it in the graphDiscuss this resultChallenge it