back to table · edit · history · where entries came from · files · download
11847 bytes, as of the version from 2026-10-25 10:19 (current). Recorded here, not run.
"""Asymptotic amplitudes of the classes of trees -- numberdb.org/T482.
Run with SageMath (or passagemath):
sage -pip install numberdb
sage -python generate.py # verify the stored draft/table
sage -python generate.py --compute # compute without network writes
sage -python generate.py --fill # fill this draft, API key required
The --fill operation writes entries, not publication or review status.
Set NUMBERDB_API_KEY for access to the unpublished draft.
All fourteen classes match the node-counting conventions of T448. In
particular, a planted root is included in n. HRS (1975), corrected (1986),
and Genitrini (2016, arXiv:1605.00837) give the singularity method.
Certified arithmetic: a_n <= Catalan(n-1) <= 4^(n-1) for each rooted
unordered class, by forgetting the order of plane trees. At y < 1/4,
truncating A(y) after M gives tail <= y(4y)^M/(1-4y); truncating yA'(y)
gives tail <= y(4y)^M*((M+1)-4My)/(1-4y)^2. Every omitted tail is added as
a symmetric Arb error ball. For Q=sum_{k>=2} sign_k A(x^k)/k, the tails
after K are bounded by x^(K+1)/((K+1)(1-x)(1-4x^(K+1))) and, for xQ',
by x^(K+1)/((1-x)(1-4x^(K+1))^2). The constants 1/2 and 23/100 bound x
and x^k respectively in the summation cutoff choices. Exact inequalities
are verified at runtime; these choices are not empirical error estimates.
Newton steps only propose a rational centre. Opposite certified signs at
centre +/- 10^(-digits-15) certify the root interval. The asymptotic formulas
are evaluated on that interval, retaining the root error. Working precision
has 160 guard bits, and series errors target digits+35 decimal places.
The build also repeated the computation with 30 extra requested digits.
"""
import os
import sys
from functools import lru_cache
if os.environ.get('NUMBERDB_KEY_FROM_STDIN') == '1':
os.environ['NUMBERDB_API_KEY'] = sys.stdin.read().strip()
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.rational_field import QQ
from sage.rings.real_arb import RealBallField
CLASSES = ('rooted', 'free', 'planted', 'identity-rooted', 'identity-free',
'series-reduced-planted', 'series-reduced-rooted',
'series-reduced-free', 'degree-bounded-2', 'degree-bounded-3',
'plane', 'plane-binary', 'labelled-rooted', 'labelled-free')
GUARD_BITS = 160
@lru_cache(None)
def coefficients(kind, N):
"""Exact integer coefficients; each division has its remainder checked."""
a = [ZZ(0)] * (N + 1)
if kind in ('rooted', 'identity', 'series'):
sigma = [ZZ(0)] * (N + 1)
for n in range(1, N + 1):
if n == 1:
a[n] = ZZ(1)
else:
total = sum((sigma[j] + ((-1)**j if kind == 'series' else 0))
* a[n-j] for j in range(1, n))
a[n], remainder = total.quo_rem(n-1)
assert remainder == 0 and a[n] >= 0
for j in range(n, N + 1, n):
sign = (-1)**(j//n + 1) if kind == 'identity' else 1
sigma[j] += sign * n * a[n]
else:
degree = int(kind)
square = [ZZ(0)] * (N+1)
for n in range(1, N+1):
m = n-1
square[m] = sum(a[i]*a[m-i] for i in range(1,m))
total = 6*(1 if m == 0 else a[m])
total += 3*(square[m] + (a[m//2] if m%2 == 0 else 0))
if degree == 3:
total += sum(square[i]*a[m-i] for i in range(1,m))
total += 3*sum(a[j]*a[m-2*j] for j in range(1,m//2+1))
total += 2*(a[m//3] if m%3 == 0 else 0)
a[n], remainder = ZZ(total).quo_rem(6)
assert remainder == 0 and a[n] >= 0
return tuple(a)
class Enclosure:
def __init__(self, kind, digits):
self.kind = kind
self.B = RealBallField(numberdb.bits(digits, losing=GUARD_BITS))
self.eps = self.B(QQ(1)/10**(digits+35))
self.N = 1
upper = {'rooted':QQ(34)/100, 'identity':QQ(41)/100,
'series':QQ(46)/100, '2':QQ(41)/100, '3':QQ(36)/100}[kind]
self.ymax = upper**2
q = self.B(4*self.ymax)
while not self.B(self.ymax)*q**self.N*(self.N+1)/(1-q)**2 < self.eps:
self.N += 1
self.a = coefficients(kind, self.N)
self.K = 4*(digits+35)
self.cutoffs = {}
def series(self, y, k):
B = self.B
assert y > 0 and y < self.ymax
# The cutoff is a speed choice only: the actual tail is bounded anew.
M = self.cutoffs.get(k)
if M is None:
M = 1
q = 4*y
while not y*q**M*(M+1)/(1-q)**2 < self.eps:
M += 1
self.cutoffs[k] = M
assert M <= self.N
value = B(0)
weighted = B(0)
for n in range(M, 0, -1):
value = (value + self.a[n])*y
weighted = (weighted + n*self.a[n])*y
q = 4*y
tail = y*q**M/(1-q)
dtail = y*q**M*((M+1)-M*q)/(1-q)**2
return value + B(0,tail.upper()), weighted + B(0,dtail.upper())
def Q(self, x, absolute=False):
B = self.B
value, weighted = B(0), B(0)
y = x
for k in range(2,self.K+1):
y *= x
A, D = self.series(y,k)
sign = (-1)**(k+1) if self.kind == 'identity' and not absolute else 1
value += sign*A/k
weighted += sign*D
y *= x
tail = y/((self.K+1)*(1-x)*(1-4*y))
dtail = y/((1-x)*(1-4*y)**2)
return value+B(0,tail.upper()), weighted+B(0,dtail.upper())
def equation(self, x):
"""Return g(x), g'(x), and the squared square-root coefficient."""
if self.kind in ('rooted','identity','series'):
Q, D = self.Q(x)
g = x.log()+1+Q
b2half = 1+D
if self.kind == 'series':
g -= (1+x).log()
b2half -= x/(1+x)
return g, b2half/x, 2*b2half
A2, D2 = self.series(x*x,2)
if self.kind == '2':
tau = 1/x-1
g = (1-x)**2/x**2-2-A2
derivative = -2*(1-x)/x**3-2*D2/x
b2 = 2*(tau/x + D2)
return g, derivative, b2
A3, D3 = self.series(x**3,3)
tau = -1+(2/x-1-A2).sqrt()
phi = 1+tau+(tau**2+A2)/2+(tau**3+3*tau*A2+2*A3)/6
g = x*phi-tau
Fx = phi+(1+tau)*D2+D3
return g, Fx, 2*Fx/(1+tau)
def solve(self, digits):
seeds = {'rooted':QQ(338)/1000, 'identity':QQ(397)/1000,
'series':QQ(457)/1000,'2':QQ(403)/1000,'3':QQ(355)/1000}
if self.kind == 'identity':
# |x Q'(x)| is bounded by its positive-term majorant at 0.4.
# Consequently g is strictly increasing on (0,0.4].
_, majorant = self.Q(self.B(QQ(2)/5), absolute=True)
assert majorant < 1
x = self.B(seeds[self.kind])
for _ in range(8):
g, d, _ = self.equation(x)
x = self.B((x-g/d).mid())
centre = QQ(x.mid())
radius = QQ(1)/10**(digits+15)
low, high = self.B(centre-radius), self.B(centre+radius)
gl, _, _ = self.equation(low)
gh, _, _ = self.equation(high)
assert (gl < 0 < gh) or (gh < 0 < gl), (self.kind,gl,gh)
rho = self.B(centre,radius)
_, derivative, b2 = self.equation(rho)
assert not derivative.contains_zero() and b2 > 0
b = b2.sqrt()
assert rho.is_finite() and b.is_finite()
return rho, b
@lru_cache(None)
def compute(digits=100):
B = RealBallField(numberdb.bits(digits, losing=GUARD_BITS))
sqrtpi = B.pi().sqrt()
out, radii, evidence = {}, {}, {}
for kind in ('rooted','identity','series','2','3'):
engine = Enclosure(kind,digits)
rho, b = engine.solve(digits)
c = b/(2*sqrtpi)
radii[kind] = rho
evidence[kind] = {'N':engine.N,'max_used':max(engine.cutoffs.values()),
'K':engine.K,'bits_retained':int(c.accuracy())}
if kind == 'rooted':
out.update({'rooted':c,'free':b**3/(4*sqrtpi),'planted':rho*c})
elif kind == 'identity':
out.update({'identity-rooted':c,'identity-free':b**3/(4*sqrtpi)})
elif kind == 'series':
out.update({'series-reduced-planted':rho*c,'series-reduced-rooted':c,
'series-reduced-free':(1+rho)*b**3/(4*sqrtpi)})
else:
out['degree-bounded-'+kind] = c
out['plane'] = 1/(4*sqrtpi)
out['plane-binary'] = B(3).sqrt()/(2*sqrtpi)
out['labelled-rooted'] = 1/(2*B.pi()).sqrt()
out['labelled-free'] = out['labelled-rooted']
for v in out.values():
assert v.is_finite() and v > 0 and v.accuracy() > numberdb.bits(digits)
return out, radii, evidence
COMMENTS = {
'rooted':r'$\alpha=3/2$. Unlabelled rooted trees, with unordered children; this is Otter\'s rooted-tree amplitude CITE{RootedAmplitude}.',
'free':r'$\alpha=5/2$. Unlabelled unrooted trees; this is Otter\'s unrooted-tree amplitude CITE{FreeAmplitude}.',
'planted':r'$\alpha=3/2$. The planted root is an additional node, so the count on $n$ nodes equals the rooted-tree count on $n-1$ nodes.',
'identity-rooted':r'$\alpha=3/2$. Only the identity automorphism preserves the root. The underlying unrooted tree need not be asymmetric CITE{Genitrini}.',
'identity-free':r'$\alpha=5/2$. The unrooted tree has trivial automorphism group CITE{Correction}.',
'series-reduced-planted':r'$\alpha=3/2$. The planted root has degree $1$ and is counted as a node; no other node has degree $2$ CITE{HRS}.',
'series-reduced-rooted':r'$\alpha=3/2$. No node has degree $2$, including the root CITE{SeriesRooted}.',
'series-reduced-free':r'$\alpha=5/2$. Unrooted trees with no node of degree $2$ CITE{HRS}.',
'degree-bounded-2':r'$\alpha=3/2$. Every node has at most two unordered children. The count on $n$ nodes is A001190$(n+1)$ CITE{Binary}.',
'degree-bounded-3':r'$\alpha=3/2$. Every node has at most three unordered children CITE{Ternary}.',
'plane':r'$\alpha=3/2$. Children are ordered. The count on $n$ nodes is the Catalan number $C_{n-1}$ CITE{Catalan}.',
'plane-binary':r'$\alpha=3/2$. Each node has zero, one or two ordered children. The count on $n$ nodes is the Motzkin number $M_{n-1}$ CITE{Motzkin}.',
'labelled-rooted':r'$\alpha=3/2$. The node labels are $1,\ldots,n$, and Cayley\'s count is $n^{n-1}$ CITE{Cayley}.',
'labelled-free':r'$\alpha=5/2$. The node labels are $1,\ldots,n$, and Cayley\'s count is $n^{n-2}$ CITE{Cayley}.',
}
# Apostrophes in raw single-quoted strings must not reach the document escaped.
COMMENTS = {k:v.replace("\\'", "'") for k,v in COMMENTS.items()}
class TreeAmplitudes(numberdb.Generator):
table = 'T482'
parameters = ('class','size','labelling')
type = 'R'
digits = 100
rigour = 'proven'
files = ('generate.py', 'checks.py', 'check.py', 'dry_run.py', 'build-report.md')
def enumerate(self):
for name in CLASSES:
yield {'class':name,'size':'nodes',
'labelling':'labelled' if name.startswith('labelled-') else 'unlabelled'}
def value(self, params, digits):
return {'number':compute(digits)[0][params['class']],
'comment':COMMENTS[params['class']]}
if __name__ == '__main__':
if '--compute' in sys.argv:
values, radii, evidence = compute()
for name in CLASSES:
print(name, values[name])
print('evidence',evidence)
elif '--fill' in sys.argv or os.environ.get('NUMBERDB_PUBLISH') == '1':
print(TreeAmplitudes().publish(message='Fill fourteen tree amplitudes with certified 100-digit enclosures'))
else:
result = TreeAmplitudes().verify(sample=None)
print(result)
sys.exit(0 if result.ok else 1)