back to table · edit · history · where entries came from · files · download
5949 bytes, as of the version from 2026-10-28 11:52. Recorded here, not run.
"""Z-polynomials of matroids -- numberdb.org/T580.
Run with SageMath and the numberdb package installed:
sage -pip install numberdb # once, in the Sage environment
sage -python generate.py # verify every stored entry
sage -python checks.py # independent exact checks
sage -python generate.py --fill # fill the existing draft (API key)
The --fill option submits entries and attachments; it does not publish a table.
Set NUMBERDB_API_KEY normally, or NUMBERDB_KEY_FROM_STDIN=1 to read the key
from stdin. The campaign wrapper can use NUMBERDB_PUBLISH=1 instead of --fill.
Proudfoot, Xu and Young, Definition 2.1 and Corollary 2.5, determine the
Kazhdan-Lusztig polynomials from the symmetry of Z. For Q_M equal to the sum
of t^rank(F) P_(M/F) over nonempty flats, the degree restriction on P gives
P_M[i] = Q_M[r-i] - Q_M[i] for 2i < r. Then Z_M = Q_M + P_M.
Uniform flats are grouped by size; braid flats are grouped by block count.
Named objects use their complete actual flat lattices, with caches indexed
by a flat, not by a numerical invariant of an interval. All arithmetic is in
ZZ[t]; there is no working precision or rounding. See argument-selection.md.
"""
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
from sage.matroids import catalog
from functools import lru_cache
from math import comb
import os
import sys
R = PolynomialRing(ZZ, 't')
t = R.gen()
NAMED = ('Fano', 'NonFano', 'Pappus', 'NonPappus', 'Vamos', 'R10',
'TicTacToe', 'K5dual')
NAMED_SIZES = {'Fano': (3, 7), 'NonFano': (3, 7), 'Pappus': (3, 9),
'NonPappus': (3, 9), 'Vamos': (4, 8), 'R10': (5, 10),
'TicTacToe': (5, 9), 'K5dual': (6, 10)}
def from_proper_flats(q, rank):
"""Recover P and Z using P's degree bound and Z's palindromicity."""
if rank == 0:
return R.one(), R.one()
p = R([q[rank-i] - q[i] for i in range((rank+1)//2)])
z = q + p
assert z.degree() == rank
assert list(z) == list(reversed(list(z)))
return p, z
@lru_cache(None)
def uniform_pair(rank, size):
if not 0 <= rank <= size:
raise ValueError('Uniform matroid needs 0 <= rank <= size')
if rank == 0:
# Only the rank-zero lattice is used internally. Looped inputs are
# outside the table's domain; no loop deletion rule is asserted.
return R.one(), R.one()
q = t**rank
for k in range(1, rank):
q += comb(size, k) * t**k * uniform_pair(rank-k, size-k)[0]
return from_proper_flats(q, rank)
@lru_cache(None)
def stirling_second(n, k):
if n == 0:
return int(k == 0)
if not 1 <= k <= n:
return 0
return stirling_second(n-1, k-1) + k*stirling_second(n-1, k)
@lru_cache(None)
def braid_pair(vertices):
if vertices < 1:
raise ValueError('A complete graph needs at least one vertex')
if vertices == 1:
return R.one(), R.one()
q = R.zero()
for blocks in range(1, vertices):
q += stirling_second(vertices, blocks)*t**(vertices-blocks)*braid_pair(blocks)[0]
return from_proper_flats(q, vertices-1)
def flat_lattice_pair(matroid):
"""Compute every upper interval in the actual flat lattice."""
if matroid.loops():
raise ValueError('Looped matroids are outside this implementation')
rank = int(matroid.full_rank())
ground = sorted(matroid.groundset(), key=str)
bits = {e: 1 << i for i, e in enumerate(ground)}
flats = []
ranks = {}
for k in range(rank+1):
for flat in matroid.flats(k):
mask = sum(bits[e] for e in flat)
flats.append(mask)
ranks[mask] = k
flats.sort(key=lambda f: (ranks[f], f))
pairs = {}
for f in reversed(flats):
q = R.zero()
for g in flats:
if g != f and (g & f) == f:
q += t**(ranks[g]-ranks[f])*pairs[g][0]
pairs[f] = from_proper_flats(q, rank-ranks[f])
return pairs[0]
@lru_cache(None)
def named_pair(name):
if name not in NAMED:
raise ValueError('Unknown catalogue selection')
matroid = getattr(catalog, name)()
assert (int(matroid.full_rank()), int(matroid.size())) == NAMED_SIZES[name]
assert matroid.is_simple()
return flat_lattice_pair(matroid)
def selection():
rows = [(r, r+c, 'U(%d,%d)' % (r, r+c))
for r in range(3, 9) for c in range(1, 5)]
rows += [(m-1, comb(m, 2), 'K(%d)' % m) for m in range(4, 9)]
rows += [(r, n, name) for name, (r, n) in NAMED_SIZES.items()]
return sorted(rows)
def pair(key):
if key.startswith('U('):
r, n = map(int, key[2:-1].split(','))
return uniform_pair(r, n)
if key.startswith('K('):
return braid_pair(int(key[2:-1]))
return named_pair(key)
class MatroidZ(numberdb.Generator):
table = 'T580'
parameters = ('matroid',)
type = 'Z[]'
rigour = 'exact'
files = ('generate.py', 'checks.py', 'argument-selection.md',
'check.py', 'dry_run.py', 'evidence.json', 'skill-evidence.json')
def enumerate(self):
for rank, size, key in selection():
yield {'matroid': key}
def value(self, params, digits):
return pair(params['matroid'])[1]
if __name__ == '__main__':
if os.environ.get('NUMBERDB_KEY_FROM_STDIN') == '1':
secret = sys.stdin.read().strip()
if '=' in secret and secret.split('=', 1)[0].isidentifier():
secret = secret.split('=', 1)[1].strip().strip('\"\'')
numberdb.configure(api_key=secret)
generator = MatroidZ()
if '--fill' in sys.argv or os.environ.get('NUMBERDB_PUBLISH') == '1':
print(generator.publish(message='Fill 37 exact Z-polynomials after independent checks'))
else:
report = generator.verify(sample=None)
print(report)
sys.exit(0 if report.ok else 1)