AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_fold_periodicity_distance_one_counterexample

theoremverified

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.

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

    lines 9–17

    uses Int.emod_nonneg, Int.emod_lt_of_pos

      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 <;> decide
  2. 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.

    lines 20–22

      by_cases hs : -12 ≤ v ∧ v ≤ 12
      · obtain ⟨hlo,hhi⟩ := hs
        interval_cases v <;> decide
  3. 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`).

    lines 23–35

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

    lines 43–45

      by_cases hs : -12 ≤ v ∧ v ≤ 12
      · obtain ⟨hlo,hhi⟩ := hs
        interval_cases v <;> decide
  5. 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.

    lines 46–62

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

    line 65

    uses Nat.cast_zero, sub_zero, Nat.zero_add

      refine ⟨0, by decide, ?_, ?_⟩ <;> simp only [Nat.cast_zero, sub_zero, Nat.zero_add, rt1_short_x] <;> split_ifs <;> decide
  7. 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.

    lines 81–90

    uses rt1_short_tight, rt1_short_count, rt1_short_cover_one, rt1_short_pairs_and_balance

      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
  8. 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`).

    lines 91–92

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

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

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