cycle_power_dyadic_alternating_paired_of_pairing
For m ≥ 2, a tight, exactly dyadically covered integer Boolean class model x : ℤ → ℕ → Bool at exponent m with x p 1 = x p (2^m - 2) for every p and the pairings x p (2i) = x p (2i+1) for 1 ≤ i, i + 1 < 2^(m-1), has the alternating-paired structure: x (p+1) 1 = !(x p 1); a class with x p 1 = false has x p j = false for 0 < j < 2^m - 1; a class with x p 1 = true has x p (2j) = x p (2j+1) for every j < 2^(m-1).
Statement
theorem cycle_power_dyadic_alternating_paired_of_pairing (m : ℕ) (hm : 2 ≤ m) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) = (Finset.range (2^m)).sum (fun a => (x p a).toNat)) (hexact : ∀ j < m, ∀ v : ℤ, (Finset.range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1) (h1 : ∀ p : ℤ, x p 1 = x p (2^m - 2)) (hpr : ∀ p : ℤ, ∀ i, 1 ≤ i → i + 1 < 2^(m-1) → x p (2*i) = x p (2*i+1)) : (∀ p : ℤ, x (p+1) 1 = !x p 1) ∧ (∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^m - 1 → x p j = false) ∧ (∀ p : ℤ, x p 1 = true → ∀ j < 2^(m-1), x p (2*j) = x p (2*j+1))
- Source
- Research thread RT-1, OP-205 (arXiv:2610.15635, Theorems 1.3-1.4: eq(C_n^k) for k+1 = 2^m, n even, (k+1) not dividing n). Reduces the hypothesis of simple_graph_equivalence_covering_number_cycle_power_two_pow_even_not_dvd_of_alternating_paired to pairing lemmas of the form of the proved m = 4 lemmas one_iff_fourteen, two_iff_three, ..., twelve_iff_thirteen.
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- cycle_power_dyadic_tight_class_inner_imp_oneFor m ≥ 2 and a tight dyadic class b : ℕ → Bool at exponent m (class weight equal to class size) with b 1 = b (2^m - 2) and b (2i) = b…
- 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 establishes the alternating-paired structure of a tight, dyadically covered class model by analyzing the dyadic covering constraints at low scales. The scale j = 0 constraint forces both boundary bits x(v, 0) and x(v, 2^m - 1) to be true for every class v. The scale j = 1 constraint links adjacent classes, forcing the sum of x(p+1, 1) and x(p, 1) to equal 1, which establishes the alternation x(p+1, 1) = !(x p 1). Finally, classes with x(p, 1) = false have no true inner bits by an established tightness lemma, while classes with x(p, 1) = true extend the interior pairing to all blocks by matching boundary values.
2^m = 2 * 2^(m - 1) and 2 ≤ 2^(m - 1).
Since m ≥ 2, we can rewrite m as (m - 1) + 1, so the exponent law `pow_succ'` gives 2^m = 2 * 2^(m - 1). Furthermore, since m - 1 ≥ 1, monotonicity of powers of 2 (`Nat.pow_le_pow_right`) yields 2 = 2^1 ≤ 2^(m - 1).
uses
pow_succ',Nat.pow_le_pow_righthave hD : 2 ^ m = 2 * 2 ^ (m - 1) := by rw [← pow_succ']; congr 1; omega have hH : 2 ≤ 2 ^ (m - 1) := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ (m - 1) := Nat.pow_le_pow_right (by norm_num) (by omega)
For every class v ∈ ℤ, both boundary bits are true: x v 0 = true and x v (2^m - 1) = true.
Instantiate the exact dyadic covering condition `hexact` at scale j = 0 for class v. The sum over range 2^0 = 1 has only the term a = 0, which reduces to (x v 0 && x v (2^m - 1)).toNat = 1. A boolean conjunction can only evaluate to 1 if both components are true, verified by checking truth values.
uses
pow_zero,Finset.range_one,Finset.sum_singleton,Nat.cast_zero,sub_zero,zero_addhave hends : ∀ v : ℤ, x v 0 = true ∧ x v (2 ^ m - 1) = true := by intro v have e := hexact 0 (by omega) v simp only [pow_zero, Finset.range_one, Finset.sum_singleton, Nat.cast_zero, sub_zero, zero_add] at e revert e cases x v 0 <;> cases x v (2 ^ m - 1) <;> decide
For every class p, the bit at index 1 alternates with parity: x (p + 1) 1 = !(x p 1).
Decompose the main conjunction into its three constituent parts and consider the first. Evaluating `hexact` at scale j = 1 for class p + 1 yields a sum of two terms: a = 0 gives x (p + 1) 0 && x (p + 1) (2^m - 2), and a = 1 gives x p 1 && x p (2^m - 1). Since the endpoints x (p + 1) 0 and x p (2^m - 1) are true by `hends`, and x (p + 1) (2^m - 2) = x (p + 1) 1 by hypothesis `h1`, this sum simplifies to (x (p + 1) 1).toNat + (x p 1).toNat = 1. Evaluating all four boolean combinations confirms that x (p + 1) 1 = !(x p 1).
uses
pow_one,Finset.sum_range_succ,Finset.sum_range_zero,zero_add,Nat.cast_zero,sub_zero,Nat.cast_one,add_sub_cancel_right,Bool.true_and,Bool.and_truerefine ⟨?_, ?_, ?_⟩ · intro p have e := hexact 1 (by omega) (p + 1) simp only [pow_one, Finset.sum_range_succ, Finset.sum_range_zero, zero_add, Nat.cast_zero, sub_zero, Nat.cast_one, add_sub_cancel_right] at e rw [show 1 + 2 ^ m - 2 = 2 ^ m - 1 by omega] at e simp only [(hends (p + 1)).1, (hends p).2, ← h1 (p + 1), Bool.true_and, Bool.and_true] at e revert e cases x (p + 1) 1 <;> cases x p 1 <;> decide
If x p 1 = false, then all inner bits vanish: x p j = false for every 0 < j < 2^m - 1.
Suppose for contradiction that some inner bit x p j is true. By lemma `cycle_power_dyadic_tight_class_inner_imp_one`, in any class satisfying tightness (`htight`), symmetry (`h1`), and internal pairing (`hpr`), a single true inner bit forces x p 1 = true. This contradicts the assumption x p 1 = false.
uses
cycle_power_dyadic_tight_class_inner_imp_one· intro p hp j hj0 hj1 by_contra hne have hb : x p j = true := by simpa using hne have := cycle_power_dyadic_tight_class_inner_imp_one m hm (x p) (htight p) (h1 p) (hpr p) j hj0 hj1 hb rw [hp] at this; exact absurd this (by decide)
If x p 1 = true, then pairing extends to all blocks: x p (2 * j) = x p (2 * j + 1) for every j < 2^(m - 1).
We split on j using `Nat.eq_zero_or_pos`. If j = 0, the pair is indices 0 and 1; x p 0 = true by `hends` and x p 1 = true by assumption, so they are equal. If j > 0, we split into j + 1 < 2^(m - 1) and j + 1 = 2^(m - 1). The strictly interior case is covered directly by the pairing hypothesis `hpr`. The boundary case j + 1 = 2^(m - 1) corresponds to indices 2^m - 2 and 2^m - 1; here x p (2^m - 2) = x p 1 = true by `h1` and x p (2^m - 1) = true by `hends`, so both sides are true.
uses
Nat.eq_zero_or_pos,Nat.mul_zero,zero_add· intro p hp j hj rcases Nat.eq_zero_or_pos j with h0 | h0 · subst h0; simp only [Nat.mul_zero, zero_add]; rw [hp, (hends p).1] rcases (show j + 1 < 2 ^ (m - 1) ∨ j + 1 = 2 ^ (m - 1) by omega) with hlt | heq · exact hpr p j h0 hlt · rw [show 2 * j = 2 ^ m - 2 by omega, show 2 ^ m - 2 + 1 = 2 ^ m - 1 by omega, ← h1 p, hp, (hends p).2]
pow_succ'- For any element a of a monoid, a^(n+1) = a * a^n.
Nat.pow_le_pow_right- If n > 0 and i ≤ j, then n^i ≤ n^j.
pow_zero- Any element raised to the zeroth power is 1.
Finset.range_one- The range of length 1 is the singleton set {0}.
Finset.sum_singleton- The sum of a function over a singleton set {a} is the value f(a).
Nat.cast_zero- The natural number 0 casts to 0 in any additive monoid with one.
sub_zero- Subtracting 0 leaves an element unchanged.
zero_add- Adding 0 on the left leaves an element unchanged.
pow_one- Any element raised to the first power is itself.
Finset.sum_range_succ- Summing over the range 0, ..., n equals the sum over 0, ..., n-1 plus the term at n.
Finset.sum_range_zero- The sum over an empty range of natural numbers is 0.
Nat.cast_one- The natural number 1 casts to 1 in any additive monoid with one.
add_sub_cancel_right- Adding b and then subtracting b returns the original element.
Bool.true_and- The conjunction true && b evaluates to b.
Bool.and_true- The conjunction b && true evaluates to b.
cycle_power_dyadic_tight_class_inner_imp_one- In a tight dyadic class with pairing and outer symmetry, if any inner bit b(j) is true for 0 < j < 2^m - 1, then b(1) must be true.
Nat.eq_zero_or_pos- Every natural number is either zero or strictly positive.
Nat.mul_zero- Multiplying any natural number by zero yields zero.
- Index boundary identities such as 1 + 2^m - 2 = 2^m - 1 and 2j = 2^m - 2 when j + 1 = 2^(m-1) are dispatched by Presburger arithmetic (`omega`), and small boolean truth-table contradictions are closed by exhaustive computation (`decide`).
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.
theorem cycle_power_dyadic_alternating_paired_of_pairing (m : ℕ) (hm : 2 ≤ m) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) = (Finset.range (2^m)).sum (fun a => (x p a).toNat)) (hexact : ∀ j < m, ∀ v : ℤ, (Finset.range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1) (h1 : ∀ p : ℤ, x p 1 = x p (2^m - 2)) (hpr : ∀ p : ℤ, ∀ i, 1 ≤ i → i + 1 < 2^(m-1) → x p (2*i) = x p (2*i+1)) : (∀ p : ℤ, x (p+1) 1 = !x p 1) ∧ (∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^m - 1 → x p j = false) ∧ (∀ p : ℤ, x p 1 = true → ∀ j < 2^(m-1), x p (2*j) = x p (2*j+1)) := by have hD : 2 ^ m = 2 * 2 ^ (m - 1) := by rw [← pow_succ']; congr 1; omega have hH : 2 ≤ 2 ^ (m - 1) := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ (m - 1) := Nat.pow_le_pow_right (by norm_num) (by omega) have hends : ∀ v : ℤ, x v 0 = true ∧ x v (2 ^ m - 1) = true := by intro v have e := hexact 0 (by omega) v simp only [pow_zero, Finset.range_one, Finset.sum_singleton, Nat.cast_zero, sub_zero, zero_add] at e revert e cases x v 0 <;> cases x v (2 ^ m - 1) <;> decide refine ⟨?_, ?_, ?_⟩ · intro p have e := hexact 1 (by omega) (p + 1) simp only [pow_one, Finset.sum_range_succ, Finset.sum_range_zero, zero_add, Nat.cast_zero, sub_zero, Nat.cast_one, add_sub_cancel_right] at e rw [show 1 + 2 ^ m - 2 = 2 ^ m - 1 by omega] at e simp only [(hends (p + 1)).1, (hends p).2, ← h1 (p + 1), Bool.true_and, Bool.and_true] at e revert e cases x (p + 1) 1 <;> cases x p 1 <;> decide · intro p hp j hj0 hj1 by_contra hne have hb : x p j = true := by simpa using hne have := cycle_power_dyadic_tight_class_inner_imp_one m hm (x p) (htight p) (h1 p) (hpr p) j hj0 hj1 hb rw [hp] at this; exact absurd this (by decide) · intro p hp j hj rcases Nat.eq_zero_or_pos j with h0 | h0 · subst h0; simp only [Nat.mul_zero, zero_add]; rw [hp, (hends p).1] rcases (show j + 1 < 2 ^ (m - 1) ∨ j + 1 = 2 ^ (m - 1) by omega) with hlt | heq · exact hpr p j h0 hlt · rw [show 2 * j = 2 ^ m - 2 by omega, show 2 ^ m - 2 + 1 = 2 ^ m - 1 by omega, ← h1 p, hp, (hends p).2]