AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_alternating_half_tight

theoremverified

In a tight, exactly dyadically covered model at exponent m+1 (m >= 1) with alternating bit 1, for every class with bit 1 both its even half and its odd half are tight at exponent m (class weight equal to cardinality).

Statement

theorem cycle_power_dyadic_alternating_half_tight (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool)
    (htight : ∀ p, cycle_power_dyadic_class_weight (m+1) (x p) =
      (Finset.range (2^(m+1))).sum (fun a => (x p a).toNat))
    (hexact : ∀ j < (m+1), ∀ v : ℤ, (Finset.range (2^j)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(m+1)-2^j)).toNat) = 1)
    (halt : ∀ p : ℤ, x (p+1) 1 = !x p 1)
    (p : ℤ) (hp : x p 1 = true) (e : ℕ) (he : e < 2) :
    cycle_power_dyadic_class_weight m (fun b => x p (2*b+e)) =
      (Finset.range (2^m)).sum (fun b => (x p (2*b+e)).toNat)
Source
Helper for RT-1 (OP-205, arXiv:2610.15635): rungs of cycle_power_dyadic_alternating_half_model (the even and odd halves of the bit-1 classes of an alternating endpoint-only dyadic model form a model one exponent lower)
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
Used by 1

The proof, explained

The proof uses a parity split formula that relates the class weight at exponent m+1 to the sum of the class weights of its even and odd halves at exponent m, along with boundary correction terms. Because the model is exact and alternates on bit 1 with x(p, 1) = true, all boundary terms evaluate to 1, while tightness at exponent m+1 allows replacing the total weight with the total bit sum, which decomposes into the sum of the even and odd cardinalities. Since each half's class weight is bounded above by its cardinality and their sums coincide, both halves must attain their upper bounds with equality.

  1. The endpoint bits x(p, 0) and x(p, 2^(m+1) - 1) are true, and the near-boundary bit x(p, 2^(m+1) - 2) equals x(p, 1).

    By cycle_power_dyadic_exact_endpoints applied at exponent m + 1 (with 1 ≤ m + 1 verified by omega), exactness implies that the endpoints x(p, 0) and x(p, 2^(m+1) - 1) are both true. By cycle_power_dyadic_boundary_pair_of_alternating (with 2 ≤ m + 1 verified by omega), exactness and the alternating bit condition imply x(p, 2^(m+1) - 2) = x(p, 1).

    lines 10–11

    uses cycle_power_dyadic_exact_endpoints, cycle_power_dyadic_boundary_pair_of_alternating

      have hend := cycle_power_dyadic_exact_endpoints (m+1) (by omega) x hexact p
      have hH := cycle_power_dyadic_boundary_pair_of_alternating (m+1) (by omega) x hexact halt p
  2. The sum of the cardinalities of the even and odd halves plus the two boundary terms equals twice the endpoint term plus the sum of the even and odd class weights.

    We instantiate the parity split formula cycle_power_dyadic_class_weight_parity_split for x(p), which relates the class weight at exponent m + 1 to the weights of the even and odd halves at exponent m. Rewriting with the endpoint values, the boundary relation, hp (x(p, 1) = true), and htight replaces the total weight by the total bit sum over range 2^(m+1). Then, rewriting 2^(m+1) = 2 * 2^m via pow_succ, cycle_power_sum_range_double, and Finset.sum_add_distrib splits the total bit sum into the sum over even indices and the sum over odd indices.

    lines 12–15

    uses cycle_power_dyadic_class_weight_parity_split, pow_succ, cycle_power_sum_range_double, Finset.sum_add_distrib

      have hsplit := cycle_power_dyadic_class_weight_parity_split m hm (x p)
      rw [hend.1, hend.2, hH, hp, htight p] at hsplit
      have hpow : 2 ^ (m + 1) = 2 * 2 ^ m := by rw [pow_succ]; omega
      rw [hpow, cycle_power_sum_range_double, Finset.sum_add_distrib] at hsplit
  3. Each half's class weight is bounded above by its cardinality, and the parity split equation reduces to equality between the sum of cardinalities and the sum of class weights.

    By cycle_power_dyadic_class_weight_le, the class weight at exponent m of the even half is bounded above by its cardinality, and likewise for the odd half. Simplifying the boolean terms (true && true).toNat to 1 via Bool.and_self and Bool.toNat_true reduces the parity identity to (sum of even bits) + (sum of odd bits) + 1 + 1 = 2 * 1 + (even weight) + (odd weight).

    lines 16–18

    uses cycle_power_dyadic_class_weight_le, Bool.and_self, Bool.toNat_true

      have hE := cycle_power_dyadic_class_weight_le m hm (fun i => x p (2 * i))
      have hO := cycle_power_dyadic_class_weight_le m hm (fun i => x p (2 * i + 1))
      simp only [Bool.and_self, Bool.toNat_true] at hsplit
  4. For each e < 2, the class weight of the half b ↦ x(p, 2b + e) equals its cardinality.

    We split into cases on e < 2 using interval_cases e. For e = 0, Nat.add_zero simplifies 2b + 0 to 2b. Since the even weight and odd weight are each bounded above by their respective cardinalities, and the sum of the weights equals the sum of the cardinalities, neither inequality can be strict. Linear arithmetic (omega) closes both the e = 0 and e = 1 cases.

    lines 19–21

    uses Nat.add_zero

      interval_cases e
      · simp only [Nat.add_zero]; omega
      · omega
