"""limit.py -- where one greedy growth walk goes: the pricing schedule a walk over F_2[x] or a curve over F_2 is an instance of, the chain its clock moves form, the one deep coordinate that chain leaves, the support beside it, the ceiling on the deep coordinate's degree, and the rules that can stop the support from widening. QUESTION. growth.py grows a modulus by the cheapest move a demand admits. Over F_2[x], and over the ring of a curve over F_2, the dynamics demand (lambda must rise) never stops. What does a greedy walk converge to, coordinate by coordinate, and which of its features belong to the ring rather than to the way moves are priced? THE SCHEDULE. ITEMS carry a positive integer DEGREE d, the SUPPLY sigma(d) >= 0 counting the items of degree d, finitely many per degree. A state gives every item an exponent a >= 0 and carries a NOTCH T, a member of a LADDER S, an infinite set of positive integers containing 1; next_S(x) is the least member of S at or above x. A degree is COVERED when it lies in the BORN set B, when nu OPENINGS have been made at it, or when the COVERING RULE says so (the default rule adds nothing). A move on an item x of degree d is an OPENING, when a(x) = 0 and d is uncovered: DOOR 1, x lands at 1, the notch stays; a CLOCK MOVE otherwise: door r = T + 1 - a(x), x lands at T + 1, and T <- next_S(T + 1), and costs the PRICE kappa(d, r). Every walk starts from the VOID, every exponent 0 and T = 1. A GREEDY walk takes a move of least price; a TIE is a menu with several least types, and a BRANCH is one way of breaking every tie. The clock is GLOBAL: one notch for every item. The invariant a <= T holds (an opening lands at 1 <= T, a clock move at T + 1 <= next_S(T + 1)), so every door is at least 1. The HOLDER of a clock move is the item it moves; the item holding every clock move from some point on is the RUNAWAY, and an item that held a clock move and is not the runaway is a STRAND. The CORNER is S = the powers of 2, kappa(d, r) = d r, nu = 1, B = {1}. THE ARGUMENT (written before the engine; the clauses marked AFTER THE RUN were added after it). (1) THE DOOR OVER F_2[x]. For P irreducible of degree d, (F_2[x]/P^a)^* is F_(2^d)^* times (1 + P)/(1 + P^a), and (1 + y)^(2^j) = 1 + y^(2^j) makes the second factor a 2-group of exponent 2^ceil(log2 a). So lambda(P^a) = lcm(2^d - 1, 2^ceil(log2 a)), and lambda of a state is the lcm over its places. A move raises lambda at P either by seating P when 2^d - 1 does not divide the state's odd part (an opening, door 1) or by carrying P past the state's 2-part T = 2^k, to exponent T + 1, which doubles T (a clock move, door T + 1 - a). The index [P^a : P^(a+r)] is 2^(dr), whose log is the price d r. A curve over F_2 has the same completions, F_(2^d)[[t]] at a place of degree d, so the same doors. So the IDEAL WORLD (a move seats one place power) over either ring is the corner schedule, with the supply its place count per degree, IF the covered degrees are the opened ones and 1. That is BANG'S THEOREM (1886, the base-2 case of Zsigmondy's): for d > 1, d != 6, 2^d - 1 has a prime p no smaller 2^j - 1 carries, and since the order of 2 mod p is d, p | 2^j - 1 iff d | j. At d = 6, 63 = 3^2 7 and v_3(2^j - 1) >= 2 iff 6 | j. So 2^d - 1 divides the lcm of 2^j - 1 over a set J iff J holds a multiple of d; a walk opening degrees in increasing order never covers a degree before opening it. The PRODUCT of the 2^j - 1, a more generous reading, frees d = 6 alone (3 from j = 2 and 4, 7 from j = 3); at base 3 neither reading frees any degree (3^2 - 1 = 8 against 3 - 1 = 2 is Zsigmondy's n = 2 exception, and 8 is not supplied). (2) THE CHAIN. Let kappa be strictly increasing in the door and nondecreasing in the degree (F2 sharpens this to the joint hypothesis). Take a clock move of Y whose previous clock move had a different holder Z. Z landed one above the notch u it met, and every exponent except Z's is at most max(1, u), so a(Y) < a(Z) and Y's door exceeds Z's. Z could have been moved, so kappa(d_Y, r_Y) <= kappa(d_Z, r_Z) < kappa(d_Z, r_Y), whence d_Y < d_Z. So the holders' degrees STRICTLY FALL at every change of holder, and no holder returns, its degree exceeding every later holder's. The holders form a finite chain: a walk with infinitely many clock moves has exactly ONE RUNAWAY, its strands are the chain's earlier members, at most as many as the supplied degrees below the first holder, each at a finite exponent >= 2, and every item never clocked stands at 0 or 1 forever. Nothing here reads the ladder, the degrees' values, nu or the ring. (3) WHEN THE CLOCK RUNS FOREVER. Between clock moves T is fixed, so a clock move's price is fixed. Each opening is spent once. If the opening prices kappa(d, 1) tend to infinity over the supply (finitely many items open below any bound), or the supply is finite, openings alone cannot continue and the walk clocks infinitely often. AFTER THE RUN: merely unbounded is not enough. Supply every degree and let kappa(d, 1) = 1 at every even d and kappa(d, r) = d r otherwise; on the doubling ladder, once the notch reaches 4 every clock move has door at least 2 and costs at least 2, and the walk opens forever. At the DEGREE-BLIND price kappa = r no holder change is possible at all, and every opening costs 1. A clocked item sits at T + 1 and its next door is next_S(T + 1) - T, at least 2 once the ladder's gap there exceeds 1; every other door is then at least 2 as well (a <= 1 < T). So after a short transient a degree-blind walk on any ladder but the exact one, over infinitely many supplied degrees that its born set and covering rule leave uncovered until they open, clocks NEVER AGAIN and opens forever: no deep coordinate. On the doubling ladder the transient is two clock moves (land at 2, notch 2, door 1 again; land at 3, notch 4, door 2). (4) THE SUPPORT. Once the runaway X holds every clock move, its door at each re-clock is the ladder's gap T_k - T_(k-1), so the recurrent price is kappa(d_X, gap). Take the default covering, no degree covered but by birth or by its nu openings. If the gaps are unbounded and kappa is unbounded in the door, then for any opening a large enough gap prices the re-clock above it, and since openings leave the notch where it is, every cheaper opening is taken before that re-clock: over infinitely many supplied degrees not born covered the support widens forever, min(nu, sigma(d)) items at exponent 1 at every uncovered-at-birth degree. If the gaps are bounded by G, no opening priced above kappa(d_X, G) is ever taken after the runaway settles, since the re-clock is always on the menu: the support is finite when only finitely many openings cost kappa(d_X, G) or less (the degree-blind price on the exact ladder has infinitely many). (5) THE CEILING. At each re-clock after settling, the runaway (degree D) beat every item of the least supplied degree d_min. If D > d_min every such item is at 0 or 1, since strands sit above D, and its price is at most kappa(d_min, T_k + 1). So kappa(D, T_k - T_(k-1)) <= kappa(d_min, T_k + 1) at every large k, and at kappa = d^alpha r, alpha > 0, D <= d_min ((T_k + 1)/(T_k - T_(k-1)))^(1/alpha). On the ladder T_k = ceil(b T_(k-1)) the ratio tends to b/(b - 1), so D <= d_min (b/(b - 1))^(1/alpha): 2 d_min at the corner. The ratio R_k satisfies R_k/(R_k - 1) = (T_k + 1)/(T_(k-1) + 1) exactly, so the bound reads the liminf of R_k, finite as soon as T + 1 grows by a fixed ratio infinitely often. AFTER THE RUN: a bound on EVERY ladder, the sum price included. Openings leave the notch at 1, so the first clock move is made at T = 1, where an item of degree d_min offers a move at price at most kappa(d_min, 2) (its opening, a door-1 clock, or a door-2 clock when its degree is covered). So the first holder has kappa(d_1, 1) <= kappa(d_min, 2) and the chain gives D <= d_1: D <= 2^(1/alpha) d_min at d^alpha r, and D <= d_min + 1 at the sum price. The ladder formula is sharper only at b > 2. (6) ATTAINMENT IS THE VOID MENU'S. Until the first clock move the notch is 1, and there the least born covered degree d_c bids kappa(d_c, 2) and the least fresh degree d_f, the least supplied degree not born covered, bids kappa(d_f, 1); an item opened meanwhile at d_f has a clock at door 1 and bids kappa(d_f, 1) again. So, at a price strictly increasing in the degree, the first holder's degree is a winner of that comparison. At the corner every ring supply with a degree-2 place ties it, kappa(1, 2) = 2 = kappa(2, 1), and a row whose supply has nothing at 1 or 3, with degree 2 born covered and 4 the least fresh, ties it at kappa(2, 2) = 4 = kappa(4, 1), a degree-4 holder being the ceiling 2 d_min itself. The tie is the ADDITIVE index's: priced by the MULTIPLICATIVE index, over a ring whose places of degree d have norm q^d, an unseated place at door r costs q^(dr) - q^(d(r-1)) and a seated one q^(dr), so the void bids are q^(2d) - q^d < q^(2d) - 1, and the born covered bid wins at every q. (7) THE STRAND. At the corner the first holder never loses the clock: at degree d_1 <= 2 d_min it re-clocks at d_1 T/2 against a least rival's d_min (T + 1) at exponent 0 (the rival at exponent 1 bids d_min T, which the chain forbids from winning unless d_min < d_1 and the bids tie). At b = 3 the tie branch's degree-2 holder bids 2 (2T/3) = 4T/3 against a rational rival's T + 1, and loses once T > 3: exactly one strand, by (2), on that branch. (8) THE COVERING RULE. An OPENED-SET rule, whose extra covered set is a function of the born and opened degrees, covers nothing new on a clock move. So between openings the HORIZON (the least uncovered supplied degree with an item left) has a constant price while the runaway's recurrent price is unbounded with the gaps: the horizon opening undercuts some later re-clock, so after any step some opening is made, and over infinitely many supplied degrees not born covered no opened-set rule stops the widening, however fast it covers. A CLOCK-KEYED rule, d covered while d <= theta T, can: at the corner over a supply holding every degree (so the horizon costs at least floor(theta T) + 1) with runaway degree D, which is the first clock's holder's by (7), T is a power of 2 at least 2 after the first clock, so D T/2 is an integer and the recurrent price D T/2 is below the horizon's floor(theta T) + 1 iff D T/2 <= theta T iff theta >= D/2. Below D/2 an opening is taken only at or below the standing clock price, D T/4 through the notch T/2, so no degree above D T/4 has been opened by the move to T once D T/4 >= 2, and the horizon just after that move is at most max(floor(theta T), floor(D T/4)) + 1, under D T/2 at a large notch. The widening stops at the first clock or never, with no T in the condition. PREDICTIONS, frozen before the engine, each naming what the run PRINTS. PR1 THE DOOR. Printed: the unit-group exponent of F_2[x]/P^a computed by brute force at every irreducible P of degree <= 4 and a with deg P^a <= 12, against lcm(2^d - 1, 2^ceil(log2 a)). KILL: one off. PR2 BANG. Printed: for d <= 300, whether 2^d - 1 divides the lcm, and the product, of 2^j - 1 over j < d, and the same at base 3; and the multiple criterion at every nonempty J within 1..12 and 1 < d <= 12. KILL: an lcm hit at any d, a product hit other than d = 6 at base 2, or one criterion miss. PR3 THE EXACT WALKER IS THE SCHEDULE. Printed: states compared between a walker covering by exact divisibility of big-integer lambda and the corner schedule, over the six ring supplies (F_2[x] and five curves over F_2 given by their zeta numerators), menus as typed multisets. KILL: one menu or covered set differing. PR4 THE CHAIN. Printed: holder changes read over every schedule walk (every section but the exact-walker comparison, which advances without the chain check), a change counted each time a walk steps through it, each checked falling. KILL: one that did not. PR5 THE CORNER'S LIMIT. Printed per ring supply, over its branches: the items above exponent 1, strands, whether exponent-1 items are one per opened degree, and the last change of holder. KILL: a second item above 1, or a strand. PR6 THE SUPPORT. Printed per ladder (exact, gaps 2, 3, 5, squares, triangular numbers, doubling, and b = 3/2, 3, 4): the last opening's step and degree against the recurrent price kappa(d_X, G), G the largest door after settling. KILL: a bounded-gap walk opening above kappa(d_X, G) after settling, or an unbounded-gap walk that stops opening before its degree cap. Read against the code after the run: it checks a bounded-gap walk opening above d_X G after its last change of holder or in the last quarter of its 240 moves (greed forbids the first, the re-clock always on the menu: a check of the engine), and an unbounded-gap walk with no opening in that quarter. PR7 THE CEILING. Printed per schedule and supply: the runaway degrees over all branches and the formula's value. Checked, not printed: the finite-notch bound at every re-clock, exercised only where the runaway is above d_min (never at a multiplicative row, whose runaways the print shows at d_min); greed makes it a check of the engine, the d_min item always on the menu. KILL: a runaway above its bound; or the designed {2, 4} supply's corner census not reaching 4. PR8 THE VOID LAW. Printed per schedule and supply: the degrees that ever hold a clock move over all branches, against the void winners, at the additive index; the branch and strand counts at the multiplicative index. KILL: one row where the census differs from the winners, or a multiplicative row with two branches or a strand. PR9 THE STRAND. Printed at b = 3/2, 2, 3, 4 per supply: branches and strands per branch. KILL: no strand at the schedules named b = 3 and b = 4, or one at any schedule on a ladder of ratio 3/2 or 2; revised before the run: a row whose void menu has one winner seats no item of degree 2 d_min at the tie and is exempt (h5, with no place of degree 2 or 3). PR10 THE DEGREE-BLIND PRICE. Printed: per tie rule (clock first, open first, open five then clock), not per branch, at alpha = 0 on the doubling ladder, the number of clock moves and the final notch (while T = 1 an opened item's clock ties every opening at price 1, so WHEN the two clocks fall is the tie-break's). KILL: a tie rule with more than two clock moves or a final notch above 4. PR11 THE COVERING RULES. Printed: the below-2^d opened-set rule's openings at the corner, and at theta in {1/4, 1/2, 3/4, 1, 3/2, 2} per branch whether the widening stopped (no opening from move 34 of 68), against theta >= D/2. KILL: the opened-set walk stopping, or one theta row against the iff. Read against the code after the run: it checks the opened-set walk's openings to be exactly 2, 4, 16, 65536 at notches 8, 16, 64, 262144, the supply ending at 65536. CONTROLS, run first: the exact-walker comparison made to fail by a tripling clock; the chain checker made to fire on a planted rising holder; the strand counter made to count a planted strand. FINDINGS (entered after the run, from its printed output). F1 THE RING IS A SUPPLY (PR1 to PR3 hit). lambda(P^a) as argued at 47 pairs, 32760 units read. Below 301 the lcm frees no degree at base 2 or 3 and the product frees 6 alone at base 2; the multiple criterion holds at all 45045 (J, d). The exact walker reads the corner's least moves and covered sets at all 720 states, 120 along one canonical walk over each of the six ring supplies cut at degree 40, and a tripling clock parts from it at the second state. Both walkers type the moves and price them alike, so the comparison reads the covered sets and the notch, never which moves raise lambda. The comparison is over SUPPLIED degrees: a degree with no place (3 on three curves, 2 and 4 on one each) is covered once a multiple of it opens, 3 by the opening at 6, which no menu reads. F2 THE CHAIN (PR4 hit). 17 changes of holder over the schedule walks, every one falling, a change counted once per tie edge stepped in the branched moves and once per branch after them. Sharpened in reading the prints: the hypothesis is the joint one, kappa(d', r') > kappa(d, r) at d' >= d and r' > r, since the multiplicative index at q = 2 prices a degree-1 unseated item one door deeper equal to a seated one; no change of holder occurred at any multiplicative row (checked per row in section_c). F3 THE CORNER'S LIMIT (PR5 hit). Branches 3, 3, 3, 3, 1, 3 over F2[x], h2, h3, h4, h5, g2; one item above exponent 1, no strand, the clock settled at its first move; every supplied degree above 1 opened, with none skipped, 290 degrees on every branch whose runaway is rational (notch 2^10) and 291 on every branch whose runaway has degree 2 (notch 2^9), the one extra being its own opening. The flat count is one per opened degree except where the runaway was itself opened fresh at degree 2. The notches are printed beside the counts. F4 THE SUPPORT (PR6 hit). The exact and gap-2 ladders never open, gap 3 opens to degree 2 and gap 5 to 4, each within d_X G, on the canonical branch, which clocks at the void's tie kappa(1, 2) = kappa(2, 1); the squares, triangular, and ratio 3/2, 2, 3, 4 ladders open 30 to 60 times in the last quarter of 240 moves. F5 THE CEILING AND THE VOID LAW (PR7, PR8 hit). 54 rows over 14 schedules; at every one the degrees ever clocked equal the void winners, no runaway exceeds its ceiling, and every degree below the highest opened, the born-covered aside, was opened min(nu, sigma(d)) times. The designed supply reads {2, 4} at the corner and at b = 3/2. Every runaway at a power or sum price lies within the first-clock bound (71 branch rows), and every ladder of the support table within 2 d_min. Every multiplicative row: one branch, no strand. The law is the sweep's, not general; the printed row off the sweep shows it: at b = 4 with degree 2 born covered and every degree from 2 supplied, the void winner is 3, above the ceiling 2, and a degree-2 item takes the clock from it; clocked {2, 3}, winners {3}, runaway 2. Argument (6) fixes only the FIRST holder. F6 THE STRAND (PR9 hit). b = 3: strands [0, 1, 1] over F2[x], [0, 1, 1, 1] over g2, [0, 1, 1] over the designed supply; b = 4: [0, 1] each; none at b = 2 or 3/2. F7 THE DEGREE-BLIND PRICE (PR10 hit). Clock-first: clocks at steps 1 and 2, notch 4, 298 openings; open-first: no clock in 300 moves; five openings then clock-first: clocks at steps 5 and 6. F8 THE COVERING RULES (PR11 hit). Below 2^d: openings at degrees 2, 4, 16, 65536 at notches 8, 16, 64, 262144. theta: 22 branches, stopped iff theta >= D/2 at every one, and a stopped branch never opens after its first clock. On all 22 the first clock's holder keeps the clock, every clock move of degree D and no change of holder. RUN RECORD. One process, CPython, no numpy: 13769 checks, 4.9 s. """ import time from bisect import bisect_left from collections import Counter from fractions import Fraction from math import gcd, isqrt CHECKS = [0] def check(cond, msg): CHECKS[0] += 1 if not cond: raise AssertionError(msg) # --------------------------------------------------------------------------- # polynomials over F_2 as integers, bit i the coefficient of x^i def pdeg(a): return a.bit_length() - 1 def pmod(a, m): dm = pdeg(m) while a and pdeg(a) >= dm: a ^= m << (pdeg(a) - dm) return a def pmul(a, b): r = 0 while b: if b & 1: r ^= a b >>= 1 a <<= 1 return r def ppowmod(a, n, m): r, a = 1, pmod(a, m) while n: if n & 1: r = pmod(pmul(r, a), m) a = pmod(pmul(a, a), m) n >>= 1 return r def irreducibles(d): return [p for p in range(1 << d, 1 << (d + 1)) if all(pmod(p, q) for q in range(2, 1 << (d // 2 + 1)))] def ceil_log2(e): return (e - 1).bit_length() def lcm(a, b): return a // gcd(a, b) * b def prime_factors(n): out, p = [], 2 while p * p <= n: if n % p == 0: out.append(p) while n % p == 0: n //= p p += 1 return out + ([n] if n > 1 else []) def mobius(n): r, p = 1, 2 while p * p <= n: if n % p == 0: n //= p if n % p == 0: return 0 r = -r p += 1 return -r if n > 1 else r def section_d(): """PR1 and PR2: the door over F_2[x], and Bang's coverage.""" print("S1 THE DOOR OVER F_2[x] AND BANG'S COVERAGE") cases = units = 0 for d in range(1, 5): for P in irreducibles(d): e = 1 while d * e <= 12: m = 1 for _ in range(e): m = pmul(m, P) L = lcm(2 ** d - 1, 2 ** ceil_log2(e)) us = [u for u in range(1, 1 << (d * e)) if pmod(u, P)] check(len(us) == 2 ** (d * e) - 2 ** (d * (e - 1)), "unit count") check(all(ppowmod(u, L, m) == 1 for u in us), f"u^L != 1 at P = {P:b}, e = {e}") for p in prime_factors(L): check(any(ppowmod(u, L // p, m) != 1 for u in us), f"exponent below L at P = {P:b}, e = {e}") cases, units, e = cases + 1, units + len(us), e + 1 print(f" PR1: lambda(P^a) = lcm(2^d - 1, 2^ceil(log2 a)) at {cases} " f"(P, e) with deg P <= 4, deg P^e <= 12, {units} units read " f"by brute force") for base in (2, 3): L, prod, lhits, phits = 1, 1, [], [] for d in range(1, 301): v = base ** d - 1 if d > 1 and L % v == 0: lhits.append(d) if d > 1 and prod % v == 0: phits.append(d) L, prod = lcm(L, v), prod * v print(f" PR2: base {base}, 1 < d <= 300: degrees freed by the lcm " f"{lhits}, by the product {phits}") check(lhits == [], "the lcm frees a degree") check(phits == ([6] if base == 2 else []), "the product frees") miss = pairs = 0 for mask in range(1, 1 << 12): J = [j + 1 for j in range(12) if mask >> j & 1] L = 1 for j in J: L = lcm(L, 2 ** j - 1) for d in range(2, 13): miss += (L % (2 ** d - 1) == 0) != any(j % d == 0 for j in J) pairs += 1 check(miss == 0, "the multiple criterion") print(f" PR2: 2^d - 1 | lcm(2^j - 1 : j in J) iff J holds a multiple " f"of d, at all {pairs} (J, d): {miss} misses") # --------------------------------------------------------------------------- # supplies, each a dict built in ascending degree RING_L = {"F2[x]": [1], "h2": [1, -1, 2], "h3": [1, 0, 2], "h4": [1, 1, 2], "h5": [1, 2, 2], "g2": [1, 2, 4, 4, 4]} def ring_supply(name, dmax): """Places per degree of a curve over F_2 with the named zeta numerator (a_0 .. a_2g), one rational place at infinity removed.""" a = RING_L[name] g = (len(a) - 1) // 2 check(all(a[2 * g - i] == 2 ** (g - i) * a[i] for i in range(g + 1)), f"functional equation at {name}") e = [(-1) ** i * c for i, c in enumerate(a)] s = [0] * (dmax + 1) for n in range(1, dmax + 1): v = (-1) ** (n - 1) * n * (e[n] if n < len(e) else 0) v += sum((-1) ** (i - 1) * e[i] * s[n - i] for i in range(1, min(n, len(e)))) s[n] = v N = [0] + [2 ** n + 1 - s[n] for n in range(1, dmax + 1)] sup = {} for d in range(1, dmax + 1): t = sum(mobius(d // k) * N[k] for k in range(1, d + 1) if d % k == 0) check(t % d == 0 and t >= 0, f"place count at {name}, degree {d}") sup[d] = t // d - (d == 1) return sup def wide(n, dmax): return {d: n for d in range(1, dmax + 1)} def designed(dmax): """Items at degree 2 and at every degree from 4, none at 1 or 3.""" return {d: (2 if d == 2 or d >= 4 else 0) for d in range(1, dmax + 1)} # --------------------------------------------------------------------------- # ladders class Ladder: def __init__(self, name, gen, bounded): self.name, self.gen, self.m, self.bounded = name, gen, [1], bounded def next(self, x): while self.m[-1] < x: self.m.append(self.gen(self.m[-1])) return self.m[bisect_left(self.m, x)] def ladder_b(b): b = Fraction(b) return Ladder(f"b = {b}", lambda t: max(t + 1, -((-b.numerator * t) // b.denominator)), False) def ladder_gap(c): return Ladder("exact" if c == 1 else f"gap {c}", lambda t: t + c, True) def _tri(t): n = (isqrt(8 * t + 1) - 1) // 2 + 1 return n * (n + 1) // 2 LADDERS = [ladder_gap(1), ladder_gap(2), ladder_gap(3), ladder_gap(5), Ladder("squares", lambda t: (isqrt(t) + 1) ** 2, False), Ladder("triangular", _tri, False), ladder_b(2)] # --------------------------------------------------------------------------- # prices: kappa(d, r, unseated) returns an orderable key def price_power(alpha): return lambda d, r, u: d ** alpha * r def price_additive(d, r, u): return d + r class MKey: """q^a - q^s, or q^a when s is None, compared exactly: at equal a the larger subtracted term is cheaper; at a < a' the first is cheaper, except at q = 2 where q^a equals q^(a+1) - q^a.""" __slots__ = ("q", "a", "s") def __init__(self, q, a, s): self.q, self.a, self.s = q, a, s def cmp(self, o): if (self.a, self.s) == (o.a, o.s): return 0 if self.a == o.a: if self.s is None or (o.s is not None and self.s < o.s): return 1 return -1 lo, hi = (self, o) if self.a < o.a else (o, self) if (self.q == 2 and lo.s is None and hi.s == hi.a - 1 and lo.a == hi.a - 1): return 0 return -1 if lo is self else 1 def __lt__(self, o): return self.cmp(o) < 0 def __gt__(self, o): return self.cmp(o) > 0 def __eq__(self, o): return self.cmp(o) == 0 def price_mult(q): return lambda d, r, u: MKey(q, d * r, d * (r - 1) if u else None) def section_m(): """The exact comparison against big integers at small exponents.""" n = 0 for q in (2, 3, 5): keys = [MKey(q, a, s) for a in range(1, 9) for s in [None] + list(range(a))] for x in keys: vx = q ** x.a - (q ** x.s if x.s is not None else 0) for y in keys: vy = q ** y.a - (q ** y.s if y.s is not None else 0) check(x.cmp(y) == (vx > vy) - (vx < vy), "MKey order") n += 1 print(f" the multiplicative key agrees with integer order at {n} pairs") # --------------------------------------------------------------------------- # the schedule walker class Sched: def __init__(self, name, ladder, price, nu=1, born=(1,), cover=None): self.name, self.ladder, self.price = name, ladder, price self.nu, self.born, self.cover = nu, frozenset(born), cover def but(self, **kw): s = Sched(self.name, self.ladder, self.price, self.nu, self.born, self.cover) for k, v in kw.items(): setattr(s, k, frozenset(v) if k == "born" else v) return s class State: __slots__ = ("T", "seat", "opens", "nseat") def __init__(self): self.T, self.seat = 1, Counter() self.opens, self.nseat = Counter(), Counter() def copy(self): s = State() s.T, s.seat = self.T, Counter(self.seat) s.opens, s.nseat = Counter(self.opens), Counter(self.nseat) return s def key(self): return (self.T, tuple(sorted(self.seat.items())), tuple(sorted(self.opens.items()))) def top(self): return max(self.seat, key=lambda de: de[1]) if self.seat else None def covered(S, st, d): return (d in S.born or st.opens[d] >= S.nu or (S.cover is not None and S.cover(st, d))) def menu(S, st, sup): """The least price and the least move TYPES (kind, degree, exponent) with their multiplicities. Kinds: c clocks a seated item, u clocks an unseated item of a covered degree, o opens. A price never falls below kappa(d, 1), which never falls as d rises, and sup runs up in degree, so the scan stops at the first degree whose kappa(d, 1) passes the best.""" best, types = None, [] for (d, e), n in st.seat.items(): k = S.price(d, st.T + 1 - e, False) if best is None or k < best: best, types = k, [(("c", d, e), n)] elif k == best: types.append((("c", d, e), n)) for d in sup: if best is not None and S.price(d, 1, True) > best: break u = sup[d] - st.nseat[d] if u <= 0: continue t, k = ((("o", d, 0), S.price(d, 1, True)) if not covered(S, st, d) else (("u", d, 0), S.price(d, st.T + 1, True))) if best is None or k < best: best, types = k, [(t, u)] elif k == best: types.append((t, u)) return best, types def apply(S, st, t): kind, d, e = t s = st.copy() if kind == "o": s.seat[(d, 1)] += 1 s.opens[d] += 1 s.nseat[d] += 1 return s if kind == "c": s.seat[(d, e)] -= 1 if not s.seat[(d, e)]: del s.seat[(d, e)] else: s.nseat[d] += 1 s.seat[(d, st.T + 1)] += 1 s.T = S.ladder.next(st.T + 1) return s def canon(types): """The canonical tie-break: a clock before an opening, low degree and low exponent first.""" return min(types, key=lambda tm: (tm[0][0] == "o", tm[0][1], tm[0][2]))[0] TALLY = Counter() def step(S, st, t, log): """Apply t, and at a change of holder check that the degree falls. (apply sets the notch itself, so no check here could catch a wrong one.) The previous holder is the item at the top exponent: it landed one above every other exponent. Log (kind, degree, door, notch before, notch after, holder changed).""" s = apply(S, st, t) if t[0] == "o": TALLY["opens"] += 1 log.append(("o", t[1], 1, st.T, s.T, False)) return s TALLY["clocks"] += 1 top = st.top() chg = top is not None and top[1] >= 2 and (t[0] == "u" or t[2] < top[1]) if chg: TALLY["changes"] += 1 check(t[1] < top[0], f"chain: holder {top} -> {t}") log.append((t[0], t[1], st.T + 1 - t[2], st.T, s.T, chg)) return s def walk(S, sup, n, st=None, log=None, choose=canon): st = st if st is not None else State() log = [] if log is None else log for _ in range(n): best, types = menu(S, st, sup) if best is None: break st = step(S, st, choose(types), log) return st, log def branches(S, sup, k, n, cap=64): """Every distinct state any tie choice reaches in k moves, each walked on canonically for n more; and the degrees clocked on any edge or walk.""" front, census = {State().key(): (State(), [])}, set() for _ in range(k): nxt = {} for st, log in front.values(): for t, _m in menu(S, st, sup)[1]: lg = list(log) s2 = step(S, st, t, lg) if t[0] != "o": census.add(t[1]) nxt.setdefault(s2.key(), (s2, lg)) front = nxt check(len(front) <= cap, "branch cap") out = [] for st, log in front.values(): st2, lg = walk(S, sup, n, st, list(log)) census |= {x[1] for x in lg if x[0] != "o"} out.append((st2, lg)) return out, census def shape(st): """(runaway degree, strands, items at exponent 1 per degree).""" above = sum(m for (d, e), m in st.seat.items() if e >= 2) flat = Counter() for (d, e), m in st.seat.items(): if e == 1: flat[d] += m return st.top()[0], above - 1, flat def settled(log): """The step of the last holder change (0 if none).""" return max([i for i, x in enumerate(log) if x[5]] + [0]) def void_winners(S, sup): bids = [] born = [d for d in sup if sup[d] and d in S.born] fresh = [d for d in sup if sup[d] and d not in S.born] if born: bids.append((S.price(born[0], 2, True), born[0])) if fresh: bids.append((S.price(fresh[0], 1, True), fresh[0])) lo = bids[0][0] for b, _ in bids: if b < lo: lo = b return {d for b, d in bids if b == lo} # --------------------------------------------------------------------------- # the exact walker: coverage read off lambda by divisibility def exact_menu(st, sup): lam_odd = 1 for (d, e) in st.seat: lam_odd = lcm(lam_odd, 2 ** d - 1) T = max([2 ** ceil_log2(e) for (d, e) in st.seat] + [1]) cov = {d for d in sup if sup[d] and lam_odd % (2 ** d - 1) == 0} items = Counter() for (d, e), n in st.seat.items(): items[("c", d, e, d * (T + 1 - e))] += n for d in sup: u = sup[d] - st.nseat[d] if u > 0: items[("u", d, 0, d * (T + 1)) if d in cov else ("o", d, 0, d)] += u lo = min(k[3] for k in items) return T, cov, Counter({k: m for k, m in items.items() if k[3] == lo}) def abstract_menu(S, st, sup): best, types = menu(S, st, sup) cov = {d for d in sup if sup[d] and covered(S, st, d)} return st.T, cov, Counter({(t[0], t[1], t[2], best): m for t, m in types}) def control_exact(S, n, dmax): """Advance by the EXACT walker's canonical move; compare every state.""" compared = 0 for name in RING_L: sup, st = ring_supply(name, dmax), State() for _ in range(n): ex, ab = exact_menu(st, sup), abstract_menu(S, st, sup) if ex != ab: return compared, False compared += 1 t = min(ex[2], key=lambda k: (k[0] == "o", k[1], k[2])) st = apply(S, st, t[:3]) return compared, True CORNER = Sched("corner", ladder_b(2), price_power(1)) def section_x(): """PR3, the controls and the MKey order check (section_m).""" print("S0 CONTROLS AND THE EXACT WALKER") for name in RING_L: sup = ring_supply(name, 8) print(f" {name:6s} affine places per degree 1..8: " f"{[sup[d] for d in range(1, 9)]}") bad, ok = control_exact(Sched("tripling", ladder_b(3), price_power(1)), 40, 40) check(not ok, "a tripling clock did not part from the exact walker") print(f" forced: a tripling clock parts from the exact walker at state " f"{bad + 1}") n, ok = control_exact(CORNER, 120, 40) check(ok, "the exact walker parts from the corner schedule") print(f" PR3: the corner schedule equals the exact walker at {n} states " f"over the six ring supplies, least moves and covered sets both") st = State() st.seat[(3, 4)] += 1 st.seat[(4, 1)] += 1 st.T = 4 try: step(CORNER, st, ("c", 4, 1), []) fired = False except AssertionError as e: fired = str(e).startswith("chain:") check(fired, "the chain check did not fire on a rising holder") st = State() st.seat[(1, 9)] += 1 st.seat[(2, 3)] += 1 check(shape(st)[1] == 1, "the strand count missed a planted strand") print(" forced: the chain check fires on a planted rising holder; the " "strand count reads a planted strand") TALLY.clear() section_m() def section_l(): """PR5: the corner's limit over the six ring supplies.""" print("S2 THE CORNER'S LIMIT OVER THE RING SUPPLIES (10 moves branched, " "290 more each)") print(" ring branches runaways above 1 strands one per opened " "opened by runaway last change") for name in RING_L: sup = ring_supply(name, 400) brs, census = branches(CORNER, sup, 10, 290) runs, nopen, above, strs, last = [], set(), set(), set(), set() notch = set() for st, log in brs: D, strands, flat = shape(st) runs.append(D) above.add(strands + 1) strs.add(strands) last.add(settled(log)) nopen.add((D, len(st.opens))) notch.add((D, st.T)) opened = sorted(st.opens) check(strands == 0, f"a strand at the corner, {name}") own = D in opened check(all(flat[d] == (0 if own and d == D else 1) for d in opened) and sum(flat.values()) == len(opened) - own, f"flat, {name}") check(opened == [d for d in sup if sup[d] and 1 < d <= opened[-1]], f"a degree skipped, {name}") check(settled(log) == 0, f"the clock changed hands, {name}") check((D, own) in ((1, False), (2, True)), f"runaway {name}") check(nopen <= {(1, 290), (2, 291)}, f"openings by runaway, {name}") by = "/".join(str(n) for _, n in sorted(nopen)) by += " notch " + "/".join(f"2^{T.bit_length() - 1}" for _, T in sorted(notch)) print(f" {name:6s} {len(brs):6d} {str(sorted(set(runs))):8s} " f"{str(sorted(above)):>6s} {str(sorted(strs)):>8s} yes" f" {by:>8s} {str(sorted(last))}") SWEEP = [ Sched("corner", ladder_b(2), price_power(1)), Sched("b = 3/2", ladder_b(Fraction(3, 2)), price_power(1)), Sched("b = 3", ladder_b(3), price_power(1)), Sched("b = 4", ladder_b(4), price_power(1)), Sched("alpha = 2", ladder_b(2), price_power(2)), Sched("additive", ladder_b(2), price_additive), Sched("nu = 2", ladder_b(2), price_power(1), nu=2), Sched("nu = 3", ladder_b(2), price_power(1), nu=3), Sched("born {}", ladder_b(2), price_power(1), born=()), Sched("born 1,2", ladder_b(2), price_power(1), born=(1, 2)), Sched("mult q=2", ladder_b(2), price_mult(2)), Sched("mult q=3", ladder_b(2), price_mult(3)), Sched("mult b=3", ladder_b(3), price_mult(2)), Sched("mult b=4", ladder_b(4), price_mult(2)), ] def ceiling(S, dmin): """The largest D with D^alpha (b - 1) <= dmin^alpha b, for a power price on a b-ladder; None where the formula does not apply.""" alpha = {"alpha = 2": 2}.get(S.name, 1) if S.name in ("additive",) or S.name.startswith("mult"): return None b = Fraction(S.ladder.name.split("= ")[1]) D = dmin while (D + 1) ** alpha * (b - 1) <= dmin ** alpha * b: D += 1 return D def section_c(): """PR7, PR8, PR9: the ceiling, the void law, the strand.""" print("S3 THE SWEEP: THE CEILING, THE VOID LAW, THE STRAND " "(10 moves branched, 150 more each)") print(" schedule supply branches clocked void runaways ceiling" " strands per branch") rows = 0 for S0 in SWEEP: sups = [(n, ring_supply(n, 60), S0) for n in ("F2[x]", "h5", "g2")] if S0.name not in ("born {}", "born 1,2"): sups.append(("{2,4}", designed(60), S0.but(born=(2,)))) for sname, sup, S in sups: brs, census = branches(S, sup, 10, 150) vw = void_winners(S, sup) dmin = min(d for d in sup if sup[d]) cap = ceiling(S, dmin) runs, strands = set(), [] for st, log in brs: D, ns, _ = shape(st) runs.add(D) strands.append(ns) top = max(st.opens) check(all(st.opens[d] == min(S.nu, sup[d]) for d in sup if d < top and sup[d] and d not in S.born), f"support width at {S.name}, {sname}") ks = [x for x in log if x[0] != "o"] check(len(ks) >= 3 and len({x[1] for x in ks[-3:]}) == 1, "no single holder over the last three clock moves") check(ns <= sum(1 for d in sup if sup[d] and d < max( x[1] for x in ks)), "more strands than the chain allows") if cap is not None: check(D <= cap, f"runaway {D} above the ceiling {cap}") if not S.name.startswith("mult"): fcb = max(d for d in sup if sup[d] and S.price(d, 1, True) <= S.price(dmin, 2, True)) check(D <= fcb, f"runaway {D} above the first-clock " f"bound {fcb}") TALLY["first-clock rows"] += 1 last = max([j for j, x in enumerate(ks) if x[5]] + [0]) for x in ks[last + 1:]: if D > dmin: check(not S.price(D, x[2], False) > S.price(dmin, x[3] + 1, True), "the finite-notch bound") check(census == vw, f"void law, {S.name} {sname}: " f"{sorted(census)} against {sorted(vw)}") if S.name.startswith("mult"): check(len(brs) == 1 and max(strands) == 0 and not any(x[5] for _st, log in brs for x in log), f"multiplicative row {S.name} {sname}") if S.ladder.name in ("b = 2", "b = 3/2"): check(max(strands) == 0, f"a strand at {S.name}, {sname}") if S.name in ("b = 3", "b = 4"): check(max(strands) >= 1 or len(vw) == 1, f"no strand at {S.name}, {sname}") rows += 1 print(f" {S.name:10s} {sname:6s} {len(brs):6d} " f"{str(sorted(census)):8s} {str(sorted(vw)):7s} " f"{str(sorted(runs)):8s} {str(cap):7s} {strands}") print(f" {rows} rows: the clocked degrees equal the void winners at " f"every row; {TALLY['first-clock rows']} branch rows at a power " f"or sum price, every runaway within the first-clock bound") _, census = branches(CORNER.but(born=(2,)), designed(60), 10, 150) check(census == {2, 4}, "the designed supply does not attain 2 d_min") S = Sched("b = 4", ladder_b(4), price_power(1), born=(2,)) sup = {d: (2 if d >= 2 else 0) for d in range(1, 61)} brs, census = branches(S, sup, 10, 150) vw, runs = void_winners(S, sup), sorted({shape(st)[0] for st, _ in brs}) print(f" off the sweep: b = 4, degree 2 born covered, every degree from " f"2 supplied: clocked {sorted(census)}, void winners {sorted(vw)}, " f"runaways {runs}, ceiling {ceiling(S, 2)}") check(census == {2, 3} and vw == {3} and runs == [2], "a void winner above its ceiling kept the clock") def section_s(): """PR6: the support against the ladder.""" print("S4 THE SUPPORT AGAINST THE LADDER (corner price, 2 items per " "degree to 400, 240 moves)") print(" ladder runaway settled last open at degree max door " "kappa(D, G) opens in last quarter") sup, n = wide(2, 400), 240 for lad in LADDERS + [ladder_b(Fraction(3, 2)), ladder_b(3), ladder_b(4)]: S = Sched(lad.name, lad, price_power(1)) st, log = walk(S, sup, n) D, _, _ = shape(st) s0 = settled(log) opens = [(i, x) for i, x in enumerate(log) if x[0] == "o"] li, ld = (opens[-1][0], opens[-1][1][1]) if opens else ("-", "-") G = max(x[2] for i, x in enumerate(log) if x[0] != "o" and i > s0) late = sum(1 for i, x in opens if i >= 3 * n // 4) check(D <= 2, f"runaway {D} above the first-clock bound 2 d_min") if lad.bounded: check(late == 0, f"a bounded ladder still opening: {lad.name}") check(all(x[1] <= D * G for i, x in opens if i > s0), f"an opening above kappa(D, G) at {lad.name}") else: check(late > 0, f"an unbounded ladder stopped: {lad.name}") print(f" {lad.name:12s} {D:5d} {s0:9d} {li:>9} {ld:>9} {G:9d} " f"{D * G:8d} {late:10d}") def section_b(): """PR10: the degree-blind price.""" print("S5 THE DEGREE-BLIND PRICE (alpha = 0, doubling ladder, 2 items " "per degree to 400, 300 moves)") S, sup = Sched("blind", ladder_b(2), price_power(0)), wide(2, 400) rules = { "clock first": canon, "open first": lambda ts: min(ts, key=lambda tm: (tm[0][0] != "o", tm[0][1]))[0], "open 5, then clock": None, } want = {"clock first": [1, 2], "open first": [], "open 5, then clock": [5, 6]} for name, rule in rules.items(): if rule is None: st, log = walk(S, sup, 5, choose=rules["open first"]) st, log = walk(S, sup, 295, st, log) else: st, log = walk(S, sup, 300, choose=rule) clocks = [i for i, x in enumerate(log) if x[0] != "o"] check(len(clocks) <= 2 and st.T <= 4, f"degree-blind {name}") check(clocks == want[name], f"degree-blind {name}: clock steps") print(f" {name:20s} clock moves at steps {clocks}, final notch " f"{st.T}, openings {len(log) - len(clocks)}") def section_k(): """PR11: the covering rules.""" print("S6 THE COVERING RULES (corner)") sup = wide(2, 65536) S = CORNER.but(cover=lambda st, d: any(d < 2 ** o for o in st.opens)) st, log = walk(S, sup, 40) opens = [(i, x[1], x[3]) for i, x in enumerate(log) if x[0] == "o"] print(f" below 2^d: openings (step, degree, notch) {opens}; " f"{len(log)} moves, the supply then covered") check([d for _, d, _ in opens] == [2, 4, 16, 65536] and [T for _, _, T in opens] == [8, 16, 64, 262144], "the below-2^d rule's openings") for i, _, _ in opens: check(all(x[0] != "o" for x in log[max(0, i - 1):i]), "two openings in a row under the below-2^d rule") print(" theta branch runaway stopped theta >= D/2 " "last open first clock") sup, rows = wide(2, 4096), 0 for th in (Fraction(1, 4), Fraction(1, 2), Fraction(3, 4), Fraction(1), Fraction(3, 2), Fraction(2)): S = CORNER.but(cover=lambda st, d, th=th: d <= th * st.T) brs, _ = branches(S, sup, 8, 60) for st, log in brs: D = shape(st)[0] opens = [i for i, x in enumerate(log) if x[0] == "o"] first = next(i for i, x in enumerate(log) if x[0] != "o") clocks = [x for x in log if x[0] != "o"] check(not any(x[5] for x in clocks) and all(x[1] == D for x in clocks), f"theta {th}: the first clock's holder lost the clock") stopped = not any(i >= 34 for i in opens) check(stopped == (th >= Fraction(D, 2)), f"theta {th}, D {D}") if stopped: check(all(i < first for i in opens), "an opening after the first clock on a stopped branch") else: check(opens[-1] >= len(log) - 4, "a climbing branch stalled") rows += 1 print(f" {str(th):6s} {D:9d} {str(stopped):7s} " f"{str(th >= Fraction(D, 2)):12s} {opens[-1] if opens else '-':>9} " f"{first:9d}") print(f" {rows} branch rows: the widening stops iff theta >= D/2 " f"(every degree supplied); on every one the first clock's " f"holder keeps the clock, every clock move of degree D") def main(): t0 = time.time() section_x() section_d() section_l() section_c() section_s() section_b() section_k() print(f"CHAIN: {TALLY['changes']} holder changes read, each checked " f"falling; {TALLY['clocks']} clock moves and " f"{TALLY['opens']} openings read") print(f"ALL CHECKS PASS: {CHECKS[0]} checks, {time.time() - t0:.1f} s") if __name__ == "__main__": main()