round_robin_sequence_is_recursively_balanced
Every Round-Robin picking sequence of length m for n agents is recursively balanced.
Statement
theorem round_robin_sequence_is_recursively_balanced (n m : ℕ) [NeZero n] :
is_recursively_balanced n (round_robin_sequence n m)- Formalizes
- arXiv:2610.23686, Sec. 2
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_recursively_balancedA picking sequence of length m for n agents is recursively balanced if each complete round of n turns contains every agent exactly once…
- round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
- Used by 1
- recursively_balanced_alpha_le_round_robin_universal_alphaThe universal EF1 approximation factor for recursively balanced sequences recursively_balanced_alpha is at most the universal factor for…
Read back from the Lean
For all natural numbers n and m, with n ≠ 0 (supplied via [NeZero n]), the sequence round_robin_sequence n m is recursively balanced with parameter n (in the sense of is_recursively_balanced).
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
To show that the round-robin sequence is recursively balanced, we show that for any block index $s \in \mathbb{N}$, the sublist of length at most $n$ starting at index $s \cdot n$ contains no duplicate elements. We characterize duplicate-free lists by the injectivity of indexing into them. Since the $t$-th element of the round-robin sequence is agent $t \bmod n$, the $k$-th position of block $s$ corresponds to agent $(s \cdot n + k) \bmod n$. Because each sublist index satisfies $k < n$, this remainder simplifies to $k$, ensuring that distinct positions in the block always receive distinct agents.
To show that the $s$-th block of length at most $n$ has no duplicate elements, it suffices to prove that indexing into it is injective.
Recursive balance requires that for each round $s$, the sublist obtained by dropping $s \cdot n$ elements and taking $n$ has no duplicates (`Nodup`). By `List.nodup_iff_injective_getElem`, this is equivalent to showing that indexing into this sublist is an injective function. We introduce two valid sublist indices $\langle i, h_i \rangle$ and $\langle j, h_j \rangle$ whose corresponding elements are assumed equal (`hij`).
uses
List.nodup_iff_injective_getElemintro s rw [List.nodup_iff_injective_getElem] rintro ⟨i, hi⟩ ⟨j, hj⟩ (hij : _ = _) dsimp at hij
The sublist indices $i$ and $j$ satisfy $i < n$ and $j < n$, and the global offsets $s \cdot n + i$ and $s \cdot n + j$ lie within the sequence length.
The valid index bounds $h_i$ and $h_j$ state that $i$ and $j$ are strictly less than the length of the sublist, which rewrites via `List.length_take` and `List.length_drop` to $\min(n, \mathrm{length} - s \cdot n)$. Linear arithmetic (`omega`) deduces from this that $i < n$ and $s \cdot n + i < \mathrm{length}$, and symmetrically for $j$.
uses
List.length_take,List.length_drophave hlen_i : s * n + i < (round_robin_sequence n m).length ∧ i < n := by rw [List.length_take, List.length_drop] at hi omega have hlen_j : s * n + j < (round_robin_sequence n m).length ∧ j < n := by rw [List.length_take, List.length_drop] at hj omega
The $i$-th and $j$-th elements of the sublist equal the $(s \cdot n + i)$-th and $(s \cdot n + j)$-th elements of the overall sequence.
By `List.getElem_take` and `List.getElem_drop`, looking up index $k$ in `(seq.drop (s * n)).take n` retrieves index $s \cdot n + k$ of `seq`. We establish this identity for both $k = i$ and $k = j$.
uses
List.getElem_take,List.getElem_drophave hi_eq : (((round_robin_sequence n m).drop (s * n)).take n)[i] = (round_robin_sequence n m)[s * n + i] := by rw [List.getElem_take, List.getElem_drop] have hj_eq : (((round_robin_sequence n m).drop (s * n)).take n)[j] = (round_robin_sequence n m)[s * n + j] := by rw [List.getElem_take, List.getElem_drop]
Equality of the sublist elements implies $(s \cdot n + i) \bmod n = (s \cdot n + j) \bmod n$.
Rewriting the assumption `hij` using the sequence-indexing lemmas and unfolding the definition of `round_robin_sequence` (which maps index $t$ to agent $t \bmod n$ via `List.ofFn`), the assumption equates the `Fin n` values $\langle (s \cdot n + i) \bmod n, \dots \rangle$ and $\langle (s \cdot n + j) \bmod n, \dots \rangle$. Extracting the equality of their underlying natural numbers via `Fin.ext_iff.mp` gives $(s \cdot n + i) \bmod n = (s \cdot n + j) \bmod n$.
uses
List.getElem_ofFn,Fin.ext_iff.mprw [hi_eq, hj_eq] at hij unfold round_robin_sequence at hij simp only [List.getElem_ofFn] at hij have hval : (s * n + i) % n = (s * n + j) % n := by exact Fin.ext_iff.mp hij
For both $k = i$ and $k = j$, $(s \cdot n + k) \bmod n = k$.
Commuting the sum and applying `Nat.add_mul_mod_self_right` reduces $(s \cdot n + k) \bmod n$ to $k \bmod n$. Since $k < n$ was established earlier, `Nat.mod_eq_of_lt` reduces this directly to $k$.
uses
Nat.add_comm,Nat.add_mul_mod_self_right,Nat.mod_eq_of_lthave hmod_i : (s * n + i) % n = i := by rw [Nat.add_comm, Nat.add_mul_mod_self_right, Nat.mod_eq_of_lt hlen_i.2] have hmod_j : (s * n + j) % n = j := by rw [Nat.add_comm, Nat.add_mul_mod_self_right, Nat.mod_eq_of_lt hlen_j.2]
The sublist indices $\langle i, h_i \rangle$ and $\langle j, h_j \rangle$ are equal, proving injectivity.
Substituting the modular evaluations into the equality yields $i = j$. Since their numerical values match, the `Fin` elements $\langle i, h_i \rangle$ and $\langle j, h_j \rangle$ are equal by `Fin.ext`.
uses
Fin.extrw [hmod_i, hmod_j] at hval exact Fin.ext hval
Fin.ext- Two `Fin` elements are equal if their underlying natural values are equal.
Fin.ext_iff.mp- If two `Fin` elements are equal, their underlying natural values are equal.
List.getElem_drop- The $j$-th element of `drop i xs` is the $(i + j)$-th element of `xs`.
List.getElem_ofFn- The $i$-th element of `List.ofFn f` is $f(i)$.
List.getElem_take- The $i$-th element of `take j xs` is the $i$-th element of `xs`.
List.length_drop- The length of dropping the first $i$ elements of a list is the original length minus $i$.
List.length_take- The length of taking the first $i$ elements of a list is the minimum of $i$ and the length of the list.
List.nodup_iff_injective_getElem- A list has no duplicate elements if and only if indexing into the list is an injective function on its valid indices.
Nat.add_comm- Addition of natural numbers is commutative: $n + m = m + n$.
Nat.add_mul_mod_self_right- Adding a multiple of $z$ does not change the remainder modulo $z$: $(x + y \cdot z) \bmod z = x \bmod z$.
Nat.mod_eq_of_lt- If $a < b$, then $a \bmod b = a$.
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.
/-- Every Round-Robin picking sequence is recursively balanced. -/theorem round_robin_sequence_is_recursively_balanced (n m : ℕ) [NeZero n] : is_recursively_balanced n (round_robin_sequence n m) := by intro s rw [List.nodup_iff_injective_getElem] rintro ⟨i, hi⟩ ⟨j, hj⟩ (hij : _ = _) dsimp at hij have hlen_i : s * n + i < (round_robin_sequence n m).length ∧ i < n := by rw [List.length_take, List.length_drop] at hi omega have hlen_j : s * n + j < (round_robin_sequence n m).length ∧ j < n := by rw [List.length_take, List.length_drop] at hj omega have hi_eq : (((round_robin_sequence n m).drop (s * n)).take n)[i] = (round_robin_sequence n m)[s * n + i] := by rw [List.getElem_take, List.getElem_drop] have hj_eq : (((round_robin_sequence n m).drop (s * n)).take n)[j] = (round_robin_sequence n m)[s * n + j] := by rw [List.getElem_take, List.getElem_drop] rw [hi_eq, hj_eq] at hij unfold round_robin_sequence at hij simp only [List.getElem_ofFn] at hij have hval : (s * n + i) % n = (s * n + j) % n := by exact Fin.ext_iff.mp hij have hmod_i : (s * n + i) % n = i := by rw [Nat.add_comm, Nat.add_mul_mod_self_right, Nat.mod_eq_of_lt hlen_i.2] have hmod_j : (s * n + j) % n = j := by rw [Nat.add_comm, Nat.add_mul_mod_self_right, Nat.mod_eq_of_lt hlen_j.2] rw [hmod_i, hmod_j] at hval exact Fin.ext hval