cycle_power_dyadic_fold_periodicity_distance_one_counterexample
There is an exponent-three tight zero-phase dyadic profile with exact lower-rank owners, the defective top-owner and active-count equations, periodic corrected lower count, and coverage at distance one, but with a defect at zero. The profile does not cover distance two at zero, so it does not satisfy full coverage.
Statement
theorem cycle_power_dyadic_fold_periodicity_distance_one_counterexample : ∃ (y : ℤ → ℕ → Bool) (e : ℤ → Bool), (∀ p, cycle_power_dyadic_class_weight 3 (y p) = (Finset.range 8).sum (fun a => (y p a).toNat)) ∧ (∀ j < 2, ∀ v : ℤ, (Finset.range (2^j)).sum (fun a => (y (v-(a:ℤ)) a && y (v-(a:ℤ)) (a+8-2^j)).toNat) = 1) ∧ (∀ v : ℤ, (Finset.range 4).sum (fun a => (y (v-(a:ℤ)) a && y (v-(a:ℤ)) (a+4)).toNat) + (e v).toNat = 1) ∧ (∀ v : ℤ, (Finset.range 8).sum (fun a => (y (v-(a:ℤ)) a).toNat) + (e v).toNat = 4) ∧ (∀ v : ℤ, (Finset.range 4).sum (fun a => (y (v-(a:ℤ)) a).toNat) + (e v).toNat = (Finset.range 4).sum (fun a => (y (v+4-(a:ℤ)) a).toNat) + (e (v+4)).toNat) ∧ (∀ v : ℤ, ∃ a : ℕ, a < 7 ∧ y (v-(a:ℤ)) a = true ∧ y (v-(a:ℤ)) (a+1) = true) ∧ e 0 = true ∧ ¬ (∃ a : ℕ, a < 6 ∧ y (-(a:ℤ)) a = true ∧ y (-(a:ℤ)) (a+2) = true)
- Source
- RT-1, defective-half fold-count reduction
- Verified
- 11 Nov 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 theorem is proved by explicitly exhibiting a candidate dyadic profile y (`rt1_short_x`) and defect indicator e (`rt1_short_e`) of exponent 3. The profile y is defined modulo 4 with a single exceptional value at -3, while e indicates whether v = 0. The required structural properties—tightness, active count, lower-rank owners, defective top-owner, fold periodicity, and distance-one coverage—are established by splitting into the bounded range [-12, 12] and an asymptotic regime where terms depend only on v % 4, both verified by exhaustive boolean computation. Finally, evaluating at the origin confirms that e 0 = true while no distance-two pair is active, demonstrating the failure of full coverage.
For every integer p, rt1_short_x p is tight at exponent 3, meaning its dyadic class weight equals the sum of its eight bits.
We case split on whether p = -3. If p = -3, both sides evaluate to 4 by direct computation (`decide`). If p ≠ -3, the value of rt1_short_x p depends only on r = p % 4, which satisfies 0 ≤ r < 4 by `Int.emod_nonneg` and `Int.emod_lt_of_pos`. Rewriting rt1_short_x with this functional form, an exhaustive check on r ∈ {0, 1, 2, 3} (`interval_cases r`) confirms the identity in all four cases by computation (`decide`).
uses
Int.emod_nonneg,Int.emod_lt_of_posby_cases h : p = -3 · subst p; decide · have h0 : 0 ≤ p % 4 := Int.emod_nonneg _ (by norm_num) have h4 : p % 4 < 4 := Int.emod_lt_of_pos _ (by norm_num) generalize hp : p % 4 = r at * have hx : rt1_short_x p = (fun a => (if r = 0 then 139 else if r = 1 then 155 else if r = 2 then 147 else 131 : ℕ).testBit a) := by funext a; simp [rt1_short_x, h, hp] rw [hx] interval_cases r <;> decide
The active-count equation holds for all integers v in the bounded range [-12, 12].
When -12 ≤ v ≤ 12, we evaluate the active-count sum plus the defect indicator rt1_short_e v directly for each of the 25 integers in the range (`interval_cases v <;> decide`), confirming that the sum equals 4 in every case.
by_cases hs : -12 ≤ v ∧ v ≤ 12 · obtain ⟨hlo,hhi⟩ := hs interval_cases v <;> decide
The active-count equation holds for all integers v outside [-12, 12], completing the proof of rt1_short_count.
When v < -12 or 12 < v (established by `omega`), v ≠ 0 so rt1_short_e v = false (evaluating to 0 by `decide_false`), and v - a ≠ -3 for all a < 8. Thus rt1_short_x (v - a) depends only on (r - a) % 4 where r = v % 4 ∈ {0, 1, 2, 3} by `Int.emod_nonneg`, `Int.emod_lt_of_pos`, and `Int.sub_emod`. Expanding the 8-term sum using `Finset.sum_range_succ`, `Finset.sum_range_zero`, and `zero_add`, the sum evaluates to 4 for each of the four possible values of r (`interval_cases r <;> decide`).
uses
Int.emod_nonneg,Int.emod_lt_of_pos,Int.sub_emod,Finset.sum_range_succ,Finset.sum_range_zero,zero_add,decide_false· have hv : v < -12 ∨ 12 < v := by omega rcases hv with hv | hv all_goals have h0 : 0 ≤ v % 4 := Int.emod_nonneg _ (by norm_num) have h4 : v % 4 < 4 := Int.emod_lt_of_pos _ (by norm_num) generalize hp : v % 4 = r at * have hx (a : ℕ) (ha : a < 8) : rt1_short_x (v-(a:ℤ)) = fun b => (if (r-(a:ℤ)) % 4 = 0 then 139 else if (r-(a:ℤ)) % 4 = 1 then 155 else if (r-(a:ℤ)) % 4 = 2 then 147 else 131 : ℕ).testBit b := by funext b have hn : v-(a:ℤ) ≠ -3 := by omega simp [rt1_short_x, hn, Int.sub_emod, hp] have hz : v ≠ 0 := by omega simp only [Finset.sum_range_succ, Finset.sum_range_zero, zero_add, hx 0 (by omega), hx 1 (by omega), hx 2 (by omega), hx 3 (by omega), hx 4 (by omega), hx 5 (by omega), hx 6 (by omega), hx 7 (by omega), rt1_short_e, hz, decide_false] interval_cases r <;> decide
The owner pairing equations at ranks 0, 1, and 2 and the fold-periodicity equation hold for all v in [-12, 12].
When -12 ≤ v ≤ 12, each of the four conjuncts is evaluated directly for every integer in this interval (`interval_cases v <;> decide`), verifying all four equations simultaneously.
by_cases hs : -12 ≤ v ∧ v ≤ 12 · obtain ⟨hlo,hhi⟩ := hs interval_cases v <;> decide
The owner pairing equations and fold-periodicity equation hold for all integers v outside [-12, 12], completing the proof of rt1_short_pairs_and_balance.
When v < -12 or 12 < v, neither v nor v + 4 can be 0, so the defect terms vanish (`decide_false`). Moreover, for any offset d ∈ [-7, 4], v + d ≠ -3, so rt1_short_x (v + d) depends only on (r + d) % 4 where r = v % 4 by `Int.add_emod`. After rewriting the terms into shifts v + d and expanding the sums with `Finset.sum_range_succ`, `Finset.sum_range_zero`, `zero_add`, and `Nat.cast_ofNat`, testing each remainder r ∈ {0, 1, 2, 3} (`interval_cases r <;> decide`) confirms all four equations.
uses
Int.emod_nonneg,Int.emod_lt_of_pos,Int.add_emod,Finset.sum_range_succ,Finset.sum_range_zero,zero_add,decide_false,Nat.cast_ofNat· have hv : v < -12 ∨ 12 < v := by omega rcases hv with hv | hv all_goals have h0 : 0 ≤ v % 4 := Int.emod_nonneg _ (by norm_num) have h4 : v % 4 < 4 := Int.emod_lt_of_pos _ (by norm_num) generalize hp : v % 4 = r at * have hx (d : ℤ) (hd : -7 ≤ d ∧ d ≤ 4) : rt1_short_x (v+d) = fun b => (if (r+d) % 4 = 0 then 139 else if (r+d) % 4 = 1 then 155 else if (r+d) % 4 = 2 then 147 else 131 : ℕ).testBit b := by funext b have hn : v+d ≠ -3 := by omega simp [rt1_short_x, hn, Int.add_emod, hp] have hz : v ≠ 0 := by omega have hz4 : v+4 ≠ 0 := by omega simp only [Finset.sum_range_succ, Finset.sum_range_zero, zero_add, rt1_short_e, hz, hz4, decide_false] norm_num only [Nat.cast_ofNat] at * simp only [show v - (0:ℤ) = v+0 by omega, show v - (1:ℤ) = v+(-1) by omega, show v - (2:ℤ) = v+(-2) by omega, show v - (3:ℤ) = v+(-3) by omega, show v+4-(0:ℤ) = v+4 by omega, show v+4-(1:ℤ) = v+3 by omega, show v+4-(2:ℤ) = v+2 by omega, show v+4-(3:ℤ) = v+1 by omega, hx 0 (by omega), hx (-1) (by omega), hx (-2) (by omega), hx (-3) (by omega), hx 1 (by omega), hx 2 (by omega), hx 3 (by omega), hx 4 (by omega)] interval_cases r <;> decide
For every integer v, rt1_short_x satisfies coverage at distance 1.
We provide the witness a = 0 (which is < 7 by `decide`). Then v - a = v, and the condition requires both bit 0 and bit 1 of rt1_short_x v to be true. In all branches defining rt1_short_x (the constants 147, 139, 155, and 131), the 0th and 1st bits are both 1. Simplifying the zero arithmetic (`Nat.cast_zero`, `sub_zero`, `Nat.zero_add`) and splitting cases on the conditions (`split_ifs <;> decide`) verifies this property for all v.
uses
Nat.cast_zero,sub_zero,Nat.zero_addrefine ⟨0, by decide, ?_, ?_⟩ <;> simp only [Nat.cast_zero, sub_zero, Nat.zero_add, rt1_short_x] <;> split_ifs <;> decide
The profile rt1_short_x and defect rt1_short_e satisfy tightness, lower-rank owners, defective top-owner, active count, fold periodicity, and distance-one coverage.
We instantiate the existential witnesses with rt1_short_x and rt1_short_e using `refine`. Tightness is supplied by `rt1_short_tight`, active count by `rt1_short_count`, and distance-one coverage by `rt1_short_cover_one`. For the lower-rank owners (j < 2, meaning j = 0 or j = 1), `interval_cases j` matches the first and second conjuncts of `rt1_short_pairs_and_balance v`. The defective top-owner equation and fold periodicity correspond to the third and fourth conjuncts of `rt1_short_pairs_and_balance v`, respectively.
uses
rt1_short_tight,rt1_short_count,rt1_short_cover_one,rt1_short_pairs_and_balancerefine ⟨rt1_short_x, rt1_short_e, rt1_short_tight, ?_, ?_, rt1_short_count, ?_, rt1_short_cover_one, ?_, ?_⟩ · intro j hj v have h := rt1_short_pairs_and_balance v interval_cases j <;> norm_num at * · exact h.1 · exact h.2.1 · intro v exact (rt1_short_pairs_and_balance v).2.2.1 · intro v exact (rt1_short_pairs_and_balance v).2.2.2
The defect is active at zero and the profile fails distance-two coverage at zero, completing the counterexample.
The defect rt1_short_e 0 evaluates to true by definition since 0 = 0. The non-existence of distance-two coverage at zero asserts that for all a < 6, it is not the case that both bit a and bit a + 2 of rt1_short_x (-a) are true; this finite search over a ∈ {0, ..., 5} is checked and verified to fail by boolean evaluation (`decide`).
· decide · decide
Int.emod_nonneg- For an integer a and non-zero integer b, the remainder a % b is non-negative.
Int.emod_lt_of_pos- For an integer a and positive integer b, the remainder a % b is strictly less than b.
Int.sub_emod- The remainder of a difference modulo n equals the difference of the remainders modulo n.
Int.add_emod- The remainder of a sum modulo n equals the sum of the remainders modulo n.
Finset.sum_range_succ- A sum over range (n + 1) equals the sum over range n plus the nth term.
Finset.sum_range_zero- The sum over an empty range is zero.
zero_add- Zero added to any element on the left leaves the element unchanged.
decide_false- Deciding a false proposition yields the boolean value false.
Nat.cast_ofNat- The coercion of a natural numeral into another numerical type equals that numeral.
Nat.cast_zero- The natural number zero coerced to a numerical type is zero.
sub_zero- Subtracting zero from an element leaves it unchanged.
Nat.zero_add- Adding zero to a natural number on the left leaves it unchanged.
rt1_short_tight- For every integer p, the dyadic class weight of rt1_short_x p at exponent 3 equals the sum of its eight bits.
rt1_short_count- For every integer v, the sum of the eight diagonal bits of rt1_short_x plus the defect term rt1_short_e v equals 4.
rt1_short_pairs_and_balance- For every integer v, the lower-rank owner sums at ranks 0 and 1 equal 1, the defective top-owner sum at rank 2 plus rt1_short_e v equals 1, and the corrected lower count is 4-periodic.
rt1_short_cover_one- For every integer v, there exists an index a < 7 such that both bit a and bit a + 1 of rt1_short_x (v - a) are true.
- Exhaustive checks over the bounded integer range [-12, 12] and over the residue classes modulo 4 are discharged by boolean reflection (`decide`), while integer bounds outside this range are discharged by Presburger arithmetic (`omega`).
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.
namespace RT1In723open Finsetdef rt1_short_x (p : ℤ) (a : ℕ) : Bool := (if p = -3 then 147 else if p % 4 = 0 then 139 else if p % 4 = 1 then 155 else if p % 4 = 2 then 147 else 131 : ℕ).testBit adef rt1_short_e (v : ℤ) : Bool := decide (v = 0)theorem rt1_short_tight (p : ℤ) : cycle_power_dyadic_class_weight 3 (rt1_short_x p) = (range 8).sum (fun a => (rt1_short_x p a).toNat) := by by_cases h : p = -3 · subst p; decide · have h0 : 0 ≤ p % 4 := Int.emod_nonneg _ (by norm_num) have h4 : p % 4 < 4 := Int.emod_lt_of_pos _ (by norm_num) generalize hp : p % 4 = r at * have hx : rt1_short_x p = (fun a => (if r = 0 then 139 else if r = 1 then 155 else if r = 2 then 147 else 131 : ℕ).testBit a) := by funext a; simp [rt1_short_x, h, hp] rw [hx] interval_cases r <;> decidetheorem rt1_short_count (v : ℤ) : (range 8).sum (fun a => (rt1_short_x (v-(a:ℤ)) a).toNat) + (rt1_short_e v).toNat = 4 := by by_cases hs : -12 ≤ v ∧ v ≤ 12 · obtain ⟨hlo,hhi⟩ := hs interval_cases v <;> decide · have hv : v < -12 ∨ 12 < v := by omega rcases hv with hv | hv all_goals have h0 : 0 ≤ v % 4 := Int.emod_nonneg _ (by norm_num) have h4 : v % 4 < 4 := Int.emod_lt_of_pos _ (by norm_num) generalize hp : v % 4 = r at * have hx (a : ℕ) (ha : a < 8) : rt1_short_x (v-(a:ℤ)) = fun b => (if (r-(a:ℤ)) % 4 = 0 then 139 else if (r-(a:ℤ)) % 4 = 1 then 155 else if (r-(a:ℤ)) % 4 = 2 then 147 else 131 : ℕ).testBit b := by funext b have hn : v-(a:ℤ) ≠ -3 := by omega simp [rt1_short_x, hn, Int.sub_emod, hp] have hz : v ≠ 0 := by omega simp only [Finset.sum_range_succ, Finset.sum_range_zero, zero_add, hx 0 (by omega), hx 1 (by omega), hx 2 (by omega), hx 3 (by omega), hx 4 (by omega), hx 5 (by omega), hx 6 (by omega), hx 7 (by omega), rt1_short_e, hz, decide_false] interval_cases r <;> decidetheorem rt1_short_pairs_and_balance (v : ℤ) : (range 1).sum (fun a => (rt1_short_x (v-(a:ℤ)) a && rt1_short_x (v-(a:ℤ)) (a+7)).toNat) = 1 ∧ (range 2).sum (fun a => (rt1_short_x (v-(a:ℤ)) a && rt1_short_x (v-(a:ℤ)) (a+6)).toNat) = 1 ∧ (range 4).sum (fun a => (rt1_short_x (v-(a:ℤ)) a && rt1_short_x (v-(a:ℤ)) (a+4)).toNat) + (rt1_short_e v).toNat = 1 ∧ (range 4).sum (fun a => (rt1_short_x (v-(a:ℤ)) a).toNat) + (rt1_short_e v).toNat = (range 4).sum (fun a => (rt1_short_x (v+4-(a:ℤ)) a).toNat) + (rt1_short_e (v+4)).toNat := by by_cases hs : -12 ≤ v ∧ v ≤ 12 · obtain ⟨hlo,hhi⟩ := hs interval_cases v <;> decide · have hv : v < -12 ∨ 12 < v := by omega rcases hv with hv | hv all_goals have h0 : 0 ≤ v % 4 := Int.emod_nonneg _ (by norm_num) have h4 : v % 4 < 4 := Int.emod_lt_of_pos _ (by norm_num) generalize hp : v % 4 = r at * have hx (d : ℤ) (hd : -7 ≤ d ∧ d ≤ 4) : rt1_short_x (v+d) = fun b => (if (r+d) % 4 = 0 then 139 else if (r+d) % 4 = 1 then 155 else if (r+d) % 4 = 2 then 147 else 131 : ℕ).testBit b := by funext b have hn : v+d ≠ -3 := by omega simp [rt1_short_x, hn, Int.add_emod, hp] have hz : v ≠ 0 := by omega have hz4 : v+4 ≠ 0 := by omega simp only [Finset.sum_range_succ, Finset.sum_range_zero, zero_add, rt1_short_e, hz, hz4, decide_false] norm_num only [Nat.cast_ofNat] at * simp only [show v - (0:ℤ) = v+0 by omega, show v - (1:ℤ) = v+(-1) by omega, show v - (2:ℤ) = v+(-2) by omega, show v - (3:ℤ) = v+(-3) by omega, show v+4-(0:ℤ) = v+4 by omega, show v+4-(1:ℤ) = v+3 by omega, show v+4-(2:ℤ) = v+2 by omega, show v+4-(3:ℤ) = v+1 by omega, hx 0 (by omega), hx (-1) (by omega), hx (-2) (by omega), hx (-3) (by omega), hx 1 (by omega), hx 2 (by omega), hx 3 (by omega), hx 4 (by omega)] interval_cases r <;> decidetheorem rt1_short_cover_one (v : ℤ) : ∃ a : ℕ, a < 7 ∧ rt1_short_x (v-(a:ℤ)) a = true ∧ rt1_short_x (v-(a:ℤ)) (a+1) = true := by refine ⟨0, by decide, ?_, ?_⟩ <;> simp only [Nat.cast_zero, sub_zero, Nat.zero_add, rt1_short_x] <;> split_ifs <;> decideend RT1In723open RT1In723theorem cycle_power_dyadic_fold_periodicity_distance_one_counterexample : ∃ (y : ℤ → ℕ → Bool) (e : ℤ → Bool), (∀ p, cycle_power_dyadic_class_weight 3 (y p) = (Finset.range 8).sum (fun a => (y p a).toNat)) ∧ (∀ j < 2, ∀ v : ℤ, (Finset.range (2^j)).sum (fun a => (y (v-(a:ℤ)) a && y (v-(a:ℤ)) (a+8-2^j)).toNat) = 1) ∧ (∀ v : ℤ, (Finset.range 4).sum (fun a => (y (v-(a:ℤ)) a && y (v-(a:ℤ)) (a+4)).toNat) + (e v).toNat = 1) ∧ (∀ v : ℤ, (Finset.range 8).sum (fun a => (y (v-(a:ℤ)) a).toNat) + (e v).toNat = 4) ∧ (∀ v : ℤ, (Finset.range 4).sum (fun a => (y (v-(a:ℤ)) a).toNat) + (e v).toNat = (Finset.range 4).sum (fun a => (y (v+4-(a:ℤ)) a).toNat) + (e (v+4)).toNat) ∧ (∀ v : ℤ, ∃ a : ℕ, a < 7 ∧ y (v-(a:ℤ)) a = true ∧ y (v-(a:ℤ)) (a+1) = true) ∧ e 0 = true ∧ ¬ (∃ a : ℕ, a < 6 ∧ y (-(a:ℤ)) a = true ∧ y (-(a:ℤ)) (a+2) = true) := by refine ⟨rt1_short_x, rt1_short_e, rt1_short_tight, ?_, ?_, rt1_short_count, ?_, rt1_short_cover_one, ?_, ?_⟩ · intro j hj v have h := rt1_short_pairs_and_balance v interval_cases j <;> norm_num at * · exact h.1 · exact h.2.1 · intro v exact (rt1_short_pairs_and_balance v).2.2.1 · intro v exact (rt1_short_pairs_and_balance v).2.2.2 · decide · decide