perm_card_filter_dvd_succ
theoremverified
For any permutation s of {0, ..., k-1} and any m, exactly floor(k/m) positions j have m dividing s(j) + 1 (the values s(j) + 1 run over 1, ..., k).
Statement
theorem perm_card_filter_dvd_succ {k : ℕ} (σ : Equiv.Perm (Fin k)) (m : ℕ) : (Finset.univ.filter fun j : Fin k => m ∣ (σ j : ℕ) + 1).card = k / m
- Source
- step towards weakly_consecutive_one_at_end_of_isPrimePow (Weakly Consecutive Sequences (2024), arXiv:2401.09497, Conjecture 5.2, prime-power case)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- weakly_consecutive_first_dvdIn a weakly consecutive sequence of length k, the first term divides k.
- weakly_consecutive_ends_coprimeIn a weakly consecutive sequence, the first and last terms are coprime.
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.
theorem perm_card_filter_dvd_succ {k : ℕ} (σ : Equiv.Perm (Fin k)) (m : ℕ) : (Finset.univ.filter fun j : Fin k => m ∣ (σ j : ℕ) + 1).card = k / m := by have h1 : (Finset.univ.filter fun j : Fin k => m ∣ (σ j : ℕ) + 1).card = (Finset.univ.filter fun v : Fin k => m ∣ (v : ℕ) + 1).card := by rw [Finset.card_filter, Finset.card_filter] exact Equiv.sum_comp σ (fun v : Fin k => if m ∣ (v : ℕ) + 1 then 1 else 0) rw [h1, ← Nat.card_multiples k m, Finset.card_filter, Finset.card_filter, Fin.sum_univ_eq_sum_range (fun j => if m ∣ j + 1 then 1 else 0)]