back to table · edit · history · where entries came from · files · download
5873 bytes, as of the version from 2026-10-28 12:29. Recorded here, not run.
"""Chow polynomials of matroids -- numberdb.org/T581.
Run with SageMath and the numberdb Python package:
sage -python generate.py # verify all stored entries
sage -python generate.py --fill # fill the draft with NUMBERDB_API_KEY
sage -python checks.py # separate coefficient checks
The ordinary Chow ring uses the maximal building set of nonempty flats,
including the top flat, and divisor degree one. Weighted chains are summed
by their first nonempty flat, using Proposition 3.5 of Ferroni, Matherne,
Stevens and Vecchi, arXiv:2212.03190v3. No augmented values are stored.
Uniform flats are grouped by cardinality and braid flats by block count.
Named matroids use their entire actual flat lattices; cache keys are flats
within a fixed lattice, never rank alone. All arithmetic is in ZZ[t].
See argument-selection.md for the finite, mixed selection and its bounds.
--fill writes entries to the existing draft; it does not make it public.
"""
import os
import re
import sys
from functools import lru_cache
from math import comb
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
R = PolynomialRing(ZZ, 't')
t = R.gen()
NAMED = ('Fano', 'NonFano', 'Pappus', 'NonPappus', 'Vamos', 'R10',
'TicTacToe', 'K5dual')
METADATA = {'Fano': (3, 7), 'NonFano': (3, 7), 'Pappus': (3, 9),
'NonPappus': (3, 9), 'Vamos': (4, 8), 'R10': (5, 10),
'TicTacToe': (5, 9), 'K5dual': (6, 10)}
@lru_cache(None)
def chain_weight(gap):
"""Positive exponents strictly below the rank jump, including zero sum."""
return R([0] + [1] * max(0, gap - 1))
@lru_cache(None)
def uniform_chow(rank, size):
if not 0 <= rank <= size:
raise ValueError('Require 0 <= rank <= size')
if rank == 0:
if size:
raise ValueError('Positive-size rank-zero matroids have loops')
return R.one()
# The first nonempty flat is top, or a j-subset with j < rank.
return R.one() + chain_weight(rank) + sum(
(ZZ(comb(size, j)) * chain_weight(j) * uniform_chow(rank-j, size-j)
for j in range(2, rank)), R.zero())
@lru_cache(None)
def stirling_second(n, k):
if n == 0:
return int(k == 0)
if k < 1 or k > n:
return 0
return k * stirling_second(n-1, k) + stirling_second(n-1, k-1)
@lru_cache(None)
def braid_chow(vertices):
if vertices < 1:
raise ValueError('A braid matroid needs a positive vertex count')
# A flat with k blocks has rank vertices-k; its upper interval is Pi_k.
return R.one() + sum(
(ZZ(stirling_second(vertices, k)) * chain_weight(vertices-k) * braid_chow(k)
for k in range(1, vertices-1)), R.zero())
@lru_cache(None)
def named_matroid(name):
if name not in NAMED:
raise ValueError('Not a selected catalogue object')
M = getattr(catalog, name)()
assert (M.rank(), len(M.groundset())) == METADATA[name]
assert M.is_simple()
return M
def lattice_chow(M):
"""First-flat chain recursion on every upper interval of the flat lattice."""
if M.loops():
raise ValueError('Looped matroids are outside this definition')
ground = tuple(sorted(M.groundset(), key=repr))
position = {e: i for i, e in enumerate(ground)}
flats = []
for rank in range(M.rank()+1):
for flat in M.flats(rank):
mask = sum(1 << position[e] for e in flat)
flats.append((rank, mask))
flats.sort(reverse=True)
values = {}
for rank, mask in flats:
value = R.one()
for upper_rank, upper_mask in flats:
if upper_rank >= rank+2 and mask & upper_mask == mask:
value += chain_weight(upper_rank-rank) * values[upper_mask]
values[mask] = value
return values[0]
@lru_cache(None)
def named_chow(name):
return lattice_chow(named_matroid(name))
def selection():
objects = [(r, r+c, 'U(%d,%d)' % (r, r+c))
for r in range(3, 9) for c in range(1, 5)]
objects += [(m-1, comb(m, 2), 'K(%d)' % m) for m in range(4, 9)]
objects += [(METADATA[k][0], METADATA[k][1], k) for k in NAMED]
return sorted(objects)
def object_metadata(key):
if key.startswith('U('):
rank, size = map(int, re.fullmatch(r'U\((\d+),(\d+)\)', key).groups())
return rank, size
if key.startswith('K('):
m = int(key[2:-1])
return m-1, comb(m, 2)
return METADATA[key]
class MatroidChow(numberdb.Generator):
table = 'T581'
parameters = ('matroid',)
type = 'Z[]'
rigour = 'exact'
files = ('generate.py', 'checks.py', 'check.py', 'argument-selection.md',
'numerical-evidence.md', 'skills-evidence.json')
def enumerate(self):
for rank, size, key in selection():
yield {'matroid': key}
def value(self, params, digits):
key = params['matroid']
if key.startswith('U('):
return uniform_chow(*object_metadata(key))
if key.startswith('K('):
return braid_chow(int(key[2:-1]))
return named_chow(key)
def authenticate_from_stdin():
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
if __name__ == '__main__':
authenticate_from_stdin()
generator = MatroidChow()
if '--fill' in sys.argv or os.environ.get('NUMBERDB_PUBLISH') == '1':
print(generator.publish(message='Fill 37 exact ordinary Chow polynomials with independent checks'))
else:
report = generator.verify(sample=None)
print(report)
sys.exit(0 if report.ok else 1)