back to table · edit · history · where entries came from · files · download
5635 bytes, as of the version from 2026-10-28 13:09. Recorded here, not run.
"""Augmented Chow polynomials of matroids -- numberdb.org/T582.
Run with SageMath:
sage -pip install numberdb # once
sage -python generate.py # verify the stored draft/table
sage -python checks.py # independent exact checks
sage -python generate.py --fill # fill, with NUMBERDB_API_KEY set
--fill calls Generator.publish to write entries and attachments. It never
publishes, offers, or reviews the table. Private reads need the owning API key.
NUMBERDB_KEY_FROM_STDIN=1 reads that key from stdin for the campaign wrapper.
The variable t is algebraic degree. We evaluate the weighted-chain formula
of Ferroni--Matherne--Stevens--Vecchi (2024), Proposition 3.6, by dynamic
programming. Upper flat intervals compute the ordinary Chow factor using
Proposition 3.5. Uniform flats are grouped by size. Braid flats are grouped
by block count: the upper interval of a partition with k blocks is Pi_k.
Named matroids use their actual flats, without identifying equal-rank minors.
Every operation is over ZZ[t]; there are no approximations or divisions.
The bounded mixed selection is explained in 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 database_matroids as 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')
@lru_cache(None)
def positive_sum(k):
"""t + ... + t^k, or zero when k <= 0."""
return R([0] + [1] * max(k, 0))
@lru_cache(None)
def stirling2(n, k):
if n == 0:
return int(k == 0)
if k <= 0 or k > n:
return 0
return k * stirling2(n - 1, k) + stirling2(n - 1, k - 1)
@lru_cache(None)
def uniform_ordinary(r, n):
if r == 0:
return R.one()
return (R.one() + positive_sum(r - 1)
+ sum((comb(n, j) * positive_sum(j - 1)
* uniform_ordinary(r - j, n - j)
for j in range(1, r)), R.zero()))
def uniform_augmented(r, n):
if not (0 <= r <= n):
raise ValueError('Require 0 <= rank <= size')
if r == 0:
if n:
raise ValueError('Looped input is outside the domain')
return R.one()
return (R.one() + positive_sum(r)
+ sum((comb(n, j) * positive_sum(j)
* uniform_ordinary(r - j, n - j)
for j in range(1, r)), R.zero()))
@lru_cache(None)
def braid_ordinary(m):
if m < 1:
raise ValueError('Require at least one vertex')
return R.one() + sum((stirling2(m, k) * positive_sum(m - k - 1)
* braid_ordinary(k) for k in range(1, m)), R.zero())
def braid_augmented(m):
return R.one() + sum((stirling2(m, k) * positive_sum(m - k)
* braid_ordinary(k) for k in range(1, m)), R.zero())
@lru_cache(None)
def named_matroid(name):
if name not in NAMED:
raise ValueError('Unknown catalogue key')
return getattr(catalog, name)()
@lru_cache(None)
def named_intervals(name):
"""Actual upper intervals, keyed by ground-set bit masks."""
M = named_matroid(name)
assert M.is_simple()
labels = {e: i for i, e in enumerate(sorted(M.groundset(), key=str))}
rank = {sum(1 << labels[e] for e in F): k
for k in range(M.rank() + 1) for F in M.flats(k)}
masks = sorted(rank, key=lambda f: (rank[f], f))
ordinary = {}
for f in reversed(masks):
ordinary[f] = R.one() + sum(
(positive_sum(rank[g] - rank[f] - 1) * ordinary[g]
for g in masks if f != g and f & g == f), R.zero())
return rank, ordinary
def named_augmented(name):
rank, ordinary = named_intervals(name)
return R.one() + sum((positive_sum(rank[f]) * ordinary[f]
for f in rank if f), R.zero())
def selected_objects():
rows = [(r, r + c, f'U({r},{r+c})')
for r in range(3, 9) for c in range(1, 5)]
rows += [(m - 1, comb(m, 2), f'K({m})') for m in range(4, 9)]
rows += [(int(named_matroid(name).rank()), int(named_matroid(name).size()), name)
for name in NAMED]
return sorted(rows)
class MatroidAugmentedChow(numberdb.Generator):
table = 'T582'
parameters = ('matroid',)
type = 'Z[]'
rigour = 'exact'
digits = 100 # ignored for exact polynomials
files = ('generate.py', 'checks.py', 'check.py', 'argument-selection.md',
'numerical-evidence.md', 'skill-evidence.json')
def enumerate(self):
for r, n, key in selected_objects():
yield {'matroid': key}
def value(self, params, digits):
key = params['matroid']
if key.startswith('U('):
r, n = map(int, key[2:-1].split(','))
return uniform_augmented(r, n)
if key.startswith('K('):
return braid_augmented(int(key[2:-1]))
return named_augmented(key)
if __name__ == '__main__':
if os.environ.get('NUMBERDB_KEY_FROM_STDIN') == '1':
numberdb.configure(api_key=sys.stdin.read().strip())
gen = MatroidAugmentedChow()
if '--fill' in sys.argv or os.environ.get('NUMBERDB_PUBLISH') == '1':
print(gen.publish(message='Fill 37 exact augmented Chow polynomials',
assisted_by=os.environ.get('NUMBERDB_ASSISTED_BY', '')))
else:
report = gen.verify(sample=None)
print(report)
sys.exit(0 if report.ok else 1)