cascade.py
Checks: CASCADE: The escape is a conjunction theorem; observation; CASCADE: The budget inequality theorem; rule; CASCADE: The characteristic sweep rule; CASCADE: Dead levels recur at eleven characteristics rule; CASCADE: The residual is inhabited at every bound theorem; CASCADE: The shape of a dead level theorem; rule; CASCADE: A dead level past 0 at odd p is a full-price opening over Z criterion; rule; GROWTH: The lock-prime law theorem; rule.
To run it: save cascade.py, with growth.py beside it; standard library only.
"""cascade.py -- whether the greedy walk over a number ring must lock:
the escape as a conjunction of carrier ladders, the budget that pins
each ladder's ceiling, where the ladders die, and why a small-prime
sieve's expected count does not see the level they die at.
QUESTION. module_law.py proves that in the ideal world of a ring of
integers O a greedy trajectory LOCKS (every later pick deepens one
place) iff its costs are bounded infinitely often. Whether costs can
diverge is left open there. This script asks what a divergent
trajectory would need, shows that the need is a conjunction over the
ring's rank-1 characteristics of one arithmetic ladder each, walks
that ladder at every odd characteristic below 1000, asks where the
walk's death holds for every seed and not only for a walk starting
low, and names the one question a proof that every ladder dies must
answer. It then asks whether the ladder's death is the same event as
the fourth kind of least move over Z, the opening at full price
(growth.py, section C).
THE OBJECT. The setting is module_law.py's: O a ring of integers, a
state an ideal M, L = lambda(M), a move an ideal priced by its norm,
the greedy move the least-norm move raising L. A RANK-1 place is a
place P over p with e = f = 1, so N(P) = p and the completion is Z_p;
p is then a RANK-1 CHARACTERISTIC of O. Fix one. The LEVEL of a state
at p is V = v_p(L). A CARRIER at level V is a place H not over p with
p^(V+1) | N(H) - 1: opening H lifts v_p(L) past V. The CARRIER LADDER
at p is the sequence of levels a trajectory climbs. The level's
CANDIDATES are the numbers n = m p^(V+1) + 1 with 1 <= m <= p - 1 at
odd p (at p = 2 the three of (3)); a level is DEAD when no candidate is
a prime power (no ring has a carrier the walk can open there, see (3)),
and the walk from level 1 stops at its first dead level, D(p). Below,
a carrier means one the walk can open, and the word also names its
norm, a prime-power candidate (as in proper_carriers, prime_carrier).
THE ARGUMENT (written before the engine).
(1) THE CONJUNCTION. Let P be rank-1 over p, at depth a in M. Since
lambda(P^b) = (p - 1) p^(b - 1) for odd p, the move P^(V + 2 - a)
raises L whatever the rest of the state, at norm p^(V + 2 - a)
<= p^(V + 2); at p = 2, where lambda(2^b) = 2^(b - 2) for
b >= 3, the bound is 2^(V + 3). The greedy move costs no more.
So if costs diverge, V diverges, and it does so at EVERY rank-1
characteristic of O at once: each bounds the cost on its own at
every step, and a divergent trajectory must defeat all of them.
One ladder dying infinitely often closes the ring.
(2) THE RISES RUN THROUGH CARRIERS. A rise of v_p(L) is a pick at a
place over p or an opening of a carrier (deepening a place H not
over p adds only powers of H's own characteristic to its column,
whose p-part is v_p(N(H) - 1) from the opening on). Let a rise
run through a place P' over p, past the pump's start
(module_law.py's h*, (4), from which E(a + e) = p E(a)). After
it P' OWNS v_p(L), so its next door is exactly e deep, at price
p^(ef) (module_law.py (6)), and the next move costs at most that.
Infinitely many such rises bound the costs infinitely often. So
along a divergent trajectory all but finitely many rises are
carrier openings.
(3) THE BUDGET PINS THE CEILING. A carrier opening the walk makes is a
least move, so
N(H) <= p^(V + 2 - a) <= p^(V + 2), and N(H), a power of a prime
other than p, cannot equal it: N(H) = m p^(V + 1) + 1 with
1 <= m <= p - 1, the rise is exactly one level (N(H) - 1 <
p^(V + 2)), and the supply at level V is those p - 1 numbers
that are prime powers. No ring does better, since a norm is a
prime power. At p = 2 the ceiling is 2^(V + 3), the candidates are
2^(V+1) + 1, 2^(V+2) + 1 and 3 2^(V+1) + 1, and the middle one
rises TWO levels; a prime power of the form 2^k + 1 is a Fermat
prime or 9 (Mihailescu), so the double rise is rationed by the
Fermat primes. A carrier never steps over a dead level (at odd p
it rises one level; at p = 2 the double rise from level V runs
through 2^(V+2) + 1, the first candidate of level V + 1 itself),
so a
divergent trajectory crosses a dead level only through a place
over p, which by (2) makes the next move cost at most p^(ef).
A divergent trajectory has finitely many moves that cheap, so it
crosses finitely many dead levels: INFINITELY MANY dead levels
at one rank-1 characteristic block every trajectory, and by
module_law.py (6) every trajectory of that ring locks. A single
dead level blocks nothing.
(4) THE ELEMENT WORLD. If P = (pi) is principal, pi^(V + 2 - a)
(pi^(V + 3 - a) at p = 2) is an element and (1) holds verbatim;
in (2) the move deepening P' by e, padded by an ideal in the
inverse class of P'^e, raises L at norm at most p^(ef) times the
least norm in that class, still bounded; in (3) a raising element
of norm below p^(V + 2) (2^(V + 3) at 2) can hold only one
carrier (each carrier's norm exceeds p^(V + 1), so two cost more
than p^(2V + 2), at least the ceiling except at p = 2, V = 0, where
two odd norms cost at least 9 > 8), so the ladder is the ideal
world's. An element walk whose costs diverge
therefore climbs the ideal world's ladder at every PRINCIPAL
rank-1 characteristic. At a non-principal rank-1 place the door's
price is padded by the least norm in a class, whose largest value over
the classes is tau_K; over an imaginary quadratic field the
classes are the reduced forms (a, b, c) of discriminant disc and
the least norm in a class is a, so tau_K = max a <= sqrt(|disc|/3),
and tau_K = 1 exactly when the class number is 1. Whether an
element walk with bounded costs locks is not settled here.
(5) THE RESIDUAL. A ring with a rank-1 characteristic carrying
infinitely many dead levels is closed for every seed. The ring
Q(sqrt(2 3 5 ... P)) ramifies every prime <= P, so its least
rank-1 characteristic exceeds P: no finite sweep of
characteristics closes every ring. What suffices is weaker than
"every ladder has infinitely many dead levels": the rank-1
characteristics of a degree-n field have density at least 1/n
(Chebotarev; the Frobenius fixes a root with probability at least
1/n), so if the characteristics with finitely many dead levels
have density zero, every ring is closed.
(6) THE EXPONENT IDENTITY. Let n = r^s be a candidate at level V >= 1
of an odd p, s >= 2 (a PROPER power; r != p since n = 1 mod p).
Put d = ord of r mod p^(V+1), so d | s; write s = d t. Then
r^d >= p^(V+1) + 1 and n > p^((V+1)t), so t < 1 + 1/(V+1) and
t = 1: s is the order. If p | s, r^(s/p) = 1 mod p^V, so
n >= (p^V + 1)^p > p^(V+2), too big; so s | p - 1. Since
p^(V+1) divides (r^s - 1)/(r - 1) (r = 1 mod p would make p
divide s), r^s > p^(V+1)(r - 1), and with r^s < p^(V+2) this
gives r < p + 1, so r < p and s >= V + 2. A proper power carrier
thus has r < p, s | p - 1, s >= V + 2: none at V >= p - 2, and
finitely many below, found by enumeration. Every other carrier
is a PRIME = 1 mod p^(V+1) below p^(V+2), a question about primes
in a progression below p times its modulus.
(7) THE SIEVE'S EXPECTED COUNT DOES NOT SEE THE LEVEL. A prime q != p divides
m p^(V+1) + 1 for exactly one class of m mod q, m = -p^(-V-1).
So the count of even m <= p - 1 whose candidate has no prime
factor below z is about ((p - 1)/2) prod (1 - 1/q) over odd q < z,
with no V in it, while a prime-count model makes the carriers
thin like 1/(V + 2). A covering congruence acts through the same
classes, so it closes a level only by an alignment of its classes
at that level; and since the class q kills at level V is periodic
in V with period ord_q(p), a covering found at one level recurs
every lcm of the orders, which is how dead levels are proved to
recur.
(8) A DEAD LEVEL PAST 0 IS A FULL-PRICE OPENING OVER Z. Over Z, an
opening at full price at odd p is the least move with p coprime
to M, p | L and (p - 1) | L, at p^(V + 2) (growth.py (8)). It is
the least move from SOME state iff no prime = 1 mod p^(V+1) lies
below p^(V+2). Only if: such a prime r divides M (then p^(V+1)
divides L) or is open at its own door 1, price r, since
(r - 1) does not divide L. If: let B be the lcm of u - 1 over the
primes u < p^(V+2), u != p, of p - 1, and of s^(c_s) over s <
p^(V+2), s != p, c_s least with s^(c_s + 2) > p^(V+2) (for s = 2, with
2^(c + 3) > p^(V+2)), its p-part set to p^V (every u - 1 has
v_p <= V by the hypothesis); take a prime S = 1 mod B with
v_p(S - 1) = V exactly (Dirichlet, any class 1 + k B mod p B
with p not dividing k). The seed S has L = S - 1: every prime u
below p^(V+2) other than p is
either shut ((u - 1) | L, its least move u^(v_u(L)+2) above the price) or
absent, and S's own least move costs S > B. So the least move is p at
p^(V + 2), at full price. Level V being dead at odd p and the
full-price opening over Z at level V read one predicate, "no
prime = 1 mod p^(V+1) below p^(V+2)", and differ only at a level
holding a proper power candidate of (6) and no prime one.
DESIGN. Standard library only; one process. growth.py's door menu is
imported for the full-price specimen.
C POSITIVE CONTROLS, before any verdict; a failed control stops
the run. C1 the supply: for p in
3, 5, 7, 11 and every level with p^(V+2) <= 2 10^6, the numbers
n < p^(V+2) with v_p(n - 1) > V, by a scan, against
{m p^(V+1) + 1 : 1 <= m <= p - 1}. C2 the primality test (Miller-
Rabin at the primes to 41, deterministic below 3.3 10^24 (J.
Sorenson and J. Webster, Strong pseudoprimes to twelve prime
bases, Math. Comp. 86, 2017); above it
a COMPOSITE verdict is a proof and a PRIME verdict can only
lengthen a ladder, the safe direction for a death) against trial
division below 20,000. C3 the confinement (6) as an enumeration
(r < p prime, s | p - 1, s >= 2) against a brute exact-root test
of every candidate at every level 1 <= V <= p + 2, odd p < 50,
the levels from p - 2 on holding none. C4 the recorded walks: at
2 the walk banking the most (the double rise first) climbs
through 9, 17, 97, 193, 257 and the least-norm walk through 5, 9,
17, 97, 193, 257, both dying at 8; 3 dies at 2; 5 at 3.
R tau_K over the imaginary quadratic fields of fundamental
discriminant down to -1000: their count, and class numbers 1 and
2 against the nine Heegner discriminants and the eighteen of
Baker and Stark (A. Baker, Imaginary quadratic fields with class
number 2, Annals of Math. 94, 1971; H. M. Stark, On complex
quadratic fields with class-number two, Math. Comp. 29, 1975);
tau_K against the bound
sqrt(|D|/3) and the Minkowski bound (2/pi) sqrt(|D|), a print, the
reduced forms stopping at 3a^2 <= |D| and the one form with a = 1
making tau_K = 1 iff h = 1; at D = -23 the principal form
x^2 + xy + 6y^2 missing 2 and 3.
B the budget: the double-rise supply 2^k + 1, k <= 300, prime
powers exactly 3, 5, 9, 17, 257, 65537.
S the sweep: D(p) at every odd p < 1000, levels to 120; the count of
accepted odd-m carriers.
K recurrence: at p = 2, 3, 5 the walk from every start V0 = 1..300;
the covering search at every odd p < 1000 (primes q < 2000 whose
order of p divides 5040); every level the covering found kills
(its one class mod L) from p - 2 to 200 certified dead, and p = 2's levels 10 <= V <= 400 with
V + 1 = 3 mod 8, the covering built by hand: there 3 divides
2^(V+1) + 1, 17 divides 2^(V+2) + 1 and 5 divides 3 2^(V+1) + 1,
none of them a power of its divisor past V = 2.
Q the residual, a print: the least rank-1 characteristic of
Q(sqrt(2 3 ... P)) for every odd prime P <= 97, above P since
every prime to P ramifies.
X the shape: the proper power carriers at every level of every odd
p < 1000 by the enumeration (6) licenses, its order clause read;
the pooled contrast over the primes with D(p) >= 10, levels 1 to
10, of carrier density (per p - 1) against sifted density (even
m, no prime factor below 10^4, per floor((p - 1)/2)); sifting
below 10^4 at every dead level D(p), p >= 100.
W the weld: at every level of every odd p < 1000 where the two can
differ, "no prime carrier" against "dead"; the construction of (8)
at p = 3, V = 2, its least prime, and growth.py's menu at that seed.
That no dead level D(p) holds a prime carrier prints, D(p) being
defined so.
PREDICTIONS, fixed before the run (the count figures are those of the
scripts this one replaces; the argument says why the laws should hold).
C1-C3 exact agreement everywhere; C4 as recorded.
R 305 fields; tau_K = 1 iff h = 1; tau_K <= sqrt(|D|/3) and <= the
Minkowski bound everywhere; D = -23: h = 3, tau_K = 2, Minkowski
3.05, no element of norm 2 or 3.
B exactly the six.
S all 167 odd p < 1000 die at or below level 120; D(19) = D(23) = 1,
D(17) = 2, D(29) = 8, D(101) = 10, D(151) = 12, D(751) = 33,
D(997) = 45, the largest D(719) = 62; no accepted odd-m carrier.
K every start dies, within 8 levels at 2, 4 at 3, 3 at 5; coverings
at exactly 3, 5, 7, 11, 13, 17, 19, 23, 31, 37; every level a
covering kills dead.
Q L > P at every P.
X the only proper power carrier at any level V >= 1 of any odd
p < 1000 is 3^5 = 243 = 2 11^2 + 1 at (11, 1) (a TRANSPLANT above
the dead levels: the replaced count stopped at D(p)); carrier
density falls by a ratio near 1/4 from level 1 to 10 while the
sifted density moves by a ratio within 5% of 1, near
2 e^(-gamma)/ln 10^4 = 0.1219; sifting empties the dead level
printed as D(p) at no p >= 100.
W the two predicates agree at every level (the level (11, 1) also
holds the prime 727); the construction's least prime is
961440481, and growth.py's menu opens 3 there at 81, full price.
A KILL is any disagreement in C, a characteristic in S alive at level
120, a start in K whose walk has not died by level 400, a proper power
carrier breaking (6)'s confinement, or a level in W where the two
predicates differ with no proper power carrier to explain it. A count
figure off its prediction is a finding to read. (Ruled on a code read:
R1's bounds and its iff, Q and W's dead levels hold by construction
and print, S's odd-m count is zero by X1's enumeration; X1 searches inside (6)'s confinement, so its
kill cannot fire; W1 reads the one level where the predicates can
differ, so W's kill cannot fire; C1 compares two inline
comprehensions, an identity; C4's walk at 2 banks the most, and the least-norm walk is
recorded beside it.)
FINDINGS. Every prediction landed: 17/17 checks PASS.
C the supply equals the scan at 27 (p, V); Miller-Rabin agrees with
trial division below 20,000; the confinement enumeration equals
the exact-root test on all 10,760 candidates of every level
1 <= V <= p + 2 at every odd p < 50, the one proper power being
3^5 at (11, 1); at 2 the walk banking the most climbs through 9,
17, 97, 193, 257 (standing at levels 1, 3, 4, 5, 6) and the
least-norm walk through 5, 9, 17, 97, 193, 257, both dying at 8;
3 dies at 2, 5 at 3.
R 305 fields; class number 1 exactly at the nine Heegner
discriminants, tau_K = 1 there only, and 2 exactly at the eighteen
of Baker and Stark; tau_K <= sqrt(|D|/3) and
below the Minkowski bound everywhere (by the forms), mean tau_K
9.58, tau_K <= 4 at 11.8% of fields, mean tau_K / Minkowski 0.705;
tau_K is unbounded over the fields by the count of reduced forms
and the class numbers' growth (Heilbronn), never by this mean.
D = -23: h = 3, tau_K = 2 against a Minkowski bound of 3.053.
B 2^k + 1 is a prime power for k <= 300 exactly at 3, 5, 9, 17, 257,
65537.
S all 167 odd p < 1000 die, the dead level erratic: D(19) = D(23) =
1, D(17) = 2 beside D(29) = 8, D(101) = 10, D(151) = 12,
D(751) = 33 beside the largest, D(719) = 62, and D(997) = 45,
each an upper bound once its ladder passes 3.3 10^24, where a
prime verdict is probable only. No odd multiplier is accepted
at any level to D(p), nor at any level by (6), X1's enumeration
holding no power of 2, so the working set is the
floor((p - 1)/2) even ones.
K every start V0 <= 300 dies, the longest spanning 8 levels at 2,
4 at 3 and 3 at 5, the start's included. The covering search
finds coverings at exactly 3, 5, 7, 11, 13, 17, 19, 23, 31 and
37 (the first found at 3 is
V + 1 = 1 mod 6 by 7; at 37 nine primes up to 67, period 1680;
at 13, 17, 31 and 37 the first killed level from p - 2 is past
200), and the 109 levels a covering kills, p = 2's class included, are
all dead.
Q the least rank-1 characteristic of Q(sqrt(2 3 ... P)) exceeds P
at every odd P <= 97: 103 at P = 97.
X across every level V >= 1 of every odd p < 1000, above the dead
levels too, the one proper power carrier is 3^5 = 2 11^2 + 1 at
(11, 1), inside the confinement. Pooled over the 144 primes with
D(p) >= 10, carrier density falls 0.05792 to 0.01418 from level 1
to 10 (ratio 0.245 against the model's 1/4) while sifted density
moves 0.11952 to 0.12250 (ratio 1.025), every level within 0.004
of 2 e^(-gamma)/ln 10^4 = 0.1219. Pooling on D(p) >= 10 (a carrier
at every level from 1 to 9) selects on the ratio's level-1
denominator and not on its level-10 count, its effect not
measured. The pooled p from 113 on, 136 of the 144, have a
level-10 candidate past 3.3 10^24, where a prime verdict is
probable. Sifting below 10^4 empties the dead level printed as
D(p) at no p >= 100.
W "no prime carrier" and "dead" agree at the one level of an odd
p < 1000 where they can differ, (11, 1), the one level with a
proper power carrier, which also holds the prime 727; elsewhere
they agree by (6). Every dead level is therefore a full-price
opening over Z by (8); the witnesses outside its hypothesis,
(3, 1), (5, 1) and (7, 1), hold the primes 19, 101 and 197. The
construction of (8) at p = 3, V = 2 gives B = 480720240, its
least prime P = 961440481, and growth.py's menu opens 3 there at
81, full price.
Tiers: (1)-(3) and the element world (4) are theorems, the recorded
walks (C4) a rule: at 3 and 5 exhaustive to their dead levels, at 2
the two walks recorded, each through 257 to level 8; the residual (5)
and its density-zero sufficiency are theorems, the latter from
Chebotarev's density theorem; the exponent identity (6) and the
one-class count (7) are theorems; (8) is a criterion, proved both
ways. The sweep and the recurrence are rules verified in the ranges
printed; so is the weld's agreement, (6) and the enumeration it
licenses leaving one level where it can fail, read there. A single
dead level D(p) closes nothing: the sweep is evidence about ladders,
and the coverings, recurring, are what close. Whether every odd p
has infinitely many dead levels is not decided here: it asks for a
prime = 1 mod p^(V+1) below p^(V+2) to fail to exist infinitely
often; a sieve's expected count has no V in it, and the search found
coverings at ten odd p below 1000 only, 2's being built by hand.
RUN RECORD. 20/20, 15.0 s wall, 9.9 MB peak commit under a memory guard. The
first run was killed at its 600 s timeout inside C3: the exact-root
test seeded Newton's method with a float root and stepped up one at a
time to pass it, which a 53-bit float leaves astronomically far to go
at 250-bit candidates. Seeded just above the float root instead, the
control runs in about a second. (3) first said a dead level at or
above a trajectory's level stops it, forgetting that deepening a place
over p crosses it; corrected in review. A code read then made the
checks that held by construction prints (R1's bounds, Q1, S3, W3),
rebuilt R1 against the known class numbers 1 and 2, widened C3 past p - 2,
recorded the least-norm walk at 2 beside the one banking the most, and
made the controls stop the run: 17/17, 15.9 s, 9.7 MB. A later read
added prints for the first killed level from p - 2 at each covering and
for the three witnesses of (8), and named S's odd-m count by its range.
A third read made K3's label the covering found (one class mod L, not
every covering), cited module_law's h* and (6) for argument (2), and
printed the levels the walk at 2 stands at: 17/17, 16.0 s, 10.0 MB.
"""
import os
import sys
import time
from math import gcd, isqrt, log, pi, sqrt, exp
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
CHECKS = []
def check(name, ok, detail=""):
CHECKS.append(bool(ok))
print(f" [{'PASS' if ok else 'FAIL'}] {name}"
+ (f" -- {detail}" if detail else ""))
def control(name, ok, detail=""):
check(name, ok, detail)
if not ok:
print(" control failed: run stopped")
raise SystemExit(1)
def section(title):
print()
print("=" * 72)
print(title)
print("=" * 72)
# ------------------------------------------------------------ arithmetic
def primes_up_to(n):
s = bytearray([1]) * (n + 1)
s[0] = s[1] = 0
for i in range(2, isqrt(n) + 1):
if s[i]:
s[i * i::i] = bytearray(len(s[i * i::i]))
return [i for i in range(n + 1) if s[i]]
PRIMES = primes_up_to(20000)
ODD = [p for p in PRIMES if 2 < p < 1000]
BASES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41)
def is_prime(n):
"""Miller-Rabin at the primes to 41, deterministic below 3.3 * 10^24
(Sorenson and Webster, 2017). Above it a composite verdict is a
proof."""
if n < 2:
return False
for b in BASES:
if n % b == 0:
return n == b
d, s = n - 1, 0
while d % 2 == 0:
d, s = d // 2, s + 1
for b in BASES:
x = pow(b, d, n)
if x in (1, n - 1):
continue
for _ in range(s - 1):
x = x * x % n
if x == n - 1:
break
else:
return False
return True
def trial_prime(n):
if n < 2:
return False
for q in PRIMES:
if q * q > n:
return True
if n % q == 0:
return n == q
return True
def iroot(n, k):
"""The integer k-th root of n, floor: a float seed below 2^1000, then
Newton from above."""
if n < 2:
return n
if n.bit_length() < 1000:
x = int(n ** (1.0 / k) * (1 + 1e-12)) + 2
else:
x = 1 << ((n.bit_length() + k - 1) // k)
while True:
y = ((k - 1) * x + n // x ** (k - 1)) // k
if y >= x:
return x
x = y
def proper_power_brute(n):
"""(r, s) with n = r^s, r prime, s >= 2, by exact roots; else None."""
for k in PRIMES:
if (1 << k) > n:
break
r = iroot(n, k)
if r ** k == n:
# n = r^k; reduce r to a prime base if r is itself a power
sub = proper_power_brute(r)
if sub:
return sub[0], sub[1] * k
if trial_prime(r) if r < PRIMES[-1] ** 2 else is_prime(r):
return r, k
return None
return None
def vp(n, p):
v = 0
while n % p == 0:
n //= p
v += 1
return v
def divisors(n):
return [d for d in range(1, n + 1) if n % d == 0]
# ------------------------------------------------------ the carrier ladder
def proper_carriers(p):
"""Every proper prime power carrier r^s at a level V >= 1 of odd p, by
the confinement (6): r < p prime, s | p - 1, s >= 2. -> {V: [(r, s)]}"""
out = {}
for r in PRIMES:
if r >= p:
break
for s in divisors(p - 1):
if s < 2:
continue
n = r ** s
if (n - 1) % p:
continue
V = vp(n - 1, p) - 1
if V >= 1 and n < p ** (V + 2):
out.setdefault(V, []).append((r, s))
return out
SIEVE_Q = [q for q in PRIMES if 2 < q < 1000]
def prime_carrier(p, V):
"""The least even m <= p - 1 with m p^(V+1) + 1 prime, or None. Small
primes are sieved through their one class of m when every candidate
exceeds them."""
k = V + 1
pk = p ** k
alive = bytearray([1]) * p
if pk > 1000:
for q in SIEVE_Q:
if q == p:
continue
c = (-pow(p, -k, q)) % q
start = c if c % 2 == 0 else c + q
if start < p:
alive[start::2 * q] = bytearray(len(alive[start::2 * q]))
for m in range(2, p, 2):
if alive[m] and is_prime(m * pk + 1):
return m
return None
def odd_carriers(p, V):
"""Accepted odd-m candidates: even numbers, carriers only as 2^t."""
pk = p ** (V + 1)
return [m * pk + 1 for m in range(1, p, 2)
if (m * pk + 1) & (m * pk) == 0]
def level_alive(p, V, props):
return (prime_carrier(p, V) is not None or V in props
or bool(odd_carriers(p, V)))
def dead_level(p, V0, cap, props):
"""The first dead level at or above V0 of odd p (the walk rises one
level at a time), or None below cap."""
V = V0
while V <= cap:
if not level_alive(p, V, props):
return V
V += 1
return None
def pp(n):
return is_prime(n) or proper_power_brute(n) is not None
def walk2(V0, cap, least=False):
"""p = 2: level V, candidates 2^(V+1)+1, 2^(V+2)+1, 3 2^(V+1)+1; the
walk takes the carrier banking the most, or with least the one of
least norm. -> (dead level, trace, the level each carrier stands
at)."""
V, trace, at = V0, [], []
while V <= cap:
c = [(2 ** (V + 2) + 1, 2), (2 ** (V + 1) + 1, 1),
(3 * 2 ** (V + 1) + 1, 1)]
got = [(n, rise) for n, rise in c if pp(n)]
if least:
got.sort()
if not got:
return V, trace, at
n, rise = got[0]
trace.append(n)
at.append(V)
V += rise
return None, trace, at
# ------------------------------------------------------------- section C
def section_c():
section("C POSITIVE CONTROLS, before any verdict reads them")
bad = 0
tested = 0
for p in (3, 5, 7, 11):
V = 1
while p ** (V + 2) <= 2 * 10 ** 6:
scan = {n for n in range(2, p ** (V + 2)) if vp(n - 1, p) > V}
gen = {m * p ** (V + 1) + 1 for m in range(1, p)}
bad += scan != gen
tested += 1
V += 1
control("C1 the supply is the p - 1 numbers m p^(V+1) + 1", bad == 0,
f"{tested} (p, V), {bad} off")
bad = sum(is_prime(n) != trial_prime(n) for n in range(20000))
control("C2 Miller-Rabin agrees with trial division below 20,000",
bad == 0, f"{bad} off")
bad, found, cands = 0, [], 0
for p in ODD:
if p >= 50:
break
props = proper_carriers(p)
for V in range(1, p + 3):
brute = []
for m in range(1, p):
n = m * p ** (V + 1) + 1
cands += 1
pw = proper_power_brute(n)
if pw:
brute.append(pw)
if sorted(brute) != sorted(props.get(V, [])):
bad += 1
found += [(p, V, r, s) for r, s in brute]
control("C3 the confinement enumeration equals an exact-root test of "
"every candidate, odd p < 50, 1 <= V <= p + 2", bad == 0,
f"{cands} candidates, {bad} levels off; proper powers {found}")
D2, tr, at = walk2(1, 400)
D2l, trl, _ = walk2(1, 400, least=True)
D3 = dead_level(3, 1, 120, proper_carriers(3))
D5 = dead_level(5, 1, 120, proper_carriers(5))
print(f" p = 2 banking the most climbs through {tr} (standing at levels "
f"{at}) and dies at {D2};"
f" least-norm through {trl}, dead at {D2l}; "
f"D(3) = {D3}, D(5) = {D5}")
control("C4 the recorded walks: 2 through 9, 17, 97, 193, 257 banking "
"the most and through 5, 9, 17, 97, 193, 257 by least norm, "
"each dead at 8; D(3) = 2; D(5) = 3",
tr == [9, 17, 97, 193, 257] and D2 == 8
and trl == [5, 9, 17, 97, 193, 257] and D2l == 8
and D3 == 2 and D5 == 3)
# ------------------------------------------------------------- section R
def fundamental(D):
"""D < 0 a fundamental discriminant."""
def sqfree(n):
return all(n % (q * q) for q in PRIMES if q * q <= n)
if D % 4 == 1:
return sqfree(-D)
if D % 4 == 0:
d = D // 4
return d % 4 in (2, 3) and sqfree(-d)
return False
def reduced_forms(D):
"""Reduced forms (a, b, c), b^2 - 4ac = D < 0."""
out = []
a = 1
while 3 * a * a <= -D:
for b in range(-a + 1, a + 1):
if (b * b - D) % (4 * a):
continue
c = (b * b - D) // (4 * a)
if c < a or (b < 0 and (a == c)):
continue
if gcd(gcd(a, abs(b)), c) != 1:
continue
out.append((a, b, c))
a += 1
return out
def section_r():
section("R tau_K OVER THE IMAGINARY QUADRATIC FIELDS, D >= -1000")
fields = []
for D in range(-3, -1001, -1):
if fundamental(D):
forms = reduced_forms(D)
tau = max(a for a, _, _ in forms)
fields.append((D, len(forms), tau))
ok1 = all((t == 1) == (h == 1) for _, h, t in fields)
ok2 = all(t <= sqrt(-D / 3) for D, _, t in fields)
ok3 = all(t <= 2 / pi * sqrt(-D) for D, _, t in fields)
mean = sum(t for _, _, t in fields) / len(fields)
share = sum(t <= 4 for _, _, t in fields) / len(fields)
ratio = sum(t / (2 / pi * sqrt(-D)) for D, _, t in fields) / len(fields)
print(f" {len(fields)} fields; mean tau_K {mean:.2f}; tau_K <= 4 at "
f"{100 * share:.1f}%; mean tau_K / Minkowski {ratio:.3f}")
print(f" tau_K = 1 iff h = 1: {ok1}; tau_K <= sqrt(|D|/3): {ok2}; "
f"<= Minkowski: {ok3} (the forms stop at 3a^2 <= |D|, one has "
"a = 1)")
h1 = sorted((-D for D, h, _ in fields if h == 1))
h2 = sorted((-D for D, h, _ in fields if h == 2))
check("R1 305 fundamental discriminants; class number 1 exactly at "
"the nine Heegner discriminants, 2 at the eighteen of "
"Baker and Stark",
len(fields) == 305 and h1 == [3, 4, 7, 8, 11, 19, 43, 67, 163]
and h2 == [15, 20, 24, 35, 40, 51, 52, 88, 91, 115, 123, 148,
187, 232, 235, 267, 403, 427], f"{h1}; {h2}")
h, t = next((h, t) for D, h, t in fields if D == -23)
norms = {x * x + x * y + 6 * y * y for x in range(-20, 21)
for y in range(-20, 21)}
mink = 2 / pi * sqrt(23)
check("R2 D = -23: h = 3, tau_K = 2, Minkowski 3.05, no element of "
"norm 2 or 3", (h, t) == (3, 2) and abs(mink - 3.05) < 0.01
and 2 not in norms and 3 not in norms and 6 in norms,
f"h {h}, tau_K {t}, Minkowski {mink:.3f}")
# ------------------------------------------------------------- section B
def section_b():
section("B THE BUDGET: THE DOUBLE RISE AT 2 IS RATIONED BY FERMAT")
got = [2 ** k + 1 for k in range(1, 301) if pp(2 ** k + 1)]
print(f" prime powers 2^k + 1, 1 <= k <= 300: {got}")
check("B1 k <= 300: exactly 3, 5, 9, 17, 257, 65537",
got == [3, 5, 9, 17, 257, 65537], str(got))
# ------------------------------------------------------------- section S
DEATH = {}
PROPS = {}
def section_s():
section("S THE SWEEP: THE DEAD LEVEL OF EVERY ODD p < 1000")
alive, odd_acc = [], []
for p in ODD:
PROPS[p] = proper_carriers(p)
D = dead_level(p, 1, 120, PROPS[p])
if D is None:
alive.append(p)
continue
DEATH[p] = D
for V in range(1, D + 1):
odd_acc += odd_carriers(p, V)
top = max(DEATH, key=DEATH.get)
want = {19: 1, 23: 1, 17: 2, 29: 8, 101: 10, 151: 12, 751: 33,
997: 45, 719: 62}
off = {p: DEATH.get(p) for p in want if DEATH.get(p) != want[p]}
print(f" {len(DEATH)} odd p die, {len(alive)} alive at 120; largest "
f"D({top}) = {DEATH[top]}; recorded values off: {off}")
print(f" accepted odd-m carriers at levels 1..D(p): {odd_acc}")
check("S1 all 167 odd p < 1000 die at or below level 120",
len(DEATH) == 167 and not alive)
check("S2 the recorded dead levels, largest D(719) = 62",
not off and top == 719)
print(f" odd-m carriers are powers of 2, among the proper powers: "
f"{len(odd_acc)} accepted")
# ------------------------------------------------------------- section K
QMAX, LMAX = 2000, 5040
def ordmod(a, q):
k, x = 1, a % q
while x != 1:
x = x * a % q
k += 1
return k
def covering(p):
"""A residue k0 mod L at which the classes m = -p^(-k) mod q, q over
the primes below QMAX whose order of p divides LMAX, cover every even
m in [2, p - 1] at every k = k0 mod L. -> (L, k0, primes) or None."""
evens = list(range(2, p, 2))
full = (1 << len(evens)) - 1
S = [q for q in PRIMES[1:] if q != p and q < QMAX
and LMAX % ordmod(p, q) == 0]
if sum(-(-len(evens) // q) for q in S) < len(evens):
return None
masks, orders, cls = {}, {}, {}
for q in S:
orders[q] = ordmod(p, q)
tbl = [0] * q
for i, m in enumerate(evens):
tbl[m % q] |= 1 << i
masks[q] = tbl
inv = pow(p, -1, q)
cls[q] = [(-pow(inv, j, q)) % q for j in range(orders[q])]
L = 1
for q in S:
L = L * orders[q] // gcd(L, orders[q])
for k in range(L):
cov, used = 0, []
for q in S:
mk = masks[q][cls[q][k % orders[q]]]
if mk & ~cov:
cov |= mk
used.append(q)
if cov == full:
Lu = 1
for u in used:
Lu = Lu * orders[u] // gcd(Lu, orders[u])
return Lu, k % Lu, used
return None
def section_k():
section("K RECURRENCE: A DEAD LEVEL ABOVE EVERY START")
worst, undead = {}, []
for p in (2, 3, 5):
props = proper_carriers(p) if p > 2 else {}
w = 0
for V0 in range(1, 301):
if p == 2:
D, _, _ = walk2(V0, 400)
else:
D = dead_level(p, V0, 400, props)
if D is None:
undead.append((p, V0))
continue
w = max(w, D - V0 + 1)
worst[p] = w
print(f" longest climb, counting the start's level: {worst}")
check("K1 every start V0 <= 300 at 2, 3, 5 dies by level 400, the "
"longest spanning 8, 4 and 3 levels, the start's included",
not undead and worst == {2: 8, 3: 4, 5: 3}, f"undying {undead}")
covered = {}
for p in ODD:
c = covering(p)
if c:
covered[p] = c
print(f" coverings at {sorted(covered)}")
for p in sorted(covered):
L, k0, used = covered[p]
first = next(V for V in range(max(1, p - 2), max(1, p - 2) + L)
if (V + 1) % L == k0)
print(f" p = {p}: V + 1 = {k0} mod {L}, primes {used}; first "
f"killed level from p - 2: {first}")
check("K2 coverings at exactly 3, 5, 7, 11, 13, 17, 19, 23, 31, 37",
sorted(covered) == [3, 5, 7, 11, 13, 17, 19, 23, 31, 37])
n, live = 0, []
for p in sorted(covered):
L, k0, _ = covered[p]
for V in range(max(1, p - 2), 201):
if (V + 1) % L == k0:
n += 1
if level_alive(p, V, PROPS[p]):
live.append((p, V))
for V in range(10, 401):
if (V + 1) % 8 == 3:
n += 1
if any(pp(x) for x in (2 ** (V + 1) + 1, 2 ** (V + 2) + 1,
3 * 2 ** (V + 1) + 1)):
live.append((2, V))
check("K3 every level the found covering kills is dead (odd p to 200; "
"p = 2 at 10 <= V <= 400, V + 1 = 3 mod 8)", not live,
f"{n} levels, alive {live}")
# ------------------------------------------------------------- section Q
def legendre(a, p):
return pow(a % p, (p - 1) // 2, p)
def section_q():
section("Q THE RESIDUAL: Q(sqrt(2 3 ... P)) HAS NO RANK-1 p <= P")
bad, rows = [], []
d = 2
for P in PRIMES[1:]:
if P > 97:
break
d *= P
# 2 ramifies (d even); an odd p is rank-1 iff it splits, i.e.
# d is a nonzero square mod p
L = next(p for p in PRIMES[1:] if d % p and legendre(d, p) == 1)
rows.append((P, L))
if L <= P:
bad.append(P)
print(" (P, least rank-1 characteristic): "
+ ", ".join(f"({P}, {L})" for P, L in rows))
print(f" L > P at every odd P <= 97, by ramification: {not bad}")
# ------------------------------------------------------------- section X
def sifted(p, V, qs):
"""Even m <= p - 1 whose candidate has no prime factor in qs."""
k = V + 1
alive = bytearray([1]) * p
for q in qs:
if q == p:
continue
c = (-pow(p, -k, q)) % q
start = c if c % 2 == 0 else c + q
if start < p:
alive[start::2 * q] = bytearray(len(alive[start::2 * q]))
return sum(alive[m] for m in range(2, p, 2))
def carriers_all(p, V):
pk = p ** (V + 1)
n = sum(is_prime(m * pk + 1) for m in range(2, p, 2))
return n + len(PROPS[p].get(V, []))
def section_x():
section("X THE SHAPE OF A DEAD LEVEL")
allp = {}
for p in ODD:
for V, lst in PROPS[p].items():
allp[(p, V)] = list(lst)
broke = [(p, V, r, s) for (p, V), lst in allp.items() for r, s in lst
if ordmod(r, p ** (V + 1)) != s]
print(f" proper power carriers at any level V >= 1, odd p < 1000: "
f"{allp}")
check("X1 the enumeration (6) licenses finds one, 3^5 = 243 at "
"(11, 1), 5 the order of 3 mod 11^2",
allp == {(11, 1): [(3, 5)]} and not broke)
Z = 10 ** 4
qs = [q for q in PRIMES if 2 < q < Z]
pool = [p for p in ODD if DEATH[p] >= 10]
A, U = [], []
for V in range(1, 11):
a = sum(carriers_all(p, V) / (p - 1) for p in pool) / len(pool)
u = sum(sifted(p, V, qs) / ((p - 1) // 2) for p in pool) / len(pool)
A.append(a)
U.append(u)
lvl = 2 * exp(-0.5772156649) / log(Z)
print(f" pool {len(pool)} primes with D(p) >= 10; carrier density "
f"{A[0]:.5f} -> {A[-1]:.5f} (ratio {A[-1] / A[0]:.3f}); sifted "
f"{U[0]:.5f} -> {U[-1]:.5f} (ratio {U[-1] / U[0]:.3f}); "
f"2e^-gamma/ln z {lvl:.4f}")
MR = 3317044064679887385961981
past = [p for p in pool if (p - 1) * p ** 11 + 1 >= MR]
print(f" pooled p with a level-10 candidate past the Miller-Rabin "
f"bound: {len(past)} of {len(pool)}, the least {min(past)}, "
f"every pooled p from it on: "
f"{past == [p for p in pool if p >= min(past)]}")
check("X2 carrier density falls near 1/4 from level 1 to 10, sifted "
"density flat within 5% near 0.1219",
0.2 < A[-1] / A[0] < 0.3 and abs(U[-1] / U[0] - 1) < 0.05
and all(abs(u - lvl) < 0.01 for u in U),
" ".join(f"{u:.4f}" for u in U))
emptied = [p for p in ODD if p >= 100
and sifted(p, DEATH[p], qs) == 0]
check("X3 sifting below 10^4 empties the printed dead level at no "
"p >= 100",
not emptied, str(emptied))
# ------------------------------------------------------------- section W
def section_w():
section("W THE WELD: A DEAD LEVEL PAST 0 IS A FULL-PRICE OPENING OVER Z")
# the predicates can differ only where a proper power carrier sits:
# none exists at V >= p - 2, and S counts the odd-m ones
diff = []
for p in ODD:
for V in PROPS[p]:
no_prime = prime_carrier(p, V) is None
dead = not level_alive(p, V, PROPS[p])
if no_prime != dead:
diff.append((p, V))
held = sorted((p, V) for p in ODD for V in PROPS[p])
print(f" levels holding a proper power carrier: {held}; least prime "
f"carrier at (11, 1): {prime_carrier(11, 1) * 121 + 1}")
check("W1 'no prime carrier' and 'dead' agree at every level of "
"every odd p < 1000 holding a proper power carrier, the only "
"levels where they can differ", not diff, str(diff))
import growth
p, V = 3, 2
price = p ** (V + 2)
B = p - 1
for r in PRIMES:
if r >= price:
break
if r == p:
continue
B = B * (r - 1) // gcd(B, r - 1)
c = 0
while (2 ** (c + 3) if r == 2 else r ** (c + 2)) <= price:
c += 1
B = B * r ** c // gcd(B, r ** c)
while B % p == 0:
B //= p
B *= p ** V
P = B + 1
while not (is_prime(P) and vp(P - 1, p) == V):
P += B
mf = {P: 1}
lamf = growth.lam(mf)
q, cost, _ = growth.menu(mf, lamf)
k = growth.kind(q, mf, lamf)
print(f" B = {B}; the least prime P = 1 mod B with v_3(P - 1) = 2: "
f"{P}; growth.py's menu there: {q}^r = {cost}, {k}")
check("W2 the construction's least prime is 961440481 and the menu "
"opens 3 there at 81, full price",
P == 961440481 and (q, cost, k) == (3, 81, "full"))
atD = [p for p in ODD if prime_carrier(p, DEATH[p]) is not None]
print(f" dead levels D(p) holding a prime carrier: {atD} (none by "
"D's definition, so each is a full-price opening by (8))")
wit = [prime_carrier(p, 1) * p ** 2 + 1 for p in (3, 5, 7)]
print(f" the least prime carrier at (3, 1), (5, 1), (7, 1): {wit}")
def main():
t0 = time.time()
section_c()
section_r()
section_b()
section_s()
section_k()
section_q()
section_x()
section_w()
print()
print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed, "
f"{time.time() - t0:.1f} s")
raise SystemExit(0 if all(CHECKS) else 1)
if __name__ == "__main__":
main()