back to table · edit · history · where entries came from · files · download
9665 bytes, as of the version from 2026-09-13 18:31. Recorded here, not run.
"""Ehrhart and h-star polynomials of Birkhoff polytopes -- numberdb.org/T232
For n = 3, ..., 9 this stores the Ehrhart polynomial H_n(t) of the
Birkhoff polytope B_n and the corresponding h-star polynomial h^*_{B_n}(z).
Run it with SageMath:
$ sage -pip install numberdb # once
$ sage -python generate.py # check the table against this code
$ sage -python generate.py --publish # fill the draft, with NUMBERDB_API_KEY set
The h-star rows are transcribed from OEIS A259473. The Ehrhart polynomials are
computed from those rows by the exact binomial transform
H_n(t) = sum_i h_i^* binomial(t + d - i, d), d = (n - 1)^2.
The rings are named rather than taken from `sage.all`, so this runs on a
modular passagemath as well as on a full SageMath.
"""
import os
import sys
from math import factorial
import numberdb.sage as numberdb
from sage.rings.rational_field import QQ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
UP_TO_N = 9
H_STAR_COEFFICIENTS = {
3: [1, 1, 1],
4: [1, 14, 87, 148, 87, 14, 1],
5: [
1, 103, 4306, 63110, 388615, 1115068, 1575669, 1115068, 388615,
63110, 4306, 103, 1,
],
6: [
1, 694, 184015, 15902580, 567296265, 9816969306, 91422589980,
490333468494, 1583419977390, 3166404385990, 3982599815746,
3166404385990, 1583419977390, 490333468494, 91422589980,
9816969306, 567296265, 15902580, 184015, 694, 1,
],
7: [
1, 5003, 8949816, 4328187920, 770190102955, 62539777787319,
2666625885682710, 65645932795749561, 997201792957964742,
9807079042316703213, 64685635446682990495, 293724350332395377192,
936028801524691414372, 2122472911258825483561,
3456425267264749604229, 4064141523287129936850,
3456425267264749604229, 2122472911258825483561,
936028801524691414372, 293724350332395377192, 64685635446682990495,
9807079042316703213, 997201792957964742, 65645932795749561,
2666625885682710, 62539777787319, 770190102955, 4328187920,
8949816, 5003, 1,
],
8: [
1, 40270, 542993185, 1551859220800, 1377632128311950,
498432452127668996, 87888683594598088174, 8529870051634691986304,
496616222722725047348525, 18473631674871162451428150,
460430347217397847803805005, 7975196334413371639908964800,
98793132162715260718675306856, 895332248243995123415156287600,
6044958149160587362885321695400, 30850706020137383990151083805760,
120403702185594213967063539302834, 362661729985413873180826930866812,
849053643729256196155791184726450,
1553234775745337911019798743412800,
2228417931600348332536332133118836,
2512737909276940696815457271935000,
2228417931600348332536332133118836,
1553234775745337911019798743412800,
849053643729256196155791184726450, 362661729985413873180826930866812,
120403702185594213967063539302834, 30850706020137383990151083805760,
6044958149160587362885321695400, 895332248243995123415156287600,
98793132162715260718675306856, 7975196334413371639908964800,
460430347217397847803805005, 18473631674871162451428150,
496616222722725047348525, 8529870051634691986304,
87888683594598088174, 498432452127668996, 1377632128311950,
1551859220800, 542993185, 40270, 1,
],
9: [
1, 362815, 41490998200, 769503081514440, 3630125421024775050,
6036626036190814706838, 4400909794684586311301544,
1634033933089041935018176440, 343817041097049120525342620499,
44349039398141660669491569945072, 3722062298879786425674784251609117,
212847899154627740838940155253034352,
8601869690376443314879703176067501316,
252987354027213124977092655376562528976,
5545936263890618405976280022882313926124,
92423483434101806903642403404436299197152,
1190255080668353455152480159395378123265777,
12009017638442881240375510915302941456800236,
96027781256448231008707141500882904946891208,
614517901377538979103721722107317203827977131,
3173106645240817213910815276648388814043712682,
13312073889037856623803461967503340699939569532,
45637872761654094348695343584831800191222335736,
128469318728990888595981428073315102335173197330,
298096903812367589540374169122550434723054640067,
571924462109190961984273392260682480694573213464,
909407873749465950837611399465682311368920596436,
1200410000051567687034587855237713661922643916056,
1316658987633385786557736875950031956970417575917,
1200410000051567687034587855237713661922643916056,
909407873749465950837611399465682311368920596436,
571924462109190961984273392260682480694573213464,
298096903812367589540374169122550434723054640067,
128469318728990888595981428073315102335173197330,
45637872761654094348695343584831800191222335736,
13312073889037856623803461967503340699939569532,
3173106645240817213910815276648388814043712682,
614517901377538979103721722107317203827977131,
96027781256448231008707141500882904946891208,
12009017638442881240375510915302941456800236,
1190255080668353455152480159395378123265777,
92423483434101806903642403404436299197152,
5545936263890618405976280022882313926124,
252987354027213124977092655376562528976,
8601869690376443314879703176067501316,
212847899154627740838940155253034352,
3722062298879786425674784251609117, 44349039398141660669491569945072,
343817041097049120525342620499, 1634033933089041935018176440,
4400909794684586311301544, 6036626036190814706838,
3630125421024775050, 769503081514440, 41490998200, 362815, 1,
],
}
_T = PolynomialRing(QQ, "t")
_t = _T.gen()
_Z = PolynomialRing(QQ, "z")
_z = _Z.gen()
def _key_from_stdin():
if os.environ.get("NUMBERDB_KEY_FROM_STDIN") != "1":
return
token = sys.stdin.read().strip()
if "=" in token and token.split("=", 1)[0].isupper():
token = token.split("=", 1)[1].strip().strip("'\"")
if token:
os.environ["NUMBERDB_API_KEY"] = token
def dimension(n):
return (n - 1) ** 2
def binomial_polynomial(shift, degree):
value = _T.one()
for j in range(degree):
value *= _t + QQ(shift - j)
return value / QQ(factorial(degree))
def h_star_polynomial(n):
return sum(QQ(c) * _z ** i for i, c in enumerate(H_STAR_COEFFICIENTS[n]))
def ehrhart_polynomial(n):
d = dimension(n)
return sum(
QQ(c) * binomial_polynomial(d - i, d)
for i, c in enumerate(H_STAR_COEFFICIENTS[n])
)
class BirkhoffPolytopeEhrhartPolynomials(numberdb.Generator):
table = os.environ.get("NUMBERDB_TABLE", "T232")
parameters = ("n", "form")
type = "Q[]"
rigour = "exact"
def enumerate(self, up_to_n=UP_TO_N):
for n in range(3, up_to_n + 1):
yield {"n": str(n), "form": "ehrhart"}
yield {"n": str(n), "form": "h-star"}
def value(self, params, digits):
n = int(params["n"])
form = params["form"]
if form == "ehrhart":
return {
"number": ehrhart_polynomial(n),
"param-latex": "$H_%d(t)$" % n,
}
if form == "h-star":
return {
"number": h_star_polynomial(n),
"param-latex": "$h^*_{B_%d}(z)$" % n,
}
raise ValueError("unknown form %r" % (form,))
def fill_draft_once(generator, message):
"""Fill a fresh draft without the empty upsert probe."""
from numberdb._generate import (
_check_precision,
_check_rigour,
_producer,
_run_name,
_source_files,
)
from numberdb._write import Entries, attach, submit_entries, to_text
table = generator.table
run = _run_name(generator)
entries = Entries(*generator.parameters)
for params in generator.enumerate():
params = dict(params)
wanted = generator.digits_for(params)
entry = generator._entry(params, wanted)
value = entry["number"]
identity = ",".join(str(params[name]) for name in generator.parameters)
_check_rigour(generator, table, identity, value)
written = to_text(value, wanted, generator.format)
_check_precision(table, identity, written, wanted, lowering=False)
record = dict(entry)
record.pop("digits", None)
entries.add(**params, **record, digits=wanted)
answer = submit_entries(
table,
entries,
message=message,
produced_by=_producer(generator),
upsert=False,
run=run,
rigour=generator.rigour,
)
files = _source_files(generator)
stored = []
for name, body in sorted(files.items()):
attach(table, name, body, run=run, message=message,
rigour=generator.rigour)
stored.append(name)
return {
"tid": answer.get("tid", table),
"revision": answer.get("revision"),
"entries": len(entries),
"files": stored,
}
if __name__ == "__main__":
_key_from_stdin()
generator = BirkhoffPolytopeEhrhartPolynomials()
if os.environ.get("NUMBERDB_PUBLISH") == "1" or "--publish" in sys.argv:
print(fill_draft_once(
generator,
message="Birkhoff polytope Ehrhart and h-star polynomials"))
else:
report = generator.verify(sample=None)
print(report)
sys.exit(0 if report.ok else 1)