# -*- coding: utf-8 -*-
"""
PHASE 3 — Constructive degree reduction of Alpoge's normalized Keller counterexample
to an explicit DEGREE <= 3 Keller counterexample in higher dimension.

METHOD (Bass-Connell-Wright style splitting, executed as verified elementary factorization):

Start: G = X + H on Q^3, det J_G = 1 (verified, phase 2), with a verified 3-point collision.

GADGET (one elimination step). Let c*u*v be a monomial term of component i with
deg(u), deg(v) >= 2. Ensure auxiliary coordinates w_u, w_v exist whose map components
are  w_u + u(x)  and  w_v + v(x)  (create them if absent; creation is composition with
the SOURCE-side elementary automorphism  Phi1: (x, w) -> (x, w + u(x)), det = 1).
Then compose on the TARGET side with the elementary automorphism
    Phi2: Y_i -> Y_i - c * Y_{slot(u)} * Y_{slot(v)}     (all other coords fixed)
which is unitriangular (slot(u), slot(v) != i), det = 1. Since the slot components are
w_u + u and w_v + v, the i-component becomes
    F_i - c*(w_u*w_v + w_u*v + w_v*u + u*v)
and the monomial c*u*v is EXACTLY cancelled, replaced by terms of strictly lower degree.

INVARIANTS PRESERVED (and machine-verified at every step):
  * F_new = Phi2 ∘ F_old  exactly (symbolic identity, independent construction paths)
  * Phi2 unitriangular (structural check: modified component's correction never
    references the modified coordinate itself)
  * every aux component is  w + (monomial of degree >= 2 in PREVIOUS variables)
    => Phi1 elementary, linear part stays identity
  * det J_new = det J_old = 1 by chain rule over the verified factorization
  * the 3-point collision lifts explicitly:  new coords take value -u(p), so all
    aux slots evaluate to 0 at the lifted points and images are unchanged
  * target monomial coefficient becomes exactly 0

TERMINATION: each step replaces a degree-D monomial (D>=4) with monomials of degree
max(2, 1+deg u, 1+deg v) <= D-1; the multiset of degrees strictly decreases.

Result: an explicit polynomial map of degree <= 3 on Q^N, det J = 1 identically,
mapping three distinct rational points to one point. By Wang's theorem (degree <= 2
Keller maps are invertible), degree 3 is SHARP.
"""
import sympy as sp
import json, time, random

t0 = time.time()
random.seed(20260721)

x, y, z = sp.symbols('x y z')

# Alpoge / Claude Fable 5 base map
f1 = (1 + x*y)**3 * z + y**2 * (1 + x*y) * (4 + 3*x*y)
f2 = y + 3*x*(1 + x*y)**2 * z + 3*x*y**2 * (4 + 3*x*y)
f3 = 2*x - 3*x**2*y - x**3*z

# Normalized (phase 2): G = L^{-1} F = (f3/2, f2, f1); det J_G = 1, G = X + H
F = [sp.expand(f3/sp.Integer(2)), sp.expand(f2), sp.expand(f1)]
V = [x, y, z]

pts = [
    [sp.Integer(0),  sp.Integer(0),      sp.Rational(-1, 4)],
    [sp.Integer(1),  sp.Rational(-3, 2), sp.Rational(13, 2)],
    [sp.Integer(-1), sp.Rational(3, 2),  sp.Rational(13, 2)],
]

def check(label, ok, fatal=True):
    print(f"[{'PASS' if ok else 'FAIL'}] {label}")
    if fatal and not ok:
        raise SystemExit("FATAL: verification failed at: " + label)
    return ok

def images():
    return [tuple(sp.expand(c.subs(dict(zip(V, p)))) for c in F) for p in pts]

# ---- entry gates ----------------------------------------------------------
im = images()
check("entry: 3-point collision on normalized map", im[0] == im[1] == im[2] and len({tuple(p) for p in pts}) == 3)
J0 = sp.Matrix([F]).T.jacobian(V)
check("entry: det J == 1 identically (3x3 symbolic)", sp.expand(J0.det()) == 1)
check("entry: linear part == I", J0.subs({x: 0, y: 0, z: 0}) == sp.eye(3))

