"""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']