""" coordinates.py -- which coordinate system on the integers reads which operation, and what kind of wall each one pays. QUESTION. Three classical coordinate systems write an integer: its residues at a set of primes, its indices (discrete logarithms, channel by channel), and its positional digits. Each makes some operations cheap to read and walls others. Which pairs of operations can one coordinate system read at once, is any system able to read addition, multiplication and size together, and are the walls the systems pay of one kind or of several? Last, for every wall met here and in the size wall's own record, what is the least structure that bears it? THE ARGUMENT (written before this script). (1) THE TWO-READINGS CRITERION. Greedy numeration on a scale 1 = T_0 < T_1 < T_2 < ... writes n with digits d_i, taking the largest multiple of T_i that fits at each step from the top, so the part of n below position i is less than T_i. Then the low prefix sum_{i= j). If it is a chain, the prefix is below T_j and n minus the prefix is a sum of multiples of T_i, i >= j, each 0 mod T_j. Conversely n = T_i (i >= j) is the single digit 1 at i with prefix 0, which forces T_j | T_i. On EVERY scale, chain or not, greedy digit strings compared most significant first are compared as numbers: at the first differing position i, d_i < d'_i, the rest of the smaller number is below T_i. So size and order come with greedy, residues come with the chain, and a positional base is the scale on which the two readings coincide. (2) THE CARRY WALL. In base b, digit j of x + y is a function of no finite set of digit positions placed relative to j, and one carry bit read least significant first computes the whole sum. For a finite offset set F choose s > 0 outside -F with l = j - s above every position the reader also reads at the low end; x = sum_{i=l}^{j-1} (b - 1) b^i, y = b^l against y' = 0. The inputs differ only at position l, and x + y = b^j has digit j equal to 1 while x + y' < b^j has digit j equal to 0. (3) THE SUFFIX AND FLOOR READS. [m | n] is a function of the last j digits in base b iff m | b^j, so some suffix reads it iff rad(m) | rad(b): n and n + b^j share the suffix, and at n = 0 they disagree unless m | b^j. On any chain of moduli M_0 = 1 | M_1 | ..., floor(n/m) mod M_t is a function of n mod M_(t+c), for M_t >= 2, iff m M_t | M_(t+c). The difference floor((n + M')/m) - floor(n/m) is the constant M'/m when m | M', and otherwise takes both values floor(M'/m) and floor(M'/m) + 1, which are never both 0 mod M_t. On the primorial chain M_t = p_1 ... p_t this reads floor(n/m) at depth t iff m is squarefree with every prime factor above p_t, at the least lookahead c = pi(P(m)) - t, P(m) the largest prime factor, and at no depth from pi(p_min(m)) on. The divisibility read on the same chain holds for every squarefree m at every depth deep enough. (4) THE VALUATION ROW. Writing n by its exponent vector (v_p(n))_p makes multiplication a coordinatewise sum and walls addition: for a finite prime set W holding 2, the CRT gives y_u with y_u = 2^u - 1 mod 2^(u+1) and y_u = 1 mod the other primes of W, so y_u and 1 have the zero vector on W while v_2(1 + y_u) = u takes every value. (5) THE INDEX COORDINATES. For squarefree M the unit group is the product of the cyclic (Z/p)^*, so choosing a primitive root per channel gives a bijection U(Z/M) -> prod Z/(p - 1) under which multiplication is addition, powering is scaling, x is an e-th power iff gcd(e, p - 1) divides its index at every p, with prod gcd(e, p - 1) roots, and x is a square mod p iff its index is even. lambda = lcm(p - 1) is the exponent of that product and is below phi = prod (p - 1) once two odd primes are present, so Z/M has no primitive root and no single index exists. (6) THE ZECH WALL. At one channel, addition in index coordinates is the unary table Z(n) = ind(1 + g^n). Z is compatible with no quotient Z/(p - 1) -> Z/q, 2 <= q <= (p - 1)/2, at any p >= 5. Indices mod q sort (Z/p)^* into cosets of the subgroup C of index q, of order h = (p - 1)/q >= 2. Compatibility says (1 + wx)/(1 + x) lies in C for every w in C and every x in (Z/p)^* outside {-1, -1/w}, p - 3 values when w != 1. For fixed w != 1 and z in C, 1 + wx = z(1 + x) reads x(w - z) = z - 1: z = w has no solution, z = 1 gives x = 0, every other z gives one admissible x. So exactly h - 2 < p - 3 of the required x comply, and each other x gives a pair of indices equal mod q whose Zech values differ mod q. A polynomial over Z/(p - 1) respects every quotient, so Z is no polynomial. (7) THE SUPPORT LOG. x^(lambda(M) + 1) = x for every x in Z/M iff M is squarefree (lambda Carmichael's): each channel is a field with p - 1 | lambda, and when p^2 | M the element M/p is a nonzero square-zero element. Then every x is (supp x, its indices on supp x); multiplication intersects supports and adds indices, x^lambda is the idempotent of supp x, and for M > 2 the meadow inverse x^(lambda - 1) negates the indices (at M = 2, 0^0 = 1). (8) THE EXPONENT WALL. For p >= 3, x^y is not a function of (x mod p, y mod p): x^(y + p) = x^(y + 1), which for y >= 1 differs from x^y exactly when x is outside {0, 1}. It is a function of x mod p and of y mod (p - 1) for POSITIVE y only: 0^0 = 1 and 0^(p - 1) = 0. (9) THE RIGIDITY DICHOTOMY. A coordinate system in which + is read coordinate by coordinate is an internal direct sum of subgroups of Z/M. A cyclic group has one subgroup per order, and two of them meet in the subgroup of order the gcd, so the summands have pairwise coprime orders a_i with product M: the decompositions ARE the coprime factorizations. Each summand is an ideal, so x_i y_j = 0 for i != j and multiplication is read coordinate by coordinate too, for free. And every such system with two summands or more walls size: at a summand of order a < M, 0 and b = a ceil(M/(2a)) share that coordinate while the sign reads 0 and 1. Multiplication alone is floppy: the unit group has direct decompositions that cross the channels. (10) THE BEARERS. Each wall, and each law the walls rest on, is pinned to the least structure that bears it. The quantifier wall: no polynomial on any composite Z/M computes [a = 0], since a polynomial is compatible with every quotient Z/d and [0 = 0] = 1 against [d = 0] = 0; at a prime it is 1 - a^(p - 1). Order's maximal failure needs one proper window and no fields (coprimality only makes two windows a coordinate system): x = a < A and y = b + A realize every pair (a, b) at the window A. The order-divisibility relation ord(x) | ord(y) on C_n1 x C_n2 is conjunctive iff gcd(n1, n2) = 1, and fails maximally iff n1 = n2: its first projection is {ord x1 | lcm(ord y1, n2)}, full iff n1 | n2, and at a prime r dividing both, x = (a, 0) of order r against y = 0 lies in both projections but not in the relation. PREDICTIONS (fixed before the run). Every check prints PASS. B: the prefix property and the chain agree on all 9,139 scales (1, a, b, c), 2 <= a < b < c <= 40, and all 3,876 scales (1, a, b, c, d) <= 20; greedy order holds on all 9,139. A: the witness pair defeats the band of half-width r with the low block {0..r}, r = 0..5, in bases 2 and 10; the one-carry scan adds exactly in bases 2, 3 and 10 for x, y < 300. S: at bases 2, 6 and 10 the suffix read holds iff m | b^j. On the primorial chain with M' <= 2,310 and m = 2..30 the readable cells are exactly these: t = 1: m = 3, 5, 7, 11, 15, 21 at c = 1, 2, 3, 4, 2, 3; t = 2: m = 5, 7, 11 at c = 1, 2, 3; t = 3: m = 7, 11 at c = 1, 2; t = 4: m = 11 at c = 1. Twelve cells, all others torn to the cap. The base-2 control reads m = 2, 4, 8, 16 at t = 1, c = v_2(m). V: the family y_u, u = 3..12, at W = {2, 3, 5, 7}. I: lambda < phi at every rung k = 3..7; 92,160 distinct index tuples at Z/510510; there 1,440 squares with 64 roots each and 10,240 cubes with 9 roots each; multiplication, powering and square classes exact at Z/210. Z: 263 pairs (p, q), 5 <= p < 200, the complying set equal to the derived set at w = g^q, and at every w != 1 of C for p < 60. G: x^(lambda + 1) = x holds at exactly the squarefree M <= 300 and at every x of Z/510510; the product on supports and indices, the support idempotent and the meadow inverse exact at Z/210. E: p - 2 witnesses at p = 3..13; positive exponents mod p - 1 exact; the zero exponent fails at x = 0 only. On the squarefree M <= 300, x^y at y >= 1 is read off (x mod M, y mod M) exactly at M = 2, 6 and 42, where lambda | M; up to 2,000 lambda | M at 2, 6, 42, 1806. R: 4, 4, 1 and 14 additive decompositions of Z/30, Z/60, Z/12 and Z/210, each a coprime factorization, multiplication read coordinate by coordinate in each, size walled at every summand; U(30) has 4 direct decompositions of which 1 follows the channels; 2,048 units of 2-power order at Z/510510. P: the polynomial functions number 64, 108, 1,024 and 19,683 at Z/4, Z/6, Z/8 and Z/9 (Kempner's counts), with [a = 0] in none; order's projections saturate at Z/6 (21 of 36) and at Z/36 with windows 4 and 9 (666 of 1,296); the order-divisibility law on all 45 pairs 2 <= n1 <= n2 <= 10, C2 x C2 x C2 maximal, U(15) of shape C2 x C4. DESIGN. Sections of checks printing PASS or FAIL. Every read is literal: a map is read by a window when no two inputs sharing the window disagree, and the engine never consults the criterion it tests. B greedy digits on every scale of the two sweeps, at every n from 0 to twice the scale's top term, which holds the witness n = T_i. A the witness pair; the least-significant-first scan. S suffix reads by brute over a full period; floor reads on the primorial chain up to M' = 2,310 and the base-2 control up to 2^7, over n in [0, m M'). V the CRT family. I per-channel discrete-log tables at Z/510510. Z the complying set by brute over x, against (z - 1)/(w - z). G every M <= 300 and every x of Z/510510. E every x at p = 3..13 at y = 1 for the wall; every x and y = 1..p - 1 at p = 2..13 for the reads; every x and y = 1..M on the squarefree M <= 300, lambda | M listed to 2,000. R subgroups of Z/M as cyclic spans, of U(30) as closures of two generators; decompositions by the sum map. P polynomial functions as the additive span of the monomial functions; relations projected and conjoined. RUN RECORD. First run: 40 of 40 PASS, every prediction met. The scale sweeps hold 60 chains among 13,015 scales with 0 mismatches; the primorial chain's readable floor cells are the twelve predicted; 182 of M = 2..300 are squarefree and x^(lambda + 1) = x holds at exactly those; Kempner's counts 64, 108, 1,024 and 19,683 came out as stated. Reading the prints removed one check. It counted 2,048 units of 2-power order at Z/510510, offered as a second instance of multiplication's floppiness, but that factor is the product of each channel's own 2-part: it splits the channels finer and crosses none. The crossing witness is U(30)'s: of its four decompositions C2 x C4, three cross the channels, two taking the C4 {1, 17, 19, 23} and the third pairing the channel's C4 {1, 7, 13, 19} with the C2 {1, 29}. The script counts the four and the one aligned; the split of the three is read by hand. Second run, after the removal and a relabelling of letters: 39 of 39. Third run, multiplication read at every pair at Z/210: 39 of 39, 2.3 s. Fourth run, the E arm on squarefree M: 41 of 41; the exponent is read mod M at 2, 6 and 42 below 300, and lambda | M at 2, 6, 42, 1806. Run: python coordinates.py (seconds, pure Python) """ from itertools import combinations from math import gcd, lcm, prod CHECKS = [] def check(name, ok, detail=""): CHECKS.append(bool(ok)) tail = f" [{detail}]" if detail else "" print(f" {'PASS' if ok else 'FAIL'} {name}{tail}") def primes_upto(n): sieve = bytearray([1]) * (n + 1) sieve[0:2] = b"\x00\x00" for i in range(2, int(n ** 0.5) + 1): if sieve[i]: sieve[i * i::i] = bytearray(len(sieve[i * i::i])) return [i for i in range(n + 1) if sieve[i]] def factorize(n): out, d = {}, 2 while d * d <= n: while n % d == 0: out[d] = out.get(d, 0) + 1 n //= d d += 1 if n > 1: out[n] = out.get(n, 0) + 1 return out def squarefree(n): return all(e == 1 for e in factorize(n).values()) def carmichael(n): lam = 1 for p, e in factorize(n).items(): if p == 2 and e >= 3: part = 2 ** (e - 2) else: part = (p - 1) * p ** (e - 1) lam = lcm(lam, part) return lam def primitive_root(p): if p == 2: return 1 qs = factorize(p - 1) for g in range(2, p): if all(pow(g, (p - 1) // q, p) != 1 for q in qs): return g raise ValueError(p) def dlog_table(p): g = primitive_root(p) ind, x = {}, 1 for e in range(p - 1): ind[x] = e x = x * g % p return g, ind P7 = [2, 3, 5, 7, 11, 13, 17] M7 = prod(P7) # ---------------------------------------------------------------- B def greedy_digits(n, scale): d = [0] * len(scale) for i in range(len(scale) - 1, -1, -1): d[i], n = divmod(n, scale[i]) return d def prefix_is_residue(scale): for n in range(2 * scale[-1] + 1): d = greedy_digits(n, scale) acc = 0 for j in range(1, len(scale)): acc += d[j - 1] * scale[j - 1] if acc != n % scale[j]: return False return True def is_chain(scale): return all(scale[j + 1] % scale[j] == 0 for j in range(len(scale) - 1)) def greedy_orders(scale): ns = list(range(2 * scale[-1] + 1)) keys = [tuple(reversed(greedy_digits(n, scale))) for n in ns] return keys == sorted(keys) and len(set(keys)) == len(keys) def section_b(): print("B the two-readings criterion") s4 = [(1, a, b, c) for a, b, c in combinations(range(2, 41), 3)] s5 = [(1,) + t for t in combinations(range(2, 21), 4)] bad4 = sum(prefix_is_residue(s) != is_chain(s) for s in s4) bad5 = sum(prefix_is_residue(s) != is_chain(s) for s in s5) chains = sum(is_chain(s) for s in s4) + sum(is_chain(s) for s in s5) check("prefix = residue iff divisibility chain", bad4 == 0 and bad5 == 0, f"{len(s4)} + {len(s5)} scales, {chains} chains, " f"{bad4 + bad5} mismatches") bad = sum(not greedy_orders(s) for s in s4) check("greedy digits, most significant first, order as numbers", bad == 0, f"{len(s4)} scales, {bad} failures") fib = (1, 2, 3, 5, 8, 13) check("Zeckendorf is no chain and fails the prefix read", not is_chain(fib) and not prefix_is_residue(fib)) # ---------------------------------------------------------------- A def digit(n, j, b): return n // b ** j % b def lsd_add(x, y, b): out, carry, j = 0, 0, 0 while x or y or carry: s = x % b + y % b + carry out += (s % b) * b ** j carry = s // b x //= b y //= b j += 1 return out def section_a(): print("A the carry wall") ok = True for b in (2, 10): for r in range(6): m = r + 1 j = m + r + 1 read = set(range(r + 1)) | set(range(j - r, j + r + 1)) x = sum((b - 1) * b ** i for i in range(m, j)) y1, y0 = b ** m, 0 agree = all(digit(y1, i, b) == digit(y0, i, b) for i in read) differ = digit(x + y1, j, b) != digit(x + y0, j, b) ok &= agree and differ and m not in read check("one launched carry defeats band plus low block", ok, "half-width 0..5, bases 2 and 10") ok = all(lsd_add(x, y, b) == x + y for b in (2, 3, 10) for x in range(300) for y in range(300)) check("one carry bit, least significant first, adds exactly", ok) # ---------------------------------------------------------------- S def suffix_reads(m, b, j): B = b ** j return all((n % m == 0) == ((n + B) % m == 0) for n in range(m * B)) def floor_reads(m, Mt, Mp): return all((n // m) % Mt == ((n + Mp) // m) % Mt for n in range(m * Mp)) def least_lookahead(m, chain, t): for c in range(1, len(chain) - t): if floor_reads(m, chain[t], chain[t + c]): return c return None def section_s(): print("S the suffix and floor reads") ok = True for b, jmax in ((2, 6), (6, 3), (10, 3)): for m in range(2, 31): for j in range(1, jmax + 1): ok &= suffix_reads(m, b, j) == (b ** j % m == 0) check("[m | n] read from j digits iff m | b^j", ok, "bases 2, 6, 10; m = 2..30") chain = [1, 2, 6, 30, 210, 2310] cells = {} for t in range(1, 5): for m in range(2, 31): c = least_lookahead(m, chain, t) if c is not None: cells[(t, m)] = c want = {(1, 3): 1, (1, 5): 2, (1, 7): 3, (1, 11): 4, (1, 15): 2, (1, 21): 3, (2, 5): 1, (2, 7): 2, (2, 11): 3, (3, 7): 1, (3, 11): 2, (4, 11): 1} check("primorial chain: the readable floor cells", cells == want, f"{len(cells)} cells: " + ", ".join( f"t{t} m{m} c{c}" for (t, m), c in sorted(cells.items()))) two = [2 ** i for i in range(8)] ctl = {m: least_lookahead(m, two, 1) for m in range(2, 31)} ctl = {m: c for m, c in ctl.items() if c is not None} check("base-2 control: m = 2, 4, 8, 16 at c = v_2(m)", ctl == {2: 1, 4: 2, 8: 3, 16: 4}, str(ctl)) # ---------------------------------------------------------------- V def crt(residues, moduli): M = prod(moduli) x = 0 for r, m in zip(residues, moduli): Mi = M // m x += r * Mi * pow(Mi, -1, m) return x % M def vp(n, p): v = 0 while n % p == 0: n //= p v += 1 return v def section_v(): print("V the valuation row") W = [2, 3, 5, 7] ok = True for u in range(3, 13): y = crt([2 ** u - 1, 1, 1, 1], [2 ** (u + 1), 3, 5, 7]) ok &= all(vp(y, p) == 0 for p in W) and vp(1 + y, 2) == u check("zero W-vector on both summands, v_2 of the sum = u", ok, "u = 3..12, W = {2, 3, 5, 7}") ok = all(vp(x * y, p) == vp(x, p) + vp(y, p) for x in range(1, 200) for y in range(1, 200) for p in W) check("multiplication adds exponent vectors", ok) # ---------------------------------------------------------------- I def section_i(): print("I the index coordinates") ps = primes_upto(20) ok = True for k in range(3, 8): P = ps[:k] lam = lcm(*[p - 1 for p in P]) ok &= lam < prod(p - 1 for p in P) check("lambda < phi at every rung k = 3..7", ok) tabs = {p: dlog_table(p) for p in P7} def index(x, primes): return tuple(tabs[p][1][x % p] for p in primes) units = [x for x in range(M7) if gcd(x, M7) == 1] idx = {index(x, P7) for x in units} check("index map is a bijection at Z/510510", len(idx) == len(units) == prod(p - 1 for p in P7), f"{len(idx)} tuples, {len(units)} units") PRIMES_210 = [2, 3, 5, 7] u210 = [x for x in range(210) if gcd(x, 210) == 1] ok = all(index(x * y, PRIMES_210) == tuple( (a + b) % (p - 1 if p > 2 else 1) for a, b, p in zip(index(x, PRIMES_210), index(y, PRIMES_210), PRIMES_210)) for x in u210 for y in u210) check("multiplication is index addition at Z/210", ok) ok = all(index(pow(x, e, 210), PRIMES_210) == tuple( (e * a) % (p - 1 if p > 2 else 1) for a, p in zip(index(x, PRIMES_210), PRIMES_210)) for x in u210 for e in range(13)) check("powering is index scaling at Z/210", ok) ok = all(((pow(x, (p - 1) // 2, p) == 1) == (tabs[p][1][x % p] % 2 == 0)) for x in u210 for p in (3, 5, 7)) check("square class is index parity at Z/210", ok) for e, want in ((2, (1440, 64)), (3, (10240, 9))): counts = {} for x in units: y = pow(x, e, M7) counts[y] = counts.get(y, 0) + 1 roots = set(counts.values()) check(f"e = {e} at Z/510510: powers and roots per power", (len(counts), roots) == (want[0], {want[1]}), f"{len(counts)} powers, roots {sorted(roots)}") # ---------------------------------------------------------------- Z def zech_pair(p, q, w_all): g, ind = dlog_table(p) h = (p - 1) // q C = {pow(g, q * i, p) for i in range(h)} ws = [w for w in C if w != 1] if w_all else [pow(g, q, p)] for w in ws: adm = [x for x in range(1, p) if x != p - 1 and w * x % p != p - 1] comply = {x for x in adm if (1 + w * x) * pow(1 + x, -1, p) % p in C} derived = {(z - 1) * pow(w - z, -1, p) % p for z in C if z not in (1, w)} if comply != derived or len(comply) != h - 2: return False if len(adm) != p - 3: return False wit = [x for x in adm if x not in comply] if not wit: return False x = wit[0] a, b = ind[x], ind[w * x % p] za, zb = ind[(1 + x) % p], ind[(1 + w * x) % p] if (a - b) % q != 0 or (za - zb) % q == 0: return False return True def section_z(): print("Z the Zech wall") pairs, ok = 0, True for p in primes_upto(199): if p < 5: continue for q in range(2, (p - 1) // 2 + 1): if (p - 1) % q == 0: pairs += 1 ok &= zech_pair(p, q, w_all=p < 60) check("complying x are exactly the h - 2 derived ones", ok and pairs == 263, f"{pairs} pairs (p, q)") # ---------------------------------------------------------------- G def section_g(): print("G the support log") bad = [M for M in range(2, 301) if all(pow(x, carmichael(M) + 1, M) == x for x in range(M)) != squarefree(M)] nsf = sum(squarefree(M) for M in range(2, 301)) check("x^(lambda+1) = x everywhere iff M squarefree", not bad, f"M = 2..300, {nsf} squarefree, mismatches {bad}") lam = carmichael(M7) ok = all(pow(x, lam + 1, M7) == x for x in range(M7)) check("x^241 = x at every x of Z/510510", ok and lam == 240) P = [2, 3, 5, 7] tabs = {p: dlog_table(p)[1] for p in P} def support_index(x): return {p: tabs[p][x % p] for p in P if x % p} ok = True for x in range(210): gx = support_index(x) for y in range(210): gy = support_index(y) want = {p: (gx[p] + gy[p]) % (p - 1 if p > 2 else 1) for p in gx if p in gy} ok &= support_index(x * y % 210) == want check("product on supports: supports meet, indices add", ok) ok = all(pow(x, 12, 210) % p == (1 if x % p else 0) for x in range(210) for p in P) check("x^lambda is the idempotent of supp x at Z/210", ok) ok = True for x in range(210): inv = pow(x, 11, 210) gx, gi = support_index(x), support_index(inv) ok &= set(gi) == set(gx) and all( (gi[p] + gx[p]) % (p - 1 if p > 2 else 1) == 0 for p in gx) ok &= x * inv * x % 210 == x check("meadow inverse x^(lambda-1) negates the indices", ok) # ---------------------------------------------------------------- E def section_e(): print("E the exponent wall") ok = True for p in primes_upto(13)[1:]: bad = [x for x in range(p) if pow(x, 1, p) != pow(x, 1 + p, p)] ok &= bad == list(range(2, p)) check("x^y at (y, y + p) disagrees exactly off {0, 1}", ok, "p = 3..13, y = 1") ok = all(pow(x, y, p) == pow(x, y + p - 1, p) for p in primes_upto(13) for x in range(p) for y in range(1, p)) check("positive exponents are read mod p - 1", ok) ok = all([x for x in range(p) if pow(x, 0, p) != pow(x, p - 1, p)] == [0] for p in primes_upto(13)) check("the zero exponent fails at x = 0 only", ok) read = [M for M in range(2, 301) if squarefree(M) and all(pow(x, y, M) == pow(x, y + M, M) for x in range(M) for y in range(1, M + 1))] check("squarefree M <= 300: exponent read mod M iff lambda | M", read == [M for M in range(2, 301) if squarefree(M) and M % carmichael(M) == 0], f"read at {read}") hits = [M for M in range(2, 2001) if squarefree(M) and M % carmichael(M) == 0] check("lambda | M up to 2,000", hits == [2, 6, 42, 1806], str(hits)) # ---------------------------------------------------------------- R def cyclic_subgroups(M): subs = set() for g in range(M): subs.add(frozenset(g * i % M for i in range(M))) return [H for H in subs if 1 < len(H) < M] def additive_decompositions(M): subs = cyclic_subgroups(M) out = [] for r in range(2, 5): for combo in combinations(subs, r): if prod(len(H) for H in combo) != M: continue sums = {0} for H in combo: sums = {(s + h) % M for s in sums for h in H} if len(sums) == M: out.append(combo) return out def coordinates_of(M, combo): coords = {} for parts in _product_lists([sorted(H) for H in combo]): coords[sum(parts) % M] = parts return coords def _product_lists(lists): if not lists: yield () return for a in lists[0]: for rest in _product_lists(lists[1:]): yield (a,) + rest def section_r(): print("R the rigidity dichotomy") for M, want in ((30, 4), (60, 4), (12, 1), (210, 14)): decs = additive_decompositions(M) orders_ok = all( all(gcd(len(a), len(b)) == 1 for a, b in combinations(c, 2)) for c in decs) mult_ok, size_ok = True, True for combo in decs: co = coordinates_of(M, combo) mult_ok &= all( co[x * y % M] == tuple(a * b % M for a, b in zip(co[x], co[y])) for x in range(M) for y in range(M)) for i in range(len(combo)): signs = {} for x in range(M): signs.setdefault(co[x][i], set()).add(2 * x >= M) size_ok &= any(len(s) == 2 for s in signs.values()) check(f"Z/{M}: + read coordinate by coordinate", len(decs) == want and orders_ok and mult_ok and size_ok, f"{len(decs)} decompositions, coprime orders {orders_ok}, " f"x local {mult_ok}, size walled {size_ok}") U = [x for x in range(30) if gcd(x, 30) == 1] subs = set() for a in U: for b in U: H, frontier = {1}, [1] while frontier: h = frontier.pop() for s in (a, b): z = h * s % 30 if z not in H: H.add(z) frontier.append(z) subs.add(frozenset(H)) subs = [H for H in subs if 1 < len(H) < len(U)] decs = [(A, B) for A, B in combinations(subs, 2) if len(A) * len(B) == len(U) and A & B == {1}] chan = [frozenset(x for x in U if x % 3 == 1), frozenset(x for x in U if x % 5 == 1)] aligned = sum(set(d) == set(chan) for d in decs) check("U(30): direct decompositions, channel-aligned ones", (len(decs), aligned) == (4, 1), f"{len(decs)} decompositions, {aligned} aligned") # ---------------------------------------------------------------- P def poly_functions(N): gens = [tuple(pow(a, k, N) for a in range(N)) for k in range(2 * N + 2)] span = {tuple([0] * N)} for g in gens: new = set(span) for s in span: v = s for _ in range(N - 1): v = tuple((a + b) % N for a, b in zip(v, g)) new.add(v) span = new return span def conjunctive_mode(elems, rel, projs): R = {(x, y) for x in elems for y in elems if rel(x, y)} P = [{(f(x), f(y)) for x, y in R} for f in projs] conj = {(x, y) for x in elems for y in elems if all((f(x), f(y)) in Pi for f, Pi in zip(projs, P))} if conj == R: return "conjunctive", len(R), len(conj) if len(conj) == len(elems) ** 2: return "maximal", len(R), len(conj) return "proper", len(R), len(conj) def cyc_order(a, n): return n // gcd(a, n) def section_p(): print("P the bearers") sizes, ok = {}, True for N in (4, 6, 8, 9): span = poly_functions(N) sizes[N] = len(span) ok &= tuple(1 if a == 0 else 0 for a in range(N)) not in span check("[a = 0] is no polynomial at Z/4, Z/6, Z/8, Z/9", ok and sizes == {4: 64, 6: 108, 8: 1024, 9: 19683}, str(sizes)) ok = all((1 - pow(a, p - 1, p)) % p == (1 if a == 0 else 0) for p in primes_upto(13) for a in range(p)) check("at a prime it is 1 - a^(p-1)", ok) mode, _, _ = conjunctive_mode( range(6), lambda x, y: x == y, [lambda x: x % 2, lambda x: x % 3]) check("control: equality at Z/6 is conjunctive", mode == "conjunctive", mode) for M, A, B in ((6, 2, 3), (36, 4, 9)): mode, r, c = conjunctive_mode( range(M), lambda x, y: x <= y, [lambda x, A=A: x % A, lambda x, B=B: x % B]) check(f"order at Z/{M} through windows {A} and {B}: {mode}", mode == "maximal", f"{r} of {c}") bad, pairs = [], 0 for n1 in range(2, 11): for n2 in range(n1, 11): elems = [(a, b) for a in range(n1) for b in range(n2)] def order(x, n1=n1, n2=n2): return lcm(cyc_order(x[0], n1), cyc_order(x[1], n2)) mode, _, _ = conjunctive_mode( elems, lambda x, y: order(y) % order(x) == 0, [lambda x: x[0], lambda x: x[1]]) pairs += 1 want = ("conjunctive" if gcd(n1, n2) == 1 else "maximal" if n1 == n2 else "proper") if mode != want: bad.append((n1, n2, mode)) check("order divisibility on C_n1 x C_n2: conjunctive iff coprime, " "maximal iff equal", not bad and pairs == 45, f"{pairs} pairs, mismatches {bad}") elems = [(a, b, c) for a in range(2) for b in range(2) for c in range(2)] mode, _, _ = conjunctive_mode( elems, lambda x, y: (2 if any(y) else 1) % (2 if any(x) else 1) == 0, [lambda x: x[0], lambda x: x[1], lambda x: x[2]]) check("order divisibility on C2 x C2 x C2: maximal", mode == "maximal", mode) U15 = [x for x in range(15) if gcd(x, 15) == 1] ords = sorted(next(k for k in range(1, 9) if pow(x, k, 15) == 1) for x in U15) shape = sorted(lcm(cyc_order(a, 2), cyc_order(b, 4)) for a in range(2) for b in range(4)) check("U(15) has the order multiset of C2 x C4", ords == shape, str(ords)) def main(): section_b() section_a() section_s() section_v() section_i() section_z() section_g() section_e() section_r() section_p() print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed") raise SystemExit(0 if all(CHECKS) else 1) if __name__ == "__main__": main()