Computational Complexity of Bruhat-Interval Invariants

Bruhat path enumeration, cd reconstruction, and the explicit-output barrier

Definitions and mathematical statement

Shared notation.

Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

A Coxeter system is a group generated by involutions with pairwise product orders specified by its Coxeter matrix. $\ell(w)$ is the shortest generator-word length. The Bruhat interval $[u,v]$ consists of elements between $u$ and $v$ in Bruhat order.

Record scope and qualifications.

The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. The exact normalization of $P_{u,v}$, $a_i$, and cd-coefficients is source-specific; their asserted equivalence is retained as supplied.

Source-record limitation: The core interval invariant Puv and coefficient normalizations are not identified by the supplied extraction.

Statement recorded in the supplied source.

Given a Coxeter system $(W,S)$ and elements $u\leq v$ with Coxeter lengths $\ell(u)$ and $\ell(v)$, what is the computational complexity of computing the Bruhat-interval quantity $P_{u,v}$, equivalently the coefficients $a_i(u,v)$, or all cd-coefficients $[w]_{u,v}$, as a function of the Coxeter matrix and the input lengths? [S2]

Source status.

The supplied catalogue labels this source record open; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Compute the listed Bruhat-interval polynomial invariants efficiently as a function of the group and input lengths.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30000683 (OWR-1455-002). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Geometric and Topological Combinatorics $2007$, Oberwolfach Reports, DOI 10.4171/owr/2007/04, pp. 195--272 https://doi.org/10.4171/owr/2007/04.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

Given a Coxeter system $(W,S)$ and elements $u\leq v$ with Coxeter lengths $\ell(u)$ and $\ell(v)$, what is the computational complexity of computing the Bruhat-interval quantity $P_{u,v}$, equivalently the coefficients $a_i(u,v)$, or all cd-coefficients $[w]_{u,v}$, as a function of the Coxeter matrix and the input lengths?

Recovered source scope

The primary report identifies $P_{u,v}$ as the Kazhdan--Lusztig polynomial. It defines the complete $cd$-index by descent words of directed paths in the reflection-labelled Bruhat graph. Problem 8 says computing $P$ is equivalent to computing the $a_i$, and then asks about "even" all $cd$ coefficients; it does not assert a two-way efficient equivalence between $P$ and the full $cd$-index. This repairs context in our discussion without altering the preserved catalogue wording. We do not rely on the report's displayed coefficient conversion formulas, whose precise indexing would need further checking, or claim to prove its complete-$cd$-index existence theorem.

Attempt and results

An exact algorithm once the labelled acyclic graph is supplied.

Let a finite directed acyclic graph have source $u$, target $v\ne u$, and ordered edge labels. For a path with labels $t_1,\ldots,t_k$, assign the noncommutative word $w_1\cdots w_{k-1}$, where $w_i=a$ if $t_i<t_{i+1}$ and $w_i=b$ otherwise, following a fixed declared descent convention. Start at $u$ with one empty path. For each first edge, create state (endpoint, last label, empty word) with count one. Process vertices in a topological order. Extending a state across an outgoing edge of label $t$ appends $a$ or $b$ according to comparison with the stored last label, and adds its count into the new state. Sum states at $v$ over their final labels. Induction on path length proves correctness: each nonempty path has a unique last edge and shorter prefix, and the extension records exactly its last comparison. Thus every path contributes once and no extraneous path occurs. It is an exact finite procedure for the supplied graph, with states potentially exponential in the longest path length. It is not a polynomial algorithm for constructing the graph from compressed Coxeter input.

A proved finite conversion from an $ab$ expansion.

Put $c=a+b$ and $d=ab+ba$. Among $ab$ words of each fixed ordinary degree, use lexicographic order with $a>b$. Expanding any $cd$ word, its leading $ab$ word is obtained by replacing $c$ with $a$ and $d$ with $ab$, and its coefficient is one. These leading words are distinct: parse a resulting word from the right, pairing every $b$ with the immediately preceding $a$ as a $d$, and reading any remaining $a$ as a $c$. This is a unique inverse parse for words built from the tokens $a,ab$. Thus the expansions of $cd$ words of a fixed weighted degree are linearly independent. If an $ab$ polynomial is known to lie in their span, recover its coefficients by leading-term subtraction: its largest remaining word must be the largest leading word among the still-present $cd$ terms, since all other terms of each expansion are smaller. Subtract its integer coefficient times that expansion and continue. The process terminates in the finite word list. This proves uniqueness and a finite reconstruction algorithm, conditional on membership in the span. In the Bruhat application that membership is the source's theorem, not a theorem re-established in this attempt.

Dense output alone can be exponential.

Let $D$ be a requested maximum weighted degree, with $\deg c=1$, $\deg d=2$. There are at least $2^{\lfloor D/2\rfloor}$ different $cd$ words of degree $D$: independently choose the block $cc$ or $d$ in each of $\lfloor D/2\rfloor$ positions and append $c$ if $D$ is odd. A format explicitly listing the coefficient of every such word, even zeros, therefore needs exponentially many entries. This does not bound the size of a sparse representation, one selected coefficient, or the Kazhdan--Lusztig polynomial. Consequently a polynomial-time statement must distinguish those outputs rather than infer identical costs from a mathematical conversion. For a simple path-count check, take the Boolean interval on three commuting generators labelled $1<2<3$. Its directed paths are the six permutations. Their comparison words are $aa$, $bb$, twice $ab$, and twice $ba$, so the path polynomial is $a^2+2ab+2ba+b^2=c^2+d$ by direct expansion. This is an illustrative small interval, not a general complexity estimate.

Adversarial audit and remaining scope

The audit checked path initialization (one edge contributes the empty word), word order in the leading-term argument, output format, and the source's weaker wording about all coefficients. Missing are efficient Coxeter word and interval construction bounds in the declared encoding, coefficient bit-size analysis, and a complexity classification for $P_{u,v}$ itself. No computation beyond hand enumeration of the six paths was performed. The preserved source limitation is clarified by actual source reading rather than silently replaced with a different invariant.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. The finite explicit-graph procedures and dense-output bound do not classify Kazhdan--Lusztig computation from the Coxeter matrix and element words or prove efficient equivalence of all output formats.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Oberwolfach Report 4/2007, Billera, The complete cd-index of a Bruhat interval, printed pp.209--211; full relevant passage read from cached primary PDF text on 11 October 2026. https://ems.press/content/serial-article-files/46090.

Final status

Unresolved in this attempt. The finite explicit-graph procedures and dense-output bound do not classify Kazhdan--Lusztig computation from the Coxeter matrix and element words or prove efficient equivalence of all output formats.