# ---- engine ---------------------------------------------------------------
aux_registry = {}   # monic monomial expr -> aux symbol
steps = []
aux_n = 0

def high_monomial():
    """(i, coeff, exps) of a max-total-degree monomial with deg > 3 in H, else None."""
    best = None
    for i in range(len(V)):
        h = sp.expand(F[i] - V[i])
        if h == 0:
            continue
        p = sp.Poly(h, *V)
        for mono, c in zip(p.monoms(), p.coeffs()):
            d = sum(mono)
            if d > 3 and (best is None or d > best[3]):
                best = (i, c, mono, d)
    return best

def monomial_expr(exps):
    return sp.prod([V[k]**exps[k] for k in range(len(exps))])

def split(exps, D):
    """u = first ceil(D/2) variable-powers, v = remainder; both deg >= 2."""
    a = (D + 1) // 2
    u_e = [0]*len(exps); rem = list(exps); got = 0
    for k in range(len(exps)):
        take = min(rem[k], a - got)
        u_e[k] = take; rem[k] -= take; got += take
        if got == a:
            break
    u_e += [0] * (len(V) - len(u_e)); rem += [0] * (len(V) - len(rem))
    return monomial_expr(u_e), monomial_expr(rem)

def get_aux(m_expr):
    """Aux symbol whose component is w + m_expr; create via elementary Phi1 if absent."""
    global aux_n
    if m_expr in aux_registry:
        return aux_registry[m_expr], False
    aux_n += 1
    w = sp.Symbol(f'a{aux_n}')
    # structural elementary-ness: m_expr uses only PREVIOUS vars, degree >= 2
    assert all(s in V for s in m_expr.free_symbols) and sp.Poly(m_expr, *V).total_degree() >= 2
    V.append(w)
    F.append(sp.expand(w + m_expr))
    for p in pts:
        p.append(sp.expand(-m_expr.subs(dict(zip(V[:len(p)], p)))))
    aux_registry[m_expr] = w
    return w, True

step_no = 0
while True:
    tgt = high_monomial()
    if tgt is None:
        break
    step_no += 1
    i, c, exps, D = tgt
    m_expr = monomial_expr(exps)
    u, v = split(exps, D)
    wu, new_u = get_aux(u)
    wv, new_v = get_aux(v)

    F_old_i = F[i]
    slot_u, slot_v = V.index(wu), V.index(wv)

    # Phi2 unitriangular: correction references slots != i (structural proof of det=1)
    assert slot_u != i and slot_v != i

    # target-side composition: F_new_i = F_old_i - c * F[slot_u] * F[slot_v]
    comp_path = sp.expand(F_old_i - c * F[slot_u] * F[slot_v])
    # independent direct-formula path
    direct_path = sp.expand(F_old_i - c*(wu*wv + wu*v + wv*u + u*v))
    assert sp.expand(comp_path - direct_path) == 0, "factorization identity failed"
    F[i] = comp_path

    # target monomial exactly eliminated
    coeff_after = sp.Poly(sp.expand(F[i] - V[i]), *V).coeff_monomial(m_expr)
    assert coeff_after == 0, "monomial not eliminated"

    # collision must survive every step
    im = images()
    assert im[0] == im[1] == im[2], "collision broken"

    steps.append({
        "step": step_no, "component": i, "coeff": str(c), "monomial": str(m_expr),
        "degree": D, "u": str(u), "v": str(v),
        "aux_u": str(wu), "aux_v": str(wv),
        "new_aux_created": [b for b, n in ((str(wu), new_u), (str(wv), new_v)) if n],
        "dimension_after": len(V),
        "max_degree_after": max(sp.Poly(sp.expand(F[k]-V[k]), *V).total_degree()
                                 if sp.expand(F[k]-V[k]) != 0 else 0 for k in range(len(V)))
    })
    print(f"step {step_no:2d}: eliminated deg-{D} monomial {c}*{m_expr} from F[{i}]  "
          f"(u={u}, v={v})  dim={len(V)}  maxdeg={steps[-1]['max_degree_after']}")

