AFTD Auto-Formalizing Theoretical Domains

round_robin_sequence_is_recursively_balanced

theoremverifiedformalization

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

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.

  1. 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`).

    lines 4–7

    uses List.nodup_iff_injective_getElem

      intro s
      rw [List.nodup_iff_injective_getElem]
      rintro ⟨i, hi⟩ ⟨j, hj⟩ (hij : _ = _)
      dsimp at hij
  2. 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$.

    lines 8–13

    uses List.length_take, List.length_drop

      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
  3. 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$.

    lines 14–17

    uses List.getElem_take, List.getElem_drop

      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]
  4. 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$.

    lines 18–22

    uses List.getElem_ofFn, Fin.ext_iff.mp

      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
  5. 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$.

    lines 23–26

    uses Nat.add_comm, Nat.add_mul_mod_self_right, Nat.mod_eq_of_lt

      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]
  6. 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`.

    lines 27–28

    uses Fin.ext

      rw [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

/-- 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
See it in the graphDiscuss this resultChallenge it