Date: 21 November 2026. Status: complete proposed proof of Conjectures 1 and 3, independently checked within this research campaign; external review remains open. The bounded priority audit is recorded separately.
Statement and attribution
Chen, Kitaev and Zhang, Distributions of statistics on separable permutations, Discrete Applied Mathematics 355 (2024), 169–179, DOI 10.1016/j.dam.2024.05.004, conclude with three conjectures. The author manuscript specifies the following two targets.
- For every length at least three, each of the four record-count distributions on separable permutations is unimodal with a maximum at two records.
- On reducible separable permutations, the right-maxima and left-minima distributions are weakly decreasing from one record. The same holds for left maxima and right minima on irreducible separable permutations, at every positive length.
These are Conjectures 1 and 3, respectively. “Irreducible” means indecomposable under direct sum; the singleton is irreducible, and the empty permutation belongs to neither positive class. Records are strict and unshifted.
The proof below supplies the missing comparisons involving one, two and three records, and combines them with the all-index declining tail used in the previously public proof of Conjecture 2. That tail method is due to the trureturing project. Its ordinary-mathematics manuscript, especially Theorems 7.2, 8.2 and 8.3, gives the complete argument. Sections 3–5 reconstruct that argument, with independently regenerated exact certificates, so the present proof can be checked without trusting a claim about a formal build. No new credit is claimed for Conjecture 2 or its Newton-kernel method. No Lean work is performed here.
The current literature audit found no earlier complete statement of Conjecture 1 or 3 in the inspected material. This remains a bounded priority finding; see the separate source audit.
1. Generating functions from the actual permutation classes
Let count nonempty separable permutations by length. Every nontrivial separable permutation is decomposable under exactly one of direct sum and skew sum. Complementation interchanges these two types. The unique decomposition into direct-indecomposable components consequently gives
Write . Thus , , , and for every , either from the displayed equation or by adjoining a final largest entry.
Let count all nonempty separable permutations by length and number of right maxima. Let count the direct-indecomposable ones. Only the last direct-sum component contributes right maxima, so
Let count skew-indecomposable separable permutations. Their skew decomposition adds record counts, while a nontrivial skew-indecomposable separable permutation is direct-decomposable. Therefore
Eliminating gives the source-faithful quadratic
Equivalently, with ,
The series has nonnegative coefficients. If , coefficient extraction yields
For the Conjecture 3 classes, let . Its first record coefficient is , and
The reducible-right-maxima series is . Reverse-complement preserves direct decomposability and exchanges right maxima with left minima. Reversal exchanges the direct and skew types at lengths at least two and exchanges right with left maxima. Inversion preserves the direct type and exchanges left maxima with right minima. Consequently the four Conjecture 3 distributions are precisely or , with the singleton correction stated above. Reverse and complement give equality of all four unrestricted record distributions.
2. The three missing low-record comparisons
We prove
Here means that every coefficient of is nonnegative.
The Schröder recurrence, obtained by differentiating the quadratic for , is
Reducing (3) modulo gives, beyond the indicated initial terms,
Apply (7) repeatedly. Each expression is
with the following exact polynomials.
| Difference | ||||
|---|---|---|---|---|
For every , both and are positive. In the middle row their sum is
In the first and third rows the sums are and , respectively. Thus the numerator of (8) is
The remaining coefficients, obtained directly from the quadratic, are:
| Series | Indices | Coefficients |
|---|---|---|
This proves (5) and (6). These are uniform inequalities over all lengths. The recurrence reductions in (8) are symbolic polynomial identities, not an extrapolation from these initial values.
3. A self-contained version of the known declining tail
This section and the next two reconstruct the prior trureturing argument cited above. The needed conclusion is
where .
Use an independent variable and set
Define polynomials by the Motzkin generating function
They have the explicit nonnegative-coefficient expression
Differentiating the quadratic and eliminating gives
Comparing coefficients proves, for every ,
Let
The key coefficient sign law is
4. Exact certificates for the sign law
For any polynomial define
Differentiating gives
Hence and imply : the derivative of is the composition , and integration divides its nonnegative coefficients by positive integers.
This test has a finite exact certificate. Write . Set and
If these integers are nonnegative, all subsequent coefficients of are nonnegative by the recurrence .
Put
Apply the certificate to the following sixteen explicitly specified polynomials. The complete coefficient lists and prefixes are in ckz_certificates.json; the table records the degree, the minimum of the entire checked prefix, and its final two coefficients. Formula (10) specifies each polynomial exactly.
| Degree | Prefix minimum | Final two prefix coefficients | |
|---|---|---|---|
| 7 | 4 | 2224, 5372 | |
| 9 | 4 | 65048, 157044 | |
| 11 | 1 | 1396800, 3372180 | |
| 13 | 0 | 28929352, 69841644 | |
| 15 | 0 | 595325008, 1437241724 | |
| 17 | 0 | 12268912216, 29619774292 | |
| 19 | 0 | 253749072288, 612604451796 | |
| 21 | 0 | 5268900164232, 12720250235340 | |
| 23 | 0 | 109820457718256, 265130038449532 | |
| 25 | 0 | 2296951016145560, 5545330295285428 | |
| 27 | 0 | 48191416390935808, 116344371040966548 | |
| 29 | 0 | 1013887358943381960, 2447740612679751468 | |
| 7 | 3 | 2252, 5440 | |
| 9 | 1 | 70668, 170612 | |
| 31 | 0 | 5530646749767915772, 13352162391984380168 | |
| 33 | 0 | 122941413579146512220, 296806828040095303908 |
Their constant terms are nonnegative. Consequently (13) holds for . Recurrence (11), after multiplication by or and substitution , propagates the last four certificates to
There is no sign loss in this induction: and have nonnegative coefficients and all scalar factors in (11) are positive.
Substitution of (11) in (12) gives the exact identity
For , the first two terms are nonnegative after composition. The remaining factor obeys
and all have nonnegative coefficients. Therefore (14) proves (13) for every remaining index. This is an unbounded induction; its sixteen certificates do not impose a cutoff on the conjectures.
5. Returning from the kernels to actual record counts
Let . Its coefficient at is
and it satisfies . Direct substitution shows that
is the unique zero-constant-term solution of
Comparing with the actual quadratic (1) gives , and hence
Apply Pascal's identity twice to the adjacent rows in (15), and use . For every this gives
The sign law (13) proves (9), with no omitted class-identification assumption or low-length exception.
6. Completion of the two conjectures
Since , equation (9) proves for every . Section 2 proves the comparison and the rise from one to two at every length at least three. Thus
The first inequality is strict. Equidistribution under reversal and complementation proves Conjecture 1 for all four record statistics.
For , equations (4) and the just-proved tail imply
Section 2 supplies . The series has the same rows at lengths at least two; its length-one row is zero and is also weakly decreasing. The exact class transports in Section 1 now prove Conjecture 3, including its singleton convention.
Reproduction and scope of checks
Run python3 verify.py in the directory containing the script. Only Python's standard library is required. It regenerates all sixteen certificates, checks their complete nonnegative prefixes and their exact polynomial remainder identities, verifies the universal reduction (14), and checks the three low-record identities symbolically in the variable . As a separate convention check, it enumerates the actual separable permutations through length eight and compares the record distributions with the displayed generating functions.
The mathematical argument covers every permitted length and record count. Enumeration through eight is a diagnostic check of the definitions; it is not the reason the all-length result holds. The exact certificate arithmetic is a finite component of the proof of the reused tail theorem. The work is unrefereed. The source audit in SOURCES.md records the prior-resolution search and its limits; it found no earlier resolution of Conjectures 1 and 3 in the searched sources.