isogeny.py

"""isogeny.py -- Boyd's F = 1 + u + 1/u + v + 1/v stays irreducible under
every isogeny of the torus, so the reciprocal pentanomials with a
reducible non-cyclotomic part lie on finitely many rays given Schinzel's
Theorem 2 with its non-reciprocity hypothesis dropped.

QUESTION. The reciprocal 0/1 pentanomials are f = x^p F(x^a, x^b), a = p,
b = p - q. Does a printed structure theorem on the factors of F(x^n),
n in Z^2 (Bombieri and Zannier's, as Schinzel extends it), put the n at
which K F(x^n) is reducible, K removing the cyclotomic factors, on
finitely many lines through 0?

THE READING (as printed). A. Schinzel, Reducibility of lacunary
polynomials XII, Acta Arith. 90 (1999) 273-289: Theorem BZ is for two
coprime P, Q; Theorems 1-4 on K F(x^n) assume K F = L F (Theorem 1), J
F(x^n) not reciprocal (Theorems 2 and 4), or a ratio J F(x^-n)/J
F^tau(x^n) outside the normal closure of the coefficient field (Theorem
3, its (10)); and after Theorem 4: "It is conjectured that a similar
reducibility condition holds without the assumption that JF(x^n) is not
reciprocal and over any finite extension of Q". Here F(x^-n) = F(x^n),
so K F = F, L F = 1, J F(x^n) is reciprocal and the ratio is 1: every
hypothesis fails. Written instead as G(x^n'), G = 1 + x1 + x2 + x3 + x4
and n' = (q, p, 2p - q, 2p) (the form Filaseta and Kalogirou use), K G =
L G holds, but every reciprocal f has rho n' = 0 at rho = (1, 0, 1, -1),
h(rho) = 1, the alternative (5) of Theorem 1 and the conclusion of
Theorem BZ for G and its reversal, so both say nothing there once their
constants are at least 1. For BZ its own statement forces c1(G,
reversal) >= 1, as the reciprocal f 1 + x + x^3 + x^5 + x^6 has a
non-cyclotomic part not 1; for Theorem 1, whose M the theorem supplies,
(22) puts c3(G, M) at a maximum of c9 and of BZ's c1 at each irreducible
factor of K G(z^M) paired with its reversal, which reaches the pair (G,
reversal) at M = I, the rest left to the proof. Schinzel's own proof of
Corollary 1 passes the reciprocal case the same way, its c6 at least 2.
Theorems 2-4 fail for G too, J G(x^n') being f, and so for every writing
f = J H(x^nu). M. Filaseta, arXiv:2207.11648 (2022), p. 2, reports the
extension to the non-cyclotomic part "in the case that f(x) is not
reciprocal". The theorem route is closed but for c3(G, M) at an M other
than I.

WHAT THE OBJECT GIVES A STRENGTHENING. Theorem 2 of XII, its
necessity half with its hypothesis dropped, would read: K F(x^n), n not
0, is reducible over Q only if n = vN, N in M_(r,2)(Z) of rank r and
height at most c4(F), with K F(y^N) = F1 F2, Fi in Q[y], and K Fi(x^v)
not in Q (F read as the polynomial uvF). At r = 2 that needs F(y^N)
reducible at a nonsingular N; at r = 1, n lies on one of finitely many
lines. The conjecture printed after Theorem 4 has Theorem 4's shape,
finite sets R and S of matrices with no factorization named, so it is
decided here only with R built as in the proof's (49), the nonsingular
M of bounded height with K F(y^(MN)) reducible; the form assumed here
is Theorem 2's. So the
reducible reciprocal f would lie on finitely many rays if F(y^N) is
irreducible at every nonsingular N, u = y^(N row 1), v = y^(N row 2).

PROOF (by hand, before the engine). C: F = 0 in the torus. F_u = 1 -
1/u^2 and F_v = 1 - 1/v^2 vanish together only at (+-1, +-1), where F is
5, 1, 1, -3: C is smooth. Its Newton polygon is the diamond with vertices
+-e1, +-e2, one interior point, four edges of lattice length 1, each edge
polynomial a binomial: C is nondegenerate, its smooth model of genus 1,
with one place at infinity per edge, at which (ord u, ord v) is the
edge's normal, +-(1, 1) or +-(1, -1). F is irreducible: the diamond's
only lattice decomposition is two segments along (1, 1) and (1, -1), and
a product of those binomials has no constant term. Now y -> (u, v) is an
isogeny phi, etale; phi^-1(C) is smooth, so its components are disjoint,
permuted transitively by ker phi. If it is disconnected, a maximal
proper subgroup containing a component's stabiliser has prime index p,
and the cover it gives is cyclic of degree p and disconnected: a p-th
root of some u^c1 v^c2, c not in pZ^2, adjoined to the function field of
C, and split, so u^c1 v^c2 = const g^p on C. At the four places p
divides c1 + c2 and c1 - c2. For p odd that puts c in pZ^2. For p = 2,
c = (1, 1) mod 2 and uv would be const g^2; div(uv) = 2P - 2Q, P, Q the
places of normal +-(1, 1), so div g = P - Q, principal only in genus 0.
So F(y^N) is irreducible over C, and so over Q, at every nonsingular N;
it is no factor of a binomial, its zero set being no torsion coset, so
K F(y^N) = F(y^N).

PREDICTIONS (the box frozen first; the Hermite family added before the
first run).
P2. F(y^N) is irreducible over Q at every nonsingular N with entries in
    [-3, 3] (BOX) and at every Hermite form of determinant at most DET.
CONTROLS. u - v^2 at N = diag(2, 1) gives y1^2 - y2^2, two factors: the
same mechanism (u a square on its curve). F itself factors as one, and
F at (+-1, +-1) prints the smoothness step's four values.
KILL: any nonsingular N in either family with F(y^N) reducible.

FINDINGS (P2 holds; the kill missed). "nonsingular N: 2112, F(y^N)
reducible: 0"; "Hermite forms: 8299, largest det 100, F(y^N) reducible:
0", 8299 the sum of sigma(d) over d <= 100; the plant u - v^2 at diag(2,
1) "splits  (2 factors)"; F at (+-1, +-1) prints [5.0, 1.0, 1.0,
-3.0]. So the irreducibility the proof gives over C holds over Q, as
computed, at every isogeny of degree at most 100, and the conditional
reading stands: given Theorem 2 of XII
without its non-reciprocity hypothesis, the reciprocal f with a
reducible non-cyclotomic part lie on finitely many rays, their height
bound c4(F), computable if the statement's constant is, as Schinzel's
is under his hypothesis, and never printed.

RUN RECORD. Bare: 6 of 6 checks, 3.0 s, flint's fmpz_mpoly factor. The
Hermite count's check, the enumeration's own sum, could not fail and
left; the count stays printed. After: 5 of 5 checks, 3.0 s.
"""
import sys
import time
from itertools import product

