back to table · edit · history · where entries came from · files · download
6719 bytes, as of the version from 2026-10-28 11:14 (current). Recorded here, not run.
"""Kazhdan–Lusztig polynomials of matroids -- numberdb.org/T579.
Run with SageMath (numberdb must be installed):
sage -pip install numberdb
sage -python generate.py # verify all stored entries
sage -python generate.py --fill # fill the draft, API key in env
sage -python checks.py # independent local checks
Exact coefficients in ZZ[t]; no numerical precision or rounding is used.
The defining recursion is EPW, Theorem 2.2 (arXiv:1412.7408).
Uniform flats are grouped by cardinality and braid flats by block sizes.
The three named objects use their actual ranked flat lattices; a cache key
never identifies different matroids merely by a rank or polynomial.
The independent checks use Z-palindromicity, PXY Proposition 2.3, and the
published EPW Appendix A values. See argument-selection.md for the finite
selection, checks.py for reproducible controls, and numerical-evidence.md.
"""
import os
import re
import sys
from collections import Counter
from functools import lru_cache
from math import comb, factorial
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
from sage.matroids.database_matroids import R10, TicTacToe, K5dual
R = PolynomialRing(ZZ, 't')
t = R.gen()
NAMED = {'R10': R10, 'TicTacToe': TicTacToe, 'K5dual': K5dual}
NAMED_SHAPES = {'R10': (5, 10), 'TicTacToe': (5, 9), 'K5dual': (6, 10)}
def selection():
"""All chosen object identities, in rank/size/key order."""
objects = [(r, r+c, f'U({r},{r+c})')
for r in range(5, 9) for c in range(1, 5)]
objects += [(m-1, comb(m, 2), f'K({m})') for m in range(6, 9)]
objects += [(r, n, name) for name, (r, n) in NAMED_SHAPES.items()]
return [key for r, n, key in sorted(objects)]
def reverse_at(p, degree):
return R([p[degree-i] for i in range(degree+1)])
def solve_epw(rhs, rank):
"""Solve t^rank P(t^-1)-P(t)=rhs under 2 deg(P)<rank."""
p = R([rhs[rank-i] for i in range((rank+1)//2)])
assert reverse_at(p, rank) - p == rhs
assert p[0] == 1 and 2*p.degree() < rank
return p
def uniform_characteristic(rank, size):
if rank == 0:
return R.one()
return (sum(((-1)**k * comb(size, k) * t**(rank-k)
for k in range(rank)), R.zero())
+ (-1)**rank * comb(size-1, rank-1))
@lru_cache(None)
def uniform_kl(rank, size):
if not 0 <= rank <= size:
raise ValueError('Uniform rank must lie between 0 and size')
if rank == 0:
if size != 0:
raise ValueError('Looped rank-zero inputs are outside this implementation')
return R.one()
rhs = uniform_characteristic(rank, size)
for k in range(1, rank):
rhs += comb(size, k) * (t-1)**k * uniform_kl(rank-k, size-k)
return solve_epw(rhs, rank)
def integer_partitions(n, bound=None):
if n == 0:
yield ()
return
for first in range(min(n, n if bound is None else bound), 0, -1):
for tail in integer_partitions(n-first, first):
yield (first,) + tail
def partition_count(parts):
denominator = 1
for size in parts:
denominator *= factorial(size)
for multiplicity in Counter(parts).values():
denominator *= factorial(multiplicity)
quotient, remainder = divmod(factorial(sum(parts)), denominator)
assert remainder == 0
return quotient
@lru_cache(None)
def braid_characteristic(vertices):
p = R.one()
for j in range(1, vertices):
p *= t-j
return p
@lru_cache(None)
def braid_kl(vertices):
if vertices < 1:
raise ValueError('At least one vertex is required')
if vertices == 1:
return R.one()
rhs = R.zero()
for parts in integer_partitions(vertices):
if len(parts) == vertices: # The empty flat gives P itself.
continue
chi = R.one()
for size in parts:
chi *= braid_characteristic(size)
rhs += partition_count(parts) * chi * braid_kl(len(parts))
return solve_epw(rhs, vertices-1)
def lattice_kl(matroid):
"""EPW recursion on the actual intervals [F,E], including parallel minors."""
if matroid.loops():
raise ValueError('Looped inputs are outside the table domain')
rank = int(matroid.rank())
if rank == 0:
return R.one()
flats = []
ranks = []
for k in range(rank+1):
layer = sorted((frozenset(f) for f in matroid.flats(k)),
key=lambda f: tuple(sorted(map(str, f))))
flats.extend(layer)
ranks.extend([k]*len(layer))
lower = [[j for j in range(i) if flats[j] < f] for i, f in enumerate(flats)]
kl = {len(flats)-1: R.one()}
for a in range(len(flats)-2, -1, -1):
mu = {a: ZZ.one()}
rhs = R.zero()
for b in range(a+1, len(flats)):
if not flats[a] < flats[b]:
continue
interval = [c for c in lower[b] if c in mu]
mu[b] = -sum((mu[c] for c in interval), ZZ.zero())
chi = sum((mu[c]*t**(ranks[b]-ranks[c]) for c in interval), R(mu[b]))
rhs += chi * kl[b]
kl[a] = solve_epw(rhs, rank-ranks[a])
return kl[0]
@lru_cache(None)
def polynomial(key):
match = re.fullmatch(r'U\((\d+),(\d+)\)', key)
if match:
return uniform_kl(*map(int, match.groups()))
match = re.fullmatch(r'K\((\d+)\)', key)
if match:
return braid_kl(int(match.group(1)))
if key not in NAMED:
raise ValueError('Unknown matroid identity: ' + key)
m = NAMED[key]()
assert m.is_simple() and (m.rank(), m.size()) == NAMED_SHAPES[key]
return lattice_kl(m)
class MatroidKazhdanLusztig(numberdb.Generator):
table = 'T579'
parameters = ('matroid',)
type = 'Z[]'
rigour = 'exact'
files = ('generate.py', 'checks.py', 'check.py', 'argument-selection.md', 'numerical-evidence.md')
def enumerate(self):
for key in selection():
yield {'matroid': key}
def value(self, params, digits):
return polynomial(params['matroid'])
if __name__ == '__main__':
if os.environ.get('NUMBERDB_KEY_FROM_STDIN') == '1':
key = sys.stdin.read().strip()
if re.match(r'^[A-Z_][A-Z0-9_]*\s*=', key):
key = key.split('=', 1)[1].strip().strip('\"\'')
os.environ['NUMBERDB_API_KEY'] = key
g = MatroidKazhdanLusztig()
if '--fill' in sys.argv or os.environ.get('NUMBERDB_PUBLISH') == '1':
print(g.publish(message='Fill the draft with 22 exactly checked matroid KL polynomials'))
else:
report = g.verify(sample=None)
print(report)
sys.exit(0 if report.ok else 1)