AFTD Auto-Formalizing Theoretical Domains

transitions_le_two_mul_card_of_bool_labels

theoremverified

For any positive natural number m with [NeZero m], any type ι, any finite set L of elements of ι, any natural number k, any coloring α : ZMod m → Fin k, and any family of boolean functions s : ι → ZMod m → Bool: if for all i, j in ZMod m, agreement of s ℓ i = s ℓ j for all ℓ ∈ L implies α i = α j, and for every ℓ ∈ L the number of cyclic transitions where s ℓ i ≠ s ℓ (i + 1) is at most 2, then the number of cyclic transitions where α i ≠ α (i + 1) is at most 2 * L.card.

Statement

theorem transitions_le_two_mul_card_of_bool_labels {m : ℕ} [NeZero m] {ι : Type*} (L : Finset ι)
    {k : ℕ} (α : ZMod m → Fin k) (s : ι → ZMod m → Bool)
    (h_alloc : ∀ i j : ZMod m, (∀ ℓ ∈ L, s ℓ i = s ℓ j) → α i = α j)
    (h_two : ∀ ℓ ∈ L, (Finset.univ.filter (fun i : ZMod m => s ℓ i ≠ s ℓ (i + 1))).card ≤ 2) :
    (Finset.univ.filter (fun i : ZMod m => α i ≠ α (i + 1))).card ≤ 2 * L.card
Source
arXiv:2610.27956 Proposition 1
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

Read back from the Lean

Let $m$ be a non-zero natural number, $\iota$ a type, and $L$ a finite subset of $\iota$. Let $k$ be a natural number, $\alpha : \mathbb{Z}/m\mathbb{Z} \to \mathrm{Fin}\ k$, and $s : \iota \to \mathbb{Z}/m\mathbb{Z} \to \mathrm{Bool}$. Assume: 1. For all $i, j \in \mathbb{Z}/m\mathbb{Z}$, if $s(\ell, i) = s(\ell, j)$ for all $\ell \in L$, then $\alpha(i) = \alpha(j)$. 2. For all $\ell \in L$, the number of elements $i \in \mathbb{Z}/m\mathbb{Z}$ such that $s(\ell, i) \neq s(\ell, i + 1)$ is at most $2$. Then the number of elements $i \in \mathbb{Z}/m\mathbb{Z}$ such that $\alpha(i) \neq \alpha(i + 1)$ is at most $2 \cdot |L|$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof proceeds in two steps. First, it establishes that every cyclic transition point of the coloring α must be a transition point for at least one coordinate function s ℓ with ℓ ∈ L, because if all coordinate functions remain constant from i to i + 1, the hypothesis forces α to remain constant as well. Second, taking cardinalities and applying subadditivity of finite unions bounds the total number of transitions of α by the sum of the transition counts of each s ℓ. Since each label changes at most twice along the cycle, the sum is at most 2 * |L|.

  1. The set of transition points of α is a subset of the union over ℓ ∈ L of the transition points of s ℓ.

    Let i be an index where α(i) ≠ α(i + 1). We argue by contradiction that i must belong to the union of transition sets. If i did not belong to the union, then for every label ℓ ∈ L, i would not be a transition point for s ℓ, meaning s ℓ i = s ℓ (i + 1). By the assumption that colorings factor through L (h_alloc), agreement across all labels in L would imply α i = α (i + 1), contradicting that i is a transition point of α.

    lines 7–18

    uses Finset.mem_filter, Finset.mem_biUnion, Finset.mem_filter.mpr, Finset.mem_univ

      have h_sub : (Finset.univ.filter (fun i : ZMod m => α i ≠ α (i + 1))) ⊆
          L.biUnion (fun ℓ => Finset.univ.filter (fun i : ZMod m => s ℓ i ≠ s ℓ (i + 1))) := by
        intro i hi
        rw [Finset.mem_filter] at hi
        rw [Finset.mem_biUnion]
        by_contra hcon
        have heq : ∀ ℓ ∈ L, s ℓ i = s ℓ (i + 1) := by
          intro ℓ hℓ
          by_contra hne
          apply hcon
          exact ⟨ℓ, hℓ, Finset.mem_filter.mpr ⟨Finset.mem_univ i, hne⟩⟩
        exact hi.2 (h_alloc i (i + 1) heq)
  2. The number of transitions of α is at most the sum over ℓ ∈ L of the transition counts of each s ℓ.

    By monotonicity of cardinality under subset inclusion (Finset.card_le_card), the number of transitions of α is bounded by the cardinality of the union of the transition sets. By subadditivity of the cardinality of a union (Finset.card_biUnion_le), this cardinality is in turn bounded by the sum of the cardinalities of the individual transition sets over all ℓ ∈ L.

    lines 19–22

    uses Finset.card_le_card, Finset.card_biUnion_le

      have h1 := Finset.card_le_card h_sub
      have h2 : (L.biUnion (fun ℓ => Finset.univ.filter (fun i : ZMod m => s ℓ i ≠ s ℓ (i + 1)))).card ≤
          ∑ ℓ ∈ L, (Finset.univ.filter (fun i : ZMod m => s ℓ i ≠ s ℓ (i + 1))).card :=
        Finset.card_biUnion_le
  3. The sum of coordinate transition counts is at most 2 * |L|, which bounds the total number of transitions of α by 2 * |L|.

    By assumption (h_two), each label ℓ ∈ L changes value at most 2 times along the cycle, so the sum of transition counts is bounded by ∑ ℓ ∈ L, 2 via Finset.sum_le_sum. Rewriting this constant sum with Finset.sum_const and smul_eq_mul gives |L| * 2. Finally, linear arithmetic (linarith) chains this bound with the previous inequalities to conclude that the number of transitions of α is at most 2 * |L|.

    lines 23–26

    uses Finset.sum_le_sum, Finset.sum_const, smul_eq_mul

      have h3 : (∑ ℓ ∈ L, (Finset.univ.filter (fun i : ZMod m => s ℓ i ≠ s ℓ (i + 1))).card) ≤ ∑ ℓ ∈ L, 2 :=
        Finset.sum_le_sum fun ℓ hℓ => h_two ℓ hℓ
      simp only [Finset.sum_const, smul_eq_mul] at h3
      linarith
