Descent sets of a permutation and its inverse

Richard Stanley asked how many pairs (S, T) of subsets of {1, …, n−1} arise as the descent sets of a permutation w of {1, …, n} and of its inverse, and what the growth rate L = lim f(n)^(1/n) is. The paper proves that almost every pair arises, 1 − f(n)/4^(n−1) ≤ 6e^(−n/150) for every n, so L = 4. An elementary obstruction (if T contains |S| + 1 consecutive integers, the pair cannot occur) gives f(n) ≤ 4^(n−1) − 3^(n−1) + 1, so the rate cannot exceed log(4/3). The pairs violating a necessary condition of Gale–Ryser type have proportion (3/4)^(n+O(log² n)), so the rate is exactly log(4/3) if a dominance-order criterion for occurrence, checked by computation for n ≤ 20, is correct. It also finds the asymptotics of the number of permutations w such that w and w⁻¹ are both alternating, g(n) = (16/π²)(4/π²)^n n! (1 + π⁴/(48n) + O(n⁻²)), confirming Stanley’s prediction, and checks Gessel’s conjecture on the largest class for n ≤ 22.

The question is Stanley’s (MathOverflow question 486548). The proof that L = 4 was first posted as the author’s MathOverflow answer on 7 October 2026.

Preprint, 8 October 2026.

Status. All proved results are formally verified in Lean 4 and all computations were independently rechecked; the proofs have not yet been checked line by line by a human. Origin. The results and proofs were found with the AI systems Claude (Anthropic) and Codex (OpenAI), directed by the author.