perm_offset_avoiding_count_neg_one_one_eq_menage_of_odd
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
- 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…
- perm_offset_avoiding_count_eq_of_board_equivIf 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…
- zmod_mul_unit_half_eq_zero_iffIn ZMod n, if 2u = 1 then x u = 0 iff x = 0.
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.
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.
obtain ⟨m, rfl⟩ := ho set N := 2 * m + 1 with hN
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.
uses
ZMod.natCast_selfhave 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
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'.
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_lthave 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
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ℤ.
uses
Nat.mod_lt,ZMod.natCast_modhave 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]
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.
uses
congrArg,Fin.ext,Finite.injective_iff_bijective.mp,Equiv.ofBijectivehave 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ρ)
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.
uses
perm_offset_avoiding_count_eq_of_board_equivapply perm_offset_avoiding_count_eq_of_board_equiv N _ _ σ ρ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.
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_applyintro 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ρ]
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.
uses
zmod_mul_unit_half_eq_zero_iffhave 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]
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.
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
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_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