AFTD Auto-Formalizing Theoretical Domains

perm_offset_avoiding_count_neg_one_one_eq_menage_of_odd

theoremverifiedformalization

For odd n >= 3 the number of permutations avoiding the offsets {-1, 1} mod n equals the menage number U(n).

Statement

theorem perm_offset_avoiding_count_neg_one_one_eq_menage_of_odd (n : ℕ) (hn : 3 ≤ n)
    (ho : Odd n) :
    perm_offset_avoiding_count n {-1, 1} = perm_offset_avoiding_count n {-1, 0}
Formalizes
arXiv:2610.23958 (Unranking S-avoiding permutations with two forbidden offsets), Proposition 6.2
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The proof shows that for odd n = 2m + 1, avoiding offsets {-1, 1} mod n is equinumerous with avoiding offsets {-1, 0} mod n (the ménage numbers) via a board isomorphism. Because n is odd, 2 is invertible modulo n with inverse m + 1. Permuting rows by σ(i) = i(m + 1) mod n and columns by ρ(j) = (j + 2m)(m + 1) mod n maps the forbidden offsets {-1, 1} bijectively onto {-1, 0}. The theorem then follows directly from the board equivalence principle perm_offset_avoiding_count_eq_of_board_equiv.

  1. Write n as an odd number N = 2m + 1.

    Since n is assumed to be odd, there is some natural number m such that n = 2m + 1. We name this odd modulus N = 2m + 1.

    lines 4–5

      obtain ⟨m, rfl⟩ := ho
      set N := 2 * m + 1 with hN
  2. In ℤ/Nℤ, 2(m + 1) = 1 and 2m = -1, so m + 1 is the multiplicative inverse of 2.

    Since N casts to 0 in ℤ/Nℤ by ZMod.natCast_self, we have 2m + 1 = 0. It follows by linear arithmetic that 2m = -1 and 2(m + 1) = 2m + 2 = 1.

    lines 6–10

    uses ZMod.natCast_self

      have hu : (2 : ZMod N) * ((m : ZMod N) + 1) = 1 := by
        have : ((N : ℕ) : ZMod N) = 0 := ZMod.natCast_self N
        rw [hN] at this; push_cast at this
        linear_combination this
      have h2m : (2 : ZMod N) * (m : ZMod N) = -1 := by linear_combination hu
  3. Multiplication by m + 1 is injective on offsets: if (a + c)(m + 1) = (b + c)(m + 1) in ℤ/Nℤ with a, b < N, then a = b in ℕ.

    Subtracting both sides gives ((a + c) - (b + c))(m + 1) = 0 by sub_mul and sub_self. Because 2(m + 1) = 1, multiplication by m + 1 has trivial kernel by zmod_mul_unit_half_eq_zero_iff, so (a + c) - (b + c) = 0 by sub_eq_zero, and hence a = b in ℤ/Nℤ by add_left_inj. Since a, b < N, each equals its own remainder modulo N by Nat.mod_eq_of_lt, which implies a = b in ℕ via ZMod.natCast_eq_natCast_iff'.

    lines 11–20

    uses ZMod.natCast_eq_natCast_iff', sub_mul, sub_self, zmod_mul_unit_half_eq_zero_iff, sub_eq_zero, add_left_inj, Nat.mod_eq_of_lt

      have hcast : ∀ a b : ℕ, (((a : ZMod N) = b) ↔ a % N = b % N) := fun a b =>
        ZMod.natCast_eq_natCast_iff' a b N
      have inj : ∀ c : ℕ, (∀ a b : ℕ, a < N → b < N →
          ((a : ZMod N) + c) * ((m : ZMod N) + 1) = ((b : ZMod N) + c) * ((m : ZMod N) + 1) → a = b) := by
        intro c a b ha hb hab
        have h1 : ((a : ZMod N) + c - (b + c)) * ((m : ZMod N) + 1) = 0 := by
          rw [sub_mul, hab, sub_self]
        rw [zmod_mul_unit_half_eq_zero_iff hu, sub_eq_zero, add_left_inj] at h1
        rw [hcast, Nat.mod_eq_of_lt ha, Nat.mod_eq_of_lt hb] at h1
        exact h1
  4. Define row and column transformations fσ, fρ : Fin N → Fin N by fσ(i) = i(m + 1) mod N and fρ(j) = (j + 2m)(m + 1) mod N, and compute their values in ℤ/Nℤ.

    Since N > 0 (by linear arithmetic via omega), reduction modulo N produces valid elements of Fin N by Nat.mod_lt. Casting to ℤ/Nℤ and applying ZMod.natCast_mod shows that fσ(i) = i(m + 1) and fρ(j) = (j + 2m)(m + 1) in ℤ/Nℤ.

    lines 21–29

    uses Nat.mod_lt, ZMod.natCast_mod

      have hNpos : 0 < N := by omega
      -- σ i = i (m + 1), ρ j = (j + 2m) (m + 1), mod N
      let fσ : Fin N → Fin N := fun i => ⟨(i.val * (m + 1)) % N, Nat.mod_lt _ hNpos⟩
      let fρ : Fin N → Fin N := fun j => ⟨((j.val + 2 * m) * (m + 1)) % N, Nat.mod_lt _ hNpos⟩
      have vσ : ∀ i, (((fσ i : ℕ) : ZMod N)) = ((i : ℕ) : ZMod N) * ((m : ZMod N) + 1) := by
        intro i; simp [fσ, ZMod.natCast_mod]
      have vρ : ∀ j, (((fρ j : ℕ) : ZMod N)) =
          (((j : ℕ) : ZMod N) + 2 * (m : ZMod N)) * ((m : ZMod N) + 1) := by
        intro j; simp [fρ, ZMod.natCast_mod]
  5. The maps fσ and fρ are injective, and therefore define permutations σ and ρ of Fin N.

    Applying the canonical projection to ℤ/Nℤ with congrArg and using Fin.ext together with the injectivity lemma from the previous step (for c = 0 and c = 2m respectively) shows that fσ and fρ are injective. By Finite.injective_iff_bijective.mp, an injective endofunction on a finite set is bijective, so Equiv.ofBijective packages fσ and fρ into permutations σ, ρ of Fin N.

    lines 30–41

    uses congrArg, Fin.ext, Finite.injective_iff_bijective.mp, Equiv.ofBijective

      have injσ : Function.Injective fσ := by
        intro a b hab
        have := congrArg (fun x : Fin N => ((x : ℕ) : ZMod N)) hab
        simp only [vσ] at this
        exact Fin.ext (inj 0 a b a.isLt b.isLt (by simpa using this))
      have injρ : Function.Injective fρ := by
        intro a b hab
        have := congrArg (fun x : Fin N => ((x : ℕ) : ZMod N)) hab
        simp only [vρ] at this
        exact Fin.ext (inj (2 * m) a b a.isLt b.isLt (by push_cast; exact this))
      let σ : Equiv.Perm (Fin N) := Equiv.ofBijective fσ (Finite.injective_iff_bijective.mp injσ)
      let ρ : Equiv.Perm (Fin N) := Equiv.ofBijective fρ (Finite.injective_iff_bijective.mp injρ)
  6. It suffices to show that the permutations (σ, ρ) map the forbidden offsets {-1, 1} bijectively to {-1, 0}.

    By perm_offset_avoiding_count_eq_of_board_equiv, two offset avoidance problems have identical permutation counts if there exist row and column permutations σ and ρ such that a position (i, j) has offset j - i ∈ {-1, 1} mod N if and only if (σ(i), ρ(j)) has offset ρ(j) - σ(i) ∈ {-1, 0} mod N.

    line 42

    uses perm_offset_avoiding_count_eq_of_board_equiv

      apply perm_offset_avoiding_count_eq_of_board_equiv N _ _ σ ρ
  7. The avoidance conditions translate in ℤ/Nℤ to (j - i - (-1) = 0 ∨ j - i - 1 = 0) on the left and (ρ(j) - σ(i) - (-1) = 0 ∨ ρ(j) - σ(i) - 0 = 0) on the right.

    Divisibility by N in ℤ is equivalent to vanishing in ℤ/Nℤ by ZMod.intCast_zmod_eq_zero_iff_dvd. Expanding set membership in {-1, 1} and {-1, 0} with Finset.mem_insert and Finset.mem_singleton, eliminating existentials with exists_eq_or_imp and exists_eq_left, pushing integer casts (Int.cast_sub, Int.cast_neg, Int.cast_one, Int.cast_natCast, Int.cast_zero), evaluating the permutations via Equiv.ofBijective_apply, and substituting the algebraic formulas for fσ and fρ gives the two disjunctions.

    lines 43–49

    uses ZMod.intCast_zmod_eq_zero_iff_dvd, Finset.mem_insert, Finset.mem_singleton, exists_eq_or_imp, exists_eq_left, Int.cast_sub, Int.cast_neg, Int.cast_one, Int.cast_natCast, Int.cast_zero, Equiv.ofBijective_apply

      intro i j
      have dv : ∀ x : ℤ, (N : ℤ) ∣ x ↔ (x : ZMod N) = 0 := fun x =>
        (ZMod.intCast_zmod_eq_zero_iff_dvd x N).symm
      simp only [Finset.mem_insert, Finset.mem_singleton, exists_eq_or_imp, exists_eq_left, dv,
        Int.cast_sub, Int.cast_neg, Int.cast_one, Int.cast_natCast, Int.cast_zero]
      simp only [σ, ρ, Equiv.ofBijective_apply]
      rw [vσ, vρ]
  8. The transformed expressions factor as ρ(j) - σ(i) - (-1) = (j - i + 1)(m + 1) and ρ(j) - σ(i) - 0 = (j - i - 1)(m + 1), which vanish if and only if j - i + 1 = 0 or j - i - 1 = 0.

    Using 2m = -1 and 2(m + 1) = 1 in ℤ/Nℤ, ring algebra shows that (j + 2m)(m + 1) - i(m + 1) - (-1) = (j - i + 1)(m + 1) and (j + 2m)(m + 1) - i(m + 1) - 0 = (j - i - 1)(m + 1). Because m + 1 is a unit with inverse 2, zmod_mul_unit_half_eq_zero_iff allows cancelling m + 1, reducing each term to j - i + 1 = 0 and j - i - 1 = 0.

    lines 50–56

    uses zmod_mul_unit_half_eq_zero_iff

      have e1 : ∀ J I : ZMod N, (J + 2 * (m : ZMod N)) * ((m : ZMod N) + 1) - I * ((m : ZMod N) + 1) - -1
          = (J - I + 1) * ((m : ZMod N) + 1) := fun J I => by
        linear_combination ((m : ZMod N) + 1) * h2m - hu
      have e2 : ∀ J I : ZMod N, (J + 2 * (m : ZMod N)) * ((m : ZMod N) + 1) - I * ((m : ZMod N) + 1) - 0
          = (J - I - 1) * ((m : ZMod N) + 1) := fun J I => by
        linear_combination ((m : ZMod N) + 1) * h2m
      rw [e1, e2, zmod_mul_unit_half_eq_zero_iff hu, zmod_mul_unit_half_eq_zero_iff hu]
  9. The conditions j - i - (-1) = 0 ∨ j - i - 1 = 0 and j - i + 1 = 0 ∨ j - i - 1 = 0 are equivalent, completing the proof.

    We split the equivalence into both directions with constructor. Since -(-1) = 1 in any ring, the two disjuncts on the left are identical to the two disjuncts on the right, and each branch is closed by linear arithmetic.

    lines 57–63

      constructor
      · rintro (h | h)
        · left; linear_combination h
        · right; linear_combination h
      · rintro (h | h)
        · left; linear_combination h
        · right; linear_combination h
