AFTD Auto-Formalizing Theoretical Domains

perm_offset_avoiding_count_four

theoremverified

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.

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

    line 2

        perm_offset_avoiding_count 4 {-1, 0} = 2 ∧ perm_offset_avoiding_count 4 {-1, 1} = 4 := by decide

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_four :    perm_offset_avoiding_count 4 {-1, 0} = 2 ∧ perm_offset_avoiding_count 4 {-1, 1} = 4 := by decide
See it in the graphDiscuss this resultChallenge it