cycle_power_dyadic_exact_endpoints
In an exact dyadic model at exponent m ≥ 1, for every class p, the boundary bits x(p, 0) and x(p, 2^m - 1) are both true.
cycle_power_dyadic_boundary_pair_of_alternating
In an exact dyadic model at exponent M ≥ 2 with alternating bit 1, the near-boundary bit x(p, 2^M - 2) equals x(p, 1) for every class p.
cycle_power_dyadic_class_weight_parity_split
For any bit sequence b and m ≥ 1, the class weight at exponent m + 1 plus two boundary overlap terms equals twice the endpoint overlap plus the sum of the class weights of the even half and the odd half at exponent m.
pow_succ
In a monoid, a^(n + 1) = a^n * a.
cycle_power_sum_range_double
The sum of a function over the range 2n equals the sum over the range n of the paired even and odd values f(2i) + f(2i + 1).
Finset.sum_add_distrib
The sum of a sum of two functions over a finite set distributes into the sum of the first plus the sum of the second.
cycle_power_dyadic_class_weight_le
For m ≥ 1, the dyadic class weight of a bit sequence at exponent m is at most the sum of its bits (its cardinality) over the range 2^m.
Bool.and_self
For every boolean b, b && b = b.
Bool.toNat_true
The numerical value of the boolean true is 1.
Nat.add_zero
Adding zero to any natural number leaves it unchanged: n + 0 = n.

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

theorem cycle_power_dyadic_alternating_half_tight (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool)    (htight : ∀ p, cycle_power_dyadic_class_weight (m+1) (x p) =      (Finset.range (2^(m+1))).sum (fun a => (x p a).toNat))    (hexact : ∀ j < (m+1), ∀ v : ℤ, (Finset.range (2^j)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(m+1)-2^j)).toNat) = 1)    (halt : ∀ p : ℤ, x (p+1) 1 = !x p 1)    (p : ℤ) (hp : x p 1 = true) (e : ℕ) (he : e < 2) :    cycle_power_dyadic_class_weight m (fun b => x p (2*b+e)) =      (Finset.range (2^m)).sum (fun b => (x p (2*b+e)).toNat) := by  have hend := cycle_power_dyadic_exact_endpoints (m+1) (by omega) x hexact p  have hH := cycle_power_dyadic_boundary_pair_of_alternating (m+1) (by omega) x hexact halt p  have hsplit := cycle_power_dyadic_class_weight_parity_split m hm (x p)  rw [hend.1, hend.2, hH, hp, htight p] at hsplit  have hpow : 2 ^ (m + 1) = 2 * 2 ^ m := by rw [pow_succ]; omega  rw [hpow, cycle_power_sum_range_double, Finset.sum_add_distrib] at hsplit  have hE := cycle_power_dyadic_class_weight_le m hm (fun i => x p (2 * i))  have hO := cycle_power_dyadic_class_weight_le m hm (fun i => x p (2 * i + 1))  simp only [Bool.and_self, Bool.toNat_true] at hsplit  interval_cases e  · simp only [Nat.add_zero]; omega  · omega
See it in the graphDiscuss this resultChallenge it