AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_half_monotone_count_barrier

theoremverified

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.

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

    lines 20–26

    uses Int.sub_emod, Int.emod_emod

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

    lines 27–41

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

    line 42

      refine ⟨x, ?_, ?_, ?_, ?_, ?_, ?_⟩
  4. 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).

    lines 43–46

      · intro p a
        dsimp [x]
        congr 1
        omega
  5. 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.

    lines 47–50

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

    lines 51–55

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

    lines 56–61

    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₁
  8. 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.

    lines 62–71

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

    line 72

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

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