Simple members of D

Abstract

Every simple permutation of size n at least four in D has even size n = 2h with h at least two and equals P(h).

Theorem 1.1 (Simple members of D).

Lean statement: D5/S3/Combinatorics/PopStack/PopStackClassification.simple_inD

Proof. Machine-checked in Lean as D5/S3/Combinatorics/PopStack/PopStackClassification.simple_inD (✓ std3). ∎

Source. Repository-derived.

Acknowledgement. Lapo Cioni, Luca Ferrari, Rebecca Smith (2025). Sorting permutations using a pop stack with a bypass. DOI: 10.1016/j.disc.2025.114964. URL: https://arxiv.org/abs/2503.08285v1.

Commentary.

Every simple permutation of size n at least four in D has even size n = 2h with h at least two and equals P(h).