← All problems

Signed cycle-type restriction polynomiality conjecture

5 years old · traced to

Let nn be a positive integer, let kk be a fixed positive integer with 1≤k≤n1\leq k\leq n, and let Sn\mathfrak{S}_n denote the symmetric group on nn elements. For π∈Sn\pi\in\mathfrak{S}_n, let type⁡(π)\operatorname{type}(\pi) be its cycle type, and let RLMv⁡(π)\operatorname{RLMv}(\pi) and EXCv⁡(π)\operatorname{EXCv}(\pi) denote its right-to-left-minimum-value and excedance-value multisets, respectively. Then the polynomiality conjecture.

∑π∈Snmin⁡(type⁡(π))≥k(−1)inv⁡(π)xRLMv⁡(π)yEXCv⁡(π)\sum_{\substack{\pi\in\mathfrak{S}_n\min(\operatorname{type}(\pi))\geq k}}(-1)^{\operatorname{inv}(\pi)}\mathbf{x}_{\operatorname{RLMv}(\pi)}\mathbf{y}_{\operatorname{EXCv}(\pi)}

is an element of N[x1,…,xn,y1,…,yn]\mathbb{N}[x_1,\dotsc,x_n,y_1,\dotsc,y_n]. This generalizes the derangement case by imposing a lower bound on the lengths of all cycles; the source provides no resolution or further evidence for the claim, so its status remains open.

References
  1. Per Alexandersson and Frether Getachew Kebede, “An involution on derangements preserving excedances and right-to-left minima”, arXiv:2105.08455 (2022).

Progress summary

Refreshed
Open · progress reported

A reader-submitted argument claims the conjecture fails for cycles of length three or more, but no independent verification was found.

The conjecture asserts that a signed generating polynomial remains coefficientwise nonnegative when every permutation cycle has length at least kk. The catalogue source reported no resolution as of May 2021.

Community submission (unverified), November 7, 2026

A submitted proof argues that the conjecture fails at k=3k=3 for every n≥8n \ge 8, by reducing a coefficient to eight permutations and obtaining normalized coefficient −1-1; it also reports computation for n≤7n \le 7. This is an unverified community claim, not an established counterexample.

Current status (as of November 2026): the conjecture has a recent unverified claimed refutation at k=3k=3 for all n≥8n \ge 8, while no independently verified resolution or counterexample is recorded.

Sources

Solutions 1

Conjecture 5.2.1 fails at k = 3 for every n >= 8 (ordinary proof; Lean certifies n = 9 for both the version-of-record and the MathDB/arXiv v3 wording); it holds for all 2 <= k <= n when n <= 7 (computation)See full solutionHide full solution

For the restriction to cycles of length at least three, a forced-prefix argument reduces the relevant coefficient to eight permutations; five survive the restriction, giving normalized coefficient -1 for every n >= 8. This is a complete ordinary proof of the infinite family. The supplied Lean certificate proves the n = 9 counterinstance for both the journal and MathDB/arXiv formulations; it does not formalize the infinite family.

Result and scope: Conjecture 5.2.1 fails at k = 3 for every n >= 8 (ordinary proof; Lean certifies n = 9 for both the version-of-record and the MathDB/arXiv v3 wording); it holds for all 2 <= k <= n when n <= 7 (computation)

Complete proof and verification sources: A negative coefficient for every n >= 8 in the Alexandersson-Kebede cycle-restricted signed sum: a refutation of Conjecture 5.2.1 (Australas. J. Combin. 86(3) (2023)) · PDF.

The paper page includes the supplementary proof-source JSON attachment and extract_sources.py, which reconstruct the archived proof and verification sources. The linked paper gives the complete rigorous argument and specifies exactly which statements are formalized.

This is an AI-assisted research preprint. Internal review is not external journal peer review; bounded prior-art searches do not certify worldwide priority. See the paper for the source, interpretation, formalization, and trust limitations.