"""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())