perm_offset_avoiding_count_eq_of_board_equiv
If bijections sigma (of rows) and rho (of columns) of Fin n carry the forbidden squares of the offset set S exactly onto those of S' -- n divides j - i - s for some s in S iff n divides rho(j) - sigma(i) - s' for some s' in S' -- then a_S(n) = a_{S'}(n): pi -> rho o pi o sigma^-1 is a bijection between the avoiding permutations.
Statement
theorem perm_offset_avoiding_count_eq_of_board_equiv (n : ℕ) (S S' : Finset ℤ)
(σ ρ : Equiv.Perm (Fin n))
(h : ∀ i j : Fin n, (∃ s ∈ S, (n : ℤ) ∣ ((j : ℕ) : ℤ) - ((i : ℕ) : ℤ) - s) ↔
(∃ s ∈ S', (n : ℤ) ∣ ((ρ j : ℕ) : ℤ) - ((σ i : ℕ) : ℤ) - s)) :
perm_offset_avoiding_count n S = perm_offset_avoiding_count n S'- Source
- lemma for arXiv:2610.23958 Proposition 6.2 (PR-301): counts of avoiding permutations are invariant under relabelling rows and columns of the board
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- perm_offset_avoiding_counta_S(n): the number of S-avoiding permutations of an n-element set, i.e. permutations pi of {0, ..., n-1} with pi(i) - i - s not divisible…
- Used by 1
- perm_offset_avoiding_count_neg_one_one_eq_menage_of_oddFor odd n >= 3 the number of permutations avoiding the offsets {-1, 1} mod n equals the menage number U(n).
The proof, explained
The theorem counts permutations of Fin n avoiding an offset set S modulo n, showing that a board equivalence induced by row permutation σ and column permutation ρ preserves the avoiding count. The proof applies `Finset.card_bij` with the transformation π ↦ ρ ∘ π ∘ σ⁻¹. The hypothesis ensures that a permutation violates avoidance of S if and only if its transformed version violates avoidance of S', and the invertibility of σ and ρ guarantees that the transformation is injective and surjective.
To show the counts are equal, it suffices to exhibit a bijection between the sets of permutations avoiding S and S'.
We unfold the definition of `perm_offset_avoiding_count`, which is the cardinality of the finset of permutations π avoiding the offset set S (meaning n does not divide π(i) - i - s for any row i and offset s ∈ S). By `Finset.card_bij`, equality of cardinalities reduces to showing that the map π ↦ ρ ∘ π ∘ σ⁻¹ (written in Lean as `σ.symm.trans (π.trans ρ)`) maps S-avoiding permutations to S'-avoiding permutations, is injective, and is surjective.
uses
Finset.card_bijunfold perm_offset_avoiding_count refine Finset.card_bij (fun π _ => σ.symm.trans (π.trans ρ)) ?_ ?_ ?_
The map preserves offset-avoidance: if π avoids S, then ρ ∘ π ∘ σ⁻¹ avoids S'.
Let π avoid S. We simplify membership in the avoiding set using `Finset.mem_filter`, `Finset.mem_univ`, and `true_and`. Suppose, for contradiction, that for some row i and offset s ∈ S', n divides (ρ ∘ π ∘ σ⁻¹)(i) - i - s. Setting i₀ = σ⁻¹(i) and j₀ = π(i₀), this condition reads n ∣ ρ(j₀) - σ(i₀) - s. Applying the backward direction of hypothesis h at (i₀, j₀) yields an offset s' ∈ S such that n ∣ j₀ - i₀ - s', meaning n ∣ π(σ⁻¹(i)) - σ⁻¹(i) - s'. This directly contradicts the assumption that π avoids S at index σ⁻¹(i).
uses
Finset.mem_filter,Finset.mem_univ,true_and· intro π hπ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hπ ⊢ intro i s hs hdvd obtain ⟨s', hs', hd'⟩ := (h (σ.symm i) (π (σ.symm i))).2 ⟨s, hs, by simpa using hdvd⟩ exact hπ _ s' hs' hd'
The map π ↦ ρ ∘ π ∘ σ⁻¹ is injective.
Suppose two permutations a and b have the same image: ρ ∘ a ∘ σ⁻¹ = ρ ∘ b ∘ σ⁻¹. By extensionality for equivalences (`Equiv.ext`), it suffices to show a(x) = b(x) for all x. Evaluating both sides of the equality at σ(x) via `congrArg` yields ρ(a(x)) = ρ(b(x)). Since ρ is a bijection, simplifying this equality implies a(x) = b(x).
uses
Equiv.ext,congrArg· intro a _ b _ hab refine Equiv.ext fun x => ?_ have := congrArg (fun e : Equiv.Perm (Fin n) => e (σ x)) hab simpa using this
For every S'-avoiding permutation π', the candidate preimage ρ⁻¹ ∘ π' ∘ σ avoids S.
Given π' avoiding S', we propose the preimage π = ρ⁻¹ ∘ π' ∘ σ (written as `σ.trans (π'.trans ρ.symm)`). To verify that π avoids S, suppose for contradiction that n divides π(i) - i - s for some row i and offset s ∈ S. Applying the forward direction of hypothesis h at row i and column j = π(i) yields an offset s' ∈ S' such that n divides ρ(π(i)) - σ(i) - s'. Since ρ(π(i)) = π'(σ(i)), this becomes n ∣ π'(σ(i)) - σ(i) - s', contradicting the fact that π' avoids S' at row σ(i).
uses
Finset.mem_filter,Finset.mem_univ,true_and· intro π' hπ' refine ⟨σ.trans (π'.trans ρ.symm), ?_, ?_⟩ · simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hπ' ⊢ intro i s hs hdvd obtain ⟨s', hs', hd'⟩ := (h i ((σ.trans (π'.trans ρ.symm)) i)).1 ⟨s, hs, hdvd⟩ apply hπ' (σ i) s' hs' simpa using hd'
The candidate preimage maps to π', completing surjectivity.
By extensionality (`ext x`), evaluating the forward map on the candidate preimage at any x gives ρ(ρ⁻¹(π'(σ(σ⁻¹(x))))). Simplifying this composition cancels the inverse pairs ρ ∘ ρ⁻¹ and σ ∘ σ⁻¹, yielding π'(x).
· ext x; simp
Finset.card_bij- Two finite sets have the same cardinality if there exists a function between them that maps into the codomain, is injective, and is surjective.
Finset.mem_filter- An element belongs to the filtered sub-finset {x ∈ s | p x} if and only if it belongs to s and satisfies the predicate p.
Finset.mem_univ- Every element of a finite type belongs to its universal set Finset.univ.
true_and- The proposition True ∧ p is equivalent to p.
Equiv.ext- Two equivalences (or permutations) are equal if they agree on all inputs.
congrArg- Equal inputs produce equal outputs under any function: if a₁ = a₂, then f a₁ = f a₂.
- In Lean, `Equiv.trans e1 e2` denotes composition in diagrammatic order (first `e1`, then `e2`), so `(e1.trans e2) x = e2 (e1 x)`. Consequently, `σ.symm.trans (π.trans ρ)` corresponds in standard functional notation to $\rho \circ \pi \circ \sigma^{-1}$, and its inverse candidate `σ.trans (π'.trans ρ.symm)` corresponds to $\rho^{-1} \circ \pi' \circ \sigma$.
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.
theorem perm_offset_avoiding_count_eq_of_board_equiv (n : ℕ) (S S' : Finset ℤ) (σ ρ : Equiv.Perm (Fin n)) (h : ∀ i j : Fin n, (∃ s ∈ S, (n : ℤ) ∣ ((j : ℕ) : ℤ) - ((i : ℕ) : ℤ) - s) ↔ (∃ s ∈ S', (n : ℤ) ∣ ((ρ j : ℕ) : ℤ) - ((σ i : ℕ) : ℤ) - s)) : perm_offset_avoiding_count n S = perm_offset_avoiding_count n S' := by unfold perm_offset_avoiding_count refine Finset.card_bij (fun π _ => σ.symm.trans (π.trans ρ)) ?_ ?_ ?_ · intro π hπ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hπ ⊢ intro i s hs hdvd obtain ⟨s', hs', hd'⟩ := (h (σ.symm i) (π (σ.symm i))).2 ⟨s, hs, by simpa using hdvd⟩ exact hπ _ s' hs' hd' · intro a _ b _ hab refine Equiv.ext fun x => ?_ have := congrArg (fun e : Equiv.Perm (Fin n) => e (σ x)) hab simpa using this · intro π' hπ' refine ⟨σ.trans (π'.trans ρ.symm), ?_, ?_⟩ · simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hπ' ⊢ intro i s hs hdvd obtain ⟨s', hs', hd'⟩ := (h i ((σ.trans (π'.trans ρ.symm)) i)).1 ⟨s, hs, hdvd⟩ apply hπ' (σ i) s' hs' simpa using hd' · ext x; simp