cycle_power_dyadic_periodic_model_tight_of_counts
For a positive exponent m, nonzero natural period n, and periodic Boolean profiles indexed by the integers, exact dyadic edge-owner sums of one and exactly m+1 active rooted profiles at every integer force each profile's dyadic class weight to equal its selected-offset count. No ordinary-edge coverage or shape hypothesis is assumed.
Statement
theorem cycle_power_dyadic_periodic_model_tight_of_counts (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (x : ℤ → ℕ → Bool) (hperiod : ∀ p a, x (p+(n : ℤ)) a = x p a) (hcount : ∀ v : ℤ, (range (2^m)).sum (fun a => (x (v-(a : ℤ)) a).toNat) = m+1) (hexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1) : ∀ p : ℤ, cycle_power_dyadic_class_weight m (x p) = (range (2^m)).sum (fun a => (x p a).toNat)
- Source
- Uniform actual-cover extraction for OP-205 / RT-1 following arXiv:2610.15635. The anchored-arc lemma is geometric bookkeeping. The saturation helpers double-count exact dyadic owners and active classes over a period; they do not classify class shapes or settle the graph covering value. No research advance is claimed.
- Verified
- 28 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_zmod_model_tight_of_countsFor a positive exponent m, nonzero natural period n, and Boolean profiles indexed by ZMod n, exact dyadic edge-owner sums of one and…
- Used by 1
- simple_graph_cycle_power_dyadic_class_model_tight_weightsEvery rooted dyadic class of an optimal cover is tight: the dyadic class weight of the arc equals its cardinality.
The proof, explained
The proof transfers the periodic problem on ℤ to a finite model on the cyclic group ℤ/nℤ. Because the Boolean profile configuration x is n-periodic, defining b on ℤ/nℤ via canonical integer representatives preserves both the rooted profile counts and the exact dyadic edge-owner sums. The theorem cycle_power_dyadic_zmod_model_tight_of_counts on ℤ/nℤ then applies directly, and rewriting the result back to ℤ yields the desired equality for every integer.
Define a profile configuration b on the cyclic group ℤ/nℤ by evaluating x at the canonical representative of each residue class.
Classical reasoning is enabled, and b(p, a) is defined for p ∈ ℤ/nℤ and a ∈ ℕ as x(p.val, a), where p.val ∈ {0, ..., n - 1} is the canonical integer representative of p.
classical let b : ZMod n → ℕ → Bool := fun p a => x (p.val : ℤ) a
The quotient profile agrees with the original configuration for every integer: b(v mod n, a) = x(v, a) for all v ∈ ℤ and a ∈ ℕ.
By ZMod.intCast_eq_iff, an integer v differs from the representative of its residue class (v mod n).val by an integer multiple z * n. Since x(·, a) is n-periodic by hypothesis, shifting by z * n leaves x invariant, proving that b(v mod n, a) and x(v, a) are equal.
uses
ZMod.intCast_eq_iff,congrArghave hval (v : ℤ) (a : ℕ) : b (v : ZMod n) a = x v a := by obtain ⟨z, hz⟩ := (ZMod.intCast_eq_iff n v (v : ZMod n)).mp rfl have hp : Function.Periodic (fun p : ℤ => x p a) (n : ℤ) := fun p => hperiod p a have hh := hp.int_mul z (((v : ZMod n).val : ℤ)) have he : ((v : ZMod n).val : ℤ)+z*(n : ℤ)=v := by calc _ = ((v : ZMod n).val : ℤ)+(n : ℤ)*z := by ring _ = v := hz.symm exact hh.symm.trans (congrArg (fun w : ℤ => x w a) he)
Evaluating b at a shifted residue class v - a coincides with evaluating x at the shifted integer v.val - a: b(v - a, i) = x(v.val - a, i).
Subtracting a in ℤ/nℤ matches casting the integer difference v.val - a, as verified by Int.cast_sub, Int.cast_natCast, and ZMod.natCast_zmod_val. Applying the evaluation identity hval to this integer difference yields the shifted identity.
uses
Int.cast_sub,Int.cast_natCast,ZMod.natCast_zmod_valhave hshift (v : ZMod n) (a i : ℕ) : b (v-(a : ZMod n)) i = x ((v.val : ℤ)-(a : ℤ)) i := by simpa only [Int.cast_sub, Int.cast_natCast, ZMod.natCast_zmod_val] using hval ((v.val : ℤ)-(a : ℤ)) i
The profile configuration b satisfies the rooted profile count condition of m + 1 at every vertex in ℤ/nℤ.
Rewriting each b(v - a, a) as x(v.val - a, a) using the shift lemma translates the sum over offsets a < 2ᵐ to the given integer count hypothesis hcount evaluated at v.val ∈ ℤ.
have hbc (v : ZMod n) : (range (2^m)).sum (fun a => (b (v-(a : ZMod n)) a).toNat) = m+1 := by simp_rw [hshift] exact hcount (v.val : ℤ)
The profile configuration b satisfies the exact dyadic edge-owner condition of 1 for every scale j < m at every vertex in ℤ/nℤ.
Rewriting the profile values via the shift lemma transforms the sum over a < 2ʲ into the integer exact dyadic edge-owner hypothesis hexact evaluated at v.val ∈ ℤ.
have hbe (j : ℕ) (hj : j < m) (v : ZMod n) : (range (2^j)).sum (fun a => (b (v-(a : ZMod n)) a && b (v-(a : ZMod n)) (a+2^m-2^j)).toNat) = 1 := by simp_rw [hshift] exact hexact j hj (v.val : ℤ)
The dyadic class weight of b(p) equals its selected-offset count for every p ∈ ℤ/nℤ.
Having verified both the profile count and dyadic edge-owner conditions on ℤ/nℤ, we apply the finite cyclic group theorem cycle_power_dyadic_zmod_model_tight_of_counts to deduce the equality for b.
uses
cycle_power_dyadic_zmod_model_tight_of_countshave ht := cycle_power_dyadic_zmod_model_tight_of_counts m n hm b hbc hbeFor every integer p ∈ ℤ, the dyadic class weight of x(p) equals its selected-offset count ∑ a < 2ᵐ, x(p, a).
For any integer p, we specialize the finite result to its residue class p mod n. Rewriting each occurrence of b(p mod n, ·) to x(p, ·) via hval and unfolding cycle_power_dyadic_class_weight completes the proof.
uses
cycle_power_dyadic_class_weightintro p simpa only [cycle_power_dyadic_class_weight, hval] using ht (p : ZMod n)
ZMod.intCast_eq_iff- An integer n projects to a residue class z in ℤ/pℤ if and only if n = z.val + p * k for some integer k.
congrArg- Equality is preserved under function application: if a₁ = a₂, then f(a₁) = f(a₂).
Int.cast_sub- The integer cast into an additive group with one preserves subtraction: ↑(m - n) = ↑m - ↑n.
Int.cast_natCast- Casting a natural number into the integers and then into a ring coincides with casting the natural number directly: ↑↑n = ↑n.
ZMod.natCast_zmod_val- Casting the canonical representative a.val of a residue class a ∈ ℤ/nℤ back to ℤ/nℤ yields a.
cycle_power_dyadic_zmod_model_tight_of_counts- For any Boolean profile configuration on ℤ/nℤ satisfying the rooted profile count of m + 1 and exact dyadic edge-owner sums of 1, the dyadic class weight of each profile equals its selected-offset count.
cycle_power_dyadic_class_weight- The dyadic class weight of an offset profile b : ℕ → Bool at parameter m, defined as twice the indicator of joint activity at the extreme offsets 0 and 2ᵐ - 1 plus the sum over scales 0 < j < m of joint activity at dyadic offsets.
- On paper, one would simply say that any n-periodic configuration on ℤ factors through the quotient ℤ/nℤ. In Lean, the profile b is defined explicitly using the canonical representative p.val, requiring auxiliary lemmas (hval and hshift) to prove that modular subtraction and valuation match the corresponding integer operations.
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 cycle_power_dyadic_periodic_model_tight_of_counts (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (x : ℤ → ℕ → Bool) (hperiod : ∀ p a, x (p+(n : ℤ)) a = x p a) (hcount : ∀ v : ℤ, (range (2^m)).sum (fun a => (x (v-(a : ℤ)) a).toNat) = m+1) (hexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1) : ∀ p : ℤ, cycle_power_dyadic_class_weight m (x p) = (range (2^m)).sum (fun a => (x p a).toNat) := by classical let b : ZMod n → ℕ → Bool := fun p a => x (p.val : ℤ) a have hval (v : ℤ) (a : ℕ) : b (v : ZMod n) a = x v a := by obtain ⟨z, hz⟩ := (ZMod.intCast_eq_iff n v (v : ZMod n)).mp rfl have hp : Function.Periodic (fun p : ℤ => x p a) (n : ℤ) := fun p => hperiod p a have hh := hp.int_mul z (((v : ZMod n).val : ℤ)) have he : ((v : ZMod n).val : ℤ)+z*(n : ℤ)=v := by calc _ = ((v : ZMod n).val : ℤ)+(n : ℤ)*z := by ring _ = v := hz.symm exact hh.symm.trans (congrArg (fun w : ℤ => x w a) he) have hshift (v : ZMod n) (a i : ℕ) : b (v-(a : ZMod n)) i = x ((v.val : ℤ)-(a : ℤ)) i := by simpa only [Int.cast_sub, Int.cast_natCast, ZMod.natCast_zmod_val] using hval ((v.val : ℤ)-(a : ℤ)) i have hbc (v : ZMod n) : (range (2^m)).sum (fun a => (b (v-(a : ZMod n)) a).toNat) = m+1 := by simp_rw [hshift] exact hcount (v.val : ℤ) have hbe (j : ℕ) (hj : j < m) (v : ZMod n) : (range (2^j)).sum (fun a => (b (v-(a : ZMod n)) a && b (v-(a : ZMod n)) (a+2^m-2^j)).toNat) = 1 := by simp_rw [hshift] exact hexact j hj (v.val : ℤ) have ht := cycle_power_dyadic_zmod_model_tight_of_counts m n hm b hbc hbe intro p simpa only [cycle_power_dyadic_class_weight, hval] using ht (p : ZMod n)