AFTD Auto-Formalizing Theoretical Domains

perm_offset_avoiding_count_eq_of_board_equiv

theoremverified

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

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.

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

    lines 6–7

    uses Finset.card_bij

      unfold perm_offset_avoiding_count
      refine Finset.card_bij (fun π _ => σ.symm.trans (π.trans ρ)) ?_ ?_ ?_
  2. 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).

    lines 8–12

    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'
  3. 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).

    lines 13–16

    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
  4. 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).

    lines 17–23

    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'
  5. 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).

    line 24

        · 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₂.

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

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