perm_offset_avoiding_count_four
Sanity check: U(4) = 2, and there are 4 permutations of 4 elements avoiding the offsets -1 and 1.
Statement
theorem perm_offset_avoiding_count_four :
perm_offset_avoiding_count 4 {-1, 0} = 2 ∧ perm_offset_avoiding_count 4 {-1, 1} = 4- Source
- sanity check for perm_offset_avoiding_count (PR-300)
- 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…
The proof, explained
The theorem establishes explicit counts for permutations of 4 elements that avoid specified circular offsets modulo 4: exactly 2 permutations avoid offsets $\{-1, 0\}$, and exactly 4 avoid $\{-1, 1\}$. Because the symmetric group $S_4$ has only $4! = 24$ elements, the property is finite and completely decidable. The proof proceeds by direct computation, verifying the counts through exhaustive enumeration of all 24 permutations.
$\mathrm{perm\_offset\_avoiding\_count}(4, \{-1, 0\}) = 2 \land \mathrm{perm\_offset\_avoiding\_count}(4, \{-1, 1\}) = 4$ automation
Because the symmetric group $S_4$ contains only $4! = 24$ elements and the offset-avoiding condition $\pi(i) - i \not\equiv s \pmod 4$ is decidable for each permutation and offset, the statement is a finite, decidable proposition. Lean's `decide` tactic checks all 24 permutations and confirms both counts by direct evaluation.
perm_offset_avoiding_count 4 {-1, 0} = 2 ∧ perm_offset_avoiding_count 4 {-1, 1} = 4 := by decide
- The proof is completed entirely by computational reflection (`decide`), exhaustively testing all 24 permutations of a 4-element set and counting the valid ones.
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_four : perm_offset_avoiding_count 4 {-1, 0} = 2 ∧ perm_offset_avoiding_count 4 {-1, 1} = 4 := by decide