signed.py
Checks: COLLIDE: Signed pentanomials theorem.
Cited on: COLLIDE.
To run it: save signed.py; needs flint.
"""signed.py -- signed pentanomials read through the reversal: which NOs
the gcd with the reversal sees, which it misses, and where the ones it
sees lie.
QUESTION. f = 1 + s1 x^q + s2 x^p + s3 x^m + s4 x^n, 0 < q < p < m < n,
s in {+1, -1}^4, f~ = x^n f(1/x), G = gcd(f, f~) over Z. A NO is an f
whose non-cyclotomic part is reducible: two non-cyclotomic irreducible
factors, with multiplicity. For the non-reciprocal 0/1 f (reversal.py)
a NO is exactly a non-cyclotomic G, given Filaseta and Solan's Theorem
1; for signed f only one direction holds. How many signed NOs does
the gcd see, and do the ones it sees satisfy a few short integer
relations among (q, p, m, n), as E. Bombieri and U. Zannier's
finiteness (Theorem 3 of M. Filaseta and A. Kalogirou,
arXiv:2508.12242) says some finite set must?
THE REDUCTION.
(a) f not +-reciprocal, u | G irreducible and not cyclotomic. If u is
+-reciprocal, f = u v with v not +-reciprocal, so v holds a
non-+-reciprocal factor, which is not cyclotomic; otherwise
u~ | f beside u. So a SURVIVOR, G with a non-cyclotomic factor,
is a NO, with no Theorem 1. The converse fails for signed f:
(x^5 - x^2 + 1)(x^3 + x^2 + 1) = 1 + x^3 - x^4 + x^7 + x^8 is a NO
with G = 1.
(b) f +-reciprocal: G = +-f, factored outright, kept apart.
(c) CANCELLATION in f f~: with e = (0, q, p, m, n) and signs (1, s),
f f~ = sum s_i s_j x^(n + e_i - e_j), 25 products; it cancels when
two ordered pairs i != j, k != l, (i, j) != (k, l), have e_i - e_j
= e_k - e_l and s_i s_j = -s_k s_l. No cancellation is exactly the
hypothesis of Filaseta and Solan's Theorem 2, the absolute values of
f f~'s coefficients summing to 25, under which every factorization
of f has a +-reciprocal factor (its proof "can be made with very
few changes" to Theorem 1's, not printed). As their Theorem 1
follows from the same statement, f with its reciprocal factors
removed is then 1 or irreducible, so a NO has a +-reciprocal
non-cyclotomic factor, which divides f~ and so G: a NO that is not
+-reciprocal and has no non-cyclotomic G cancels. P3 is that
theorem's consequence, and its print checks the engine.
(d) DILATION. G(x^k) = gcd(f(x^k), f~(x^k)), so f(x^k) is a survivor
exactly when f is: the survivors are the dilations of those with
coprime exponents, the primitive ones.
(e) ORBITS. Reversal, normalized to constant 1, takes (e, s) to
((n - m, n - p, n - q, n), (s3 s4, s2 s4, s1 s4, s4)), and x -> -x
takes s_i to s_i (-1)^(e_i); each preserves +-reciprocity, G's
non-cyclotomic part up to the same map, the NO property and
cancellation in f f~. The route reads one f of each orbit and
counts it with its orbit: a quarter of the gcds.
DESIGN. python-flint's fmpz_poly, exact over Z.
C1 R (1 + x + x^3), R = x^2 - 3x + 1, through read(): reported.
C2 1 + x^3 - x^4 + x^7 + x^8: a NO by factoring, G = 1, not reported.
C3 the all-plus slice to N: no survivor (reversal.py's verdict).
C4 the cover reads a plant: the tuples on q + p = m, as survivors,
give the one relation j = (1, 1, -1, 0); a uniform sample of the
population of the survivors' size prints the flat reading.
P1 every survivor to ND is a NO by factoring.
P2 of the non-+-reciprocal NOs to ND, the share the gcd sees, a print.
P3 every non-+-reciprocal NO with G cyclotomic, to ND, has
cancellation in f f~.
P4 relations j, primitive, nonzero, |j_i| <= 2, first nonzero entry
positive, j . (q, p, m, n) = 0; greedy cover of the survivors'
distinct exponent tuples to N.
RAYS R0 the dilations to N of the primitives with n <= 20 are all
survivors, a check of the engine at (d); R1 the new primitives in
the window LO < n <= N (--window LO, read when N > LO); R2 a planted
new primitive with its mirror, and its double where that lies in the
window, counted once.
PREDICTIONS, fixed before the run. P1 holds. P2 at least 80%. P3 no
exception. P4 at most 10 relations hold 90% of the survivor tuples,
holding below 30% of the population. After the first run, from its
printed survivors: the survivors are the dilations of finitely many
primitives, so R1 finds at most one new primitive in each window
(41..60 at --top 60, then 61..100 at --top 100).
KILL. P4 over h relations and population share s: h > 10 or s >= 50%
kills "the shared factors sit on a few short hyperplanes"; fewer than
30 survivor tuples is unreadable and kills nothing. R1: two or more new
primitives in its window kill the rays.
FINDINGS (N = 40, ND = 30). 1,462,240 signed f, 760 +-reciprocal; 28
survivors over 14 exponent tuples; C1-C4 hold, C3 the all-plus slice
none; P1 every survivor a NO.
P2 MISSED: to n = 30, 1,168 non-+-reciprocal NOs, 20 seen by the gcd
(1.7%): the gcd route reads almost none of the signed NOs.
P3 HOLDS: all 1,148 missed NOs have cancellation in f f~.
P4 unreadable at 14 tuples. C4's plant reads as the one relation, 5.2%
of the population; a flat sample of 14 tuples needs 11 relations,
28.0%.
THE RAYS. The survivors are the dilations of three primitives, up to
reversal, each with a sign twin under x -> -x: (1, 7, 9, 11), signs
(1, 1, 1, -1), f = (1 + x - x^3)(1 + x^3 - x^4 + x^5 + x^8); (2, 10,
11, 15), (-1, -1, 1, -1), and (1, 13, 16, 19), (1, 1, -1, -1), both
sharing 1 - x + x^3 - x^4 + x^5 - x^6 + x^7 - x^9 + x^10. Two of the
six tuples (both signs) have no cancellation in f f~: a shared
reciprocal factor, which Theorem 2 forces. --top 60: 7,802,160 signed
f, 48 survivors over 24 tuples, no new primitive in 41..60. --top 100
--window 60: 62,739,600 signed f, 4,900 +-reciprocal, 80 survivors
over 40 tuples, the dilations of the three, (1, 7, 9, 11) at n = 11,
22, ..., 99, (2, 10, 11, 15) at 15, ..., 90, (1, 13, 16, 19) at 19,
..., 95; R0 40 wanted, none missing; "primitive survivors, new with
61 <= n <= 100: 0". The rays hold to n = 100. None is all-plus, so no
0/1 pentanomial of degree at most 100 is among them. P4 reads at n =
100, 4 relations holding 90% of the 40 tuples at a share of 6.6%, a
reading the rays make trivial (a ray lies on every relation through
its primitive).
RESOURCE. A quarter of 16 C(N, 4) gcds and of 16 C(ND, 4)
factorizations; --rehearse runs N = ND = 20, the default N = 40, ND = 30.
RUN RECORD. Before the orbits: N = 40, 43.5 s, peak 35.5 MB; --top 60,
118.2 s, peak commit 116.2 MB. Through the orbits the N = 40 counts
above reprint exactly, 13.9 s, 18.8 MB, the cover's population
streamed; --top 100 --window 60, 372.6 s, peak commit 158.2 MB, still
rising with N, the cause not found. At --rehearse --window 9, keying the
rays on e rather than its primitive, dropping the mirror, or hard-coding
the window each fails R2
("control failed: run stopped").
"""
import os
import random
import sys
import time
from collections import Counter
from itertools import product
from math import comb, gcd
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
from flint import fmpz_poly # noqa: E402
CHECKS = []
REHEARSE = "--rehearse" in sys.argv
N = 20 if REHEARSE else (int(sys.argv[sys.argv.index("--top") + 1])
if "--top" in sys.argv else 40)
ND = 20 if REHEARSE else 30
LO = (int(sys.argv[sys.argv.index("--window") + 1])
if "--window" in sys.argv else 40)
def check(name, ok, detail=""):
CHECKS.append(bool(ok))
tag = "ok " if ok else "FAIL"
print(f" [{tag}] {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(title)
def penta(e, s):
c = [0] * (e[-1] + 1)
c[0] = 1
for ei, si in zip(e, s):
c[ei] = si
return fmpz_poly(c)
def reverse(f):
return fmpz_poly(list(reversed(f.coeffs())))
def noncyclotomic(f):
_, fl = f.factor()
return [g for g, k in fl for _ in range(k)
if g.degree() > 0 and not g.is_cyclotomic()]
def plusminus_reciprocal(f):
r = reverse(f)
return r == f or r == -f
def read(f):
"""The non-cyclotomic factors of G when f is not +-reciprocal
(empty: not a survivor); None when f is +-reciprocal."""
if plusminus_reciprocal(f):
return None
g = f.gcd(reverse(f))
if g.degree() == 0:
return []
return noncyclotomic(g)
def is_no(f):
return len(noncyclotomic(f)) >= 2
def cancels(e, s):
ee = (0,) + tuple(e)
ss = (1,) + tuple(s)
seen = {}
for i in range(5):
for j in range(5):
if i == j:
continue
d = ee[i] - ee[j]
sg = ss[i] * ss[j]
if d in seen and -sg in seen[d]:
return True
seen.setdefault(d, set()).add(sg)
return False
def tuples(top):
for n in range(4, top + 1):
for q in range(1, n):
for p in range(q + 1, n):
for m in range(p + 1, n):
yield (q, p, m, n)
def mirror(e):
q, p, m, n = e
return (n - m, n - p, n - q, n)
def orbit(e, s):
"""(e, s) under reversal, normalized to constant 1, and x -> -x: every
statistic the route reads is constant on it."""
rs = (s[2] * s[3], s[1] * s[3], s[0] * s[3], s[3])
out = set()
for ee, ss in ((e, s), (mirror(e), rs)):
out.add((ee, ss))
out.add((ee, tuple(si * (-1) ** ei for ei, si in zip(ee, ss))))
return sorted(out)
def signed(top):
"""One signed f of each orbit to n = top, carried with its orbit."""
for e in tuples(top):
if mirror(e) < e:
continue
for s in product((1, -1), repeat=4):
o = orbit(e, s)
if (e, s) == o[0]:
yield e, s, o
def relations():
out = []
for j in product(range(-2, 3), repeat=4):
if not any(j):
continue
if next(x for x in j if x) < 0:
continue
g = 0
for x in j:
g = gcd(g, abs(x))
if g == 1:
out.append(j)
return out
def cover(points, rels):
"""Greedy: the fewest relations holding 90% of points, and the
share of the population, every tuple to n = N, they hold."""
points = set(points)
need = 0.9 * len(points)
on = {j: {t for t in points if sum(a * b for a, b in zip(j, t)) == 0}
for j in rels}
chosen, held = [], set()
while len(held) < need:
j = max(rels, key=lambda r: len(on[r] - held))
if not on[j] - held:
break
chosen.append(j)
held |= on[j]
pop = sum(1 for t in tuples(N)
if any(sum(a * b for a, b in zip(j, t)) == 0 for j in chosen))
return chosen, len(held), pop / comb(N, 4)
def section_controls():
section("CONTROLS")
R = fmpz_poly([1, -3, 1])
v = read(R * fmpz_poly([1, 1, 0, 1]))
control("C1 R (1 + x + x^3): the gcd route reports R", v == [R], f"{v}")
f = penta((3, 4, 7, 8), (1, -1, 1, 1))
control("C2 1 + x^3 - x^4 + x^7 + x^8: a NO, G = 1, not reported",
is_no(f) and read(f) == [], f"{f.factor()}")
def section_route():
section(f"ROUTE -- every signed f to n = {N}; factored to n = {ND}")
t0 = time.time()
surv, recip, total = [], 0, 0
plus = 0
nos = seen = 0
missed, missed_nc = [], []
for e, s, o in signed(N):
w = len(o)
total += w
f = penta(e, s)
v = read(f)
if v is None:
recip += w
continue
if v:
surv.extend(o)
plus += sum(ss == (1, 1, 1, 1) for _, ss in o)
if e[-1] <= ND and is_no(f):
nos += w
if v:
seen += w
else:
missed.extend(o)
if not cancels(e, s):
missed_nc.extend(o)
surv.sort()
print(f" {total} signed f, {recip} +-reciprocal; {len(surv)} survivors "
f"over {len({e for e, _ in surv})} exponent tuples, "
f"{time.time() - t0:.1f} s")
control("C3 the all-plus slice has no survivor", plus == 0)
for e, s in surv:
f = penta(e, s)
nc = read(f)
print(f" survivor e = {e} s = {s}: G's non-cyclotomic "
f"{[str(g) for g in nc]}, cancellation {cancels(e, s)}")
bad = [x for x in surv if x[0][-1] <= ND and not is_no(penta(*x))]
check("P1 every survivor to ND is a NO by factoring", not bad, f"{bad[:3]}")
share = seen / nos if nos else float("nan")
print(f" to n = {ND}: {nos} non-+-reciprocal NOs, {seen} seen by the "
f"gcd ({100 * share:.1f}%), {len(missed)} missed, of them "
f"{len(missed_nc)} without cancellation in f f~")
for e, s in missed_nc[:8]:
print(f" no cancellation: e = {e} s = {s}: "
f"{penta(e, s).factor()}")
check("P3 every missed NO has cancellation in f f~", not missed_nc,
f"{len(missed_nc)} exceptions")
return surv
def section_cover(surv):
section(f"HYPERPLANES -- relations |j_i| <= 2 over the survivor tuples "
f"to n = {N}")
rels = relations()
plant = [t for t in tuples(N) if t[0] + t[1] == t[2]]
chosen, _, s = cover(plant, rels)
control("C4 the planted hyperplane q + p = m is read as one relation",
chosen == [(1, 1, -1, 0)], f"{chosen}, population {100 * s:.1f}%")
pts = sorted({e for e, _ in surv})
S = len(pts)
rng = random.Random(1)
# the indices rng.sample would draw from the list, the list not built
idx = set(rng.sample(range(comb(N, 4)), S)) if S else set()
flat = [t for i, t in enumerate(tuples(N)) if i in idx]
fc, _, fs = cover(flat, rels)
print(f" flat reading: a uniform sample of {S} tuples needs "
f"{len(fc)} relations, population share {100 * fs:.1f}%")
if S < 30:
print(f" cover: unreadable, S = {S} survivor tuples")
return
chosen, held, s = cover(pts, rels)
print(f" cover: {len(chosen)} relations hold 90% of {S} survivor "
f"tuples; population share {100 * s:.1f}%")
for j in chosen:
on = sum(1 for t in pts if sum(a * b for a, b in zip(j, t)) == 0)
print(f" j = {j}: {on} survivor tuples")
check("P4 at most 10 relations, population share below 30%",
len(chosen) <= 10 and s < 0.3)
counts = Counter(s for _, s in surv)
print(f" survivors by sign pattern: {dict(counts.most_common())}")
def primitive(e):
g = 0
for x in e:
g = gcd(g, x)
return tuple(x // g for x in e)
def rays(found):
"""Primitive survivor tuples up to reversal, each with its dilations."""
prim = {}
for e in found:
b = primitive(e)
prim.setdefault(min(b, mirror(b)), set()).add(e)
return prim
def new_in(prim, lo, hi):
return sorted(b for b in prim if lo < b[-1] <= hi)
def section_rays(surv):
section(f"RAYS -- survivors as dilations of coprime ones, to n = {N}")
found = {e for e, _ in surv}
prim = rays(found)
for b in sorted(prim, key=lambda t: t[-1]):
print(f" primitive {b} (n = {b[-1]}): dilations at n = "
f"{sorted({e[-1] for e in prim[b]})}")
# G(x^k) = gcd(f(x^k), f~(x^k)), so a tuple survives exactly when its
# primitive does: R0 checks the gcd engine at the dilations, a
# property, not the detector the kill reads
base = [b for b in prim if b[-1] <= 20]
want = {tuple(k * x for x in c) for b in base for c in (b, mirror(b))
for k in range(1, N // b[-1] + 1)}
control("R0 every dilation to n = N of the n <= 20 primitives is a "
"survivor", want <= found, f"{len(want)} wanted, missing "
f"{sorted(want - found)[:4]}")
if N <= LO:
print(f" R1 not read: the window {LO} < n <= {N} is empty")
return
# a planted new primitive with its mirror, and its double where that
# still lies in the window, must count once
planted = (1, 2, 4, LO + 1)
plant = {planted, mirror(planted)}
if 2 * (LO + 1) <= N:
plant.add(tuple(2 * x for x in planted))
seen = new_in(rays(found | plant), LO, N)
control("R2 the detector counts a planted new primitive once, with its "
"mirror" + (" and double" if len(plant) == 3 else ""),
planted in seen and len(seen) == len(new_in(prim, LO, N)) + 1,
f"{seen}")
new = new_in(prim, LO, N)
print(f" primitive survivors, new with {LO + 1} <= n <= {N}: "
f"{len(new)}" + (f" {new}" if new else ""))
check(f"R1 at most one new primitive survivor in {LO + 1}..{N}",
len(new) <= 1)
def main():
t0 = time.time()
section_controls()
surv = section_route()
section_cover(surv)
section_rays(surv)
print()
print(f"{sum(CHECKS)} of {len(CHECKS)} checks, {time.time() - t0:.1f} s")
return 0 if all(CHECKS) else 1
if __name__ == "__main__":
sys.exit(main())