Symmetry Reduction in the Superpattern Problem

The problem

A permutation π contains a pattern σ if some entries of π appear in the same relative order as σ. For example, 35124 contains 213 through its entries 3, 1, 4. A k-superpattern contains every permutation of length k. For instance, 25314 contains all six patterns of length 3, so the shortest 3-superpattern has length at most 5.

The shortest possible length, m(k), is a long-standing open problem. The best known bounds are

k²(1/e² + o(1)) ≤ m(k) ≤ ⌈(k² + 1)/2⌉

The lower bound is counting: a permutation of length n has only (n choose k) subsequences but must realize all k! patterns. The upper bound is Engen and Vatter’s construction, which concatenates alternating ascending and descending runs. Neither bound is sharp, and the construction treats every pattern the same way, ignoring any structure inside subclasses of patterns.

Symmetry reduction

Draw a permutation as dots on a grid. The eight symmetries of the square (reverse, complement, inverse, and their compositions: the dihedral group D₈) act on these plots. Every one of them preserves pattern containment, so π is a k-superpattern exactly when its image under any symmetry is.

That suggests a family of relaxations. For each subgroup G ≤ D₈, let a_G(k) be the length of the shortest permutation that contains one representative of every G-orbit of patterns. The trivial subgroup recovers the classical m(k), and the family forms a lattice: more symmetry means fewer orbits to cover, so a larger subgroup never needs a longer permutation.

Result 1: symmetry alone is not enough

Covering k!/|G| orbits with (n choose k) subsequences still forces

a_G(k) ≥ (1/e² + o(1)) k² for every G ≤ D₈.

A subgroup has at most 8 elements, and dividing k! by a constant doesn’t change the k² leading term. So no symmetry reduction by itself can beat the quadratic barrier. Any real savings has to come from structure inside a subclass of patterns, which is exactly what the uniform Engen–Vatter construction ignores.

Result 2: the involution branch

I focus on the inverse symmetry ι, the reflection of the plot across its main diagonal. Its orbits come in two kinds:

• involutions (σ = σ⁻¹, plots symmetric about the diagonal), which are their own orbit, and
• inverse pairs {σ, σ⁻¹} for everything else.

That splits the problem into two parts:

a_⟨ι⟩(k) ≤ m_inv(k) + m_nonInv(k)

where m_inv(k) is the shortest permutation containing every involution, and m_nonInv(k) the shortest containing one representative of every inverse pair.

Involutions are rare. There are only about √k! of them (Moser–Wyman, Knuth). Rerunning the counting argument with that smaller target gives

m_inv(k) ≥ (1/e^3/2 + o(1)) k^3/2.

This is the only sub-quadratic counting bound in this framework. It leaves open a wide gap, between order k^3/2 and the k²/2 of the general upper bound, where sub-quadratic behavior is possible.

New tools for the gap

An involution is exactly an ordered matching: 3412 pairs up positions {1–3, 2–4}. Pattern containment between involutions becomes induced sub-matching containment. That opens up three toolkits:

• RSK: involutions correspond to standard Young tableaux, which brings in hook lengths and the longest increasing and decreasing subsequences.
• Arc diagrams: crossing and nesting statistics, and arc-by-arc recursion.
• Inverse closure: a container for involutions gets inverses for free.

Open questions

• Is m_inv(k) = Θ(k^3/2)? The lower bound is proved; no sub-k² construction is known yet.
• Computation: find m_inv(k) exactly for k ≤ 6 and see whether the k^3/2 scale appears.
• The other half: bound m_nonInv(k), the one-representative-per-inverse-pair problem.
• Other fixed-point classes: permutations fixed by rc or ιrc are also only about √k! in number.
• Modify Engen–Vatter for involutions, possibly reaching order k^3/2.

I presented this work as a talk and a poster at UMRS in spring 2026. The slides are below.