Large Hypercube Intervals in Bruhat Order
How large can a Bruhat interval in that is a poset hypercube be? Using a permutation pattern suggested by AlphaEvolve, the authors exhibit hypercube intervals of dimension for a power of 2, matching the largest possible dimension up to a constant - in the problem circle around the combinatorial invariance conjecture for Kazhdan-Lusztig polynomials.
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI co-developed
- Method
- Construction
- Field
- Coxeter combinatorics
- Posed by
- —
- Year posed
- —
- Years open
- —
- Solved
- 2026-01-03
- Model
- AlphaEvolve
- Vendor
- Google DeepMind
- Collaborators
- Jordan Ellenberg, Nicolas Libedinsky, David Plaza, José Simental, Geordie Williamson
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 10 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Asymptotically optimal for powers of 2; the exact extremal answer for general n stays open.
What the AI did
AlphaEvolve, searching evolutionarily rather than exhaustively, "produced a pattern which performed well for the n tested, and which we show works well for general n" - the agent found the construction, the humans proved it works in general.