ZMod.natCast_self
In the ring ℤ/nℤ, the integer n casts to 0.
ZMod.natCast_eq_natCast_iff'
In ℤ/cℤ, two natural numbers have equal residue if and only if their remainders modulo c are equal.
sub_mul
Multiplication distributes over subtraction from the right: (a - b) * c = a * c - b * c.
sub_self
Subtracting any element from itself gives zero: a - a = 0.
zmod_mul_unit_half_eq_zero_iff
In ℤ/nℤ, if 2u = 1 (so u is an invertible element with inverse 2), then xu = 0 if and only if x = 0.
sub_eq_zero
In an additive group, a - b = 0 if and only if a = b.
add_left_inj
Adding an element on the right is injective: b + a = c + a if and only if b = c.
Nat.mod_eq_of_lt
If a < b, then the remainder a % b equals a.
Nat.mod_lt
If y > 0, the remainder x % y is strictly less than y.
ZMod.natCast_mod
In ℤ/nℤ, the natural number remainder a % n casts to the same element as a.
congrArg
Applying a function to equal arguments yields equal results.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Finite.injective_iff_bijective.mp
An injective map from a finite set to itself is bijective.
Equiv.ofBijective
A bijective map can be packaged as a permutation (equivalence).
perm_offset_avoiding_count_eq_of_board_equiv
Permuting rows by σ and columns by ρ preserves the count of offset-avoiding permutations, provided it bijectively maps the forbidden board cells for offset set S to those for S'.
ZMod.intCast_zmod_eq_zero_iff_dvd
An integer x casts to 0 in ℤ/Nℤ if and only if N divides x.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
exists_eq_or_imp
An existential quantifier over a disjunction with an equality (a = a' ∨ q a) simplifies to testing a' or the remainder.
exists_eq_left
An existential quantifier with an equality constraint ∃ a, a = a' ∧ p a simplifies to p a'.
Int.cast_sub
Integer cast preserves subtraction: ↑(m - n) = ↑m - ↑n.
Int.cast_neg
Integer cast preserves negation: ↑(-n) = -↑n.
Int.cast_one
Integer cast preserves 1: ↑1 = 1.
Int.cast_natCast
Casting a natural number through ℤ to a ring is the same as casting directly from ℕ.
Int.cast_zero
Integer cast preserves 0: ↑0 = 0.
Equiv.ofBijective_apply
Applying an equivalence defined by Equiv.ofBijective to an element is the same as evaluating the underlying function.

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_neg_one_one_eq_menage_of_odd (n : ℕ) (hn : 3 ≤ n)    (ho : Odd n) :    perm_offset_avoiding_count n {-1, 1} = perm_offset_avoiding_count n {-1, 0} := by  obtain ⟨m, rfl⟩ := ho  set N := 2 * m + 1 with hN  have hu : (2 : ZMod N) * ((m : ZMod N) + 1) = 1 := by    have : ((N : ℕ) : ZMod N) = 0 := ZMod.natCast_self N    rw [hN] at this; push_cast at this    linear_combination this  have h2m : (2 : ZMod N) * (m : ZMod N) = -1 := by linear_combination hu  have hcast : ∀ a b : ℕ, (((a : ZMod N) = b) ↔ a % N = b % N) := fun a b =>    ZMod.natCast_eq_natCast_iff' a b N  have inj : ∀ c : ℕ, (∀ a b : ℕ, a < N → b < N →      ((a : ZMod N) + c) * ((m : ZMod N) + 1) = ((b : ZMod N) + c) * ((m : ZMod N) + 1) → a = b) := by    intro c a b ha hb hab    have h1 : ((a : ZMod N) + c - (b + c)) * ((m : ZMod N) + 1) = 0 := by      rw [sub_mul, hab, sub_self]    rw [zmod_mul_unit_half_eq_zero_iff hu, sub_eq_zero, add_left_inj] at h1    rw [hcast, Nat.mod_eq_of_lt ha, Nat.mod_eq_of_lt hb] at h1    exact h1  have hNpos : 0 < N := by omega  -- σ i = i (m + 1), ρ j = (j + 2m) (m + 1), mod N  let fσ : Fin N → Fin N := fun i => ⟨(i.val * (m + 1)) % N, Nat.mod_lt _ hNpos⟩  let fρ : Fin N → Fin N := fun j => ⟨((j.val + 2 * m) * (m + 1)) % N, Nat.mod_lt _ hNpos⟩  have vσ : ∀ i, (((fσ i : ℕ) : ZMod N)) = ((i : ℕ) : ZMod N) * ((m : ZMod N) + 1) := by    intro i; simp [fσ, ZMod.natCast_mod]  have vρ : ∀ j, (((fρ j : ℕ) : ZMod N)) =      (((j : ℕ) : ZMod N) + 2 * (m : ZMod N)) * ((m : ZMod N) + 1) := by    intro j; simp [fρ, ZMod.natCast_mod]  have injσ : Function.Injective fσ := by    intro a b hab    have := congrArg (fun x : Fin N => ((x : ℕ) : ZMod N)) hab    simp only [vσ] at this    exact Fin.ext (inj 0 a b a.isLt b.isLt (by simpa using this))  have injρ : Function.Injective fρ := by    intro a b hab    have := congrArg (fun x : Fin N => ((x : ℕ) : ZMod N)) hab    simp only [vρ] at this    exact Fin.ext (inj (2 * m) a b a.isLt b.isLt (by push_cast; exact this))  let σ : Equiv.Perm (Fin N) := Equiv.ofBijective fσ (Finite.injective_iff_bijective.mp injσ)  let ρ : Equiv.Perm (Fin N) := Equiv.ofBijective fρ (Finite.injective_iff_bijective.mp injρ)  apply perm_offset_avoiding_count_eq_of_board_equiv N _ _ σ ρ  intro i j  have dv : ∀ x : ℤ, (N : ℤ) ∣ x ↔ (x : ZMod N) = 0 := fun x =>    (ZMod.intCast_zmod_eq_zero_iff_dvd x N).symm  simp only [Finset.mem_insert, Finset.mem_singleton, exists_eq_or_imp, exists_eq_left, dv,    Int.cast_sub, Int.cast_neg, Int.cast_one, Int.cast_natCast, Int.cast_zero]  simp only [σ, ρ, Equiv.ofBijective_apply]  rw [vσ, vρ]  have e1 : ∀ J I : ZMod N, (J + 2 * (m : ZMod N)) * ((m : ZMod N) + 1) - I * ((m : ZMod N) + 1) - -1      = (J - I + 1) * ((m : ZMod N) + 1) := fun J I => by    linear_combination ((m : ZMod N) + 1) * h2m - hu  have e2 : ∀ J I : ZMod N, (J + 2 * (m : ZMod N)) * ((m : ZMod N) + 1) - I * ((m : ZMod N) + 1) - 0      = (J - I - 1) * ((m : ZMod N) + 1) := fun J I => by    linear_combination ((m : ZMod N) + 1) * h2m  rw [e1, e2, zmod_mul_unit_half_eq_zero_iff hu, zmod_mul_unit_half_eq_zero_iff hu]  constructor  · rintro (h | h)    · left; linear_combination h    · right; linear_combination h  · rintro (h | h)    · left; linear_combination h    · right; linear_combination h
See it in the graphDiscuss this resultChallenge it