AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_sparse_defect_support_card

theoremverified

For each t≥4, the sparse defect support contains exactly t points.

Statement

theorem cycle_power_dyadic_sparse_defect_support_card (t : ℕ) (ht : 4 ≤ t) :
  (cycle_power_dyadic_sparse_defect_support t).card = t
Source
RT-1 and OP-205, arXiv:2610.15635. The sparse constant family was identified in experiment 22695; it is a weakened-coverage obstruction, not a full graph-cover model.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

By definition, the sparse defect support is the union of {0, q - 1} and T = {2^t - 2^j | 0 ≤ j < t - 2}, where q = 2^(t-2). For t ≥ 4, we have q ≥ 4, so 0 ≠ q - 1 and |{0, q - 1}| = 2. The mapping j ↦ 2^t - 2^j is injective on {0, ..., t-3}, giving |T| = t - 2. Furthermore, every element of T exceeds q - 1, ensuring that the two sets are disjoint. Summing their cardinalities yields 2 + (t - 2) = t.

  1. Define q = 2^(t-2) and T = {2^t - 2^j | 0 ≤ j < t-2}, and establish that 4 ≤ q.

    We define q = 2^(t-2) and T as the image of {0, ..., t-3} under j ↦ 2^t - 2^j. Since t ≥ 4, we have t - 2 ≥ 2, so q = 2^(t-2) ≥ 2^2 = 4 by monotonicity of powers (Nat.pow_le_pow_right).

    lines 3–8

    uses Nat.pow_le_pow_right

      classical
      let q : ℕ := 2^(t-2)
      let T : Finset ℕ := (Finset.range (t-2)).image (fun j => 2^t - 2^j)
      have hq : 4 ≤ q := by
        have h := Nat.pow_le_pow_right (by decide : 0 < (2 : ℕ)) (show 2 ≤ t-2 by omega)
        simpa [q] using h
  2. 2^t = 4 * q

    Since t ≥ 4, we have t = (t - 2) + 2. Splitting the exponent using pow_add gives 2^t = 2^(t-2) * 2^2 = q * 4 = 4 * q.

    lines 9–13

    uses pow_add

      have hD : 2^t = 4*q := by
        have ht' : t-2+2 = t := by omega
        calc
          2^t = 2^(t-2+2) := by rw [ht']
          _ = 4*q := by simp [pow_add, q]; ring
  3. Every element of T is strictly greater than q - 1.

    For any index j in {0, ..., t-3}, we have j < t - 2 by Finset.mem_range.mp. Since the base 2 is greater than 1, strict monotonicity (Nat.pow_lt_pow_right) gives 2^j < 2^(t-2) = q. Using 2^t = 4 * q and 4 ≤ q, we obtain 2^t - 2^j > 4 * q - q = 3 * q > q - 1.

    lines 14–20

    uses Finset.mem_range.mp, Nat.pow_lt_pow_right

      have hbig : ∀ j ∈ Finset.range (t-2), q-1 < 2^t-2^j := by
        intro j hj
        have hj' : j < t-2 := Finset.mem_range.mp hj
        have hp : 2^j < q := by
          dsimp [q]
          exact Nat.pow_lt_pow_right (by decide) hj'
        omega
  4. The function j ↦ 2^t - 2^j is injective on {0, ..., t-3}.

    Suppose j, k < t - 2 satisfy 2^t - 2^j = 2^t - 2^k. Since j, k < t, both 2^j and 2^k are strictly less than 2^t (by Finset.mem_range.mp and Nat.pow_lt_pow_right). Subtracting from 2^t preserves equality, giving 2^j = 2^k, which implies j = k by injectivity of powers of 2 (Nat.pow_right_injective).

    lines 21–29

    uses Finset.mem_range.mp, Nat.pow_lt_pow_right, Nat.pow_right_injective

      have hinj : Set.InjOn (fun j : ℕ => 2^t-2^j) ↑(Finset.range (t-2)) := by
        intro j hj k hk heq
        have hj' : j < t := by have := Finset.mem_range.mp hj; omega
        have hk' : k < t := by have := Finset.mem_range.mp hk; omega
        have hpj : 2^j < 2^t := Nat.pow_lt_pow_right (by decide) hj'
        have hpk : 2^k < 2^t := Nat.pow_lt_pow_right (by decide) hk'
        change 2^t - 2^j = 2^t - 2^k at heq
        have hp : 2^j = 2^k := by omega
        exact (Nat.pow_right_injective (by decide)) hp
  5. The cardinality of T is t - 2.

    Because T is the image of {0, ..., t-3} under an injective map, its cardinality equals that of the domain (Finset.card_image_iff.mpr), which is t - 2 (Finset.card_range).

    lines 30–32

    uses Finset.card_image_iff.mpr, Finset.card_range

      have hcardT : T.card = t-2 := by
        dsimp [T]
        rw [Finset.card_image_iff.mpr hinj, Finset.card_range]
  6. The sets {0, q - 1} and T are disjoint.

    By Finset.disjoint_left.mpr, it suffices to show that no element of {0, q - 1} belongs to T. Any element x ∈ T equals 2^t - 2^j for some j < t - 2 (Finset.mem_image.mp). By the lower bound proved earlier, x > q - 1 ≥ 3, which contradicts both x = 0 and x = q - 1 (unfolded via Finset.mem_insert and Finset.mem_singleton).

    lines 33–39

    uses Finset.disjoint_left.mpr, Finset.mem_image.mp, Finset.mem_insert, Finset.mem_singleton

      have hdisj : Disjoint ({0,q-1} : Finset ℕ) T := by
        apply Finset.disjoint_left.mpr
        intro x hx hy
        obtain ⟨j,hj,rfl⟩ := Finset.mem_image.mp (show x ∈ (Finset.range (t-2)).image (fun j => 2^t-2^j) from hy)
        have hb := hbig j hj
        simp only [Finset.mem_insert, Finset.mem_singleton] at hx
        rcases hx with h0 | hq' <;> omega
  7. The cardinality of {0, q - 1} is 2.

    Since q ≥ 4, 0 ≠ q - 1. The two elements are distinct, so the set has size 2.

    lines 40–42

      have hcardA : ({0,q-1} : Finset ℕ).card = 2 := by
        have hne : (0 : ℕ) ≠ q-1 := by omega
        simp [hne]
  8. The sparse defect support has cardinality t.

    By definition, the sparse defect support is the union {0, q - 1} ∪ T. Because this union is disjoint, its cardinality is |{0, q - 1}| + |T| by Finset.card_union_of_disjoint, which evaluates to 2 + (t - 2) = t.

    lines 43–45

    uses Finset.card_union_of_disjoint

      change (({0,q-1} : Finset ℕ) ∪ T).card = t
      rw [Finset.card_union_of_disjoint hdisj, hcardA, hcardT]
      omega
Nat.pow_le_pow_right
For any positive base n, if i ≤ j then n^i ≤ n^j.
pow_add
Raising a base to the sum of two exponents equals the product of the powers: a^(m+n) = a^m * a^n.
Finset.mem_range.mp
If a natural number k is in the range of n (the set {0, ..., n-1}), then k < n.
Nat.pow_lt_pow_right
For a base a > 1, strictly increasing the exponent strictly increases the power: if m < n, then a^m < a^n.
Nat.pow_right_injective
For an integer base a ≥ 2, the exponential function x ↦ a^x is injective.
Finset.card_image_iff.mpr
If a function is injective on a finite set s, then the cardinality of its image under that function equals the cardinality of s.
Finset.card_range
The finite set of natural numbers strictly less than n has cardinality n.
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first set belongs to the second set.
Finset.mem_image.mp
If an element belongs to the image of a set under a function f, then it equals f(a) for some element a in that set.
Finset.mem_insert
An element belongs to the insertion of b into a finite set s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton set {a} if and only if it is equal to a.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.

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_sparse_defect_support_card (t : ℕ) (ht : 4 ≤ t) :  (cycle_power_dyadic_sparse_defect_support t).card = t := by  classical  let q : ℕ := 2^(t-2)  let T : Finset ℕ := (Finset.range (t-2)).image (fun j => 2^t - 2^j)  have hq : 4 ≤ q := by    have h := Nat.pow_le_pow_right (by decide : 0 < (2 : ℕ)) (show 2 ≤ t-2 by omega)    simpa [q] using h  have hD : 2^t = 4*q := by    have ht' : t-2+2 = t := by omega    calc      2^t = 2^(t-2+2) := by rw [ht']      _ = 4*q := by simp [pow_add, q]; ring  have hbig : ∀ j ∈ Finset.range (t-2), q-1 < 2^t-2^j := by    intro j hj    have hj' : j < t-2 := Finset.mem_range.mp hj    have hp : 2^j < q := by      dsimp [q]      exact Nat.pow_lt_pow_right (by decide) hj'    omega  have hinj : Set.InjOn (fun j : ℕ => 2^t-2^j) ↑(Finset.range (t-2)) := by    intro j hj k hk heq    have hj' : j < t := by have := Finset.mem_range.mp hj; omega    have hk' : k < t := by have := Finset.mem_range.mp hk; omega    have hpj : 2^j < 2^t := Nat.pow_lt_pow_right (by decide) hj'    have hpk : 2^k < 2^t := Nat.pow_lt_pow_right (by decide) hk'    change 2^t - 2^j = 2^t - 2^k at heq    have hp : 2^j = 2^k := by omega    exact (Nat.pow_right_injective (by decide)) hp  have hcardT : T.card = t-2 := by    dsimp [T]    rw [Finset.card_image_iff.mpr hinj, Finset.card_range]  have hdisj : Disjoint ({0,q-1} : Finset ℕ) T := by    apply Finset.disjoint_left.mpr    intro x hx hy    obtain ⟨j,hj,rfl⟩ := Finset.mem_image.mp (show x ∈ (Finset.range (t-2)).image (fun j => 2^t-2^j) from hy)    have hb := hbig j hj    simp only [Finset.mem_insert, Finset.mem_singleton] at hx    rcases hx with h0 | hq' <;> omega  have hcardA : ({0,q-1} : Finset ℕ).card = 2 := by    have hne : (0 : ℕ) ≠ q-1 := by omega    simp [hne]  change (({0,q-1} : Finset ℕ) ∪ T).card = t  rw [Finset.card_union_of_disjoint hdisj, hcardA, hcardT]  omega
See it in the graphDiscuss this resultChallenge it