is_recursively_balanced
def
A picking sequence of length m for n agents is recursively balanced if each complete round of n turns contains every agent exactly once and any final incomplete round contains no agent more than once.
Statement
def is_recursively_balanced (n : ℕ) (seq : List (Fin n)) : Prop
- Defined in
- arXiv:2610.23686, Sec. 2
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Used by 3
- 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…
- round_robin_sequence_is_recursively_balancedEvery Round-Robin picking sequence of length m for n agents is recursively balanced.
- recursively_balanced_alphaThe universal EF1 approximation factor α_RB for recursively balanced picking sequences is the infimum over all recursively balanced…
Read back from the Lean
A list seq of elements of Fin n is recursively balanced if, for every natural number s, the sublist obtained by dropping the first s * n elements of seq and taking the first n elements of what remains has no duplicate elements (List.Nodup).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A picking sequence of length m for n agents is recursively balanced if every complete round of n turns is a permutation of the agents and the final incomplete round has no repeated agents. -/ def is_recursively_balanced (n : ℕ) (seq : List (Fin n)) : Prop := ∀ s : ℕ, ((seq.drop (s * n)).take n).Nodup