transitions_le_two_mul_card_of_bool_labels
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
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|.
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 α.
uses
Finset.mem_filter,Finset.mem_biUnion,Finset.mem_filter.mpr,Finset.mem_univhave 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)
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.
uses
Finset.card_le_card,Finset.card_biUnion_lehave 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
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|.
uses
Finset.sum_le_sum,Finset.sum_const,smul_eq_mulhave 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`.
- In Lean, summing a constant natural number produces scalar multiplication `L.card • 2` (via `Finset.sum_const`), which must be rewritten to standard arithmetic multiplication `L.card * 2` via `smul_eq_mul` before `linarith` can verify the inequality.
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.
/-- 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