back to table · edit · history · where entries came from · files · download
12319 bytes, as of the version from 2026-10-25 10:38. Recorded here, not run.
"""Independent counts and identities for numberdb.org/T483.
sage -python checks.py
sage -python checks.py --stored # NUMBERDB_API_KEY for a private draft
The small-map enumerator uses permutations of darts with a fixed edge
involution, filters connected genus-zero rotation systems, and divides by
the free action of relabellings fixing the root dart. No counting formula
is used inside that enumerator. Formal series and count-ratio checks are
exact over QQ. Assertions fail loudly; JSON on stdout is the evidence.
"""
import json
import math
import os
import sys
from collections import Counter
from itertools import permutations
import numberdb.sage as numberdb
from sage.rings.rational_field import QQ
from sage.rings.integer_ring import ZZ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
from sage.rings.real_arb import RealBallField
from numberdb._write import to_text
from numberdb._generate import _stored_entries
from generate import PlanarMapGrowth
from check import exactness, measure, agrees_with, names_its_rings
P = PolynomialRing(QQ, 'x')
x = P.gen()
LIMIT = 45
def mul(a, b):
return (a * b).truncate(LIMIT)
def power(a, k):
out = P.one()
for _ in range(k):
out = mul(out, a)
return out
def inverse(a):
c = [QQ(1) / a[0]]
for n in range(1, LIMIT):
c.append(-sum(a[k] * c[n-k] for k in range(1, n+1)) / a[0])
return P(c)
def compose(a, b):
out = P.zero()
for c in reversed(a.list()):
out = mul(out, b) + c
return out
def factorial_count(scale, top, bottom, n, prefactor=2):
numerator = QQ(prefactor) * QQ(scale)**n
for a,b in top:
numerator *= math.factorial(a*n+b)
denominator = QQ(1)
for a,b in bottom:
denominator *= math.factorial(a*n+b)
return numerator / denominator
SPECS = {
'all': (3, [(2,0)], [(1,0),(1,2)], 2),
'2-connected': (1, [(3,-3)], [(1,0),(2,-1)], 2),
'bipartite': (2, [(2,0)], [(1,0),(1,2)], QQ(3)/2),
'loopless': (1, [(4,1)], [(1,1),(3,2)], 2),
'triangulations-II': (2, [(3,0)], [(1,0),(2,2)], 2),
'triangulations-III': (1, [(4,-3)], [(1,0),(3,-1)], 2),
}
SPECS['eulerian'] = SPECS['bipartite']
SPECS['quadrangulations'] = SPECS['all']
SPECS['simple-quadrangulations'] = SPECS['2-connected']
def count(key, n):
a,b,c,d = SPECS[key]
return factorial_count(a,b,c,n,d)
def ratio_polynomials(spec):
scale, top, bottom, _ = spec
num = P(scale)
den = P.one()
for a,b in top:
for j in range(1,a+1):
num *= a*x+b+j
for a,b in bottom:
for j in range(1,a+1):
den *= a*x+b+j
assert num.degree() == den.degree()
return num, den
def double_factorial(n):
return math.prod(range(n, 0, -2))
def type_i_count(n):
# n+2 vertices; Curien-Le Gall monogon with n+1 inner vertices.
return QQ(2 * 4**n * double_factorial(3*n)) / QQ(
math.factorial(n+1) * double_factorial(n+2))
def cycles(perm):
labels = [-1] * len(perm)
parts = []
for start in range(len(perm)):
if labels[start] != -1:
continue
cycle = []
k = start
while labels[k] == -1:
labels[k] = len(parts)
cycle.append(k)
k = perm[k]
parts.append(cycle)
return parts, labels
def reachable(adj, deleted=None):
nodes = [v for v in range(len(adj)) if v != deleted]
if not nodes:
return True
seen = {nodes[0]}
todo = [nodes[0]]
while todo:
v = todo.pop()
for w in adj[v]:
if w != deleted and w not in seen:
seen.add(w)
todo.append(w)
return len(seen) == len(nodes)
def enumerate_maps(n):
totals = Counter()
for sigma in permutations(range(2*n)):
vertices, labels = cycles(sigma)
faces, _ = cycles(tuple(sigma[k ^ 1] for k in range(2*n)))
if len(vertices) + len(faces) != n + 2:
continue
edges = [(labels[k], labels[k+1]) for k in range(0,2*n,2)]
adj = [set() for _ in vertices]
for a,b in edges:
adj[a].add(b)
adj[b].add(a)
if not reachable(adj):
continue
loopless = all(a != b for a,b in edges)
simple = loopless and len({tuple(sorted(e)) for e in edges}) == n
colours = {0: 0}
todo = [0]
bipartite = True
while todo:
v = todo.pop()
for w in adj[v]:
if w not in colours:
colours[w] = 1-colours[v]
todo.append(w)
elif colours[w] == colours[v]:
bipartite = False
totals['all'] += 1
totals['trees'] += len(faces) == 1 and len(vertices) == n+1
totals['loopless'] += loopless
totals['bipartite'] += bipartite
totals['eulerian'] += all(len(v)%2 == 0 for v in vertices)
totals['2-connected'] += (n >= 2 and loopless and
all(reachable(adj,v) for v in range(len(vertices))))
if all(len(f) == 3 for f in faces):
totals['triangulations-I'] += 1
totals['triangulations-II'] += loopless
totals['triangulations-III'] += simple
if all(len(f) == 4 for f in faces):
totals['quadrangulations'] += 1
totals['simple-quadrangulations'] += simple
orbit = 2**(n-1)*math.factorial(n-1)
assert all(v % orbit == 0 for v in totals.values())
return {k:v//orbit for k,v in totals.items()}
def serialized_interval(text):
# This generator emits integers, fractions, or a plain decimal.
if '.' not in text and 'e' not in text.lower():
q = QQ(text)
return q,q
from decimal import Decimal
d = Decimal(text)
digits = d.as_tuple()
numerator = int(''.join(map(str, digits.digits))) * (-1 if digits.sign else 1)
scale = QQ(10)**digits.exponent
centre = QQ(numerator)*scale
return centre-scale,centre+scale
def main():
generator = PlanarMapGrowth()
params = list(generator.enumerate())
values = {p['class']:generator.value(p,100)['number'] for p in params}
assert not exactness(values)
assert not names_its_rings(os.path.join(os.path.dirname(__file__),'generate.py'))
report = {'measurement': measure(values), 'count_ratio_tests': {}}
# Known independent control: Catalan counts have growth constant 4.
catalan_spec = (1,[(2,0)],[(1,0),(1,1)],1)
cn,cd = ratio_polynomials(catalan_spec)
assert cn.leading_coefficient()/cd.leading_coefficient() == 4
expected = {}
for key,spec in SPECS.items():
num,den = ratio_polynomials(spec)
expected[key] = num.leading_coefficient()/den.leading_coefficient()
for n in range(2,82):
assert count(key,n).denominator() == 1
assert count(key,n+1)/count(key,n) == num(n)/den(n)
approximation = num(5000)/den(5000)
assert abs(approximation/expected[key]-1) < QQ(1)/1000
report['count_ratio_tests'][key] = {'limit':str(expected[key]),'checked_n':'2..81','ratio_at_5000':str(RealBallField(60)(approximation))}
assert not agrees_with({k:values[k] for k in expected}, lambda k:expected[k])
# Type I uses a two-step count ratio, tending to 432.
num = 16*(3*x+2)*(3*x+4)*(3*x+6)
den = (x+2)*(x+3)*(x+4)
assert num.leading_coefficient()/den.leading_coefficient() == 432
for n in range(1,81):
assert type_i_count(n).denominator() == 1
assert type_i_count(n+2)/type_i_count(n) == num(n)/den(n)
v = values['triangulations-I']
assert v.is_finite() and v > 0
assert v.rad() < QQ(1)/10**115
assert 432 in v*v
text_value = to_text(v,100)
lo,hi = serialized_interval(text_value)
assert 0 < lo and lo*lo < 432 < hi*hi
v150 = generator.value({'class':'triangulations-I','size':'vertices','labelling':'unlabelled'},150)['number']
assert v150.is_finite() and v.overlaps(v150) and v150.rad() < QQ(1)/10**165
report['type_I'] = {'number':text_value,'radius':str(v.rad()),'field':str(v.parent()),'exact_bracket_squared':True,'two_step_ratios':80}
# Rooted maps' 2-core parameter: z=u(1-u)^2, B=u^2(1-2u).
# D=B/z=u(1-2u)/(1-u)^2. The inverse equation has discriminant 1-4x.
K = P.fraction_field()
u=K(x)
z=u*(1-u)**2
D=u*(1-2*u)/(1-u)**2
assert z.derivative()(QQ(1)/3) == 0
assert z(QQ(1)/3) == QQ(4)/27
assert D.derivative()(QQ(1)/3) == 0
assert D(QQ(1)/3) == QQ(1)/4
assert (2*x+1)**2-4*x*(x+2) == 1-4*x
expected['3-connected'] = 1 / D(QQ(1)/3)
assert values['3-connected'] == expected['3-connected']
# Formal inverse and 3-core relation, through degree 44.
sq = [QQ(1)]
for n in range(1,LIMIT):
sq.append(sq[-1]*(QQ(1)/2-(n-1))*(-4)/n)
w = mul(1+2*x-P(sq), inverse(2*(x+2)))
F = mul(w,power(1-w,2))
assert mul(w*(1-2*w),inverse(power(1-w,2))) == x
T = mul(x, x-2*mul(x*x,inverse(1+x))-F)
assert [T[i] for i in range(6)] == [0]*6
assert T[6] == 1 and T[7] == 0 and T[8] == 4
assert all(T[i] in ZZ and T[i]>=0 for i in range(LIMIT))
# a=1+x*a^3; q=x*(a-1)*(2-a). Compare every coefficient to shifted factorials.
a=P.one()
for _ in range(LIMIT):
a=(1+x*power(a,3)).truncate(LIMIT)
q=mul(x,mul(a-1,2-a))
assert all(q[n] == count('simple-quadrangulations',n) for n in range(2,LIMIT))
# Recover the 2-core parametrisation independently and check the full
# corner-substitution identity A=1+2*z*A^2+B(z*A^2).
u=P.zero()
for _ in range(LIMIT):
u=mul(x,inverse(power(1-u,2)))
B=mul(power(u,2),1-2*u)
assert all(B[n]==count('2-connected',n) for n in range(2,LIMIT))
A=P([count('all',n) for n in range(LIMIT)])
zA2=mul(x,power(A,2))
assert A==(1+2*zA2+compose(B,zA2)).truncate(LIMIT)
report['formal_series']={'degree':LIMIT-1,'triconnected_first_nonzero':str(T[6]),'triconnected_n8':str(T[8]),'quadrangulation_index_shift_resolved':True}
# Enumerate actual maps. The one-edge count and trees are controls.
small={n:enumerate_maps(n) for n in range(1,5)}
assert small[1]['all']==2 and small[1]['loopless']==1
for n,counts in small.items():
assert counts['trees']==math.comb(2*n,n)//(n+1)
for key in ['all','loopless','bipartite','eulerian']:
assert counts[key] == count(key,n),(n,key,counts[key],count(key,n))
if n>=2:
assert counts['2-connected']==count('2-connected',n)
if n%2==0:
assert counts.get('quadrangulations',0)==count('quadrangulations',n//2)
if n==3:
assert counts['triangulations-I']==type_i_count(1)
assert counts['triangulations-II']==count('triangulations-II',1)
assert counts['triangulations-III']==count('triangulations-III',1)
assert small[4]['simple-quadrangulations']==1
report['rotation_system_counts']=small
# Check relationships on every generated row.
assert values['all']==values['quadrangulations']
assert values['2-connected']==values['simple-quadrangulations']
assert values['bipartite']==values['eulerian']
assert values['loopless']==values['triangulations-III']
assert values['triangulations-III']<values['triangulations-II']<values['triangulations-I']
report['source_count_identity_checks']='passed'
if '--stored' in sys.argv or os.environ.get('NUMBERDB_KEY_FROM_STDIN')=='1':
if os.environ.get('NUMBERDB_KEY_FROM_STDIN')=='1':
numberdb.configure(api_key=sys.stdin.read().strip())
doc=numberdb.table('T483')
rows=_stored_entries(doc)
assert len(rows)==11
for identity,p in zip(rows,params):
assert identity==','.join(p[k] for k in generator.parameters)
lo,hi=serialized_interval(rows[identity])
key=p['class']
if key=='triangulations-I':
assert 0<lo and lo*lo<432<hi*hi
assert hi-lo<=QQ(2)/10**98
else:
assert lo==hi==expected[key]
checked=generator.verify(sample=None)
assert checked.ok
report['stored']={'rows':len(rows),'independent_exact_checks':11,'verify':str(checked)}
print(json.dumps(report,indent=2,default=str))
if __name__=='__main__':
main()