cycle_power_dyadic_half_monotone_count_barrier
There exists a3-periodic radius4 Boolean class model with tight class weights, all exact dyadic edge equations, all ordinary edge coverage, and monotone first and second halves, but active count at vertex0 is2, below the putative optimal local lower bound3. This only refutes recovering the pointwise lower bound from these auxiliary assumptions; the original constant optimal-count hypothesis is omitted, so it is not a counterexample to OP-205.
Statement
theorem cycle_power_dyadic_half_monotone_count_barrier : ∃ x : ℤ → ℕ → Bool, (∀ p a, x (p+3) a = x p a) ∧ (∀ p, cycle_power_dyadic_class_weight 2 (x p) = (range 4).sum (fun a => (x p a).toNat)) ∧ (∀ j < 2, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+4-2^j)).toNat) = 1) ∧ (∀ d : ℕ, 1 ≤ d → d < 4 → ∀ v : ℤ, ∃ a : ℕ, a < 4-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) ∧ (∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2 → x p b = true → x p a = true) ∧ (∀ a b : ℕ, 2 ≤ a → a ≤ b → b < 4 → x p a = true → x p b = true)) ∧ (range 4).sum (fun a => (x (-(a : ℤ)) a).toNat) = 2
- Source
- Auxiliary-model route barrier for OP-205 / RT-1 following arXiv:2610.15635 Section3; explicit period3 radius4 witness found in experiment7537. Existing radius8 count-variation witnesses already demonstrate the related omission-of-counts obstruction. No graph covering value or research advance claimed.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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.
The proof, explained
The proof constructs an explicit 3-periodic Boolean model x : ℤ → ℕ → Bool of radius 4 defined by x(p, a) = b(p % 3, a), where the three residue classes yield bit patterns [1, 1, 1, 1], [1, 0, 0, 1], and [1, 0, 1, 1]. Because of 3-periodicity, the universal conditions—tight class weights, exact dyadic edge equations, ordinary edge coverage, and monotonicity on both halves—reduce to finite checks over the residue classes {0, 1, 2}, each verified by exhaustive computation via `decide`. Finally, evaluating the active count at vertex 0 gives x(0, 0) + x(-1, 1) + x(-2, 2) + x(-3, 3) = 1 + 0 + 0 + 1 = 2, demonstrating that these auxiliary hypotheses alone cannot force the putative lower bound of 3.
Define the 3-periodic Boolean model candidate x and establish modular shift invariance.
We define a base pattern b(r, a) for residue r and bit index a to be true if and only if a ∈ {0, 3}, or r ≡ 0 and a < 4, or r ≡ 2 and a = 2. The global model is set to x(p, a) = b(p % 3, a). We note that p % 3 always takes values in {0, 1, 2} (hres), and we prove the shift identity x(p - a) = x((p % 3) - a) (hshift) by rewriting with the modular arithmetic identities Int.sub_emod and Int.emod_emod.
uses
Int.sub_emod,Int.emod_emodlet b : ℤ → ℕ → Bool := fun r a => decide (a=0 ∨ a=3 ∨ (r=0 ∧ a<4) ∨ (r=2 ∧ a=2)) let x : ℤ → ℕ → Bool := fun p => b (p%3) have hres (p : ℤ) : p%3=0 ∨ p%3=1 ∨ p%3=2 := by omega have hshift (p : ℤ) (a : ℕ) : x (p-(a : ℤ)) = x (p%3-(a : ℤ)) := by dsimp [x] simp only [Int.sub_emod,Int.emod_emod]
Verify by finite computation that b satisfies tight class weights, dyadic edge equations, edge coverage, and half-monotonicity on each residue class modulo 3. automation
Because x is 3-periodic and of radius 4, the universal properties need only be checked on the three residue classes r ∈ Fin 3. Using the decide tactic, Lean exhaustively verifies four finite tables: htableT (class weight equals the bit sum for all r), htableE (dyadic edge sum equals 1 for all r and scales j < 2), htableC (for each r and difference 1 ≤ d < 4, an active edge of length d exists), and htableS (monotonicity on the first half {0, 1} and second half {2, 3} for all r).
have htableT : ∀ r : Fin 3, cycle_power_dyadic_class_weight 2 (b (r.val : ℤ)) = (range 4).sum (fun a => (b (r.val : ℤ) a).toNat) := by decide have htableE : ∀ r : Fin 3, ∀ j : Fin 2, (range (2^j.val)).sum (fun a => (x ((r.val : ℤ)-(a : ℤ)) a && x ((r.val : ℤ)-(a : ℤ)) (a+4-2^j.val)).toNat) = 1 := by decide have htableC : ∀ r : Fin 3, ∀ d : Fin 4, 1 ≤ d.val → ∃ a : Fin 4, a.val < 4-d.val ∧ x ((r.val : ℤ)-(a.val : ℤ)) a.val = true ∧ x ((r.val : ℤ)-(a.val : ℤ)) (a.val+d.val) = true := by decide have htableS : ∀ r : Fin 3, (∀ a c : Fin 4, a.val ≤ c.val → c.val < 2 → b (r.val : ℤ) c.val = true → b (r.val : ℤ) a.val = true) ∧ (∀ a c : Fin 4, 2 ≤ a.val → a.val ≤ c.val → b (r.val : ℤ) a.val = true → b (r.val : ℤ) c.val = true) := by decide
Instantiate the existential goal with x and split into six subgoals.
Using refine, we supply x as the witness for the existential quantifier, leaving six subgoals: 3-periodicity, tight class weights, dyadic edge equations, ordinary edge coverage, half-monotonicity, and the active count at vertex 0.
refine ⟨x, ?_, ?_, ?_, ?_, ?_, ?_⟩The model x is 3-periodic: x(p + 3, a) = x(p, a) for all p and a.
By definition x(p + 3, a) = b((p + 3) % 3, a) and x(p, a) = b(p % 3, a). The congruence (p + 3) % 3 = p % 3 is solved immediately by linear integer arithmetic (omega).
· intro p a dsimp [x] congr 1 omega
The class weight of x(p) is tight for every p.
For any integer p, the remainder p % 3 is non-negative by Int.emod_nonneg and strictly less than 3 by omega. Using Int.toNat_of_nonneg to convert this remainder to a natural number in Fin 3, we instantiate the precomputed table htableT at r = (p % 3).toNat.
uses
Int.emod_nonneg,Int.toNat_of_nonneg· intro p have hr : 0 ≤ p%3 := Int.emod_nonneg _ (by decide) simpa only [x,Int.toNat_of_nonneg hr] using htableT ⟨(p%3).toNat, by omega⟩
All exact dyadic edge equations hold for all scales j < 2 and vertices v.
Rewriting each term x(v - a) using the shift identity hshift reduces the sum to depend only on v % 3. Since 0 ≤ v % 3 < 3 by Int.emod_nonneg and omega, we convert the residue using Int.toNat_of_nonneg and instantiate the precomputed table htableE at r = (v % 3).toNat and scale j.
uses
Int.emod_nonneg,Int.toNat_of_nonneg· intro j hj v simp_rw [hshift v] have hr : 0 ≤ v%3 := Int.emod_nonneg _ (by decide) simpa only [Int.toNat_of_nonneg hr] using htableE ⟨(v%3).toNat,by omega⟩ ⟨j,hj⟩
All ordinary edge coverage conditions are satisfied.
Given a difference 1 ≤ d < 4 and vertex v, we convert v % 3 to a natural number using Int.emod_nonneg and Int.toNat_of_nonneg, and extract a witness offset a < 4 - d from the precomputed table htableC. The conditions that x(v % 3 - a, a) and x(v % 3 - a, a + d) are true are then transferred back to vertex v using hshift.
uses
Int.emod_nonneg,Int.toNat_of_nonneg· intro d hd hd4 v have hr : 0 ≤ v%3 := Int.emod_nonneg _ (by decide) obtain ⟨a,ha,ha₀,ha₁⟩ := htableC ⟨(v%3).toNat,by omega⟩ ⟨d,hd4⟩ hd refine ⟨a.val,ha,?_,?_⟩ · simpa only [hshift v a.val,Int.toNat_of_nonneg hr] using ha₀ · simpa only [hshift v a.val,Int.toNat_of_nonneg hr] using ha₁
The first and second halves of x(p, ·) are monotone for every p.
For any integer p, we verify 0 ≤ p % 3 < 3 with Int.emod_nonneg and omega, and instantiate the table htableS at residue (p % 3).toNat. We split into two cases: the first half is downward monotone on {0, 1} (if b < 2 and x(p, b) = true, then x(p, a) = true for a ≤ b), and the second half is upward monotone on {2, 3} (if 2 ≤ a ≤ b < 4 and x(p, a) = true, then x(p, b) = true), simplifying with Int.toNat_of_nonneg.
uses
Int.emod_nonneg,Int.toNat_of_nonneg· intro p have hr : 0 ≤ p%3 := Int.emod_nonneg _ (by decide) have hs := htableS ⟨(p%3).toNat,by omega⟩ constructor · intro a c hac hc hb simpa only [x,Int.toNat_of_nonneg hr] using hs.1 ⟨a,by omega⟩ ⟨c,by omega⟩ hac hc (by simpa only [x,Int.toNat_of_nonneg hr] using hb) · intro a c ha hac hc hb simpa only [x,Int.toNat_of_nonneg hr] using hs.2 ⟨a,by omega⟩ ⟨c,by omega⟩ ha hac (by simpa only [x,Int.toNat_of_nonneg hr] using hb)
The active count at vertex 0 is 2. automation
The sum ∑_{a=0}^3 x(-a, a) = x(0, 0) + x(-1, 1) + x(-2, 2) + x(-3, 3) evaluates directly to 1 + 0 + 0 + 1 = 2, which Lean verifies by finite evaluation using decide.
· decide
Int.sub_emod- The remainder of a difference modulo n equals the difference of the remainders modulo n: (a - b) % n = ((a % n) - (b % n)) % n.
Int.emod_emod- Taking the remainder modulo b twice is the same as taking it once: (a % b) % b = a % b.
Int.emod_nonneg- For any integer a and non-zero divisor b, the remainder a % b is non-negative.
Int.toNat_of_nonneg- For a non-negative integer a ≥ 0, casting its conversion to a natural number back to an integer recovers a.
- The verification of properties across all vertices and scales reduces via periodicity to finitely many checks over residues {0, 1, 2}, which Lean verifies by exhaustive computation using the `decide` tactic.
- The theorem constructs a barrier model showing that tight class weights, dyadic edge equations, ordinary edge coverage, and half-monotonicity together are insufficient to imply a local active count lower bound of 3; the constant optimal-count assumption of OP-205 is omitted here.
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 2000000set_option maxRecDepth 4000theorem cycle_power_dyadic_half_monotone_count_barrier : ∃ x : ℤ → ℕ → Bool, (∀ p a, x (p+3) a = x p a) ∧ (∀ p, cycle_power_dyadic_class_weight 2 (x p) = (range 4).sum (fun a => (x p a).toNat)) ∧ (∀ j < 2, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+4-2^j)).toNat) = 1) ∧ (∀ d : ℕ, 1 ≤ d → d < 4 → ∀ v : ℤ, ∃ a : ℕ, a < 4-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) ∧ (∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2 → x p b = true → x p a = true) ∧ (∀ a b : ℕ, 2 ≤ a → a ≤ b → b < 4 → x p a = true → x p b = true)) ∧ (range 4).sum (fun a => (x (-(a : ℤ)) a).toNat) = 2 := by let b : ℤ → ℕ → Bool := fun r a => decide (a=0 ∨ a=3 ∨ (r=0 ∧ a<4) ∨ (r=2 ∧ a=2)) let x : ℤ → ℕ → Bool := fun p => b (p%3) have hres (p : ℤ) : p%3=0 ∨ p%3=1 ∨ p%3=2 := by omega have hshift (p : ℤ) (a : ℕ) : x (p-(a : ℤ)) = x (p%3-(a : ℤ)) := by dsimp [x] simp only [Int.sub_emod,Int.emod_emod] have htableT : ∀ r : Fin 3, cycle_power_dyadic_class_weight 2 (b (r.val : ℤ)) = (range 4).sum (fun a => (b (r.val : ℤ) a).toNat) := by decide have htableE : ∀ r : Fin 3, ∀ j : Fin 2, (range (2^j.val)).sum (fun a => (x ((r.val : ℤ)-(a : ℤ)) a && x ((r.val : ℤ)-(a : ℤ)) (a+4-2^j.val)).toNat) = 1 := by decide have htableC : ∀ r : Fin 3, ∀ d : Fin 4, 1 ≤ d.val → ∃ a : Fin 4, a.val < 4-d.val ∧ x ((r.val : ℤ)-(a.val : ℤ)) a.val = true ∧ x ((r.val : ℤ)-(a.val : ℤ)) (a.val+d.val) = true := by decide have htableS : ∀ r : Fin 3, (∀ a c : Fin 4, a.val ≤ c.val → c.val < 2 → b (r.val : ℤ) c.val = true → b (r.val : ℤ) a.val = true) ∧ (∀ a c : Fin 4, 2 ≤ a.val → a.val ≤ c.val → b (r.val : ℤ) a.val = true → b (r.val : ℤ) c.val = true) := by decide refine ⟨x, ?_, ?_, ?_, ?_, ?_, ?_⟩ · intro p a dsimp [x] congr 1 omega · intro p have hr : 0 ≤ p%3 := Int.emod_nonneg _ (by decide) simpa only [x,Int.toNat_of_nonneg hr] using htableT ⟨(p%3).toNat, by omega⟩ · intro j hj v simp_rw [hshift v] have hr : 0 ≤ v%3 := Int.emod_nonneg _ (by decide) simpa only [Int.toNat_of_nonneg hr] using htableE ⟨(v%3).toNat,by omega⟩ ⟨j,hj⟩ · intro d hd hd4 v have hr : 0 ≤ v%3 := Int.emod_nonneg _ (by decide) obtain ⟨a,ha,ha₀,ha₁⟩ := htableC ⟨(v%3).toNat,by omega⟩ ⟨d,hd4⟩ hd refine ⟨a.val,ha,?_,?_⟩ · simpa only [hshift v a.val,Int.toNat_of_nonneg hr] using ha₀ · simpa only [hshift v a.val,Int.toNat_of_nonneg hr] using ha₁ · intro p have hr : 0 ≤ p%3 := Int.emod_nonneg _ (by decide) have hs := htableS ⟨(p%3).toNat,by omega⟩ constructor · intro a c hac hc hb simpa only [x,Int.toNat_of_nonneg hr] using hs.1 ⟨a,by omega⟩ ⟨c,by omega⟩ hac hc (by simpa only [x,Int.toNat_of_nonneg hr] using hb) · intro a c ha hac hc hb simpa only [x,Int.toNat_of_nonneg hr] using hs.2 ⟨a,by omega⟩ ⟨c,by omega⟩ ha hac (by simpa only [x,Int.toNat_of_nonneg hr] using hb) · decide