converse.py
Checks: TOWER: The unitary spectrum theorem; rule.
Cited on: TOWER.
To run it: save converse.py; standard library only.
"""converse.py -- the doubling rung's converse: past k = 3, must a rung
of the tower with no totient collision bring a new prime into lambda?
QUESTION. At the rung k, p = p_k, n = p - 1 and Q the odd primes below
p, a totient collision is a pair of disjoint subsets A, B of Q with
prod_A (q - 1) = n * prod_B (q - 1) (a prime in both cancels). A prime
of n dividing no q - 1, q in Q (a new prime of lambda) forbids one.
Does a rung past k = 3 with no new prime always have one?
DESIGN.
(1) THE CAPACITY (proved). A collision forces, at every prime l,
v_l(n) <= cap_l(p), the sum over q in Q of v_l(q - 1): v_l(prod_A) =
v_l(n) + v_l(prod_B) >= v_l(n). A new prime is cap 0. So the converse
fails by a CAPACITY BREAK at an old l (v_l(n) > cap_l > 0), or with
capacity held at every l and no collision.
(2) AT l = 2 the break is p = 5 alone: with e = v_2(n), Bertrand puts
an odd prime in (2^j, 2^(j+1)] for j = 1..e-1, all below p, so cap_2
>= e - 1, and 5 adds one more at e >= 3; at e = 2 and p >= 13, 3 and 5
give 3; at e = 1, 3 gives 1.
(3) AT ODD l a break with l old needs v_l(n) >= 2: p is the m-th prime
= 1 mod l with v_l(p - 1) above the sum over the earlier ones, m >= 2,
each at least 1, so v_l(p - 1) >= m, p > 2l^m, and fewer than m primes
= 1 mod l lie below 2l^m + 1. At m = 2, p = 1 mod l^2 is the second
prime = 1 mod l, with at most one prime among the l - 1 candidates
2lj + 1 below 2l^2. A TRANSPLANT (independent candidates, prime with chance
about 1/ln l): about (l/ln l) e^(-l/ln l) / l, so an m = 2 break, if
any, comes at a small l.
(4) THE WITNESS SEARCH. Below 100 the exact listing: U, the set of
prod (q - 1) over subsets of Q, against n U. Past it, a depth-first
search on the residual exponent vector r (r = v(n) at the start, a
prime put in A subtracts v(q - 1), in B adds it): take the largest
prime l with r_l != 0, put an unused q = 1 mod l on the side that
lowers |r_l|, the candidates ordered by the largest prime of (q - 1)
other than l, four tried, deepening to 12 moves. TABLE, the eleven
odd primes 3..41 whose q - 1 is 7-smooth, is kept out of the search;
once r lives on {2, 3, 5, 7}, a table of all 3^11 signed choices
among them, the fewest primes kept per vector, closes it. Every
witness is verified exactly: A, B disjoint, inside Q, no repeat, the
products equal.
PREDICTIONS (frozen before the code).
C1 (proved) cap_2 >= v_2(n) at every odd p but 3 (2 new) and 5 (the
break); printed to 10^6.
C2 (pattern, 85%) no capacity break at an odd old l, p < 10^6.
C3 (pattern, 85%) at every rung 7 <= p_k < X1 with capacity held at
every l, the search finds a witness.
C4 (a guess, 60%) |A| + |B| <= 6 at every witnessed rung.
THE KILL, frozen. The script prints CAPACITY BREAKS at odd l with l
and every prime of n old, p < 10^6: past 5, "CONVERSE FALSE AT p =
..." (proved, the capacity being necessary). Over 7 <= p < X1 with
capacity held, UNWITNESSED [...]: nonempty, "UNDECIDED AT ...". Both
empty: "THE CONVERSE HOLDS AT EVERY RUNG p_k < X1".
CONTROLS, read first. K1 17's witness found and verified. K2 the exact
listing below 100: its collision rungs are exactly the rungs with
capacity held, the search (run with the exact listing off) witnesses
every one at 43 <= p < 100 (the table's primes below p), and its
non-collision rungs are 3, 5, 7, 11, 23, 29, 47, 53, 59, 83, the
doubling rung's list to k = 24. K3 the verifier rejects planted
witnesses: A = {17} at 17, a repeated prime, a product off by 2. K4
the capacity flags 5 at l = 2 and no other p < 10^6 there.
FINDINGS (from the printed run; the controls passed first). K1 prints
17's witness A = {3, 5, 13}, B = {7}; K2 (narrowed after the freeze
from k <= 20 to 43..97, the table's primes lying below p) the listing's
non-collision
rungs below 100 are 3, 5, 7, 11, 23, 29, 47, 53, 59, 83, the rest
exactly the capacity-held rungs, and the search witnesses all 8
collision rungs in 43..97; K3 and K4 hold, the capacity at 2 breaking
at 5 alone below 10^6 (C1). Below 10^6, 13143 of the 78497 odd p bring
a new prime, the first 3, 7, 11, 23, 29, 47, 53, 59, 83, 103, 107,
149; CAPACITY BREAKS at an odd l: none, with every prime old or with a
new one beside (C2 holds). Every one of the 65353 rungs 7 <= p_k <
10^6 with capacity held is witnessed, 14 by the listing, verified
exactly: UNWITNESSED none (C3 holds). THE PRINT: THE CONVERSE HOLDS AT
EVERY RUNG p_k < 1000000. The search's |A| + |B|, not minimal (a
depth-first find, the table minimal over its own primes), runs 2 to 14
(C4 FAILS): 4875,
17711, 16421, 10367, 6616, 3866, 2392, 1029, 959, 795, 293, 27 and 2
rungs at 2..14, the largest at p = 958931. At X1 = 10^3, 10^4, 10^5
the same verdict, 116, 946 and 7726 rungs witnessed. A witness read
by hand: 9311, n = 2 * 5 * 7^2 * 19, A = {1217, 113, 11, 19, 29, 31},
B = {3, 5, 13, 17, 37, 41}: 2^15 3^3 5^2 7^2 19 over 2^14 3^3 5.
So the converse holds to 10^6, and with it the sharper statement:
there, a rung has a collision exactly when the capacity holds at every
l, the capacity failing only at a new prime and at 5.
RUN RECORD. Rehearsal --x1 1000: 6/6, 0.8 s, peak 119.8 MB; --x1
10^4 0.8 s, 120.7 MB; --x1 10^5 1.3 s, 127.7 MB; the full run (X1 =
10^6) 6/6, 52.0 s, peak 188.4 MB under a memory guard.
python converse.py [--x1 X1] (X1 default 10^6)
"""
import sys
import time
from array import array
from itertools import product
N6 = 10 ** 6
TABLE = (3, 5, 7, 11, 13, 17, 19, 29, 31, 37, 41)
SMALL = (2, 3, 5, 7)
CHECKS = []
def check(name, ok, detail=""):
CHECKS.append((name, bool(ok)))
print(f" [{'PASS' if ok else 'FAIL'}] {name}"
+ (f" -- {detail}" if detail else ""))
def spf_to(n):
s = array("i", [0]) * (n + 1)
for i in range(2, int(n ** 0.5) + 1):
if s[i] == 0:
for j in range(i * i, n + 1, i):
if s[j] == 0:
s[j] = i
return s
def factor(m, spf):
out = {}
while m > 1:
r = spf[m] or m
while m % r == 0:
m //= r
out[r] = out.get(r, 0) + 1
return out
def capacity(primes, spf):
"""{p: (new primes of n, breaks [(l, v_l(n), cap_l)])} over the odd
primes p, cap read before p joins Q."""
cap, out = {}, {}
for p in primes:
if p == 2:
continue
f = factor(p - 1, spf)
new = [l for l in f if cap.get(l, 0) == 0]
brk = [(l, v, cap[l]) for l, v in f.items()
if 0 < cap.get(l, 0) < v]
out[p] = (new, brk)
for l, v in f.items():
cap[l] = cap.get(l, 0) + v
return out
def verify(p, A, B, primes_set):
if len(set(A)) != len(A) or len(set(B)) != len(B) or set(A) & set(B):
return False
if any(q == 2 or q >= p or q not in primes_set for q in A + B):
return False
a = b = 1
for q in A:
a *= q - 1
for q in B:
b *= q - 1
return a == (p - 1) * b
def exact(p, Q):
"""A witness (A, B) from the listing of U over Q, or None."""
U = {1: ()}
for q in Q:
for v, S in list(U.items()):
w = v * (q - 1)
if w not in U:
U[w] = S + (q,)
n = p - 1
for v, S in U.items():
if v * n in U:
A, B = set(U[v * n]), set(S)
c = A & B
return sorted(A - c), sorted(B - c)
return None
def vec(f):
return tuple(f.get(r, 0) for r in SMALL)
def build_table(spf):
vs = [vec(factor(q - 1, spf)) for q in TABLE]
best = {}
for signs in product((0, 1, -1), repeat=len(TABLE)):
v = [0, 0, 0, 0]
for s, x in zip(signs, vs):
if s:
for i in range(4):
v[i] += s * x[i]
v = tuple(v)
size = sum(1 for s in signs if s)
if v not in best or size < best[v][0]:
best[v] = (size, signs)
return best
class Search:
def __init__(self, spf, primes, table):
self.spf, self.table = spf, table
self.fac = {q: factor(q - 1, spf) for q in primes if q > 2}
self.by = {} # l -> [q with l | q - 1]
for q, f in self.fac.items():
if q in TABLE:
continue
for l in f:
self.by.setdefault(l, []).append(q)
self.key = {}
for q, f in self.fac.items():
for l in f:
others = [r for r in f if r != l]
self.key[(q, l)] = (max(others) if others else 1, q)
def close(self, r):
"""Table primes closing r on {2, 3, 5, 7}, or None."""
if any(l not in SMALL for l in r):
return None
hit = self.table.get(vec(r))
if hit is None:
return None
A = [q for q, s in zip(TABLE, hit[1]) if s == 1]
B = [q for q, s in zip(TABLE, hit[1]) if s == -1]
return A, B
def run(self, p, depth=12, width=4):
r0 = factor(p - 1, self.spf)
for d in range(1, depth + 1):
got = self.dfs(p, dict(r0), [], [], set(), d, width)
if got:
return got
return None
def dfs(self, p, r, A, B, used, d, width):
c = self.close(r)
if c is not None:
return A + c[0], B + c[1]
if d == 0:
return None
big = [l for l in r if l not in SMALL]
l = max(big) if big else max(r)
side = 1 if r[l] > 0 else -1 # 1: into A, -1: into B
cand = [q for q in self.by.get(l, ()) if q < p and q not in used]
cand.sort(key=lambda q: self.key[(q, l)])
for q in cand[:width]:
r2 = dict(r)
for x, v in self.fac[q].items():
r2[x] = r2.get(x, 0) - side * v
if r2[x] == 0:
del r2[x]
used.add(q)
got = self.dfs(p, r2, A + [q] * (side == 1), B + [q] * (side == -1),
used, d - 1, width)
used.discard(q)
if got:
return got
return None
def main():
x1 = 10 ** 6
if "--x1" in sys.argv:
x1 = int(float(sys.argv[sys.argv.index("--x1") + 1]))
t0 = time.time()
spf = spf_to(N6)
primes = [p for p in range(2, N6) if spf[p] == 0]
pset = set(primes)
print(f"sieve to {N6}: {len(primes)} primes ({time.time() - t0:.1f} s)")
cap = capacity(primes, spf)
table = build_table(spf)
S = Search(spf, [q for q in primes if q < x1], table)
print(f"table: {len(table)} vectors ({time.time() - t0:.1f} s)")
print("CONTROLS")
w = exact(17, [q for q in primes if 2 < q < 17])
check("K1 17's witness found and verified",
w is not None and verify(17, w[0], w[1], pset), f"{w}")
low = [p for p in primes if 2 < p < 100]
ex, bad = {}, []
for p in low:
ex[p] = exact(p, [q for q in primes if 2 < q < p])
if ex[p] is not None and not verify(p, *ex[p], pset):
bad.append(p)
nocol = [p for p in low if ex[p] is None]
held = [p for p in low if not cap[p][0] and not cap[p][1]]
srch = [p for p in low if p >= 43 and ex[p] is not None]
miss = [p for p in srch if not (S.run(p) and verify(p, *S.run(p), pset))]
check("K2 below 100 the collision rungs are the capacity-held rungs",
not bad and sorted(set(low) - set(nocol)) == held,
f"no collision at {nocol}")
check("K2 the non-collision rungs are 3, 5, 7, 11, 23, 29, 47, 53, 59, 83",
nocol == [3, 5, 7, 11, 23, 29, 47, 53, 59, 83])
check("K2 the search witnesses every collision rung 43 <= p < 100",
not miss, f"{len(srch)} rungs, missed {miss}")
check("K3 the verifier rejects A = {17} at 17, a repeat, an off-by-2",
not verify(17, [17], [], pset)
and not verify(17, [5, 5], [], pset)
and not verify(17, [3, 5, 13], [5], pset)
and verify(17, [3, 5, 13], [7], pset))
two = [p for p, (new, brk) in cap.items() if any(l == 2 for l, _, _ in brk)]
check("K4 the capacity breaks at l = 2 at 5 alone, p < 10^6 (C1)",
two == [5], f"{two[:5]}")
if not all(ok for _, ok in CHECKS):
print("CONTROL FAILED: nothing below is read.")
raise SystemExit(1)
print("THE CAPACITY TO 10^6")
newr = [p for p, (new, _) in cap.items() if new]
brk = [(p, b) for p, (new, bs) in cap.items() for b in bs
if b[0] != 2 and not new]
print(f" rungs with a new prime: {len(newr)} of {len(cap)} odd p; "
f"first {newr[:12]}")
print(f" CAPACITY BREAKS at odd l, every prime old: {brk[:10]}"
f" ({len(brk)})")
allb = [(p, b) for p, (new, bs) in cap.items() for b in bs if b[0] != 2]
print(f" breaks at odd l with a new prime beside: {allb[:6]} "
f"({len(allb)})")
print(f"THE WITNESSES, 7 <= p < {x1}")
t1 = time.time()
unw, sizes, ex_used = [], {}, 0
for p in primes:
if p < 7 or p >= x1:
continue
new, bs = cap[p]
if new or bs:
continue
if p < 100:
w = ex[p]
ex_used += 1
else:
w = S.run(p)
if w is None or not verify(p, w[0], w[1], pset):
unw.append(p)
else:
sizes[p] = len(w[0]) + len(w[1])
big = max(sizes, key=lambda p: (sizes[p], p)) if sizes else None
hist = {}
for v in sizes.values():
hist[v] = hist.get(v, 0) + 1
print(f" {len(sizes)} witnessed ({ex_used} by the listing), "
f"{time.time() - t1:.1f} s; |A| + |B| counts {sorted(hist.items())}"
f", largest at p = {big}")
print(f" UNWITNESSED: {unw[:20]} ({len(unw)})")
print(f" C4: {'HOLDS' if all(v <= 6 for v in sizes.values()) else 'FAILS'}")
print("THE PRINT")
if [b for b in brk if b[0] > 5]:
print(f" CONVERSE FALSE AT p = {brk[0][0]}")
elif unw:
print(f" UNDECIDED AT {unw[:10]}")
else:
print(f" THE CONVERSE HOLDS AT EVERY RUNG p_k < {x1}")
print(f"{sum(ok for _, ok in CHECKS)}/{len(CHECKS)} checks passed, "
f"{time.time() - t0:.1f} s")
raise SystemExit(0 if all(ok for _, ok in CHECKS) else 1)
if __name__ == "__main__":
main()