back to table · edit · history · where entries came from · files · download
21789 bytes, as of the version from 2026-11-01 21:19. Recorded here, not run.
"""Run with SageMath:
$ sage -pip install numberdb
$ sage -python generate.py # verify all live entries, no key needed
$ sage -python generate.py --publish # uses NUMBERDB_API_KEY
An optional offline mode verifies an exported table document instead:
$ sage -python generate.py --snapshot snapshot.json
This repaired T339 generator reproduces the 717 retained published rows,
including their ordering. The frozen
Bernoulli, geometric and logarithmic probability lists preserve published
identities; they do not endorse the legacy hundredths mesh or introduce a new
grid. No application for that mesh has been established.
All logarithms are natural before conversion to bits by division by log(2).
Working precision is numberdb.bits(digits, losing=128). Positive series tails
are bounded by 10^(-digits-12) nats and added to the computed ball before unit
conversion. Every returned ball must be finite, positive and have radius at
most 10^(-digits-6) times its lower bound. This measures achieved accuracy
rather than assuming that extra working bits guarantee it.
An all-entry audit at 100 requested digits measured at least 110 relative
decimal digits, with the weakest enclosure at logarithmic p=3/100 in nats.
For negative binomial probabilities, the decreasing successive ratio is
bounded by alpha=(1+q)/2 after the tested cutoff, with q=1-p.
Since the binomial coefficient is at least one,
-log(P_k) <= -r*log(p)-k*log(q). Summing the geometric majorant and its first
moment gives _negative_binomial_tail_bound.
For Poisson probabilities, the tested cutoff makes all later ratios at most
alpha=1/2. The inequality log(k!) <= k^2 gives
-log(P_k) <= lambda+k*abs(log(lambda))+k^2. The first two geometric moments
give _poisson_tail_bound.
For logarithmic probabilities P_k=c*p^k/k, c=-1/log(1-p), use
-log(P_k) <= abs(log(c))-k*log(p)+k. For k>=m, 1/k<=1/m;
summing p^k gives _logarithmic_tail_bound. No unproved fixed constant is used.
Fresh snapshot verification is not evidence of how the published values were
originally produced. Publishing uses the standard numberdb.Generator method
and its environment-based credentials and provenance, including
NUMBERDB_API_KEY and NUMBERDB_ASSISTED_BY. It does not authorize numerical
corrections, precision reductions or removals.
"""
import argparse
import json
import math
import sys
import numberdb.sage as numberdb
from sage.arith.misc import binomial
from sage.rings.rational_field import QQ
from sage.rings.real_arb import RealBallField
WORKING_GUARD = 128
TAIL_GUARD_DIGITS = 12
LEGACY_BERNOULLI_PROBABILITIES = tuple(QQ(value) for value in (
"1/2",
"1/3",
"1/4",
"1/5",
"1/10",
"11/100",
"2/5",
"1/6",
"1/7",
"2/7",
"3/7",
"1/8",
"3/8",
"1/9",
"2/9",
"4/9",
"3/10",
"1/11",
"2/11",
"3/11",
"4/11",
"5/11",
"1/12",
"5/12",
"1/20",
"1/25",
"2/25",
"1/50",
"3/50",
"1/100",
"3/100",
"7/100",
"9/100",
"3/20",
"7/20",
"9/20",
"3/25",
"4/25",
"6/25",
"7/25",
"8/25",
"9/25",
"11/25",
"12/25",
"7/50",
"9/50",
"11/50",
"13/50",
"17/50",
"19/50",
"21/50",
"23/50",
"13/100",
"17/100",
"19/100",
"21/100",
"23/100",
"27/100",
"29/100",
"31/100",
"33/100",
"37/100",
"39/100",
"41/100",
"43/100",
"47/100",
"49/100",
))
LEGACY_SHARED_PROBABILITIES = tuple(QQ(value) for value in (
"1/2",
"1/3",
"1/4",
"1/5",
"1/10",
"11/100",
"2/5",
"3/10",
"1/20",
"3/20",
"7/20",
"9/20",
"1/25",
"2/25",
"3/25",
"4/25",
"6/25",
"7/25",
"8/25",
"9/25",
"11/25",
"12/25",
"1/50",
"3/50",
"7/50",
"9/50",
"11/50",
"13/50",
"17/50",
"19/50",
"21/50",
"23/50",
"1/100",
"3/100",
"7/100",
"9/100",
"13/100",
"17/100",
"19/100",
"21/100",
"23/100",
"27/100",
"29/100",
"31/100",
"33/100",
"37/100",
"39/100",
"41/100",
"43/100",
"47/100",
"49/100",
))
SMALL_PROBABILITIES = (
QQ(1) / 2,
QQ(1) / 3,
QQ(1) / 4,
QQ(1) / 10,
)
HYPERGEOMETRIC_SHAPES = (
(10, 2, 2),
(10, 2, 5),
(10, 2, 8),
(10, 5, 2),
(10, 5, 5),
(10, 5, 8),
(20, 2, 2),
(20, 2, 5),
(20, 2, 10),
(20, 5, 2),
(20, 5, 5),
(20, 5, 10),
(20, 10, 2),
(20, 10, 5),
(20, 10, 10),
)
def _field(digits):
return RealBallField(numberdb.bits(digits, losing=WORKING_GUARD))
def _q(text):
return QQ(str(text))
def _target(field, digits):
return field(QQ(1) / QQ(10) ** (digits + TAIL_GUARD_DIGITS))
def _ordered_probabilities():
return LEGACY_BERNOULLI_PROBABILITIES
def _half_integer_grid():
return tuple(QQ(k) / QQ(2) for k in range(1, 21)) + tuple(QQ(k) for k in range(11, 21))
def _entropy_term(probability):
if probability == 0:
return probability
if (not probability.is_finite() or probability.lower() <= 0
or probability.upper() > 1):
raise ArithmeticError("probability is not enclosed in (0, 1]")
return -probability * probability.log()
def _finite_entropy(probabilities, digits):
field = _field(digits)
total = field(0)
for probability in probabilities:
total += _entropy_term(field(probability))
return total
def _finite_entropy_from_balls(probabilities, digits):
return _finite_entropy(probabilities, digits)
def _bernoulli_entropy(shape, digits):
p = _q(shape)
return _finite_entropy((p, 1 - p), digits)
def _binomial_entropy(shape, digits):
n_text, p_text = shape.split(",")
n = int(n_text)
p = _q(p_text)
q = 1 - p
probabilities = [
QQ(binomial(n, k)) * p ** k * q ** (n - k)
for k in range(n + 1)
]
return _finite_entropy(probabilities, digits)
def _geometric_entropy(shape, digits):
field = _field(digits)
p = field(_q(shape))
q = 1 - p
return -p.log() - q * q.log() / p
def _negative_binomial_tail_bound(field, p_start, k_start, r, p, alpha):
q = 1 - p
one = field(1)
a = field(alpha)
denominator = one - a
k = field(k_start)
a_log = field(r) * (-field(p).log())
b_log = -field(q).log()
return p_start * (
(a_log + k * b_log) / denominator
+ b_log * a / (denominator ** 2)
)
def _negative_binomial_entropy(shape, digits):
r_text, p_text = shape.split(",")
r = int(r_text)
p = _q(p_text)
q = 1 - p
field = _field(digits)
target = _target(field, digits)
alpha = (1 + q) / 2
total = field(0)
probability = field(p) ** r
k = 0
while True:
total += _entropy_term(probability)
next_probability = probability * field(q) * field(k + r) / field(k + 1)
k_start = k + 1
ratio_bound = q * QQ(k_start + r) / QQ(k_start + 1)
if ratio_bound <= alpha:
tail = _negative_binomial_tail_bound(
field, next_probability, k_start, r, p, alpha)
if tail.upper() < target.lower():
return total.add_error(tail.upper())
probability = next_probability
k += 1
def _poisson_tail_bound(field, p_start, k_start, lam, alpha):
one = field(1)
a = field(alpha)
denominator = one - a
k = field(k_start)
lam_ball = field(lam)
abs_log_lam = lam_ball.log().abs()
sum_one = one / denominator
sum_j = a / (denominator ** 2)
sum_j2 = a * (one + a) / (denominator ** 3)
sum_k = k * sum_one + sum_j
sum_k2 = (k ** 2) * sum_one + 2 * k * sum_j + sum_j2
return p_start * (lam_ball * sum_one + abs_log_lam * sum_k + sum_k2)
def _poisson_entropy(shape, digits):
lam = _q(shape)
field = _field(digits)
target = _target(field, digits)
alpha = QQ(1) / QQ(2)
total = field(0)
probability = (-field(lam)).exp()
k = 0
while True:
total += _entropy_term(probability)
next_probability = probability * field(lam) / field(k + 1)
k_start = k + 1
if QQ(lam) / QQ(k_start + 1) <= alpha:
tail = _poisson_tail_bound(
field, next_probability, k_start, lam, alpha)
if tail.upper() < target.lower():
return total.add_error(tail.upper())
probability = next_probability
k += 1
def _uniform_entropy(shape, digits):
field = _field(digits)
return field(int(shape)).log()
def _hypergeometric_entropy(shape, digits):
population_text, successes_text, draws_text = shape.split(",")
population = int(population_text)
successes = int(successes_text)
draws = int(draws_text)
denominator = QQ(binomial(population, draws))
low = max(0, draws - (population - successes))
high = min(draws, successes)
probabilities = []
for k in range(low, high + 1):
probabilities.append(
QQ(binomial(successes, k))
* QQ(binomial(population - successes, draws - k))
/ denominator)
return _finite_entropy(probabilities, digits)
def _logarithmic_tail_bound(field, p_power, n_plus_one, c, p):
p_ball = field(p)
one_minus_p = field(1 - p)
a = c.log().abs()
b = -p_ball.log()
geometric_tail = p_power / one_minus_p
return c * (a * geometric_tail / field(n_plus_one)
+ (b + 1) * geometric_tail)
def _logarithmic_entropy(shape, digits):
p = _q(shape)
field = _field(digits)
target = _target(field, digits)
p_ball = field(p)
c = -1 / (1 - p_ball).log()
total = field(0)
p_power = p_ball
k = 1
while True:
probability = c * p_power / field(k)
total += _entropy_term(probability)
next_power = p_power * p_ball
tail = _logarithmic_tail_bound(field, next_power, k + 1, c, p)
if tail.upper() < target.lower():
return total.add_error(tail.upper())
p_power = next_power
k += 1
def _zipf_entropy(shape, digits):
s_text, n_text = shape.split(",")
exponent = int(s_text)
size = int(n_text)
normalisation = sum(QQ(1) / QQ(k) ** exponent for k in range(1, size + 1))
probabilities = [
(QQ(1) / QQ(k) ** exponent) / normalisation
for k in range(1, size + 1)
]
return _finite_entropy(probabilities, digits)
def _benford_entropy(digits):
field = _field(digits)
log10 = field(10).log()
probabilities = [
(1 + field(QQ(1) / QQ(d))).log() / log10
for d in range(1, 10)
]
return _finite_entropy_from_balls(probabilities, digits)
def _entropy_nats(distribution, shape, digits):
if distribution == "bernoulli":
return _bernoulli_entropy(shape, digits)
if distribution == "binomial":
return _binomial_entropy(shape, digits)
if distribution == "geometric":
return _geometric_entropy(shape, digits)
if distribution == "negative-binomial":
return _negative_binomial_entropy(shape, digits)
if distribution == "poisson":
return _poisson_entropy(shape, digits)
if distribution == "discrete-uniform":
return _uniform_entropy(shape, digits)
if distribution == "hypergeometric":
return _hypergeometric_entropy(shape, digits)
if distribution == "logarithmic":
return _logarithmic_entropy(shape, digits)
if distribution == "zipf":
return _zipf_entropy(shape, digits)
if distribution == "benford":
return _benford_entropy(digits)
raise ValueError("unknown distribution %r" % (distribution,))
def _to_unit(value, unit, digits):
if unit == "nats":
return value
if unit != "bits":
raise ValueError("unknown unit %r" % (unit,))
field = _field(digits)
return field(value) / field(2).log()
def _check_enclosure(value, digits):
if not value.is_finite():
raise ArithmeticError("entropy enclosure is not finite")
lower = value.lower().exact_rational()
upper = value.upper().exact_rational()
if lower <= 0:
raise ArithmeticError("entropy enclosure is not strictly positive")
if (upper - lower) / 2 > lower / QQ(10) ** (digits + 6):
raise ArithmeticError("entropy enclosure does not justify requested digits")
def _power_of_two(n):
return n > 0 and (n & (n - 1)) == 0
def _skip_entry(distribution, shape, unit):
if unit != "bits":
return False
if distribution == "bernoulli" and shape == "1/2":
return True
if distribution == "geometric" and shape == "1/2":
return True
if distribution == "discrete-uniform" and _power_of_two(int(shape)):
return True
if distribution == "binomial" and shape == "2,1/2":
return True
return False
def _comment(distribution, shape, unit):
if unit != "nats":
return ""
if distribution == "bernoulli" and shape == "1/2":
return "The omitted bits row is exactly $1$."
if distribution == "geometric" and shape == "1/2":
return "The omitted bits row is exactly $2$."
if distribution == "discrete-uniform":
n = int(shape)
if _power_of_two(n):
return "The omitted bits row is exactly $%d$." % (n.bit_length() - 1)
if distribution == "binomial" and shape == "2,1/2":
return "The omitted bits row is exactly $3/2$."
return ""
def _format_probability(value):
return str(value)
def _scipy_expected(params):
import scipy.stats as stats
distribution = params["distribution"]
shape = params["shape"]
unit = params["unit"]
if distribution == "bernoulli":
expected = stats.bernoulli(float(_q(shape))).entropy()
elif distribution == "binomial":
n_text, p_text = shape.split(",")
expected = stats.binom(int(n_text), float(_q(p_text))).entropy()
elif distribution == "geometric":
expected = stats.geom(float(_q(shape))).entropy()
elif distribution == "negative-binomial":
r_text, p_text = shape.split(",")
expected = stats.nbinom(int(r_text), float(_q(p_text))).entropy()
elif distribution == "poisson":
expected = stats.poisson(float(_q(shape))).entropy()
elif distribution == "discrete-uniform":
expected = math.log(int(shape))
elif distribution == "hypergeometric":
population_text, successes_text, draws_text = shape.split(",")
expected = stats.hypergeom(
int(population_text), int(successes_text), int(draws_text)).entropy()
elif distribution == "logarithmic":
expected = stats.logser(float(_q(shape))).entropy()
elif distribution == "zipf":
s_text, n_text = shape.split(",")
if hasattr(stats, "zipfian"):
expected = stats.zipfian(int(s_text), int(n_text)).entropy()
else:
weights = [k ** (-int(s_text)) for k in range(1, int(n_text) + 1)]
total = sum(weights)
expected = -sum((w / total) * math.log(w / total) for w in weights)
elif distribution == "benford":
probabilities = [math.log10(1 + 1 / d) for d in range(1, 10)]
expected = -sum(p * math.log(p) for p in probabilities)
else:
raise ValueError("unknown distribution %r" % (distribution,))
if unit == "bits":
expected /= math.log(2)
return expected
def _midpoint(value):
if isinstance(value, dict):
value = value["number"]
return float((value.lower() + value.upper()) / 2)
class ShannonEntropies(numberdb.Generator):
table = "T339"
parameters = ("distribution", "shape", "unit")
type = "R"
digits = 100
rigour = "proven"
def enumerate(self):
for p in _ordered_probabilities():
shape = _format_probability(p)
for unit in ("nats", "bits"):
if not _skip_entry("bernoulli", shape, unit):
yield {"distribution": "bernoulli", "shape": shape, "unit": unit}
for n in range(2, 21):
for p in SMALL_PROBABILITIES:
shape = "%d,%s" % (n, p)
for unit in ("nats", "bits"):
if not _skip_entry("binomial", shape, unit):
yield {"distribution": "binomial", "shape": shape, "unit": unit}
for p in LEGACY_SHARED_PROBABILITIES:
shape = _format_probability(p)
for unit in ("nats", "bits"):
if not _skip_entry("geometric", shape, unit):
yield {"distribution": "geometric", "shape": shape, "unit": unit}
for r in range(2, 11):
for p in SMALL_PROBABILITIES:
shape = "%d,%s" % (r, p)
for unit in ("nats", "bits"):
yield {"distribution": "negative-binomial", "shape": shape, "unit": unit}
for lam in _half_integer_grid():
shape = _format_probability(lam)
for unit in ("nats", "bits"):
yield {"distribution": "poisson", "shape": shape, "unit": unit}
for n in range(2, 31):
shape = str(n)
for unit in ("nats", "bits"):
if not _skip_entry("discrete-uniform", shape, unit):
yield {"distribution": "discrete-uniform", "shape": shape, "unit": unit}
for population, successes, draws in HYPERGEOMETRIC_SHAPES:
shape = "%d,%d,%d" % (population, successes, draws)
for unit in ("nats", "bits"):
yield {"distribution": "hypergeometric", "shape": shape, "unit": unit}
for p in LEGACY_SHARED_PROBABILITIES:
shape = _format_probability(p)
for unit in ("nats", "bits"):
yield {"distribution": "logarithmic", "shape": shape, "unit": unit}
for exponent in (1, 2, 3):
for size in (10, 100):
shape = "%d,%d" % (exponent, size)
for unit in ("nats", "bits"):
yield {"distribution": "zipf", "shape": shape, "unit": unit}
for unit in ("nats", "bits"):
yield {"distribution": "benford", "shape": "-", "unit": unit}
def value(self, params, digits):
distribution = str(params["distribution"])
shape = str(params["shape"])
unit = str(params["unit"])
value = _to_unit(_entropy_nats(distribution, shape, digits), unit, digits)
_check_enclosure(value, digits)
comment = _comment(distribution, shape, unit)
if comment:
return {"number": value, "comment": comment}
return value
def run_integrity_checks(digits=100):
import scipy
generator = ShannonEntropies()
largest = {
unit: {"absolute_difference": 0.0, "params": None}
for unit in ("nats", "bits")
}
checked = 0
for params in generator.enumerate():
value = generator.value(params, digits)
got = _midpoint(value)
expected = _scipy_expected(params)
if not math.isfinite(got) or not math.isfinite(expected):
raise ArithmeticError("nonfinite SciPy comparison: %s" % params)
difference = abs(got - expected)
unit = params["unit"]
if difference > largest[unit]["absolute_difference"]:
largest[unit] = {
"absolute_difference": difference,
"params": dict(params),
"computed": got,
"scipy": expected,
}
if difference > 5e-9:
raise ArithmeticError(
"SciPy check failed for %s: %.17g here, %.17g independently"
% (params, got, expected))
checked += 1
return {
"checked": checked,
"scipy": scipy.__version__,
"absolute_tolerance_in_each_rows_unit": 5e-9,
"largest_by_unit": largest,
"role": "double-precision convention check, not a 100-digit proof",
}
class SnapshotClient:
def __init__(self, document):
self.document = document
def request(self, path, parameters):
if path != "api/table" or parameters != {"id": "T339"}:
raise RuntimeError("only the offline T339 snapshot can be read")
return self.document
def verify_snapshot(document):
generator = ShannonEntropies()
expected = [
(distribution, shape, unit)
for distribution, shapes in document["Numbers"].items()
for shape, units in shapes.items()
for unit in units
]
enumerated = [
tuple(str(params[name]) for name in generator.parameters)
for params in generator.enumerate()
]
if enumerated != expected or len(set(enumerated)) != len(enumerated):
raise ArithmeticError("default enumeration differs from the snapshot")
return generator.verify(sample=None, client=SnapshotClient(document))
def main(argv=None):
parser = argparse.ArgumentParser(description=__doc__)
modes = parser.add_mutually_exclusive_group()
modes.add_argument("--snapshot", help="verify an offline table export")
modes.add_argument("--publish", action="store_true")
options = parser.parse_args(argv)
generator = ShannonEntropies()
print(json.dumps(run_integrity_checks(), indent=2))
if options.publish:
print(generator.publish(
message="restore reproducible coverage of retained Shannon entropies"))
return 0
if options.snapshot:
with open(options.snapshot, encoding="utf-8") as snapshot_file:
snapshot = json.load(snapshot_file)
report = verify_snapshot(snapshot)
else:
report = generator.verify(sample=None)
print(report)
return 0 if report.ok and not report.coarser else 1
if __name__ == "__main__":
sys.exit(main())