from flint import fmpz_mpoly_ctx

CHECKS = []
BOX = 3
DET = int(sys.argv[sys.argv.index("--det") + 1]) if "--det" in sys.argv \
    else 100
CTX = fmpz_mpoly_ctx.get(("y1", "y2"), "lex")
F_TERMS = [((0, 0), 1), ((1, 0), 1), ((-1, 0), 1), ((0, 1), 1),
           ((0, -1), 1)]


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 pull(terms, N):
    """terms(u, v) at u = y^(N row 1), v = y^(N row 2), times the monomial
    that makes it a polynomial with no monomial factor."""
    d = {}
    for (i, j), c in terms:
        e = (i * N[0][0] + j * N[1][0], i * N[0][1] + j * N[1][1])
        d[e] = d.get(e, 0) + c
    d = {e: c for e, c in d.items() if c}
    lo = (min(e[0] for e in d), min(e[1] for e in d))
    return CTX.from_dict({(e[0] - lo[0], e[1] - lo[1]): c
                          for e, c in d.items()})


def nfactors(terms, N):
    _, fac = pull(terms, N).factor()
    return sum(m for p, m in fac if p.total_degree() > 0)


def hermite(top):
    """Lower-triangular [[a, 0], [b, c]], a, c > 0, 0 <= b < c, ac <= top:
    one per lattice of the columns, so one per isogeny up to a change of
    the y coordinates."""
    for a in range(1, top + 1):
        for c in range(1, top // a + 1):
            for b in range(c):
                yield ((a, 0), (b, c))


def section_controls():
    print("CONTROLS")
    plant = [((1, 0), 1), ((0, 2), -1)]
    n = nfactors(plant, ((2, 0), (0, 1)))
    check("u - v^2 at diag(2, 1) splits", n == 2, f"{n} factors")
    n = nfactors(F_TERMS, ((1, 0), (0, 1)))
    check("F itself is irreducible", n == 1, f"{n} factor")
    vals = [1 + u + 1 / u + v + 1 / v for u in (1, -1) for v in (1, -1)]
    check("F at (+-1, +-1) is nonzero (C smooth)", all(vals), f"{vals}")


def section_box():
    print(f"BOX: every nonsingular N with entries in [-{BOX}, {BOX}]")
    total = bad = 0
    for e in product(range(-BOX, BOX + 1), repeat=4):
        N = ((e[0], e[1]), (e[2], e[3]))
        if e[0] * e[3] - e[1] * e[2] == 0:
            continue
        total += 1
        if nfactors(F_TERMS, N) != 1:
            bad += 1
            print(f"    reducible at {N}")
    print(f"    nonsingular N: {total}, F(y^N) reducible: {bad}")
    check("F(y^N) irreducible at every nonsingular N in the box",
          total and bad == 0)


def section_hermite():
    print(f"HERMITE: every isogeny of degree at most {DET}")
    total = bad = 0
    worst = 0
    for N in hermite(DET):
        total += 1
        n = nfactors(F_TERMS, N)
        if n != 1:
            bad += 1
            print(f"    reducible at {N}")
        worst = max(worst, N[0][0] * N[1][1])
    print(f"    Hermite forms: {total}, largest det {worst}, "
          f"F(y^N) reducible: {bad}")
    check("F(y^N) irreducible at every isogeny of degree <= DET",
          bad == 0)


def main():
    t0 = time.time()
    section_controls()
    section_box()
    section_hermite()
    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())