Nakamura's conjecture for consecutive patterns of length seven

Two permutation patterns are c-Wilf equivalent when, for every n, the same number of permutations of size n avoid each of them as a consecutive pattern. They are strongly c-Wilf equivalent when the whole distribution of the number of occurrences agrees. Nakamura conjectured that c-Wilf equivalence implies strong c-Wilf equivalence. We prove the conjecture for patterns of length 7: the 5040 patterns fall into 329 c-Wilf classes, and each class is a single strong class. The proof uses the cluster method. Cluster numbers up to cluster length 27 separate exactly 329 classes, and every pair of patterns in a class is then linked by a chain of known equivalences and two new criteria: Local rearrangement (Theorem A). This criterion swaps a few entries of a pattern without changing its cluster numbers. It settles 22 pairs. Gluing at one-point overlaps (Theorem B). This criterion reduces the comparison of all chains to runs over a single shift. It settles the 9 remaining pairs. For each pair, an explicit bijection between the linear extensions of the runs, valid for every run length, keeps the ranks of the first and last position. For length 8 the same method leaves 71 of 1330 classes undecided. The proof is checked in Lean 4 (core library, no Mathlib). The kernel-checked part covers: the separation of the 329 classes; a certificate linking all 5040 patterns to their class representatives; Theorems A and B in general, together with all 31 of their applications. The final Lean theorem assumes only the cited results: invariance under reversal and complement; the criterion of Dwyer and Elizalde; the criterion of Khoroshkin and Shapiro. The link between cluster numbers and occurrence distributions is the cluster method of Elizalde and Noy, and it is cited rather than formalised. The archive contains the paper (LaTeX source and PDF), the programs and data for the cluster computations and certificates, logs, and the Lean development with its build script and generators.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-08
DOI
https://doi.org/10.5281/zenodo.24052489
Primary Topic
Advanced Combinatorial Mathematics
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Nakamura's conjecture for consecutive patterns of length seven

William Huanshan Chuang
2 links
Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
preprint

Nakamura's conjecture for consecutive patterns of length seven

William Huanshan Chuang
preprint en

Abstract

Two permutation patterns are c-Wilf equivalent when, for every n, the same number of permutations of size n avoid each of them as a consecutive pattern. They are strongly c-Wilf equivalent when the whole distribution of the number of occurrences agrees. Nakamura conjectured that c-Wilf equivalence implies strong c-Wilf equivalence. We prove the conjecture for patterns of length 7: the 5040 patterns fall into 329 c-Wilf classes, and each class is a single strong class. The proof uses the cluster method. Cluster numbers up to cluster length 27 separate exactly 329 classes, and every pair of patterns in a class is then linked by a chain of known equivalences and two new criteria: Local rearrangement (Theorem A). This criterion swaps a few entries of a pattern without changing its cluster numbers. It settles 22 pairs. Gluing at one-point overlaps (Theorem B). This criterion reduces the comparison of all chains to runs over a single shift. It settles the 9 remaining pairs. For each pair, an explicit bijection between the linear extensions of the runs, valid for every run length, keeps the ranks of the first and last position. For length 8 the same method leaves 71 of 1330 classes undecided. The proof is checked in Lean 4 (core library, no Mathlib). The kernel-checked part covers: the separation of the 329 classes; a certificate linking all 5040 patterns to their class representatives; Theorems A and B in general, together with all 31 of their applications. The final Lean theorem assumes only the cited results: invariance under reversal and complement; the criterion of Dwyer and Elizalde; the criterion of Khoroshkin and Shapiro. The link between cluster numbers and occurrence distributions is the cluster method of Elizalde and Noy, and it is cited rather than formalised. The archive contains the paper (LaTeX source and PDF), the programs and data for the cluster computations and certificates, logs, and the Lean development with its build script and generators.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon