Skip to content

[application] Short AJQ peak real-rootedness proof via signed descents and gamma transform #2568

Closed

Description

@PerAlexandersson

Shorter AJQ peak proof via signed descents and a gamma transform

Task and status

Implement and verify an alternative proof of the real-rootedness of the peak
polynomials in P. Alexandersson, A. Jal and M. Quemener,
Rook-Eulerian polynomials and permutation ideals. The proof below replaces
the six-condition D/U induction by a signed-descent interlacing recurrence.

The mathematical argument has been checked symbolically and its combinatorial
identities have passed the finite exact checks below. This alternative has
not been implemented or checked in Lean.
The purpose of this issue is to
verify it formally, including its identification with the actual peak
enumerator, not just a polynomial recurrence with that name.

Preserve the existing proof and its stronger refined interlacing API while
developing the alternative. Related scope clarification: #1627. This is about
the one-index peak enumerator, not the abandoned two-endpoint refinement.

Objects and conventions

Let lambda = (lambda_1,...,lambda_n) have weakly increasing row lengths,
with lambda_i >= i. Let S_lambda consist of injective words of positive
integers satisfying pi_i <= lambda_i. Allow arbitrary rectangular boards,
not only lambda_n = n.

Let P^lambda(t) = sum_{pi in S_lambda} t^pk(pi), where peaks are strictly
interior: pi_(i-1) < pi_i > pi_(i+1), for 2 <= i <= n-1.

Independently assign each entry of each placement a sign. Define
B^lambda(x) = sum_{pi,epsilon} x^des(epsilon_1 pi_1,...,epsilon_n pi_n).
Here des counts ordinary adjacent descents in the integer order, with
no comparison against an initial 0. This is not the usual type-B descent
statistic.

The companion uses zero-based columns. In that model, the signed value of
column j must be +(j+1) or -(j+1), never +j or -j.

1. Signing identity

For a fixed positive injective word pi of length n >= 1, with p peaks,

sum_epsilon x^des(epsilon*pi) = 2^(2p+1) x^p (1+x)^(n-2p-1).

Proof: assign each of the n-1 adjacent comparisons to the endpoint with
larger absolute value. The comparison depends only on that endpoint's sign.
An entry owns two comparisons exactly when it is an interior peak; its two
signs each give one descent, contributing 2x. An entry owning one comparison
contributes 1+x. If a,b,c count entries owning two, one, zero comparisons,
then a=p, 2a+b=n-1 and a+b+c=n, so b=n-2p-1 and c=p+1.
The remaining factors are therefore 2^(p+1).

Summing over placements gives

B^lambda(x) = 2(1+x)^(n-1) P^lambda(4x/(1+x)^2).

For Lean, use the denominator-free polynomial identity. Writing p_i for
the coefficient of t^i in P^lambda, it is

B^lambda = sum_{i=0}^{floor((n-1)/2)} 2*4^i*p_i * X^i*(1+X)^(n-1-2i).

Equivalently, with gamma = C 2 * (P^lambda).comp (C 4 * X),

B^lambda = RealRooted.gammaTransform (n-1) gamma.

Prove natDegree gamma <= (n-1)/2: peaks cannot be adjacent. The degree bound
is essential because the library's gammaTransform truncates coefficients
outside its ambient degree range. Handle n=0 separately: both enumerators
are 1, but the displayed signing formula is only for n >= 1.

2. Interlacing of signed first-entry refinements

If the first row of lambda has length m, let F^lambda_a refine B^lambda
by the signed first entry a. Use precisely this order:

(F_-m,...,F_-1,F_1,...,F_m).

We prove that this is an interlacing sequence of nonnegative-coefficient
polynomials. For a one-row board (m), every coordinate is 1.

Suppose lambda^+ = (r,lambda_1+1,...,lambda_n+1), with 1 <= r <= m+1.
Write the ordered input vector as (f_1,...,f_(2m)) and define

H_s = X * sum_{j<=s} f_j + sum_{j>s} f_j, for 0 <= s <= 2m.

Then, for 1 <= k <= r,

F^(lambda^+)_(-k) = H_(m-k+1),

