back to table · edit · history · where entries came from · files · download
11879 bytes, as of the version from 2026-09-27 14:10 (current). Recorded here, not run.
"""Reproduce T447 from Shur's published decimal bounds, without network writes.
Run with Python 3 (no third-party dependencies for these commands):
python3 generate.py
python3 generate.py --entries
python3 generate.py --verify candidate.json
python3 generate.py --verify baseline.json --relation contains
python3 generate.py --metadata
Optional NumberDB interface: install numberdb, then import this file and call
numberdb_generator().verify(sample=None, client=your_read_client).
Source: https://arxiv.org/html/1009.4415v2, Tables 1 and 2 (2012-04-04).
The embedded strings retain the source's seven decimal places. A singleton
cell is a rounded growth rate, NOT an exact decimal. Each printed endpoint
is expanded by 0.00000005. All reconstruction arithmetic uses Fraction;
explicit centre/radius strings denote exact endpoints in NumberDB. The sole
exact value, alpha(2, 7/3) = 1, follows from polynomial growth. For binary
cube-free and ternary square-free languages, replace only the upper endpoint
with the explicitly stated introductory prose upper bound plus half a unit
at its last printed place. This conservative rounding margin is our choice;
it is not a new bound algorithm. The original expanded lower endpoints stay.
This is a transcription, not a rerun of Shur's regular-language algorithm.
Rigour is conservatively assumed-bound: the enclosure relies on the paper's
stated bounds and nearest-decimal rounding. No 12- or 100-digit accuracy is
claimed. The optional interface returns strings, not certified Sage balls.
The prose estimates are NOT bounds and are never substituted.
"""
import argparse
import json
from fractions import Fraction
from pathlib import Path
SOURCE_URL = 'https://arxiv.org/html/1009.4415v2'
SOURCE_DECIMAL_PLACES = 7
ROUNDING_HALF_WIDTH = Fraction(1, 20000000)
RIGOUR = 'assumed-bound'
PROSE_UPPER_BOUNDS = {
('2', '3'): ('binary cube-free', '1.4575772869240'),
('3', '2'): ('ternary square-free', '1.301761876'),
}
EXACT_COMMENT = r'This language has polynomial growth, so $\gamma=1$ CITE{ShurTables}.'
BINARY = '''\
7/3 1.0000000 1.2206318:1.2206448
17/7 1.2222235:1.2222380 1.2287081:1.2287205
5/2 1.2294871:1.2295017 1.3662971:1.3663011
18/7 1.3669547:1.3669601 1.3692782:1.3692832
13/5 1.3693912:1.3693962 1.3760821:1.3760876
8/3 1.3762649:1.3762704 1.4508577:1.4508611
14/5 1.4522648:1.4522680 1.4552314:1.4552358
17/6 1.4552552:1.4552596 1.4567773:1.4567815
3 1.4575732:1.4575773 1.7951246:1.7951264
13/4 1.7957598:1.7957616 1.7972871:1.7972888
10/3 1.7973088:1.7973105 1.8029861:1.8029877
7/2 1.8032409 1.8172665
11/3 1.8174176 1.8204960
4 1.8211000 1.9208015
9/2 1.9214442 1.9241348
5 1.9244437 1.9646285
6 1.9653118 1.9832942
7 1.9834409 1.9918972
8 1.9919310 1.9960151
9 1.9960232 1.9980255
'''
LARGER_ALPHABETS = '''\
3 1.3017597:1.3017619 2.6058789:2.6058791 2.7015614:2.7015616 2.9119240:2.9119242 2.9172846 2.9737546
4 2.6215080 3.7284944 3.7789513 3.9487867 3.9507588 3.9879972
5 3.7325386 4.7898507 4.8220672 4.9662411 4.9671478 4.9935251
6 4.7914069 5.8277328 5.8503616 5.9760100 5.9764861 5.9961170
7 5.8284661 6.8537250 6.8705878 6.9820558 6.9823298 6.9974912
8 6.8541173 7.8727609 7.8858522 7.9860649 7.9862337 7.9982866
9 7.8729902 8.8873424 8.8978188 8.9888625 8.9889721 8.9987785
10 8.8874856 9.8988872 9.9074705 9.9908932 9.9909674 9.9990989
11 9.8989813 10.9082635 10.9154294 10.9924142 10.9924662 10.9993163
12 10.9083279 11.9160348 11.9221106 11.9935831 11.9936207 11.9994691
13 11.9160804 12.9225835 12.9278022 12.9945010 12.9945288 12.9995796
14 12.9226167 13.9281788 13.9327109 13.9952350 13.9952560 13.9996615
15 13.9282035 14.9330157 14.9369892 14.9958311 14.9958473 14.9997234
'''
EXPONENTS = ('2', '2+', '3', '3+', '4', '4+')
def source_cells():
cells = {}
for line in BINARY.splitlines():
exponent, ordinary, plus = line.split()
cells['2', exponent] = ordinary
cells['2', exponent + '+'] = plus
for line in LARGER_ALPHABETS.splitlines():
alphabet, *values = line.split()
if len(values) != len(EXPONENTS):
raise ValueError('Incorrect Table 2 column count')
for exponent, value in zip(EXPONENTS, values):
cells[alphabet, exponent] = value
if len(cells) != 118:
raise ValueError('Expected 118 distinct entries')
return cells
def decimal_text(value):
value = Fraction(value)
denominator = value.denominator
twos = fives = 0
while denominator % 2 == 0:
denominator //= 2
twos += 1
while denominator % 5 == 0:
denominator //= 5
fives += 1
if denominator != 1:
raise ValueError('A terminating decimal is required')
places = max(twos, fives)
scaled = abs(value.numerator) * 2 ** (places - twos) * 5 ** (places - fives)
digits = str(scaled).zfill(places + 1)
if places:
digits = (digits[:-places] + '.' + digits[-places:]).rstrip('0').rstrip('.')
return ('-' if value < 0 else '') + digits
def table_bounds(identity):
cell = source_cells()[identity]
if identity == ('2', '7/3'):
return Fraction(1), Fraction(1)
endpoints = cell.split(':')
return (Fraction(endpoints[0]) - ROUNDING_HALF_WIDTH,
Fraction(endpoints[-1]) + ROUNDING_HALF_WIDTH)
def prose_upper_metadata(identity):
language, printed = PROSE_UPPER_BOUNDS[identity]
places = len(printed.split('.')[1])
margin = Fraction(1, 2 * 10 ** places)
return {
'language': language, 'printed_upper': printed,
'source': SOURCE_URL,
'source_location': 'Introductory prose before Table 1',
'source_decimal_places': places,
'half_last_unit_margin': decimal_text(margin),
'expanded_upper': decimal_text(Fraction(printed) + margin),
'interpretation': 'Explicit upper bound, not the nearby estimated value',
}
def bounds(identity):
lower, upper = table_bounds(identity)
if identity in PROSE_UPPER_BOUNDS:
refined_upper = Fraction(prose_upper_metadata(identity)['expanded_upper'])
if not lower < refined_upper < upper:
raise ValueError('Prose upper bound is not a strict refinement')
upper = refined_upper
return lower, upper
def relative_digits(lower, upper):
"""NumberDB's radius-based digit measure, not common-prefix digits."""
if lower == upper:
return None
ratio = abs(lower + upper) / (upper - lower)
count = 0
while ratio >= 1:
count += 1
ratio /= 10
return count
def number(identity):
lower, upper = bounds(identity)
if lower == upper:
return str(lower)
return (decimal_text((lower + upper) / 2) + ' +/- '
+ decimal_text((upper - lower) / 2))
def entries():
result = {}
for identity in source_cells():
alphabet, exponent = identity
value = number(identity)
if identity == ('2', '7/3'):
value = {'number': value, 'comment': EXACT_COMMENT}
result.setdefault(alphabet, {})[exponent] = value
return result
def metadata():
records = []
for identity, cell in source_cells().items():
lower, upper = bounds(identity)
record = {
'params': dict(zip(('alphabet', 'exponent'), identity)),
'source_table': 1 if identity[0] == '2' else 2,
'printed_cell': cell,
'source_decimal_places': SOURCE_DECIMAL_PLACES,
'lower': decimal_text(lower), 'upper': decimal_text(upper),
'digits': relative_digits(lower, upper),
'rigour': 'exact' if lower == upper else RIGOUR,
}
if identity in PROSE_UPPER_BOUNDS:
record['upper_source'] = prose_upper_metadata(identity)
record['original_table_upper'] = decimal_text(table_bounds(identity)[1])
record['lower_endpoint_retained'] = True
records.append(record)
return {'source': SOURCE_URL, 'rounding_half_width': decimal_text(ROUNDING_HALF_WIDTH),
'digit_measure': 'floor(log10(abs(midpoint)/radius)) + 1; null means exact',
'records': records}
def verify_document(document, relation='exact'):
"""Check equality, or that each stored interval contains the new bounds."""
if relation not in ('exact', 'contains'):
raise ValueError('Unknown interval relation')
actual = document['Numbers']
expected = entries()
equalities = 1
strict_containments = 0
if list(actual) != list(expected):
raise ValueError('Alphabet identities/order changed')
for alphabet, rows in expected.items():
if list(actual[alphabet]) != list(rows):
raise ValueError('Exponent identities/order changed')
for exponent in rows:
leaf = actual[alphabet][exponent]
written = leaf['number'] if isinstance(leaf, dict) else leaf
if (alphabet, exponent) == ('2', '7/3'):
if written != '1':
raise ValueError('Exact row must remain verbatim exact')
continue
centre, radius = map(Fraction, written.split(' +/- '))
stored = (centre - radius, centre + radius)
lower, upper = bounds((alphabet, exponent))
equal = stored == (lower, upper)
contains = stored[0] <= lower <= upper <= stored[1]
if radius <= 0 or not (equal if relation == 'exact' else contains):
raise ValueError('Endpoint mismatch: ' + alphabet + ',' + exponent)
equalities += int(equal)
strict_containments += int(not equal)
return {'entries': 118, 'bounded': 117, 'exact': 1, 'relation': relation,
'endpoint_equalities': equalities, 'strict_containments': strict_containments,
'all_endpoints_equal': equalities == 118}
def numberdb_generator():
import numberdb
class PowerFreeLanguageGrowthRates(numberdb.Generator):
table = 'T447'
parameters = ('alphabet', 'exponent')
type = 'R'
digits = 6
rigour = RIGOUR
def enumerate(self):
for identity in source_cells():
yield dict(zip(self.parameters, identity))
def digits_for(self, params):
identity = tuple(str(params[key]) for key in self.parameters)
return relative_digits(*bounds(identity)) or self.digits
def value(self, params, digits):
identity = tuple(str(params[key]) for key in self.parameters)
available = relative_digits(*bounds(identity))
if available is not None and digits > available:
raise ValueError('Requested precision exceeds the published source enclosure')
if available is None:
return {'number': 1, 'comment': EXACT_COMMENT}
return {'number': number(identity), 'digits': available}
return PowerFreeLanguageGrowthRates()
def main():
parser = argparse.ArgumentParser(description=__doc__)
modes = parser.add_mutually_exclusive_group()
modes.add_argument('--entries', action='store_true')
modes.add_argument('--metadata', action='store_true')
modes.add_argument('--verify', type=Path)
parser.add_argument('--relation', choices=('exact', 'contains'), default='exact')
args = parser.parse_args()
if args.relation != 'exact' and not args.verify:
parser.error('--relation contains requires --verify')
if args.entries:
output = entries()
elif args.metadata:
output = metadata()
elif args.verify:
output = verify_document(json.loads(args.verify.read_text()), relation=args.relation)
else:
output = verify_document({'Numbers': entries()})
output.update(rigour=RIGOUR, source=SOURCE_URL, requested_digits_100='unsupported')
print(json.dumps(output, indent=2))
if __name__ == '__main__':
main()