Finset.mem_filter
An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies predicate `p`.
Finset.mem_biUnion
An element belongs to `s.biUnion t` if and only if it belongs to `t a` for some `a ∈ s`.
Finset.mem_filter.mpr
If an element belongs to `s` and satisfies predicate `p`, then it belongs to `Finset.filter p s`.
Finset.mem_univ
Every element of a finite type belongs to its universal finset `Finset.univ`.
Finset.card_le_card
If a finite set `s` is a subset of `t`, then the cardinality of `s` is at most the cardinality of `t`.
Finset.card_biUnion_le
The cardinality of a union of finite sets indexed by a finite set `s` is at most the sum of their individual cardinalities.
Finset.sum_le_sum
If `f i ≤ g i` for all `i ∈ s`, then the sum of `f` over `s` is at most the sum of `g` over `s`.
Finset.sum_const
Summing a constant value `b` over a finite set `s` equals `s.card • b`.
smul_eq_mul
Scalar multiplication `a • b` is equal to the product `a * b`.

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

/-- If each label in a finite set L induces at most two transitions along a cyclic sequence of length m, and colorings factor through L, then the total number of transitions is at most 2 * |L|. -/theorem transitions_le_two_mul_card_of_bool_labels {m : ℕ} [NeZero m] {ι : Type*} (L : Finset ι)    {k : ℕ} (α : ZMod m → Fin k) (s : ι → ZMod m → Bool)    (h_alloc : ∀ i j : ZMod m, (∀ ℓ ∈ L, s ℓ i = s ℓ j) → α i = α j)    (h_two : ∀ ℓ ∈ L, (Finset.univ.filter (fun i : ZMod m => s ℓ i ≠ s ℓ (i + 1))).card ≤ 2) :    (Finset.univ.filter (fun i : ZMod m => α i ≠ α (i + 1))).card ≤ 2 * L.card := by  have h_sub : (Finset.univ.filter (fun i : ZMod m => α i ≠ α (i + 1))) ⊆      L.biUnion (fun ℓ => Finset.univ.filter (fun i : ZMod m => s ℓ i ≠ s ℓ (i + 1))) := by    intro i hi    rw [Finset.mem_filter] at hi    rw [Finset.mem_biUnion]    by_contra hcon    have heq : ∀ ℓ ∈ L, s ℓ i = s ℓ (i + 1) := by      intro ℓ hℓ      by_contra hne      apply hcon      exact ⟨ℓ, hℓ, Finset.mem_filter.mpr ⟨Finset.mem_univ i, hne⟩⟩    exact hi.2 (h_alloc i (i + 1) heq)  have h1 := Finset.card_le_card h_sub  have h2 : (L.biUnion (fun ℓ => Finset.univ.filter (fun i : ZMod m => s ℓ i ≠ s ℓ (i + 1)))).card ≤      ∑ ℓ ∈ L, (Finset.univ.filter (fun i : ZMod m => s ℓ i ≠ s ℓ (i + 1))).card :=    Finset.card_biUnion_le  have h3 : (∑ ℓ ∈ L, (Finset.univ.filter (fun i : ZMod m => s ℓ i ≠ s ℓ (i + 1))).card) ≤ ∑ ℓ ∈ L, 2 :=    Finset.sum_le_sum fun ℓ hℓ => h_two ℓ hℓ  simp only [Finset.sum_const, smul_eq_mul] at h3  linarith
See it in the graphDiscuss this resultChallenge it