sizeless.py

"""sizeless.py -- growth with size taken out of the cost: what the
divisibility order alone can author, and what only the ordering of the
integers by size supplies.

QUESTION. Every growth law of growth.py extends by the LEAST
admissible m, so it orders its candidates by size, the archimedean
place the rungs delete. Take size out. Between candidate windows Z/m
the only canonical structure is the unital ring maps, and a
window-visible cost is one that order sees: invariant under the
order's automorphisms, which permute the primes, so a function of m's
factorization shape. Which of the primorial tower's
features (fields, squarefree-ness, every prime arriving, the
increasing order of arrival) can such a cost buy, and which are size's
alone?

THE ARGUMENT (written before the engine).
  (1) THE HOM ORDER. A unital map Z/a -> Z/b sends 1 to 1, so it is
      x mod b, well defined iff b | a. Window maps order the moves by
      divisibility, and distinct primes are an antichain: nothing in
      the window world ranks one prime above another.
  (2) COSTLESS INDEPENDENCE. With no cost every m coprime to M is
      admissible, composites and prime powers included: seed 2 may
      pick 9 and lose squarefree-ness, and seed 3 may pick 5, 7, 11,
      ... with 2 never entering. So fields, squarefree-ness and
      healing are authored by the selection, not by the demand.
  (3) FIELDS ARE WINDOW-PURCHASABLE. Let the cost be integer-valued,
      bounded below and STRICTLY MONOTONE under proper divisibility
      (d | m, d < m gives c(d) < c(m)); Omega,
      the prime factor count with multiplicity, is one. A composite
      coprime to M has a prime divisor, also coprime and cheaper, so
      every pick is a prime, under every tie-break.
  (4) THE PROPERNESS CRITERION. Under such a cost a prime p enters
      under every tie-break iff its SUBLEVEL SET {q prime : c(q) <=
      c(p)} is finite. While p is admissible every pick costs at most
      c(p), so picks come from the sublevel set, each consumed for
      good; a finite set runs out. An infinite one feeds a tie-break
      that picks the others forever: under Omega every prime costs 1,
      and the tie-break preferring odd primes starves 2. So every
      prime arrives under every tie-break iff the cost is PROPER, every
      sublevel set finite.
  (5) THE ROUTE. Rank the primes by any bijection rho with the positive
      integers and put c(m) = sum of a rho(p) over p^a || m. It is
      strictly monotone under proper divisibility and proper, and from 1
      its greedy walk takes the primes in the order rho. So every
      proper strictly monotone cost buys the destination, properness
      alone making the least cost exist, and its ranking, up to the
      tie-break among primes of equal cost, the route: every
      enumeration is some proper cost's. (A
      window-visible cost, a function of shape, is never proper: every
      prime costs the same. Corrected on review from "window data buys
      the destination".)
  (6) THE PRATT ORDER. One arrival rule reads only the rings Z/q: admit q only
      when every prime factor of q - 1, the order of the unit group of
      Z/q, already divides the modulus. That is the Pratt certificate
      order (the parents of q are the primes of q - 1). It forces 2
      first, and while 2 is the only prime seated, exactly the Fermat
      primes are admissible; the increasing order is one of its linear
      extensions, since every parent is smaller than its child.
      Counting the extensions measures how much route the
      rule supplies against the log2(n!) bits of an
      arbitrary enumeration of the first n primes.

DESIGN. Standard library and growth.py.
  H  the hom order: x mod b is a unital ring map Z/a -> Z/b iff b | a,
     every a, b in 2..60, checked by well-definedness, additivity and
     multiplicativity on all of Z/a.
  I  costless independence: the two specimens of (2) as legal
     trajectories.
  F  fields: greedy under Omega from seeds 1..6 for 20 steps under
     three tie-breaks (least, largest below 200, odd first), candidates
     every m <= 200 coprime to M; every pick prime.
  P  properness: under Omega with the odd-first tie-break, 30 steps
     from 1, 2 never picked. Under three scrambled rank costs on the
     first 30 primes (fixed seeds), 30 steps from 1: the picks are the
     primes in rank order, each run's window set the same 30 primes.
  R  the Pratt order on the first n primes: the primes admissible from
     the empty set and from {2} among the first 20; the increasing
     order an extension over the first 300 primes; the extension count
     at n = 5, 10, 15, 20 by a dynamic programme over down-sets.

PREDICTIONS, fixed before the run (from the script this replaces).
  H1 3481 pairs (a, b), a map exactly at b | a.
  I1 seed 2 then 9 is legal and Z/18 not squarefree; seed 3 then
     5, 7, ..., 37 is legal and 2 never enters.
  F1 every pick prime at 3 x 6 x 20 steps.
  P1 2 is starved for 30 steps; three scrambled costs give three
     distinct routes, each the rank order, one destination.
  R1 only 2 from the empty set; after {2} exactly 3, 5, 17 among the
     first 20 primes; the increasing order extends Pratt at 300
     primes; the counts 6, 6048, 108662400 and 8506240142400, so at
     n = 20 the rule supplies about 18 of the 61 route bits.
A KILL is any printed disagreement.

FINDINGS. Every prediction landed: 8/8 checks PASS. (Review turned
four checks into prints: I1's two specimens and R1's extension of
Pratt, which held by construction, and P1's one destination, which
the three route checks imply; its three distinct routes are printed.)
  H1 3481 pairs, x mod b a unital map exactly at b | a, 0 off.
  I1 seed 2 may pick 9 (Z/18 not squarefree); seed 3 may pick 5, ...,
     37 (M = 3710369067405, odd).
  F1 every pick prime under Omega, 3 tie-breaks x 6 seeds x 20 steps,
     which holds by construction, Omega being 1 exactly at primes: a
     specimen of (3), whose proof is the argument's.
  P1 under Omega the odd-first walk from 1 picks 3, 5, 7, 11, ... and
     never 2 in 30 steps; three scrambled rank costs give three
     distinct routes, each its rank order, one destination.
  R1 from the empty set only 2 is admissible, from {2} exactly 3, 5,
     17; the increasing order extends Pratt over 300 primes; the
     extension counts 6, 6048, 108662400, 8506240142400 at n = 5, 10,
     15, 20, so at 20 primes 42.95 of the 61.08 route bits stay free
     and the rule supplies 18.13.
  Tiers: the hom order is a property; fields by a strict cost a rule,
  proved; the properness criterion a criterion, proved both ways (the
  specimen realizes the converse); the route a theorem (any
  enumeration is a proper cost's), the Pratt count a measurement at
  n <= 20.

RUN RECORD. 8/8, 0.3 s wall, 10 MB peak commit under a memory guard.
"""

