reversal.py
Checks: COLLIDE: The reversal reduction theorem.
Cited on: COLLIDE.
To run it: save reversal.py; needs flint.
"""reversal.py -- the Filaseta-Solan question read through the reversal:
a 0/1 pentanomial whose non-cyclotomic part is reducible shares a
non-cyclotomic factor with its reversal, so an exact gcd replaces
factoring.
QUESTION. f = 1 + x^q + x^p + x^m + x^n, 0 < q < p < m < n. M. Filaseta
and I. Solan (An extension of a theorem of Ljunggren, Math. Scand. 84
(1999) 5-10, Theorem 1) prove that f with its irreducible reciprocal
factors removed is 1 or irreducible, and leave open whether the same
holds with only its cyclotomic factors removed; they state it "in the
special case that n is exactly one of 2m, 2q, 2p, m + p, p + q, or
m + q", the proof not printed, and report no computation. Is the
non-cyclotomic part of f ever reducible?
THE REDUCTION (written before the engine). Write f~ = x^n f(1/x) and
G = gcd(f, f~) over Z.
(1) f NOT RECIPROCAL. The non-cyclotomic part of f is reducible
exactly when G has a non-cyclotomic irreducible factor. If f had
no non-cyclotomic reciprocal irreducible factor, its
non-cyclotomic part would be its non-reciprocal part, 1 or
irreducible by Theorem 1; so some non-cyclotomic reciprocal w
divides f, and w~ = +-w divides f~. Conversely let u | G be
irreducible and not cyclotomic. If u is reciprocal, f = u v with v
not reciprocal, so v has a non-reciprocal factor, which is not
cyclotomic. If u is not reciprocal, u | f~ puts u~ in f beside u.
Either way f has two non-cyclotomic factors.
(2) f RECIPROCAL (n = 2p, m = n - q). G = f; the non-cyclotomic part
is reducible exactly when f has at least two non-cyclotomic
irreducible factors, with multiplicity: f is factored outright.
(3) f -> f~ sends (q, p, m) to (n - m, n - p, n - q) and keeps the
verdict, so one of each pair, the lexicographically smaller, is
read.
(4) THE SIX CASES ARE WHERE f - f~ CANCELS (by hand, after the
run). A shared zero of f and f~ is a zero of f - f~ = x^q + x^p
+ x^m - x^(n-m) - x^(n-p) - x^(n-q). Setting one of {q, p, m}
equal to one of {n - m, n - p, n - q}, over all nine pairs, gives
n in {m + q, p + q, 2q, m + p, 2p, 2m}: exactly the six cases. Off
them a shared zero is a zero of a six-term +-1 polynomial with no
cancellation. Known beside it (E. Bombieri and U. Zannier, as
Theorem 3 of M. Filaseta and A. Kalogirou, arXiv:2508.12242): a
shared non-cyclotomic factor forces j . (q, p, m, n) = 0 for some
nonzero integer j with |j| below a computable constant, so every
NO lies on finitely many hyperplanes, none named.
(5) THE SIX CASES, PROVED FOR NON-RECIPROCAL f (by hand, after the
run). An off-diagonal equality cancels two pairs at once (q = n -
m iff m = n - q, likewise p = n - m and q = n - p), leaving
f - f~ a monomial times x^a - x^(n-a), a in {p, q, m}. A diagonal
one (n = 2q, 2p or 2m) cancels one pair; with a < b the other two
of {q, p, m} and d = n - a - b, the rest is x^a + x^b - x^(a+d) -
x^(b+d) = x^a (1 + x^(b-a)) (1 - x^d), Laurent when d < 0.
Either way every nonzero
zero of f - f~ is a root of unity, unless f - f~ = 0, which is f
reciprocal. So in the six cases G is cyclotomic for every
non-reciprocal f, and (1) leaves its non-cyclotomic part 1 or
irreducible (a theorem, given their Theorem 1). Two of the six
values can be equal only as 2p = m + q (2q < p + q < m + q <
m + p < 2m and p + q < 2p < m + p), and n = 2p = m + q is exactly
f reciprocal. So if
their "exactly one of" excludes an n equal to two of the values,
(5) proves every case they stated; if it does not, the reciprocal
f are the remainder, which (5) does not reach. SIX prints the
check.
DESIGN. Polynomials are python-flint's fmpz_poly; gcd and factor are
exact over Z, a factor's cyclotomy is flint's is_cyclotomic. It is
the one script here that needs python-flint (pip install
python-flint).
C1 POSITIVE: R h, R = x^2 - 3x + 1 (reciprocal, not cyclotomic),
h = 1 + x + x^3: branch (1) reports R. R^2: branch (2) reports two
non-cyclotomic factors.
C2 NEGATIVE: 1 + x + x^3 + x^4 + x^7 = Phi_5 (1 - x^2 + x^3): G = Phi_5,
not reported. R Phi_5, reciprocal with one non-cyclotomic factor:
not reported.
C3 CROSS: every pentanomial with n <= 30, unhalved, read by the gcd
route and by flint's full factorization of f; the verdicts agree
on every one, and the reducible count is pentanomial.py's P6 print
(made with sympy).
C4 COUNT: the halved enumeration expanded, 2 per non-reciprocal
representative and 1 per reciprocal, totals C(N, 4).
SCAN: n = 4..N, per decade of n the representatives, how many
non-reciprocal ones have deg G > 0 (a reciprocal f has G = f), and
survivors.
Added after the run, on review:
C5 two NOs planted in the scan's own loop, one per branch: at
(1, 3, 4, 7) f becomes R f, at the reciprocal (1, 3, 5, 6) R^2 f,
R = x^2 - 3x + 1, and a scan to 30 must find these two alone.
SIX for n <= 40: f - f~ for every non-reciprocal f in the six cases
has only cyclotomic factors besides x; C6, the control, finds
f - f~ with a non-cyclotomic factor off the six cases; and an n
equal to two of the six values occurs only at a reciprocal f.
PREDICTIONS (fixed before the engine).
C1-C4 as written; C3 reads 3,007 reducible of 27,405.
SCAN: 0 survivors to N. A survivor is a NO to the question, printed
with its factorization and its n read against the six cases.
KILL. The line "survivors: s" over n = 4..N, both branches summed; s > 0
kills YES to degree N. C1 is read before the scan; if it misses, the
scan is not read.
RESOURCE. About 10 us per representative at degree 100. --rehearse runs
N = 30; --top N sets the scan's top degree.
FINDINGS (run at --top 180). Every check held: 7 of 7.
C1 R h reports [x^2 - 3x + 1]; R^2 reports it twice.
C2 1 + x + x^3 + x^4 + x^7: G = x^4 + x^3 + x^2 + x + 1, not reported;
R Phi_5 not reported.
C3 27405 pentanomials, 3007 reducible, the two routes agree on 27405.
C4 42296805 against C(180, 4) = 42296805.
SCAN 21,150,405 representatives over n = 4..180, 4,005 of them
reciprocal (n/2 - 1 at each even n, consistent with C4); 2,076,390
non-reciprocal ones with deg G > 0, every such G cyclotomic:
survivors: 0. GIVEN THEOREM 1, THE NON-CYCLOTOMIC PART OF EVERY
0/1 PENTANOMIAL OF DEGREE AT MOST 180 IS 1 OR IRREDUCIBLE. Per
decade of n the share of non-reciprocal representatives with
deg G > 0 runs from 9.4% (161..170) to 14.0% (4..10).
At --rehearse after review: C5 finds its two plants alone; SIX
reads 13680 non-reciprocal six-case f, 0 with a non-cyclotomic
factor of f - f~, against 65186 of 77520 off them (C6); an n equal
to two of the values at 190 reciprocal f and 0 others.
Tier: rule (verified n <= 180, exhaustively, every verdict exact over
Z), the non-reciprocal verdicts resting on Filaseta and Solan's
Theorem 1, whose proof is printed; the reduction (1)-(3) and the six
cases (5) for non-reciprocal f are theorems given that Theorem 1, (4)
a property.
RUN RECORD. --rehearse 7 of 7, 4.0 s. --top 100: 7 of 7, 27.1 s, peak
29 MB. --top 180: 7 of 7, 397.8 s, peak commit 173.5 MB under a memory
guard, the estimate 7 minutes. The first draft inlined the gcd in the
scan, outside the path C1 tests; both now read through read(). The
per-decade rows were printed labelled "n <= b"; they count n in
b - 9..b, and the label now says so. The question as frozen
before the engine put RAM under 100 MB, flint's polys freed per
step, yet the peak commit rose with N (13.2 MB at 30, 29 at 100, 173.5
at 180); the cause is not found. Review moved the loop into scan() for
C5 and added SIX: --top 100 11 of 11, 40.3 s, peak 40.1 MB, its ten
rows equal to the --top 180 run's first ten; then C5's second plant,
read at --rehearse.
"""
import os
import sys
import time
from math import comb
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
from flint import fmpz_poly # noqa: E402
CHECKS = []
REHEARSE = "--rehearse" in sys.argv
TOP = 30 if REHEARSE else (int(sys.argv[sys.argv.index("--top") + 1])
if "--top" in sys.argv else 100)
SIX = ("2m", "2p", "2q", "m+p", "m+q", "p+q")
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(q, p, m, n):
c = [0] * (n + 1)
for e in (0, q, p, m, n):
c[e] = 1
return fmpz_poly(c)
def reverse(f):
return fmpz_poly(list(reversed(f.coeffs())))
def noncyclotomic(f):
"""Non-cyclotomic irreducible factors of f, with multiplicity."""
_, fl = f.factor()
return [g for g, e in fl for _ in range(e)
if g.degree() > 0 and not g.is_cyclotomic()]
def read(f):
"""(whether G = gcd(f, f~) is non-constant, the non-cyclotomic
factors that make f's non-cyclotomic part reducible by (1) or (2),
[] when it is 1 or irreducible). The scan and the controls both
read through here."""
r = reverse(f)
if r == f or r == -f:
nc = noncyclotomic(f)
return True, (nc if len(nc) >= 2 else [])
g = f.gcd(r)
if g.degree() == 0:
return False, []
return True, noncyclotomic(g)
def verdict(f):
return read(f)[1]
def direct(f):
"""The same verdict by factoring f alone."""
nc = noncyclotomic(f)
return nc if len(nc) >= 2 else []
def six(q, p, m, n):
vals = (2 * m, 2 * p, 2 * q, m + p, m + q, p + q)
return [s for s, v in zip(SIX, vals) if v == n]
def section_controls():
section("CONTROLS")
R = fmpz_poly([1, -3, 1])
h = fmpz_poly([1, 1, 0, 1])
v = verdict(R * h)
control("C1 R h: the gcd route reports R", v == [R], f"{v}")
v = verdict(R * R)
control("C1 R^2: the reciprocal branch reports two factors",
v == [R, R], f"{v}")
f = penta(1, 3, 4, 7)
g = f.gcd(reverse(f))
control("C2 1 + x + x^3 + x^4 + x^7: G = Phi_5, not reported",
g == fmpz_poly.cyclotomic(5) and verdict(f) == [], f"G = {g}")
v = verdict(R * fmpz_poly.cyclotomic(5))
control("C2 R Phi_5: one non-cyclotomic factor, not reported",
v == [], f"{v}")
def section_cross():
section("CROSS -- every pentanomial with n <= 30, two routes")
total = red = agree = 0
for n in range(4, 31):
for q in range(1, n):
for p in range(q + 1, n):
for m in range(p + 1, n):
f = penta(q, p, m, n)
total += 1
_, fl = f.factor()
red += sum(e for _, e in fl) > 1
agree += bool(verdict(f)) == bool(direct(f))
print(f" {total} pentanomials, {red} reducible, the two routes "
f"agree on {agree}")
control("C3 the routes agree on every one, 3,007 reducible of 27,405",
total == 27405 and agree == total and red == 3007)
def scan(top, plant=None, show=True):
"""Read one of each reversal pair with n <= top; at a tuple of the
dict plant, f is replaced by its value times f, a planted NO."""
t0 = time.time()
expanded, found = 0, []
row = [0, 0, 0]
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):
rq, rp, rm = n - m, n - p, n - q
if (q, p, m) > (rq, rp, rm):
continue
rec = (q, p, m) == (rq, rp, rm)
expanded += 1 if rec else 2
row[0] += 1
f = penta(q, p, m, n)
if plant and (q, p, m, n) in plant:
f = plant[(q, p, m, n)] * f
nonconstant, v = read(f)
row[1] += nonconstant and not rec
if v:
found.append((q, p, m, n))
row[2] += 1
if show:
print(f" SURVIVOR (q, p, m, n) = "
f"{(q, p, m, n)} six cases "
f"{six(q, p, m, n)}: {f.factor()}")
if show and (n % 10 == 0 or n == top):
print(f" n {max(4, n - 9):3d}..{n:3d}: {row[0]:8d} representatives, "
f"{row[1]:7d} with deg G > 0, {row[2]} survivors, "
f"{time.time() - t0:6.1f} s")
row = [0, 0, 0]
return expanded, found
def section_scan():
section(f"SCAN -- n = 4..{TOP}, one of each reversal pair; the deg G > 0"
" count is over non-reciprocal f")
R = fmpz_poly([1, -3, 1])
plant = {(1, 3, 4, 7): R, (1, 3, 5, 6): R * R}
_, found = scan(30, plant=plant, show=False)
control("C5 NOs planted in the loop, one per branch, are its only "
"survivors", sorted(found) == sorted(plant), f"{found}")
expanded, found = scan(TOP)
check("C4 the expanded count is C(N, 4)", expanded == comb(TOP, 4),
f"{expanded} against {comb(TOP, 4)}")
print(f" survivors: {len(found)}")
check("SCAN no survivor", not found)
def section_six():
section("SIX -- f - f~ over the six cases, n <= 40")
x = fmpz_poly([0, 1])
counts = {True: [0, 0], False: [0, 0]}
twice = {True: 0, False: 0}
for n in range(4, 41):
for q in range(1, n):
for p in range(q + 1, n):
for m in range(p + 1, n):
f = penta(q, p, m, n)
r = reverse(f)
rec = r == f
hits = len(six(q, p, m, n))
if hits >= 2:
twice[rec] += 1
if rec:
continue
_, fl = (f - r).factor()
bad = any(g.degree() > 0 and g != x
and not g.is_cyclotomic() for g, _ in fl)
counts[hits > 0][0] += 1
counts[hits > 0][1] += bad
print(f" non-reciprocal, in the six cases: {counts[True][0]}, f - f~ "
f"with a non-cyclotomic factor {counts[True][1]}; off them: "
f"{counts[False][0]}, with one {counts[False][1]}")
print(f" n equal to two of the six values: reciprocal {twice[True]}, "
f"non-reciprocal {twice[False]}")
control("C6 the test fires off the six cases", counts[False][1] > 0)
check("SIX f - f~ has only cyclotomic factors in every six case",
counts[True][1] == 0)
check("SIX two of the six values meet only at the reciprocal f",
twice[False] == 0 and twice[True] > 0)
def main():
t0 = time.time()
section_controls()
section_cross()
section_six()
section_scan()
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())