"""clock.py -- what one place charges a growth walk: the tick ladder of a place of a Dedekind ring with finite residue field, read as the orbit of one map, with one overshoot and one number beside it. QUESTION. A growth walk raising lambda pays, at a place P, the norm of the least climb in depth that raises lambda's p-part: N(P)^r at door r (module_law.py). The depths where that p-part jumps are the place's TICK LADDER. module_law.py proves the ladder's tail: past a threshold it steps by e in mixed characteristic, and it is the powers of p in equal characteristic. What is the WHOLE ladder, head included? Is it the orbit of the level map psi(i) = min(p i, i + e) from level 1, so that one map prices every tick a place ever charges, and if not, what else does a place hand the walk? THE OBJECTS. K is the completion of the ring at P, a complete discrete valuation field with residue field F_q, q = p^f, ramification index e over p (e is infinite in equal characteristic, where p = 0 in K), pi a uniformizer, U_i = 1 + pi^i O_K. E(a) is the exponent of U_1/U_a, a power of p, and lambda(P^a) = (q - 1) E(a) (module_law.py). The LADDER is the set of depths a >= 1 with E(a + 1) > E(a). The BEND is s = e/(p - 1). Write p = u pi^e with u a unit and u_bar its residue. psi(i) = min(p i, i + e) (p i when e is infinite); for i < s it is p i, for i > s it is i + e. THE ARGUMENT (written before the engine). (1) THE LEVEL STEP. Let z be in U_i but not U_(i+1), z = 1 + x, v(x) = i. In (1 + x)^p - 1 = p x + sum_(1 e + i, the term p x has valuation e + i and x^p has p i. So v(z^p - 1) = psi(i) WHENEVER i != s, and v(z^p - 1) >= p s = s + e when i = s (only possible when (p - 1) | e). At i = s write x = c pi^s + (deeper); the coefficient of pi^(ps) in z^p - 1 is c^p + u_bar c in F_q. The map c -> c^p + u_bar c is additive on F_q, with kernel of size 1 or p (the roots of c^(p-1) = -u_bar, with 0). A class at the bend overshoots iff its c is in the kernel. (2) A LEVEL-1 UNIT ATTAINS THE EXPONENT. U_1/U_a is an abelian p-group, so its exponent is the largest order of an element. If y has the largest order p^k and v(y - 1) > 1, take any z with v(z - 1) = 1: if z's order is below p^k then z y has order p^k and v(z y - 1) = 1. So E(a) = max over units z with v(z - 1) = 1 of the order of z in U_1/U_a, which is p^(k_z(a)) with k_z(a) = least k having t_k(z) >= a, t_k(z) = v(z^(p^k) - 1). (3) THE TRAJECTORY OF A LEVEL-1 UNIT. t_0 = 1 and, by (1), t_(k+1) = psi(t_k) at every k with t_k != s. The orbit of 1 below the bend is 1, p, p^2, ..., so the trajectory meets the bend iff s = p^n for some n >= 0, i.e. e = (p - 1) p^n. Otherwise every level-1 unit has the one trajectory psi^k(1), k(a) is the least k with psi^k(1) >= a, and E(a + 1) > E(a) iff a is on the orbit: THE LADDER IS THE ORBIT OF 1 UNDER psi. When s = p^n every level-1 unit reaches the bend at step n, with bend coefficient c^(p^n), c its level-1 coefficient; as c runs over F_q^x so does c^(p^n). Put A = the least t_(n+1)(z) over level-1 units z, the ARRIVAL, and w = A - s - e >= 0, the WIDTH. Past the bend every step is + e exactly, so the slowest level-1 unit is one attaining A (trajectories past the bend never cross: they add e each step), and THE LADDER IS 1, p, ..., p^n, A, A + e, A + 2e, ... . (4) THE HEAD CRITERION. w >= 1 iff EVERY bend coefficient c^(p^n), c != 0, lies in the kernel of (1), i.e. the kernel is all of F_q, which needs q - 1 <= p - 1, so f = 1, and then c^p = c on F_p makes the map c (1 + u_bar), zero iff u_bar = -1. So: w >= 1 iff f = 1, e = (p - 1) p^n, and u_bar = -1. Given (p - 1) | e, the third clause is the statement that -u_bar is a (p - 1)-th power in F_p, which is mu_p inside K (K contains mu_p iff it contains a (p - 1)-th root of -p, since Q_p(zeta_p) = Q_p((-p)^(1/(p - 1))), and a unit is a (p - 1)-th power iff its residue is, p - 1 being prime to p). Its e are the ramification indices of Q_p(zeta_(p^(n+1))). (5) THE TWO NUMBERS. The gap at a landing depth a (one past a ladder member) is next(a) + 1 - a with next(a) the least member >= a. Along the ladder the gaps are p^j (p - 1) below the bend, each less than e; at most e at the step crossing it; e + w at the one splice p^n -> A; e forever after. So the sup of the gaps a walk can land on is e + w, the tail gap is e, and nothing else of the ladder varies: a place hands the walk (p, e, f) and the one number w. In equal characteristic e is infinite and psi(i) = p i: the orbit is the powers of p, module_law.py's log clock, and there is no bend. Tier, if the engine agrees: (1)-(3) and (5) are a theorem, (4) a criterion; w's VALUES are observations per place. DESIGN. Standard library only; one process. The local rings are module_law.py's (O_K = Z_p[x]/(g), g Eisenstein or irreducible mod p; E by the generators 1 + (a residue lift) pi^i, controlled there against the whole group). For an Eisenstein g = x^n + ... + c_0, pi^n = -c_0 (1 + ...), so u_bar = -(c_0/p)^(-1) mod p and u_bar = -1 iff c_0/p = 1 mod p; at Z_p (unramified, n = 1) u_bar = 1. C POSITIVE CONTROL, before any verdict: (a) at every place and every a with q^(a-1) <= 20,000, E(a) by generators against the whole of U_1/U_a; (b) at the same (place, a), (2)'s claim: the largest order among units with v(z - 1) = 1 equals E(a). L THE LADDER at each place to depth D = ceil(s) + 5e + 8 (D >= 12): the measured ladder against (3)'s prediction. Where s is not a p-power, the ladder must equal psi's orbit of 1 below D. Where s = p^n, the ladder must begin 1, p, ..., p^n, its next member A is READ, and every later member below D must be A + je. H THE HEAD: w = A - s - e >= 1 exactly at the places the criterion of (4) names, and w = 0 at every other place with s = p^n. W THE WIDTH VALUES, printed per place. Q EQUAL CHARACTERISTIC: F_2, F_3, F_4, F_9 [[t]] ladders to depth 40 are the powers of p (the orbit of psi with e infinite). The places, g low degree first (32 of them): p = 2: Z_2; unramified of degree 2 and 3; x^2 + 2, x^2 - 2, x^2 - 2x + 2 (Q_2(i), i = sqrt -1 in a field's name), x^2 - 2x + 6 (Q_2(sqrt -5)), x^2 + 2x - 2 (Q_2(sqrt 3), the field of sqrt -5 again, since -15 is a square in Q_2), x^2 - 10, x^2 + 10, x^3 + 2, x^4 - 2, x^4 + 2, x^6 - 2, x^8 - 2; with x^2 + 2, x^2 - 2 and Q_2(i) these are all six ramified quadratic fields over Q_2; p = 3: Z_3; unramified of degree 2; x^2 + 3, x^2 - 3, x^2 - 6, x^3 + 3, x^4 - 3, x^6 - 3, x^6 + 3; p = 5: Z_5; x^2 + 5, x^4 + 5, x^4 - 5, x^4 + 10; p = 7: x^2 + 7, x^6 + 7, x^6 - 7. PREDICTIONS, fixed before the run. C (a) and (b) hold at every tested (place, a). L every ladder is (3)'s shape to depth D at all 32 places. H heads (w >= 1) at exactly: Z_2, the ten Eisenstein places over 2 with e in {2, 4, 8}, x^2 + 3, x^2 - 6, x^6 + 3, x^4 + 5, x^6 + 7 (16 places). The bend is a p-power and there is no head at: the unramified places over 2 (f >= 2, s = 1), x^6 - 3, x^4 - 5, x^4 + 10, x^6 - 7, x^2 - 3. W TRANSPLANTED from the records this script replaces: w = 1 at Z_2, x^2 + 2, x^2 - 2 and x^2 + 3; 2 at Q_2(sqrt -5) and x^4 - 2; 3 at Q_2(i); 4 at x^8 - 2. Q_2(sqrt 3): 2, since K(i)/K is unramified there and at e = 2 over Q_2 the width is 1, 2, 3 as K(i)/K is ramified, unramified or split (also a transplant); by the same rule 1 at x^2 - 10 and x^2 + 10, where K(i) = K(sqrt -d) is ramified. x^2 - 6 at 3 is the field of x^2 + 3, so 1. The rest are read. Q the powers of p, at all four. KILLS, as printed observables: any C line off (the instrument fails); any place whose measured ladder parts from (3)'s shape below D, or any place with w >= 1 outside (4)'s list or w = 0 inside it (the argument fails). A width value off its transplant is a finding to read, never a kill: the argument does not fix w. FINDINGS. Every prediction landed: 40/40 checks PASS, no kill fired. C generators against the whole group at 346 (place, a), 0 off; a unit of level exactly 1 attains E(a) at the same 346, 0 off; the 32 at a = 1, one per place, hold trivially (U_1/U_1 is trivial). L all 32 ladders have the argument's shape to depth D (14 to 56). Where s is not a p-power the ladder is psi's orbit: 1, 2, 4, 7, 10, ... at x^3 + 2; 1, 2, 4, 8, 14, 20, ... at x^6 - 2, where psi(4) = 8 is still the multiplying branch and the next step is + 6. Where s = p^n it is 1, ..., p^n, A, A + e, ...: 1, 2, 7, 9, ... at Q_2(i); 1, 2, 4, 8, 20, 28, ... at x^8 - 2; 1, 3, 12, 18, ... at x^6 + 3. H heads at exactly the sixteen places of the criterion; the bend a p-power and no head at the seven others: both unramified places over 2 (f = 2, 3), x^2 - 3, x^6 - 3, x^4 - 5, x^4 + 10, x^6 - 7. W w = 1 at Z_2, x^2 + 2, x^2 - 2, x^2 - 10, x^2 + 10, x^2 + 3, x^2 - 6, x^4 + 5, x^6 + 7; 2 at Q_2(sqrt -5), Q_2(sqrt 3), x^4 - 2, x^4 + 2; 3 at Q_2(i) and x^6 + 3; 4 at x^8 - 2. Every transplant landed; Q_2(sqrt 3) and Q_2(sqrt -5), one field under two polynomials, agree. Over the six ramified quadratic fields of Q_2 the width is 1, 2, 3 as K(i)/K is ramified (four fields), unramified (sqrt -5) or trivial (Q_2(i)). Q the ladder is 1, 2, 4, 8, 16, 32 over F_2 and F_4, and 1, 3, 9, 27 over F_3 and F_9. Tiers: the ladder theorem (1)-(3) and the two numbers (5) are a theorem, the head criterion (4) a criterion, their proofs the argument above; the widths are observations per place, and at e = 2 over Q_2 a rule, exhaustive over the six fields (since proved at every head: tame.py at odd p, wild.py at 2 for e >= 2). RUN RECORD. 40/40, 25.3 s wall, 9.0 MB peak commit under a memory guard. After the run the Kummer level e/(p - 1) was renamed the BEND, the least level p-th powers of level-1 units reach past it the ARRIVAL A, and the exponent of the bend n, to keep seat, L and T free for the seated places, the invariant lambda and the tick; the rerun printed the same 40/40 and no number moved. """ from math import ceil from module_law import Local, LocalEq, check, section, CHECKS LIMIT = 20000 PLACES = [ Local(2, [0, 1], "unr", "Z_2"), Local(2, [1, 1, 1], "unr", "unramified f=2 at 2"), Local(2, [1, 1, 0, 1], "unr", "unramified f=3 at 2"), Local(2, [2, 0, 1], "eis", "x^2 + 2"), Local(2, [-2, 0, 1], "eis", "x^2 - 2"), Local(2, [2, -2, 1], "eis", "Q_2(i)"), Local(2, [6, -2, 1], "eis", "Q_2(sqrt -5)"), Local(2, [-2, 2, 1], "eis", "Q_2(sqrt 3)"), Local(2, [-10, 0, 1], "eis", "x^2 - 10"), Local(2, [10, 0, 1], "eis", "x^2 + 10"), Local(2, [2, 0, 0, 1], "eis", "x^3 + 2"), Local(2, [-2, 0, 0, 0, 1], "eis", "x^4 - 2"), Local(2, [2, 0, 0, 0, 1], "eis", "x^4 + 2"), Local(2, [-2, 0, 0, 0, 0, 0, 1], "eis", "x^6 - 2"), Local(2, [-2] + [0] * 7 + [1], "eis", "x^8 - 2"), Local(3, [0, 1], "unr", "Z_3"), Local(3, [1, 0, 1], "unr", "unramified f=2 at 3"), Local(3, [3, 0, 1], "eis", "x^2 + 3"), Local(3, [-3, 0, 1], "eis", "x^2 - 3"), Local(3, [-6, 0, 1], "eis", "x^2 - 6"), Local(3, [3, 0, 0, 1], "eis", "x^3 + 3"), Local(3, [-3, 0, 0, 0, 1], "eis", "x^4 - 3"), Local(3, [-3, 0, 0, 0, 0, 0, 1], "eis", "x^6 - 3"), Local(3, [3, 0, 0, 0, 0, 0, 1], "eis", "x^6 + 3"), Local(5, [0, 1], "unr", "Z_5"), Local(5, [5, 0, 1], "eis", "x^2 + 5"), Local(5, [5, 0, 0, 0, 1], "eis", "x^4 + 5"), Local(5, [-5, 0, 0, 0, 1], "eis", "x^4 - 5"), Local(5, [10, 0, 0, 0, 1], "eis", "x^4 + 10"), Local(7, [7, 0, 1], "eis", "x^2 + 7"), Local(7, [7, 0, 0, 0, 0, 0, 1], "eis", "x^6 + 7"), Local(7, [-7, 0, 0, 0, 0, 0, 1], "eis", "x^6 - 7"), ] EQUAL = [ LocalEq(2, [0, 1], "F_2[[t]]"), LocalEq(3, [0, 1], "F_3[[t]]"), LocalEq(2, [1, 1, 1], "F_4[[t]]"), LocalEq(3, [1, 0, 1], "F_9[[t]]"), ] HEADS = {"Z_2", "x^2 + 2", "x^2 - 2", "Q_2(i)", "Q_2(sqrt -5)", "Q_2(sqrt 3)", "x^2 - 10", "x^2 + 10", "x^4 - 2", "x^4 + 2", "x^8 - 2", "x^2 + 3", "x^2 - 6", "x^6 + 3", "x^4 + 5", "x^6 + 7"} WIDTH = {"Z_2": 1, "x^2 + 2": 1, "x^2 - 2": 1, "x^2 + 3": 1, "Q_2(sqrt -5)": 2, "x^4 - 2": 2, "Q_2(i)": 3, "x^8 - 2": 4, "Q_2(sqrt 3)": 2, "x^2 - 6": 1, "x^2 - 10": 1, "x^2 + 10": 1} def bend_power(loc): """n with e = (p - 1) p^n, or None.""" e, p = loc.e, loc.p if e % (p - 1): return None s, n = e // (p - 1), 0 while s % p == 0: s //= p n += 1 return n if s == 1 else None def u_bar_is_minus_one(loc): if loc.kind == "unr": return loc.p == 2 return (loc.g[0] // loc.p) % loc.p == 1 def criterion(loc): return (loc.f == 1 and bend_power(loc) is not None and u_bar_is_minus_one(loc)) def psi(loc, i): return min(loc.p * i, i + loc.e) def depth(loc): return max(12, -(-loc.e // (loc.p - 1)) + 5 * loc.e + 8) def ladder(loc, D): E = [None] + [loc.E_gen(a) for a in range(1, D + 2)] return [a for a in range(1, D + 1) if E[a + 1] > E[a]] def orbit(loc, D): out, i = [], 1 while i <= D: out.append(i) i = psi(loc, i) return out def section_control(): section("C POSITIVE CONTROL: generators, the whole group, level 1") tested = bad_a = bad_b = 0 for loc in PLACES: a = 1 while loc.q ** (a - 1) <= LIMIT: tested += 1 full = loc.E_full(a) bad_a += full != loc.E_gen(a) N = loc.prec(a) lvl1 = [z for z in loc.reps(a, False) if loc.val([z[0] - 1] + z[1:], N) == 1] best = max(loc.order_exp(z, a, N) for z in lvl1) if lvl1 else 0 bad_b += loc.p ** best != full a += 1 check("C(a) E(a) by generators = E(a) over the whole of U_1/U_a", bad_a == 0, f"{tested} (place, a), {bad_a} off") check("C(b) a unit of level exactly 1 attains E(a)", bad_b == 0, f"{tested} (place, a), {bad_b} off") def section_ladder(): section("L THE LADDER: psi's orbit of 1, one overshoot at the bend") rows = {} for loc in PLACES: D = depth(loc) lad = ladder(loc, D) n = bend_power(loc) if n is None: ok, w = lad == orbit(loc, D), None else: s = loc.e // (loc.p - 1) head = [loc.p ** j for j in range(n + 1)] ok = lad[:n + 1] == head and len(lad) > n + 1 if ok: A = lad[n + 1] w = A - s - loc.e ok = w >= 0 and lad[n + 1:] == list(range(A, D + 1, loc.e)) else: w = None rows[loc.name] = (ok, n, w) print(f" {loc.name:20s} p={loc.p} e={loc.e} f={loc.f} " f"n={n} D={D} w={w} ladder {lad[:9]}" f"{' ...' if len(lad) > 9 else ''}") check(f"L {loc.name}: the ladder has (3)'s shape to depth {D}", ok) return rows def section_head(rows): section("H THE HEAD CRITERION: w >= 1 iff f = 1, e = (p-1)p^n, " "u_bar = -1") got = {n for n, (ok, _, w) in rows.items() if w} by_crit = {loc.name for loc in PLACES if criterion(loc)} zero = sorted(n for n, (ok, _, w) in rows.items() if w == 0) print(f" heads measured: {len(got)}; by the criterion: {len(by_crit)}") print(f" bend a p-power, no head: {zero}") check("H the measured heads are exactly the criterion's places", got == by_crit, f"off: {sorted(got ^ by_crit)}") check("H the criterion's places are the slate's sixteen", by_crit == HEADS, f"off: {sorted(by_crit ^ HEADS)}") def section_width(rows): section("W THE WIDTH VALUES") for n, (ok, _, w) in rows.items(): if w: note = WIDTH.get(n) print(f" {n:20s} w = {w}" + ("" if note is None else f" (transplant {note}{'' if note == w else ' OFF'})")) off = {n: rows[n][2] for n in WIDTH if rows[n][2] != WIDTH[n]} print(f" widths off their transplant: {off}") def section_equal(): section("Q EQUAL CHARACTERISTIC: the orbit of p i") for loc in EQUAL: E = [None] + [loc.E_gen(a) for a in range(1, 42)] lad = [a for a in range(1, 41) if E[a + 1] > E[a]] pw = [loc.p ** j for j in range(8) if loc.p ** j <= 40] print(f" {loc.name:9s} ladder {lad}") check(f"Q {loc.name}: the ladder is the powers of p to 40", lad == pw) def main(): section_control() if not all(CHECKS): print(" control failed: run stopped") raise SystemExit(1) rows = section_ladder() section_head(rows) section_width(rows) section_equal() print() print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed") raise SystemExit(0 if all(CHECKS) else 1) if __name__ == "__main__": main()