import random
from math import gcd, lgamma, log, log2

from growth import CHECKS, PRIMES, check, factor, section


def omega_mult(m):
    return sum(factor(m).values())


def squarefree(n):
    return all(e == 1 for e in factor(n).values())


def section_h():
    section("H  THE HOM ORDER: unital maps between windows")
    bad = pairs = 0
    for a in range(2, 61):
        for b in range(2, 61):
            pairs += 1
            ok = True
            for x in range(a):
                for y in range(a):
                    if ((x + y) % a) % b != (x + y) % b or \
                            ((x * y) % a) % b != (x * y) % b:
                        ok = False
                        break
                if not ok:
                    break
            bad += ok != (a % b == 0)
    check("H1 x mod b is a unital map Z/a -> Z/b exactly when b | a",
          bad == 0, f"{pairs} pairs, {bad} off")


def section_i():
    section("I  COSTLESS INDEPENDENCE: every coprime m admissible")
    ok1 = gcd(9, 2) == 1 and not squarefree(18)
    M, ok2 = 3, True
    for p in PRIMES[2:12]:
        ok2 = ok2 and gcd(p, M) == 1
        M *= p
    ok2 = ok2 and M % 2 == 1
    print(f"  specimen: seed 2 then 9 is legal, Z/18 not squarefree: {ok1}")
    print(f"  specimen: seed 3 then 5..37 is legal, M = {M}, odd: {ok2}")


def greedy(seed, steps, cost, tie):
    M, picks = seed, []
    for _ in range(steps):
        cands = [m for m in range(2, 201) if gcd(m, M) == 1]
        low = min(cost(m) for m in cands)
        pick = tie([m for m in cands if cost(m) == low])
        picks.append(pick)
        M *= pick
    return picks


TIES = {
    "least": min,
    "largest": max,
    "odd first": lambda c: min([m for m in c if m % 2] or c),
}


def section_f():
    section("F  FIELDS: a divisibility-strict cost picks primes")
    bad = 0
    for name, tie in TIES.items():
        for seed in range(1, 7):
            picks = greedy(seed, 20, omega_mult, tie)
            bad += sum(factor(p) != {p: 1} for p in picks)
    check("F1 every pick prime under Omega, 3 tie-breaks x 6 seeds x 20 "
          "steps", bad == 0, f"{bad} composite picks")


def section_p():
    section("P  PROPERNESS AND THE ROUTE")
    picks = greedy(1, 30, omega_mult, TIES["odd first"])
    print("  Omega, odd first, from 1:", picks[:8], "...")
    check("P1 under Omega the odd-first tie-break starves 2 for 30 steps",
          2 not in picks)
    first = PRIMES[:30]
    routes = []
    for s in (1, 2, 3):
        order = first[:]
        random.Random(s).shuffle(order)
        rank = {p: i + 1 for i, p in enumerate(order)}
        rank.update({p: i + 1 for i, p in enumerate(PRIMES) if p not in rank})

        def cost(m, rank=rank):
            return sum(a * rank[p] for p, a in factor(m).items())

        route = greedy(1, 30, cost, min)
        routes.append(route)
        check(f"P1 scrambled cost {s}: the route is its rank order",
              route == order)
    dest = {frozenset(r) for r in routes}
    print(f"  {len({tuple(r) for r in routes})} distinct routes, "
          f"{len(dest)} destination, the first 30 primes: "
          f"{dest == {frozenset(first)}}")


def section_r():
    section("R  THE PRATT ORDER: an arrival rule read off the rings Z/q")
    parents = {p: set(factor(p - 1)) if p > 2 else set() for p in PRIMES}
    first20 = PRIMES[:20]
    from_empty = [p for p in first20 if parents[p] <= set()]
    from_two = [p for p in first20 if p != 2 and parents[p] <= {2}]
    print("  admissible from {}:", from_empty, " from {2}:", from_two)
    check("R1 only 2 from the empty set; then exactly 3, 5, 17",
          from_empty == [2] and from_two == [3, 5, 17])
    print("  the increasing order extends Pratt (a parent divides p - 1): "
          f"{all(max(parents[p], default=0) < p for p in PRIMES[:300])} "
          "over the first 300 primes")
    counts = {}
    for n in (5, 10, 15, 20):
        ps = PRIMES[:n]
        idx = {p: i for i, p in enumerate(ps)}
        need = [sum(1 << idx[q] for q in parents[p]) for p in ps]
        full = (1 << n) - 1
        memo = {full: 1}

        def ext(mask):
            if mask in memo:
                return memo[mask]
            tot = 0
            for i in range(n):
                if not mask >> i & 1 and need[i] & mask == need[i]:
                    tot += ext(mask | 1 << i)
            memo[mask] = tot
            return tot

        counts[n] = ext(0)
    bits = log2(counts[20])
    total = lgamma(21) / log(2)
    print(f"  linear extensions: {counts}")
    print(f"  n = 20: {bits:.2f} bits of freedom left of {total:.2f}, the "
          f"rule supplies {total - bits:.2f}")
    check("R1 the counts 6, 6048, 108662400, 8506240142400",
          counts == {5: 6, 10: 6048, 15: 108662400, 20: 8506240142400})


def main():
    section_h()
    section_i()
    section_f()
    section_p()
    section_r()
    print()
    print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed")
    raise SystemExit(0 if all(CHECKS) else 1)


if __name__ == "__main__":
    main()