F^(lambda^+)_k = H_(m+k-1).

To verify the recurrence, delete the first row and occupied absolute-value
column k. Standardize positive labels by j -> j for j<k and j -> j-1
for j>k, retaining signs. This is increasing on the remaining signed
alphabet, so all tail descents are preserved. The inverse insertion on
positive labels is j -> j for j<k, j -> j+1 for j>=k.
Every remaining row contains column k, so the reduced board is independent
of k; unused columns do not cause a problem.

For first entry -k, the new first comparison is a descent exactly when the
standardized tail begins with -j for j>=k. These occupy the first
m-k+1 positions of the ordered input vector. For first entry +k, it is a
descent for every negative tail first entry and for positive j<k: the first
m+k-1 positions.

The thresholds in the ordered output are

m-r+1, ..., m-1, m, m, m+1, ..., m+r-1.

They are weakly increasing and belong to [0,2m]. Thus the recurrence is
exactly the staircase matrix of Branden, Corollary 8.7,
which preserves interlacing. The repeated middle threshold is permitted.
When r=m+1, the extreme outputs are H_0=sum f_j and
H_(2m)=X*sum f_j; neither boundary needs a separate invariant.

Every admissible Ferrers board with at least two rows has this form:
its predecessor is (lambda_2-1,...,lambda_n-1), which still contains the
staircase. This closes induction for arbitrary widths. Summing the signed
refinements gives real-rootedness of B^lambda. Nonnegative coefficients
exclude positive roots, and the increasing placement shows B^lambda(0)>0.

3. Recover peak real-rootedness

Apply the inverse gamma-transform theorem to
gamma = C 2 * P.comp (C 4 * X), using the degree bound, nonzeroness,
splitness and nonpositive-root hypotheses. Remove the nonzero scalar and
invert the positive linear rescaling to conclude that P splits.

An elementary check of the implication is useful: if y is a root of P,
then y != 0 because the increasing placement contributes to P(0).
Solve y(1+x)^2=4x over the complex numbers. No solution is -1 or 0.
Every solution is a root of B, hence real and negative; therefore
y=4x/(1+x)^2 is real and negative.

Existing Lean sources and implementation choices

The following names were inspected in source; the threshold module and
inverse-gamma declarations were also checked against the public main.
This is not a new build certificate.

  • RowThresholdOne.lean:
    has2x2_thresholdEntry_one, thresholdOneMatrix_preserves_interlacing_weak.
    The latter lists consecutive thresholds; use a monotone subsequence with
    the repeated middle output, or instantiate the more general entry theorem.
  • ThresholdMatrix/Basic.lean:
    thresholdMatrix_preserves_interlacing_seq0_of_entry_weak and
    isRealRooted_sum_of_isInterlacingSeq0Nonneg.
  • GammaTransform/Preservation.lean:
    isRealRooted_and_hasRootsNonpos_of_isRealRooted_gammaTransform_of_natDegree_le
    or IsGammaExpansion.isRealRooted_and_hasRootsNonpos_iff.
  • Existing six-condition proof:
    Applications/PeakPolynomials/PeakInduction.lean.
  • Concrete Ferrers objects and their row-deletion lemmas already exist in
    the companion formalization. The maintainer/worker has its location;
    coordinate the bridge there without publishing private source material.
    Reuse the existing definitions or their lower-level equivalents; do not
    create an incompatible second meaning of the paper's peak polynomial.

Optional algebraic route through the existing D/U recurrence

It may be shorter in Lean to transport the already-proved combinatorial D/U
recurrence rather than introduce a second signed-placement enumeration.
For n>=2, set y=4x/(1+x)^2. Directly fixing the first sign gives

F_-k = 2(1+x)^(n-2) D_k(y) + (1+x)^(n-1) U_k(y),

F_k = 2x(1+x)^(n-2) D_k(y) + (1+x)^(n-1) U_k(y).

If the word starts with an ascent, its first sign controls no comparison,
so either choice takes half the total signing sum. If it starts with a
descent, its first entry controls exactly one comparison: fixing its sign
to minus gives factor 1, and fixing it to plus gives factor x.

In polynomial notation let
d_k = gammaTransform (n-2) (D_k.comp (C 4*X)) and
u_k = gammaTransform (n-1) (U_k.comp (C 4*X)).
Then F_-k=2*d_k+u_k and F_k=2*X*d_k+u_k.
Prove the support bounds deg D_k <= floor((n-2)/2) and
deg U_k <= floor((n-1)/2) whenever those polynomials are nonzero.
An initial descent prevents a peak at position 2, giving the tighter D bound.

Substituting these expressions into
D_k^+ = sum_{j<k}(D_j+U_j) and
U_k^+ = sum_{j>=k}(t D_j+U_j) yields the same staircase recurrence.
For example, F_-j+F_j=2(1+x)^(n-1)(D_j(y)+U_j(y)) and
x F_-j+F_j=(1+x)^n(y D_j(y)+U_j(y)).
This uses the combinatorial recurrence, not its six interlacing conditions.
Treat the one-row seed separately rather than using n-2 there.

Either implementation is acceptable if the final theorem concerns the actual
enumerator and the new proof dependency does not pass through the old peak
real-rootedness or six-condition induction.

Exact finite checks

A bounded, standard-library Python probe checked:

  • The signing identity for every permutation of lengths 1 through 7:
    695,482 sign assignments.
  • The signed first-comparison deletion formula on every signed permutation
    of lengths 2 through 7: 695,480 cases.
  • Both first-sign D/U identities for every permutation of lengths 2 through 7.
  • The deletion/insertion bijection on all 290 weakly increasing admissible
    boards with 2 through 5 rows and every row length at most 6; all first-entry
    fibers, including rectangular boards. There were 16,590 placement deletions.

All comparisons were exact integer identities; these are indexing checks,
not the proof of the infinite family. No numerical root solver was used.
The probe is included below for reproducibility.

Small regression: for the increasing board (2,3,3),
P(t)=2+2t, B(x)=4+24x+4x^2, and the signed-first vector is

(2+6x, 1+6x+x^2, 1+6x+x^2, 6x+2x^2).

Acceptance criteria

  • Prove the signed recurrence and its interlacing induction, or the
    equivalent polynomial transport of the concrete D/U recurrence.
  • Prove the denominator-free peak/signing or gamma identity, with degree
    bounds proved rather than assumed away.
  • Obtain an unconditional alternate proof for the actual Ferrers peak
    enumerator, covering arbitrary widths, the one-row case and the empty case.
    For boards with no placements, distinguish splitness of zero from the
    nonzero isRealRooted predicate.
  • The new proof does not invoke the old six-condition theorem or existing
    peak real-rootedness as an input. Audit the dependency route as well as axioms.
  • Keep the old refined API until its consumers and stronger conclusions
    are accounted for; this issue does not claim the six refinements follow
    from signed interlacing.
  • Add the small regressions above, build affected modules and direct
    importers, run the repository's applicable source/style/axiom checks, and
    validate the exact revision through the normal integration gates.
  • If the concrete bridge stays downstream, record its checked companion
    revision with the owner before reporting end-to-end verification. Do not close this as
    fully verified with only an abstract recurrence theorem.

No manuscript replacement is requested by this issue. First verify the new
proof, then report its formal scope and whether it actually simplifies the
mathematical exposition.

Reproduce the bounded identity checks (Python 3, standard library)
"""Bounded independent checks of AJQ signing and deletion identities.

No polynomial family generator or root checker: enumerate individual words
and signs, then compare their finite counts and local deletion maps.
"""
from collections import Counter
from itertools import combinations_with_replacement, permutations, product
from math import comb


def des(w):
    return sum(a > b for a, b in zip(w, w[1:]))


