"""Exact finite cross-checks for the growing-period manuscript. Python 3, standard library.""" import json from collections import Counter from fractions import Fraction as F from math import factorial, gcd, lcm, prod def primes_of(number): prime = 2 while prime * prime <= number: if number % prime == 0: yield prime while number % prime == 0: number //= prime prime += 1 if number > 1: yield number def phi(n): value = n for p in primes_of(n): value = (value // p) * (p - 1) return value def grid_tests(): cutoffs = (1, 2, 3, 4, 6, 7, 9, 11, 13, 18, 23, 31, 40, 48, 60, 64) periods = (*range(1, 33), 35, 60, 105, 210) # phi(q)^2 >= q/2, obtained prime power by prime power. maximum = 2 * max(cutoffs) ** 2 small_q = [(q, phi(q)) for q in range(1, maximum + 1) if phi(q) <= max(cutoffs)] totals = Counter() for D in periods: for B in cutoffs: grids = [q for q, cost in small_q if q % D == 0 and cost <= B] totals['period_cutoff_pairs'] += 1 first = {} on_units = set() for q in grids: # natural denominator order, ties in totient cause no ambiguity. for j in range(1, q + 1): x = F(j, q) first.setdefault(x, q) if j < q and gcd(j, D) == 1: on_units.add(x) assert all(lcm(D, x.denominator) == q for x, q in first.items()) sizes = Counter(first.values()) for q in grids: r = q // D weight = prod((F(p - 1, p) for p in primes_of(gcd(r, D))), start=F(1)) assert sizes[q] == D * phi(r) == D * F(phi(q), phi(D)) * weight totals['physical_grid_fibers'] += 1 expected = {F(a, q) for q in grids for a in range(1, q) if gcd(a, q) == 1} assert on_units == expected assert len(on_units) == sum(phi(q) for q in grids) - int(1 in grids) if D != 5: continue for pair in ((1, 4), (2, 3)): actual = {F(j, q) for q in grids for j in range(1, q) if j % 5 in pair} predicted = {x for x in expected if x.denominator % 2 or x.numerator % 5 in pair or 2 * phi(x.denominator) <= B} assert actual == predicted even = [phi(q) for q in grids if q % 2 == 0] assert 2 * len(actual) == 2 * len(expected) - sum(c for c in even if 2 * c > B) totals['sparse_pair_set_equalities'] += 1 return totals # In these functions indices are Taylor orders; orders >= len(poly) are discarded. def linear(poly, constant, slope=1): return [constant * v + (slope * poly[i-1] if i else 0) for i, v in enumerate(poly)] def multiply(lhs, rhs): return [sum(lhs[i] * rhs[n-i] for i in range(n+1)) for n in range(len(lhs))] def quotient(numerator, divisor): result = [] for n, value in enumerate(numerator): value -= sum(divisor[i] * result[n-i] for i in range(1, n+1)) result.append(F(value, divisor[0])) return result def normalizer(n, i): blocks, final = divmod(i, n) return factorial(n) ** blocks * factorial(final) def coefficients(n, s, theta, i, j): multiplier = factorial(n) ** (s - len(theta)) for x in theta: b = x.denominator assert all(n % (p-1) == 0 for p in primes_of(b)) multiplier *= b**n * prod(p ** (n // (p-1)) for p in primes_of(b)) scale = F(multiplier, normalizer(n, i) * normalizer(n, j)) terms = {} for k in range(n+1): base = [scale] + [0] * (s-1) for x in theta: for v in range(n): base = linear(base, x+v-k) branches = [] for sign in (1, -1): branch = [1] + [0] * (s-1) for degree in (i, j): for v in range(degree): branch = linear(branch, sign * (n//2 - k) + v, sign) branches.append(branch) num = multiply(base, [u+v for u,v in zip(*branches)]) den = [1] + [0] * (s-1) for other in range(n+1): if other != k: for _ in range(s): den = linear(den, other-k) for order, c in enumerate(quotient(num, den)): terms[k, s-order] = c return terms def arithmetic_tests(): profiles = [(2, (F(1,3), F(2,3))), (2, (F(1,2),)), (4, (F(1,5), F(4,5))), (4, (F(2,5), F(3,5))), (6, (F(1,4), F(3,4), F(1,7), F(6,7)))] counts = Counter() example = None for n, theta in profiles: d = lcm(*range(1, n+1)) for s in (5, 6): for i,j in ((0,0), (1,1), (2,3), (n+1,2)): assert i+j <= (n+1)*s - n*len(theta)-2 terms = coefficients(n, s, theta, i, j) counts['rational_functions'] += 1 assert sum(terms[k,1] for k in range(n+1)) == 0 for (k, order), value in terms.items(): assert (d ** (s-order) * value).denominator == 1 assert terms[n-k,order] == (-1) ** (s+order) * value counts['local_coefficients'] += 1 for x in (*theta, F(1)): for k in range(1,n+1): for v in range(k): pieces = [d**s * terms[k,order]/(v+x)**order for order in range(1,s+1)] assert sum(pieces).denominator == 1 counts['grouped_corrections'] += 1 denoms = [a.denominator for a in pieces] if max(denoms) > 1: counts['groups_requiring_cancellation'] += 1 if example is None: example = dict(n=n, s=s, theta=[str(z) for z in theta], i=i, j=j, k=k, v=v, x=str(x), individual_denominators=denoms, scaled_group_sum=str(sum(pieces))) assert example return dict(counts), example def main(): arithmetic, example = arithmetic_tests() print(json.dumps({'grids':dict(grid_tests()), 'arithmetic':arithmetic, 'example_of_cancellation':example}, indent=2)) if __name__ == '__main__': main()