back to table · edit · history · where entries came from · files · download
8123 bytes, as of the version from 2026-10-28 21:43 (current). Recorded here, not run.
"""Checks for T591: exact cut counts, independent even subgraphs, and roots.
Run: sage -python checks.py
Needs generate.py and check.py (the campaign's reusable checking module).
No key is required. All JSON evidence is written to stdout with an EVIDENCE
prefix so the campaign wrapper can retain it without writable container mounts.
The even-subgraph algorithm tracks parity of selected edges, not spin states.
The direct enumerator uses individual vertex assignments and an explicit edge
list; it checks the full two-variable count table when mn <= 16.
"""
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.rational_field import QQ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
from sage.rings.complex_interval_field import ComplexIntervalField
from sage.rings.real_mpfi import RealIntervalField
from sage.rings.real_arb import RealBallField
from sage.rings.qqbar import QQbar
from sage.arith.misc import binomial
from generate import rectangles, partition_polynomial, roots, root_ball, FisherZeros
from check import exactness, measure, agrees_with, names_its_rings
from numberdb._write import to_text
from numberdb._compare import digits_of, counts_digits
import json
import time
import sage.version
R = PolynomialRing(QQ, 'x')
x = R.gen()
def edges(m, n):
return [(r*m+c, r*m+c+1) for r in range(n) for c in range(m-1)] + [
(r*m+c, (r+1)*m+c) for r in range(n-1) for c in range(m)]
def brute_counts(m, n):
ee = edges(m, n)
result = [[0] * (len(ee)+1) for _ in range(m*n+1)]
for spins in range(1 << (m*n)):
cut = sum(((spins >> u) ^ (spins >> v)) & 1 for u,v in ee)
result[spins.bit_count()][cut] += 1
return result
def packed_counts(m, n):
"""Full P(z,b), with coefficients in disjoint binary blocks.
Exponent k*(E+1)+d encodes z^k b^d. Each coefficient is < 2^(N+1),
so no carry can mix coefficients; this is exact integer arithmetic.
"""
N, E = m*n, 2*m*n-m-n
width = N+1
states = range(1 << m)
hor = [sum(((s >> c) ^ (s >> (c+1))) & 1 for c in range(m-1))
for s in states]
offset = [(s.bit_count()*(E+1)+hor[s])*width for s in states]
current = [1 << offset[s] for s in states]
for row in range(1, n):
current = [sum(current[s] << (offset[t]+(s^t).bit_count()*width)
for s in states) for t in states]
packed = sum(current)
mask = (1 << width)-1
return [[(packed >> ((k*(E+1)+d)*width)) & mask for d in range(E+1)]
for k in range(N+1)]
def even_subgraphs(m, n):
"""Weight enumerator of edge subsets having even degree at every vertex."""
states = range(1 << m)
horizontal = range(1 << (m-1))
dp = [R.zero() for _ in states]
dp[0] = R.one()
for row in range(n):
new = [R.zero() for _ in states]
for incoming in states:
for h in horizontal:
# Every horizontal edge contributes to its two endpoint parities.
outgoing = incoming ^ h ^ (h << 1)
if row == n-1 and outgoing:
continue
power = h.bit_count() + (outgoing.bit_count() if row < n-1 else 0)
new[outgoing] += dp[incoming] * x**power
dp = new
return dp[0]
def from_even(m, n, ev):
N, E = m*n, 2*m*n-m-n
return QQ(2)**(N-E) * sum((ev[k]*(1-x)**k*(1+x)**(E-k)
for k in range(ev.degree()+1)), R.zero())
def component_accuracy(value):
"""Conservative decimal digits from certified relative interval width."""
ci = ComplexIntervalField(450)(value)
out = []
for part in (ci.real(), ci.imag()):
low, high = (e.exact_rational() for e in part.endpoints())
if low == high:
continue
assert not part.contains_zero()
width = QQ(high)-QQ(low)
scale = min(abs(QQ(low)), abs(QQ(high)))
# Count using exact rational comparisons, without logarithm rounding.
d = 0
while width * 10**(d+1) <= scale:
d += 1
out.append(d)
return min(out) if out else None
def main():
started = time.monotonic()
# Controls precede measurements: C4 has only empty and full even subgraphs.
assert even_subgraphs(2,2) == 1+x**4
assert from_even(2,2,1+x**4) == 2*(1+6*x*x+x**4)
assert brute_counts(2,2) == packed_counts(2,2)
assert component_accuracy(RealBallField(450)(2).sqrt()) >= 130
assert 98 <= component_accuracy(RealIntervalField(450)(1, 1+QQ(1)/10**100)) <= 100
print('Controls passed: C4 counts, high-temperature transform, sqrt(2) precision.',flush=True)
stats, entries, exact_polys, packed_archive = [], {}, {}, {}
for m,n in rectangles():
p = partition_polynomial(m,n)
N,E = m*n,2*m*n-m-n
counts = packed_counts(m,n)
full_at_one = [sum(counts[k][d] for k in range(N+1)) for d in range(E+1)]
assert list(p) == full_at_one
assert [sum(row) for row in counts] == [binomial(N,k) for k in range(N+1)]
assert [row[0] for row in counts] == [1]+[0]*(N-1)+[1]
assert counts == counts[::-1]
if N <= 16:
assert counts == brute_counts(m,n)
ev = even_subgraphs(m,n)
assert ev(1) == 2**(E-N+1)
assert agrees_with({(m,n):R(p)}, lambda _:from_even(m,n,ev)) == []
assert p(0) == 2 and p(1) == 2**N
assert p.degree() == E and p.leading_coefficient() == 2
assert list(p) == list(p)[::-1] # bipartite sublattice flip
rr = roots(m,n)
assert sum(e for r,e in rr) == E
# Independent rational root calculation checks all possible rational cases.
rational = R(p).roots(QQ)
assert all(r == -1 for r,e in rational)
balls, accuracy = [], []
for j,(r,mult) in enumerate(rr,1):
assert r.conjugate() in [s for s,e in rr]
v = root_ball(m,n,j)
a = component_accuracy(v)
if a is not None:
assert a >= 100
accuracy.append(a)
ci = ComplexIntervalField(450)(v)
# A residual is only a consistency check; isolation certifies roots.
assert p(ci).contains_zero()
if j > 1:
assert not ci.overlaps(balls[-1])
balls.append(ci)
entry = FisherZeros().value({'m':m,'n':n,'j':j},100)
text = to_text(entry['number'],digits=100)
assert not counts_digits(text) or digits_of(text) >= 100
entries[(m,n,j)] = entry
assert all(sum((1/v).overlaps(w) for w in balls) == 1 for v in balls)
# Polynomial reconstructed with all multiplicities, in interval arithmetic.
C = PolynomialRing(ComplexIntervalField(450),'t'); t=C.gen()
product=C(p.leading_coefficient())
for ci,(r,e) in zip(balls,rr):
product *= (t-ci)**e
assert all(p[k] in product[k] for k in range(E+1))
assert all(c.real().diameter() < QQ(1)/10**80 and
c.imag().diameter() < QQ(1)/10**80 for c in product)
row={'m':m,'n':n,'degree':E,'distinct_roots':len(rr),
'multiplicities':[int(e) for r,e in rr],
'minimum_component_digits':min(accuracy),
'brute_force':N <= 16}
stats.append(row)
key='%s,%s'%(m,n)
exact_polys[key]=[int(c) for c in p]
packed_archive[key]=counts
print('PASS',json.dumps(row),flush=True)
assert exactness(entries) == []
assert names_its_rings(__import__('pathlib').Path(__file__).with_name('generate.py')) == []
print('EVIDENCE '+json.dumps({'table':'T591','skill_manifest':
'agents/runs/20261028T210416Z-build-skills/manifest.json',
'skill_sha256':'e37efb7e2ededf6c1d7134c673f152f648f26e0267c556aebdf3ec65765d8b4c',
'sage_version':sage.version.version,'shapes':stats,
'measure':measure(entries),'seconds':round(time.monotonic()-started,2),
'polynomials':exact_polys,'bivariate_counts':packed_archive},default=str))
if __name__ == '__main__':
main()