signed_words = 0
deletions = 0
for n in range(1, 8):
    for w in permutations(range(1, n + 1)):
        p = sum(w[i - 1] < w[i] > w[i + 1] for i in range(1, n - 1))
        actual = Counter()
        by_first_sign = {-1: Counter(), 1: Counter()}
        for signs in product((-1, 1), repeat=n):
            v = tuple(s * a for s, a in zip(signs, w))
            actual[des(v)] += 1
            by_first_sign[signs[0]][des(v)] += 1
            signed_words += 1
            if n > 1:
                k = abs(v[0])
                tail = tuple((1 if a > 0 else -1) *
                             (abs(a) - (abs(a) > k)) for a in v[1:])
                m = n - 1
                j = tail[0]
                # 1-based index in -m,...,-1,1,...,m.
                index = m + j + 1 if j < 0 else m + j
                cut = m - k + 1 if v[0] < 0 else m + k - 1
                assert des(v) == des(tail) + (index <= cut), (v, tail, cut)
                deletions += 1
        singles = n - 2 * p - 1
        expected = Counter({p + j: 2 ** (2 * p + 1) * comb(singles, j)
                            for j in range(singles + 1)})
        assert actual == expected, (w, actual, expected)
        if n > 1:
            for sign in (-1, 1):
                if w[0] < w[1]:
                    expected_refined = Counter({j: c // 2 for j, c in expected.items()})
                else:
                    power = n - 2 * p - 2
                    expected_refined = Counter({p + j + (sign == 1):
                                                2 ** (2 * p + 1) * comb(power, j)
                                                for j in range(power + 1)})
                assert by_first_sign[sign] == expected_refined, (w, sign)

boards = 0
placement_deletions = 0
for n in range(2, 6):
    for shape in combinations_with_replacement(range(1, 7), n):
        if any(a < i + 1 for i, a in enumerate(shape)):
            continue
        boards += 1
        mu = tuple(a - 1 for a in shape[1:])
        tails = {w for w in permutations(range(1, 6), n - 1)
                 if all(a <= b for a, b in zip(w, mu))}
        fibers = {k: set() for k in range(1, shape[0] + 1)}
        for w in permutations(range(1, 7), n):
            if all(a <= b for a, b in zip(w, shape)):
                k = w[0]
                tail = tuple(a - (a > k) for a in w[1:])
                fibers[k].add(tail)
                # The insertion is the inverse, including unused columns.
                assert (k,) + tuple(a + (a >= k) for a in tail) == w
                placement_deletions += 1
        for k, fiber in fibers.items():
            assert fiber == tails, (shape, k)

print(f"PASS signing identity: all permutations of lengths 1..7; {signed_words} signings")
print(f"PASS signed descent deletion: {deletions} signed words of lengths 2..7")
print("PASS first-sign refinement formulas: all permutations of lengths 2..7")
print(f"PASS Ferrers deletion bijections: {boards} admissible boards, 2..5 rows, width <=6")
print(f"PASS inverse insertion: {placement_deletions} placements, all first-entry fibers")

Activity

  1. PerAlexandersson commented on Nov 14, 2026

    @PerAlexandersson
    OwnerAuthor

    Taken. Plan: the algebraic transport route (last section of the issue). It needs no second signed-placement enumeration.

    1. RealRooted (this repo), branch feat/peak-signed-staircase: new module Applications/PeakPolynomials/SignedStaircase.lean.
      • The invariant SignedPeakInvariant n m D U: the signed vector (F_-m,…,F_-1,F_1,…,F_m) built from D/U via gammaTransform, with weak zero-aware interlacing, nonnegative coefficients, and the degree bounds deg D ≤ (n-2)/2, deg U ≤ (n-1)/2.
      • The one-row seed, and the step D⁺_k = Σ_{j<k}(D_j+U_j), U⁺_k = Σ_{k≤j<m}(X D_j+U_j), which acts as a monotone-threshold staircase matrix (Brändén Cor. 8.7, via has2x2_thresholdEntry_one). The degree bounds are proved inside the induction.
      • The gamma identity Σ F = gammaTransform (n-1) (C 2 * P.comp (C 4 * X)), and P.Splits via the inverse gamma theorem. P = 0 is handled through Splits of zero.
      • It does not use PeakFamily.Conditions or the old real-rootedness theorem; the dependency route will be audited before merge. The old refined API stays untouched.
    2. Concrete bridge: after (1) merges, instantiate it with the actual Ferrers enumerator's first-entry refinements. The bridge stays downstream; its checked companion revision will be recorded here.

    Status: implementation started; I'll report results and any obstruction here.

  2. PerAlexandersson commented on Nov 14, 2026

    @PerAlexandersson
    OwnerAuthor

    Progress:

    • Abstract part: Peak polynomials: signed-staircase proof via the gamma transform #2569 (SignedStaircase.lean). It builds locally and all repository guards pass. The axiom audit shows only propext, Classical.choice, Quot.sound. Its import closure contains no peak-induction module.
    • Concrete bridge: written and built against the actual Ferrers peak enumerator, downstream at a RealRooted revision that contains Peak polynomials: signed-staircase proof via the gamma transform #2569.
      • Proved by the same row induction as the existing proof, now through SignedPeakInvariant.step. It covers arbitrary first-row width, the one-row board, and the empty board via Splits of the zero-row case.
      • It gives both the Splits statement (any weakly increasing board) and the nonzero real-rooted statement (λ_k > k).
      • The (2,3,3) regression P = 2 + 2t is checked on the actual enumerator.
    • Dependency audit: a transitive-constant scan from the new theorems finds no constant from either six-condition peak-induction module, and none of the old theorems conditions_peakFamily / peakPolynomial_splits / peakPolynomial_isRealRooted. A positive control (the old theorem) is flagged by the same scan.
    • Remaining obstruction (integration only): the downstream repository must advance its RealRooted pin. One unrelated downstream library depends on modules RealRooted has since removed. By the maintainer's decision, those are being relocated into that library. After that comes a full downstream build, then the checked downstream revision will be recorded here.
  3. PerAlexandersson commented on Nov 14, 2026

    @PerAlexandersson
    OwnerAuthor

    Verified end-to-end.

    • Abstract part: Peak polynomials: signed-staircase proof via the gamma transform #2569, merged as RealRooted a001947d4.
    • Concrete bridge: in the downstream companion, merged at companion revision 859b098. That revision pins RealRooted to a001947d4.
      • Theorems: signedPeakInvariant_peak (the invariant for the actual first-entry refinements of every Ferrers board), peakPolynomial_splits_of_signedStaircase (any weakly increasing board, including the one-row and empty boards) and peakPolynomial_isRealRooted_of_signedStaircase (nonzero and split when λ_k > k).
      • Checked at that revision:
        • full downstream build;
        • all Comparator catalogs re-accepted;
        • the transitive-constant independence scan reports no constant from either six-condition PeakInduction module and none of conditions_peakFamily, peakPolynomial_splits or peakPolynomial_isRealRooted, with a positive control on the old theorem;
        • only propext, Classical.choice and Quot.sound axioms.

    Acceptance checklist:

    • Signed recurrence and its interlacing induction. Implemented as the polynomial transport of the concrete D/U recurrence; one step is a monotone marker-one threshold matrix, via the new general thresholdMatrix_one_preserves_interlacing.
    • Gamma identity sum_signedVector. Degree bounds proved inside the induction, not assumed.
    • Unconditional alternative proof for the actual enumerator: arbitrary widths, the one-row case and the empty case. Splits is distinguished from the nonzero real-rooted statement.
    • Dependency route audited as well as axioms.
    • Old refined API untouched.
    • Regressions for (2,3,3): abstract signed vector and sum in RealRooted, and P = 2 + 2t on the actual enumerator downstream.
    • Exact revisions checked and recorded above.

    Formal scope and whether it simplifies the exposition. The alternative proof is about 440 lines plus a ~30-line board induction. The six-condition engine is about 1,190 lines, plus the downstream copy. The new route has a single invariant (one interlacing sequence) instead of six interlacing conditions. The step is an instance of a standard staircase-matrix lemma (Brändén, Cor. 8.7) rather than a bespoke case analysis. The only paper-specific algebra is the two gamma-transform identities F_{-j}+F_j and x F_{-j}+F_j. My reading: it is a genuine simplification of the real-rootedness argument. It does not recover the six refined interlacings, which the old route still provides. The manuscript was not changed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions