Positive Counting Rule for Type-A Schubert Structure Constants

Positive Counting Rule for Type-A Schubert Structure Constants

Definitions and mathematical statement

Let $\mathfrak S_w$ be the ordinary type-A Schubert polynomial indexed by a finite permutation $w$, in the stable polynomial convention. Its nonnegative integer multiplication constants are defined by \[ \mathfrak S_u\mathfrak S_v=\sum_w c_{u,v}^{w}\mathfrak S_w. \] Encode $u,v,w$ explicitly in one-line notation as a bit string $x$. The desired positive counting rule has the precise complexity meaning \[ \begin{gathered} \exists\text{ polynomial }p\ \exists\text{ polynomial-time predicate }R\\ \forall x=(u,v,w):\quad c_{u,v}^{w}=\#\{y\in\{0,1\}^{p(|x|)}:R(x,y)=1\}. \end{gathered} \] Thus the function belongs to $\#\mathrm P$ under this encoding. A signed sum with cancellations or a nonconstructive positivity proof is not such a rule. The predicate and polynomial must be uniform across all permutations; there is no fixed-rank restriction.

Formulation and concept references: [S1].

Short English statement

Can every ordinary type-A Schubert multiplication coefficient be counted by a single polynomial-time-verifiable family of positive witnesses?

Research attempt

Scope and a distinction in the source literature.

This attempt by GPT-6 Astra Ultra was prepared on 27 September 2026. The supplied target asks for exact counting by a uniform polynomial-time verifier. Positivity of the integer, decidability of its nonvanishing, and an exact witness count are three different assertions. In particular, Pak--Robichaux [S1], Theorem 2.1, proves a positive rule for the decision problem under GRH and the Miltersen--Vinodchandran derandomization assumption. Their Section 2.2 explicitly distinguishes such a rule from membership of the counting function in $\#\mathrm P$. That conditional decision theorem is not an unconditional counting rule for this entry. The consulted source continues to present a general unsigned interpretation as an open problem.

The proof attempt has two routes. Repeated multiplication by divisors gives honest positive chain witnesses, but expressing an arbitrary Schubert polynomial positively in those generators fails on a very small example. Divided differences give a uniform, polynomial-length signed history model for every coefficient. Its missing step can be stated as a polynomial-time sign-reversing pairing. The aim is to identify the exact combinatorial obligation at that step rather than turn geometric positivity into an unsupported assertion that cancellation is efficiently removable.

We extend one-line permutations by trailing fixed points. Let $s_i$ swap positions $i,i+1$, let $t_{ab}$ swap positions $a,b$, and let $\ell(w)$ be the number of inversions. Right multiplication acts on positions. The polynomial $\mathfrak S_w$ has degree $\ell(w)$. Hence $c_{u,v}^w=0$ unless $\ell(w)=\ell(u)+\ell(v)$. Invalid input encodings can uniformly be assigned zero. These checks take polynomial time in the explicit input length.

Positive route: divisor multiplication and explicit chain witnesses.

Write $D_k=x_1+\cdots+x_k=\mathfrak S_{s_k}$. The classical Monk rule, used here as an established theorem, is \begin{equation}\label{wsref-0-61-34-39-30-3a-6d-6f-6e-6b} \mathfrak S_uD_k= \sum_{\substack{a\leq k<b\\\ell(ut_{ab})=\ell(u)+1}} \mathfrak S_{ut_{ab}}. \end{equation} The stable-polynomial version and its indexing are stated in [E1], Theorem 0.1; it is important not to replace this by multiplication in the cohomology ring of a fixed-rank flag variety, which could discard terms.

For completeness, the cover test in (a490:monk) is elementary: for $a<b$ and $u(a)<u(b)$, \begin{equation}\label{wsref-0-61-34-39-30-3a-63-6f-76-65-72} \ell(ut_{ab})-\ell(u) =1+2\#\{j:a<j<b,\ u(a)<u(j)<u(b)\}. \end{equation} Indeed the pair $(a,b)$ creates one inversion; an intermediate value between the two endpoint values creates two more; all other changes cancel in pairs. If $u(a)>u(b)$ the same calculation with the swapped permutation gives the negative of a positive odd integer. Thus an upward cover is verified by checking the strict endpoint inequality and the absence of an intermediate value in that interval. This takes linear time in the stored permutation length.

Lemma 490.1 (positive chain special case). Supply an ambient rank $n$ by an explicit length-$n$ identity permutation, with $u,w\in S_n$ and $1\leq k_j<n$ for every entry of an explicitly listed sequence $k_1,\ldots,k_r$. The coefficient of $\mathfrak S_w$ in \[ \mathfrak S_u\prod_{j=1}^r D_{k_j} \] is the number of sequences $(a_1,b_1),\ldots,(a_r,b_r)$ satisfying \[ \begin{gathered} u_0=u,\qquad u_j=u_{j-1}t_{a_jb_j},\qquad u_r=w,\\ a_j\leq k_j<b_j,\qquad \ell(u_j)=\ell(u_{j-1})+1. \end{gathered} \] These sequences have polynomial length and polynomial-time verification in the explicit input, uniformly in the ranks and in $r$.

Proof. Repeatedly apply (a490:monk); each allowed move has coefficient one, so induction on $r$ gives precisely this path count, including multiplicities when different paths have the same final vertex. To verify the complexity statement, take $M_0=n$. The explicit rank encoding guarantees $M_0$ is at most the input length, including when the sequence of divisor indices is empty. If the current permutation fixes every position greater than $M$, an allowed cover cannot have $b\geq M+2$. Otherwise $a\leq k_j<M_0\leq M$ and the intermediate position $M+1$ would have value $M+1$, strictly between $u(a)\leq M$ and $u(b)=b$, contradicting (a490:cover). Thus the support expands by at most one at each step, and all indices are at most $M_0+r$. Store each pair in fixed-width binary, reject out-of-range indices, update the permutation, and apply the cover test. There are $r$ steps and $O(r\log(M_0+r))$ witness bits. Force every unused padding bit to zero so that one sequence has exactly one encoding.$\square$

In particular, the target has the required rule when one factor is a simple transposition. The lemma also treats arbitrary explicitly given products of divisor classes. It does not claim that every individual $\mathfrak S_v$ is such a product.

A failed generalization is ruled out by a single coefficient.

One possible extension was to write $\mathfrak S_v$ as a nonnegative integer combination of products of the $D_k$ and then attach the chains from Lemma 490.1. This is impossible in general. Every product of $d$ nonzero divisors $D_k$ has coefficient exactly one at $x_1^d$. Therefore every nonempty nonnegative integer combination of such products has a positive coefficient at $x_1^d$.

But \[ \mathfrak S_{231}=x_1x_2 \] has degree two and coefficient zero at $x_1^2$. It cannot have the proposed positive expansion. Allowing products of other degrees does not help: their nonnegative monomials could not cancel to leave a homogeneous quadratic. The signed identity \[ x_1x_2=D_1D_2-D_1^2 \] shows exactly what the positive reduction was trying to avoid. This is a counterexample to an intermediate representation claim, not to existence of some other positive witness family for Schubert multiplication.

Signed route: coefficient extraction with a fixed convention.

Let $s_i$ interchange variables $x_i,x_{i+1}$ and put \[ \partial_i F=\frac{F-s_iF}{x_i-x_{i+1}}. \] The basic Schubert identities are \begin{equation}\label{wsref-0-61-34-39-30-3a-64-64-73-63-68-75-62-65-72-74} \partial_i\mathfrak S_z= \begin{cases} \mathfrak S_{zs_i},&z(i)>z(i+1),\\ 0,&z(i)<z(i+1), \end{cases} \qquad \mathfrak S_{w_0}=x_1^{n-1}x_2^{n-2}\cdots x_{n-1} \quad(w_0\in S_n). \end{equation} These defining and nil-divided-difference identities, including stability, are recorded in [E2], Section 4. They are the algebraic input to the next derivation; no new proof of the whole Schubert basis theory is claimed.

Choose a deterministic descent-removal list $j_1,\ldots,j_d$ for $w$: at each step take, for example, the leftmost descent and swap it, ending at the identity after $d=\ell(w)$ steps. Define $\Phi_w(F)$ by applying $\partial_{j_1}$ first, then $\partial_{j_2}$, and so on, and finally taking the constant term. This operational description fixes the order of composition unambiguously. For every $z$ of length $d$, \begin{equation}\label{wsref-0-61-34-39-30-3a-64-75-61-6c-69-74-79} \Phi_w(\mathfrak S_z)=\mathbf{1}_{z=w}. \end{equation} To prove it, use (a490:ddschubert) at each step. Either some step is an ascent and the result becomes zero, or all $d$ swaps decrease length and the final permutation has length zero. The product of the chosen swaps is $w^{-1}$, so in the latter case $zw^{-1}$ is the identity, forcing $z=w$. For $z=w$, the chosen descent sequence indeed produces $\mathfrak S_{\mathrm{id}}=1$. Linearity and homogeneity therefore give \begin{equation}\label{wsref-0-61-34-39-30-3a-65-78-74-72-61-63-74-69-6f-6e} c_{u,v}^w=\Phi_w(\mathfrak S_u\mathfrak S_v) \qquad\text{if }\ell(w)=\ell(u)+\ell(v). \end{equation} This uses the stable basis expansion. It makes no assumption that the whole product expansion stays in the symmetric group initially used for $u,v$.

Lemma 490.2: an explicit uniform signed history model.

There are two polynomial-time predicates on polynomial-length histories whose numbers of accepted histories $P(u,v,w)$ and $N(u,v,w)$ satisfy \begin{equation}\label{wsref-0-61-34-39-30-3a-73-69-67-6e-65-64} c_{u,v}^w=P(u,v,w)-N(u,v,w). \end{equation} Equivalently this derivation places the function in $\mathrm{GapP}$, the class of differences of two $\#\mathrm P$ functions. The point of the lemma is its explicit witness representation, not a claim that this known signed-complexity conclusion solves the positive-counting problem.

Proof. Extend all three input permutations to a common $S_n$. After the degree check, construct deterministic divided-difference programs for $\mathfrak S_u$ and $\mathfrak S_v$. One program is obtained by sorting its target to $w_0$ using adjacent ascents, recording those swaps, and applying the recorded list in reverse to the single top monomial in (a490:ddschubert). The reversed swaps are descents of the intermediate permutations, so the recursion proves the program's output is the desired Schubert polynomial. Each program has at most $\binom n2$ operations.

For the monomial part involving variables $x_i,x_{i+1}$, direct division gives \begin{equation}\label{wsref-0-61-34-39-30-3a-6d-6f-6e-6f-6d-69-61-6c-62-72-61-6e-63-68} \partial_i(x_i^a x_{i+1}^b)= \begin{cases} \displaystyle\sum_{q=0}^{a-b-1}x_i^{a-1-q}x_{i+1}^{b+q},&a>b,\\[3pt] 0,&a=b,\\[3pt] \displaystyle-\sum_{q=0}^{b-a-1}x_i^{a+q}x_{i+1}^{b-1-q},&a<b. \end{cases} \end{equation} Other exponents stay fixed. A branch history chooses one summand at every step, stores its exponent vector, and flips a sign when the third case occurs. A step with $a=b$ kills that history. Different histories leading to the same monomial stay distinct; their signed multiplicities are exactly the polynomial coefficient by linearity and induction on the program.

Choose one history for the $u$ program and one for the $v$ program, add the exponent vectors and multiply their signs, then branch through the descent-removal program for $w$. Accept only histories ending at the constant monomial, separating them by their final sign. Distributivity and (a490:extraction) give (a490:signed).

For the uniform resource bound, put $L=\binom n2$. Under the degree condition the number of divided-difference steps over all three stages is exactly \[ (L-\ell(u))+(L-\ell(v))+\ell(w)=2L. \] All intermediate degrees are at most $2L<n^2$ for $n\geq2$. Every branch index $q$ can be stored in $O(\log(n+1))$ bits, and every exponent vector uses $O(n\log(n+1))$ bits. At each step the verifier computes the permitted range of $q$, rejects noncanonical or out-of-range choices, updates two exponents, and updates one sign bit. It never expands or sums the whole polynomial. Deterministic sorting, updates, and final checks all take polynomial time. The history length is $O(n^2\log(n+1))$, hence polynomial in the explicit one-line input length. Pad to a single polynomial bound with required zero bits; this prevents multiplying the answer by the number of arbitrary padding strings. The case $n=1$ has no steps and exactly one empty valid history when all permutations are identities. $\square$

This proof also bounds the absolute output by $2^{\operatorname{poly}(|x|)}$. There is no output-size obstruction to the requested $\#\mathrm P$ rule. The obstruction in this construction is subtraction. Counting all its positive histories alone gives $P$, which may be strictly larger than the desired integer.

A cancellation stress test in four letters.

Take $u=v=1324$, so $\mathfrak S_u=x_1+x_2$. For $w=3124$, the descent-removal list is $1,2$. Its first divided difference annihilates the symmetric polynomial $(x_1+x_2)^2$, so $c_{u,v}^{3124}=0$. At the monomial-history level, however, \[ x_1^2\xrightarrow{\partial_1}x_1+x_2 \xrightarrow{\partial_2}1,\qquad x_2^2\xrightarrow{\partial_1}-(x_1+x_2) \xrightarrow{\partial_2}-1. \] The mixed monomials are killed by $\partial_1$. There is one positive and one negative surviving history, and the zero coefficient is their difference. This refutes counting positive survivors without pairing.

For $w=2314$, the list is $2,1$ instead. The two copies of $x_1x_2$ each give $+1$ after these operations, whereas the $x_2^2$ summand gives $-1$ and $x_1^2$ gives zero. Thus the coefficient is $2-1=1$. For $w=1423$, the list $2,3$ gives one positive history and no negative ones. These calculations agree with the full identity \begin{equation}\label{wsref-0-61-34-39-30-3a-65-78-61-6d-70-6c-65} \mathfrak S_{1324}^2 =\mathfrak S_{1423}+\mathfrak S_{2314}. \end{equation} Indeed the two right-hand polynomials are $x_1^2+x_1x_2+x_2^2$ and $x_1x_2$, respectively, as can also be checked by the top-monomial recursion. They illustrate that monomial positivity of the factors does not make coefficient extraction a positive operation. The displayed path counts refer to extraction from the explicitly expanded product; the longer construction histories in Lemma 490.2 may contain additional cancelling pairs.

The first missing lemma, stated as a verifiable obligation.

Let $\Omega_x$ be the finite set of valid signed histories from Lemma 490.2 for an input $x=(u,v,w)$, with sign $\sigma(h)\in\{1,-1\}$. A sufficient route to the target would be a uniform polynomial-time map $\tau_x:\Omega_x\to\Omega_x$ satisfying \begin{equation}\label{wsref-0-61-34-39-30-3a-69-6e-76-6f-6c-75-74-69-6f-6e} \tau_x^2=\mathrm{id},\qquad \tau_x(h)\ne h\Longrightarrow \sigma(\tau_x(h))=-\sigma(h),\qquad \tau_x(h)=h\Longrightarrow\sigma(h)=1. \end{equation} If such a map were constructed, every nonfixed orbit would contribute zero to the signed sum, and the coefficient would count its fixed points. A verifier would check history validity and $\tau_x(h)=h$, in polynomial time. This proves that (a490:involution), with its complexity and validity requirements, really would suffice.

Nonnegativity of $c_{u,v}^w$ guarantees only a set-theoretic pairing of all negative histories with some positive histories. It gives no efficient mate-finding algorithm or efficiently recognizable unpaired subset. Pairing the $j$th negative history with the $j$th positive one in lexicographic order does not repair this: finding the rank or the $j$th member involves counting or searching through exponentially many histories, and no polynomial bound for that operation has been established. Even an efficiently computed injection of negative histories into positive ones would not alone suffice unless membership in its image could also be tested efficiently.

The small example permits local cancellation by swapping the two symmetric monomial contributions. In general the construction has three coupled stages, each with many choices. A proposed local swap must preserve the validity of the remaining suffix, reverse the sign, be involutive, and leave no negative fixed point. None of these properties follows merely from the algebraic equality of total sums. No uniform map meeting (a490:involution) is produced here. This is a sufficient missing ingredient for the chosen approach, not a claim that every possible positive rule must arise from this particular signed model.

Finite verification and conventions checked.

The companion exact-integer Python script constructs Schubert polynomials by divided differences of the top monomial. For all permutations of ranks two through five it checks 2,048 equal-degree instances of (a490:duality). It independently verifies 72 full polynomial instances of the stable Monk formula: $u\in S_4$, $k\in\{1,2,3\}$, with output allowed in $S_5$. This extra rank is required because a stable divisor product can introduce a new position.

For all 36 pairs of factors from $S_3$, extended to $S_6$, the script extracts 1,189 degree-compatible coefficients, checks their nonnegativity, and reconstructs each product as an exact polynomial from its extracted Schubert expansion. It separately records the three signed extraction counts above as $(1,1)$, $(2,1)$, and $(1,0)$. No random numerical evaluation or floating-point comparison is used. The script and results are saved as verify.py and results.json in

\nolinkurl{_Local/top_problems/continuation_descending_2026_09_27/combinatorics/}

.

The checks are finite tests of operator order, stable rank, and cancellation; they do not prove a uniform positive rule. The empty product has one empty chain, not many encodings. Unequal degrees reject every history. Permutation indices are explicit, so a polynomial bound in $n$ is a polynomial bound in the prescribed input length; a succinct circuit encoding of permutations would be a different problem. The divisor-chain lemma assumes its sequence of factors is explicitly listed, not a binary exponent representing an exponentially long product, and its ambient rank is explicitly encoded. It does not claim polynomial time for binary divisor indices exponentially larger than that rank.

Outcome and next targets.

UNRESOLVED. The attempt gives positive polynomial-time witnesses for divisor products, proves a small obstruction to a proposed positive reduction to divisors, and derives a complete signed history model with uniform polynomial witness length. It then states and checks the exact condition under which that signed model would become an unsigned count. No sign-reversing involution with the required uniform efficiency has been constructed, and the original $\#\mathrm P$ assertion remains open here.

Concrete next experiments would attach complete suffix data to local cancellation moves, test the involution property before counting fixed points, and seek subclasses where suffix preservation follows from an explicit monotonicity condition. Any successful generalization must then prove the witness bound and all four obligations: validity, efficient computation, involutivity, and positive fixed points. A mere decision certificate for nonvanishing would leave the exact-counting target unmet.

Sources

• S1 Igor Pak and Colleen Robichaux, Positivity of Schubert Coefficients (2024 preprint; Comptes Rendus Mathématique 363 $2025$, 1507–1515). https://arxiv.org/html/2412.18984. Formulation source.
• E1 Rudolf Winkel, On the Multiplication of Schubert Polynomials, author manuscript, October 1996, revised January 1997, Theorem 0.1. https://www.th-bingen.de/fileadmin/Prof_Uploads/rudolfwinkel/08.pdf. Primary research source stating stable Monk multiplication; consulted 27 September 2026. Only the established divisor rule is used, not the speculative rules in later sections.
• E2 I. G. Macdonald, Notes on Schubert Polynomials, Publications du LACIM 6 $1991$, Section 4, equations $4.2$, $4.5$, and $4.14$, and the surrounding proofs. https://www.math.uwaterloo.ca/~opecheni/macdonaldschubert.pdf. Author's treatment of the divided-difference identities, stability, and coefficient extraction; consulted 27 September 2026.