N = len(V)
print()
print(f"reduction complete: {step_no} elimination steps, dimension 3 -> {N}")

# ---- final verification battery -------------------------------------------
# (1) degree audit
degs = []
mono_total = 0
for k in range(N):
    h = sp.expand(F[k] - V[k])
    if h == 0:
        degs.append(0); continue
    p = sp.Poly(h, *V)
    degs.append(p.total_degree())
    mono_total += len(p.monoms())
    assert min(sum(m) for m in p.monoms()) >= 2, "linear/constant term leaked into H"
check(f"final: deg(H_k) <= 3 for all {N} components (max = {max(degs)})", max(degs) <= 3)
check(f"final: H has no terms of degree < 2 (linear part = identity)", True)

# (2) J(0) == I
zero = {v_: 0 for v_ in V}
Jbig = sp.Matrix([F]).T.jacobian(V)
check("final: J(0) == Identity", Jbig.subs(zero) == sp.eye(N))

# (3) det J == 1: chain proof already established per-step (asserted factorizations);
#     independent confirmation: exact rational det at 30 random points
ok_det = True
for trial in range(30):
    sub = {v_: sp.Rational(random.randint(-7, 7), random.randint(1, 5)) for v_ in V}
    d = Jbig.subs(sub).det()
    if d != 1:
        ok_det = False
        print("  det mismatch at", sub, "->", d)
        break
check("final: det J == 1 at 30 random rational points (exact arithmetic)", ok_det)

# (4) collision, dual evaluation paths (subs and xreplace)
imA = [tuple(sp.expand(c.subs(dict(zip(V, p)))) for c in F) for p in pts]
imB = [tuple(sp.expand(c.xreplace(dict(zip(V, p)))) for c in F) for p in pts]
check("final: 3 lifted points map to SAME image (subs path)", imA[0] == imA[1] == imA[2])
check("final: 3 lifted points map to SAME image (xreplace path)", imB[0] == imB[1] == imB[2])
check("final: dual evaluation paths agree", imA == imB)
check("final: the 3 lifted points are pairwise distinct",
      len({tuple(p) for p in pts}) == 3)

art = {
    "artifact": "Explicit degree-3 Keller counterexample to the Jacobian Conjecture",
    "date": "2026-07-21",
    "provenance": "Constructed from the Alpoge/Claude-Fable-5 dim-3 counterexample (2026-07-20) "
                  "by verified elementary-factorization degree reduction (BCW-style splitting).",
    "dimension": N,
    "variables": [str(v_) for v_ in V],
    "components": [str(sp.expand(F[k])) for k in range(N)],
    "degree_of_H_per_component": degs,
    "total_monomials_in_H": mono_total,
    "max_degree": max(degs),
    "collision_points": [[str(c) for c in p] for p in pts],
    "collision_image": [str(c) for c in imA[0]],
    "elimination_steps": steps,
    "det_proof": "chain rule over machine-verified elementary factorization "
                 "(every Phi unitriangular, every composition identity checked symbolically) "
                 "+ 30 exact random-rational point confirmations",
    "sharpness": "Wang (1980): every Keller map of degree <= 2 is invertible. "
                 "Hence degree 3 is the minimal possible degree for any counterexample.",
    "elapsed_sec": round(time.time() - t0, 2)
}
with open('post-jc-program/degree3_counterexample.json', 'w', encoding='utf-8') as fh:
    json.dump(art, fh, indent=2)

print()
print("=" * 66)
print(f"DEGREE-3 KELLER COUNTEREXAMPLE CONSTRUCTED AND VERIFIED")
print(f"  dimension        : {N}")
print(f"  max degree       : {max(degs)}  (SHARP: degree 2 is impossible by Wang's theorem)")
print(f"  monomials in H   : {mono_total}")
print(f"  elimination steps: {step_no}")
print(f"  elapsed          : {art['elapsed_sec']}s")
print(f"  artifact         : degree3_counterexample.json")
