"""
Interval certificate that the 2O and 2I critical values of β are global minima.

β(I) = Σ_C δ_C sin²θ_C (1 - max_a (a·I)²)  on the unit sphere, with
c = Σ δ_C sin²θ_C = 3/4.  β is even, so it is enough to cover a
hemisphere; we use the three positive cube faces
    +X: (1,x,y), +Y: (x,1,y), +Z: (x,y,1),   (x,y) ∈ [-1,1]²
which are a fundamental domain for I ~ -I.

Lipschitz lemma (used as a discard test).  For unit a,I and a tangent
unit v, |∂_v (a·I)²| = 2|(a·I)(a·v)| ≤ 2|u|√(1-u²) ≤ 1, so each
(a·I)² is 1-Lipschitz on the sphere (geodesic distance), and so is
the pointwise max over a finite set.  Hence
    |β(I)-β(J)| ≤ c · d_geo(I,J) = (3/4) arccos(I·J)
(whenever I·J ≥ 0; in general (3/4) arccos(clip(I·J,-1,1))).

On any cube-face rectangle the spherical image is a spherically convex
quad (sides are great circles, being plane sections through the origin).
The geodesic radius from the image of the rectangle centre is therefore
attained at a vertex.

Active-set / quadratic test.  On a region where a single choice of
axes is uniquely maximal, β(I) = c - Iᵀ M I with M fixed, so
β(I) ≥ c - λ_max(M) for every unit I (hence on the region).

Branch-and-bound: subdivide until every box is discarded by the
Lipschitz test or by the quadratic test.  Boxes that contain a global
minimiser cannot be discarded by Lipschitz; they are discarded once
the active set is certified constant, because c-λ_max equals the
candidate value.
"""
from __future__ import annotations
import json, time, sys
from itertools import combinations, product, permutations
from fractions import Fraction as Q
from pathlib import Path
from flint import arb, arb_mat, arb_poly, ctx

HERE = Path(__file__).resolve().parent
ctx.dps = 64

# ---------------------------------------------------------------------------
# Exact group elements in Q(√d)
# ---------------------------------------------------------------------------

class Rad:
    """a + b√d with a,b rational, d square-free."""
    __slots__ = ("a", "b", "d")
    def __init__(self, a, b=0, d=1):
        self.a = Q(a); self.b = Q(b); self.d = int(d)
    def _coerce(self, other):
        if not isinstance(other, Rad):
            other = Rad(other, 0, self.d)
        if other.d == self.d:
            return other
        if other.b == 0:
            return Rad(other.a, 0, self.d)
        if self.b == 0:
            return None  # signal to flip
        raise ValueError(f"incompatible fields Q(√{self.d}) and Q(√{other.d})")
    def __add__(self, o):
        o = self._coerce(o)
        if o is None:
            return Rad(o := Rad(self.a, 0, other.d if False else 0))  # noqa
        return Rad(self.a + o.a, self.b + o.b, self.d)
    def __radd__(self, o):
        return self.__add__(o)
    def __sub__(self, o):
        o = self._coerce(o)
        return Rad(self.a - o.a, self.b - o.b, self.d)
    def __neg__(self):
        return Rad(-self.a, -self.b, self.d)
    def __mul__(self, o):
        if not isinstance(o, Rad):
            return Rad(self.a * Q(o), self.b * Q(o), self.d)
        if o.b == 0:
            return Rad(self.a * o.a, self.b * o.a, self.d)
        if self.b == 0:
            return Rad(self.a * o.a, self.a * o.b, o.d)
        if self.d != o.d:
            raise ValueError("incompatible fields")
        return Rad(self.a * o.a + self.b * o.b * self.d,
                   self.a * o.b + self.b * o.a, self.d)
    def __rmul__(self, o):
        return self.__mul__(o)
    def __truediv__(self, o):
        if not isinstance(o, Rad):
            return Rad(self.a / Q(o), self.b / Q(o), self.d)
        # (a+b√d)/(c+e√d) * (c-e√d)/(c-e√d)
        c, e, d = o.a, o.b, o.d
        den = c*c - e*e*d
        num = self * Rad(c, -e, d)
        return Rad(num.a / den, num.b / den, num.d)
    def __eq__(self, o):
        if not isinstance(o, Rad):
            return self.b == 0 and self.a == Q(o)
        d = self.d if self.b != 0 else o.d
        o2 = Rad(o.a, o.b, d) if o.b == 0 or o.d == d else o
        return self.a == o2.a and self.b == o2.b and (self.b == 0 or self.d == o2.d)
    def __hash__(self):
        if self.b == 0:
            return hash((self.a, 0, 0))
        return hash((self.a, self.b, self.d))
    def __repr__(self):
        return f"{self.a}+{self.b}√{self.d}"
    def arb(self):
        def qarb(fr):
            fr = Q(fr)
            return arb(int(fr.numerator)) / arb(int(fr.denominator))
        if self.b == 0:
            return qarb(self.a)
        return qarb(self.a) + arb(self.d).sqrt() * qarb(self.b)


def qmul(p, q):
    a0,a1,a2,a3 = p; b0,b1,b2,b3 = q
    return (a0*b0 - a1*b1 - a2*b2 - a3*b3,
            a0*b1 + a1*b0 + a2*b3 - a3*b2,
            a0*b2 - a1*b3 + a2*b0 + a3*b1,
            a0*b3 + a1*b2 - a2*b1 + a3*b0)

def qconj(p):
    return (p[0], -p[1], -p[2], -p[3])

def group_2O():
    """The 48 binary octahedral units, coordinates in Q(√2)."""
    d = 2
    z, o = Rad(0, 0, d), Rad(1, 0, d)
    h, r = Rad(Q(1, 2), 0, d), Rad(0, Q(1, 2), d)  # 1/2, √2/2 = 1/√2
    els = []
    # 8: ±1, ±i, ±j, ±k
    for i in range(4):
        for s in (o, -o):
            q = [z, z, z, z]; q[i] = s; els.append(tuple(q))
    # 16: (±1±i±j±k)/2
    for s in product((h, -h), repeat=4):
        els.append(s)
    # 24: two nonzero coordinates equal to ±1/√2
    for i, j in combinations(range(4), 2):
        for si, sj in product((r, -r), repeat=2):
            q = [z, z, z, z]; q[i] = si; q[j] = sj; els.append(tuple(q))
    assert len(els) == 48 and len(set(els)) == 48
    return els

def group_2I():
    """The 120 binary icosahedral units (icosians), coordinates in Q(√5)."""
    d = 5
    z, o = Rad(0, 0, d), Rad(1, 0, d)
    h = Rad(Q(1, 2), 0, d)
    # φ/2 = (1+√5)/4,  1/(2φ) = (√5-1)/4 = φ/2 - 1/2
    phi2 = Rad(Q(1, 4), Q(1, 4), d)
    iphi2 = Rad(Q(-1, 4), Q(1, 4), d)
    els = []
    # 8: ±1, ±i, ±j, ±k
    for i in range(4):
        for s in (o, -o):
            q = [z, z, z, z]; q[i] = s; els.append(tuple(q))
    # 16: (±1±i±j±k)/2
    for s in product((h, -h), repeat=4):
        els.append(s)
    # 96: even permutations of (0, ±1/2, ±1/(2φ), ±φ/2)
    # Even perms of 0123: the 12 elements of A4
    even = [p for p in permutations(range(4)) if _sign(p) == 1]
    for perm in even:
        for s1, s2, s3 in product((-1, 1), repeat=3):
            vals = [z, h * s1, iphi2 * s2, phi2 * s3]
            q = tuple(vals[perm[k]] if False else None for k in range(4))
            # vals placed at positions given by perm: coord perm[i] gets vals[i]
            # actually: even perm of the 4-tuple (0, ±1/2, ±1/(2φ), ±φ/2)
            qq = [None]*4
            base = [z, h*s1, iphi2*s2, phi2*s3]
            for i, j in enumerate(perm):
                qq[j] = base[i]
            # wait: "even perm of (0, a, b, c)" means the tuple is (t_{p0}, t_{p1}, t_{p2}, t_{p3})
            # if p is the perm of source indices. Standard: all even perms of the coordinates.
            els.append(tuple(base[p] for p in perm))
    # The last construction used `for p in perm` incorrectly possibly; fix by unique + count
    # Rebuild 96 cleanly:
    els = els[:24]  # 8+16
    seen = set(els)
    for perm in even:
        for s1, s2, s3 in product((-1, 1), repeat=3):
            base = [z, h*s1, iphi2*s2, phi2*s3]
            q = tuple(base[p] for p in perm)
            if q not in seen:
                seen.add(q); els.append(q)
    if len(els) != 120:
        # some sources use all even-sign patterns; try all 24 perms and filter later by closure
        pass
    return els, seen

def _sign(p):
    s = 1
    p = list(p)
    for i in range(len(p)):
        for j in range(i):
            if p[j] > p[i]:
                s *= -1
    return s


def close_exact(gens, d, expected):
    one = (Rad(1, 0, d), Rad(0, 0, d), Rad(0, 0, d), Rad(0, 0, d))
    els = [one]
    seen = {one}
    frontier = [one]
    while frontier:
        new = []
        for x in frontier:
            for g in gens:
                y = qmul(x, g)
                if y not in seen:
                    seen.add(y); els.append(y); new.append(y)
        frontier = new
    if len(els) != expected:
        raise RuntimeError(f"closure got {len(els)}, expected {expected}")
    return els


def group(name):
    if name == "2T":
        d = 2  # actually Q, but Q(√2) is fine with b=0
        h = Rad(Q(1, 2), 0, d)
        gens = [
            (Rad(0,0,d), Rad(1,0,d), Rad(0,0,d), Rad(0,0,d)),
            (h, h, h, h),
        ]
        return close_exact(gens, d, 24), d
    if name == "2O":
        return group_2O(), 2
    if name == "2I":
        d = 5
        h = Rad(Q(1, 2), 0, d)
        phi2 = Rad(Q(1, 4), Q(1, 4), d)
        iphi2 = Rad(Q(-1, 4), Q(1, 4), d)
        gens = [
            (h, h, h, h),
            (h, phi2, iphi2, Rad(0, 0, d)),
        ]
        return close_exact(gens, d, 120), d
    raise ValueError(name)


def conjugacy_classes(els):
    used = set(); classes = []
    for i, g in enumerate(els):
        if i in used:
            continue
        orb = []
        for h in els:
            c = qmul(qmul(h, g), qconj(h))
            for j, e in enumerate(els):
                if e == c:
                    if j not in used:
                        used.add(j); orb.append(e)
                    break
            else:
                raise RuntimeError("conjugate not in the group")
        classes.append(orb)
    return classes


def class_data(els):
    """Non-central classes: (delta, s2, lines) with arb entries.  Lines unique up to sign."""
    N = len(els)
    data = []
    classes = conjugacy_classes(els)
    for C in classes:
        re = C[0][0]
        s2_exact = Rad(1, 0, re.d) - re*re
        # skip central: sin²θ = 0
        if s2_exact.a == 0 and s2_exact.b == 0:
            continue
        raw_axes = []
        for q in C:
            im = (q[1], q[2], q[3])
            raw_axes.append(im)
        # unique lines: identify v ~ λw, here λ=± (same ray up to sign)
        lines_exact = []
        def same_line(u, v):
            # u = λ v, λ=±.  Compare components with a common scale by a cross product.
            # u × v = 0 and u·v != 0, all exact.
            cx = u[1]*v[2] - u[2]*v[1]
            cy = u[2]*v[0] - u[0]*v[2]
            cz = u[0]*v[1] - u[1]*v[0]
            z = Rad(0, 0, u[0].d if u[0].b or True else 1)
            # zero test
            def is0(t):
                return t.a == 0 and t.b == 0
            return is0(cx) and is0(cy) and is0(cz)
        for a in raw_axes:
            if not any(same_line(a, b) for b in lines_exact):
                lines_exact.append(a)
        # convert to unit arb vectors
        def unit(im):
            xs = [t.arb() for t in im]
            n2 = xs[0]*xs[0] + xs[1]*xs[1] + xs[2]*xs[2]
            n = n2.sqrt()
            return [xs[0]/n, xs[1]/n, xs[2]/n]
        lines = [unit(a) for a in lines_exact]
        delta = arb(len(C)) / arb(N)
        s2 = s2_exact.arb()
        data.append(dict(delta=delta, s2=s2, lines=lines, size=len(C), n_lines=len(lines),
                         re=re.arb()))
    return data, classes


# ---------------------------------------------------------------------------
# β, Lipschitz radius, active set, M, λ_max
# ---------------------------------------------------------------------------

def dot(u, v):
    return u[0]*v[0] + u[1]*v[1] + u[2]*v[2]

def nrm(v):
    return dot(v, v).sqrt()

def unit(v):
    n = nrm(v)
    return [v[0]/n, v[1]/n, v[2]/n]

def beta_of(I, data):
    s = arb(0)
    for C in data:
        m = None
        for a in C["lines"]:
            val = dot(a, I)
            val = val*val
            m = val if m is None else arb.max(m, val)
        s += C["delta"] * C["s2"] * (arb(1) - m)
    return s

def c_of(data):
    return sum((C["delta"] * C["s2"] for C in data), arb(0))

def active_indices(I, data):
    """Winning line index in each class (raises if a tie to working precision)."""
    idx = []
    gaps = []
    for C in data:
        vals = [dot(a, I)**2 for a in C["lines"]]
        # uniquely determined winner: lower(best) > upper(second)
        order = sorted(range(len(vals)), key=lambda i: float(vals[i].mid()), reverse=True)
        best, second = vals[order[0]], vals[order[1]]
        if not (best.lower() > second.upper()):
            return None, None  # not certified unique
        idx.append(order[0])
        gaps.append(best - second)
    return tuple(idx), gaps

def matrix_M(data, choice):
    """M = Σ δ s2 a aᵀ for the given line choice (one index per class)."""
    entries = [[arb(0) for _ in range(3)] for _ in range(3)]
    for C, k in zip(data, choice):
        a = C["lines"][k]
        w = C["delta"] * C["s2"]
        for i in range(3):
            for j in range(3):
                entries[i][j] += w * a[i] * a[j]
    return arb_mat(entries)

def lam_max(M):
    ev = M.eig(algorithm="rump")
    # ev[k] is acb; take real part, verify imag ~ 0
    reals = []
    for z in ev:
        if not (abs(z.imag).upper() < arb("1e-20")):
            raise RuntimeError(f"non-real eigenvalue {z}")
        reals.append(z.real)
    m = reals[0]
    for x in reals[1:]:
        m = arb.max(m, x)
    return m

def enclose_cos2_on_box(a, face, x0, x1, y0, y1):
    """Enclosure of (a·I)² for I = v/||v||, v = place(face,x,y), (x,y) in the rectangle.

    (a·v)² / (v·v).  v·v = 1 + x² + y².  Use interval x,y.
    """
    X, Y = arb(0, 0), arb(0, 0)  # placeholders; build intervals from endpoints
    # arb interval from endpoints
    def iv(lo, hi):
        lo, hi = arb(lo), arb(hi)
        mid = (lo + hi) / 2
        rad = (hi - lo) / 2
        # include endpoint rounding
        return mid + arb(0, rad + arb("1e-40"))
    x, y = iv(x0, x1), iv(y0, y1)
    v = place_arb(face, x, y)
    num = dot(a, v) ** 2
    den = dot(v, v)
    return num / den

def place_arb(face, x, y):
    one = arb(1)
    if face == 0:
        return [one, x, y]
    if face == 1:
        return [x, one, y]
    return [x, y, one]

def place_float(face, x, y):
    if face == 0:
        return (1.0, x, y)
    if face == 1:
        return (x, 1.0, y)
    return (x, y, 1.0)

def I_of(face, x, y):
    return unit(place_arb(face, arb(x), arb(y)))

def geodesic_radius(face, x0, x1, y0, y1):
    """Upper bound on max d_geo(I_centre, I) over the spherical image of the rectangle."""
    xc, yc = (x0 + x1) / 2, (y0 + y1) / 2
    I0 = I_of(face, xc, yc)
    r = arb(0)
    for xx, yy in ((x0, y0), (x0, y1), (x1, y0), (x1, y1)):
        Ic = I_of(face, xx, yy)
        c = dot(I0, Ic)
        # θ = acos(c); upper(θ) = acos(lower(c)) with c clipped to [-1,1]
        clo = c.lower()
        if clo >= 1:
            th = arb(0)
        elif clo <= -1:
            th = arb.pi()
        else:
            th = arb(clo).acos()
        # add a tiny pad for the fact that I0,Ic themselves have tiny radius
        th = th + arb("1e-30")
        r = arb.max(r, th)
    return r

def active_certified_on_box(data, face, x0, x1, y0, y1):
    """If every class has a unique winning line on the whole box, return the choice tuple."""
    choice = []
    for C in data:
        enclosures = [enclose_cos2_on_box(a, face, x0, x1, y0, y1) for a in C["lines"]]
        # unique winner: some i with lower(i) > upper(j) for all j≠i
        winner = None
        for i, ei in enumerate(enclosures):
            if all(ei.lower() > enclosures[j].upper() for j in range(len(enclosures)) if j != i):
                winner = i
                break
        if winner is None:
            return None
        choice.append(winner)
    return tuple(choice)


# ---------------------------------------------------------------------------
# Branch-and-bound
# ---------------------------------------------------------------------------

LIP = arb(3) / arb(4)  # = c

def certify(name, max_depth=24, min_w=None):
    t0 = time.time()
    els, d = group(name)
    data, classes = class_data(els)
    c = c_of(data)
    # sanity: c = 3/4
    if not (c - arb(3)/4).contains(0) and abs(c - arb(3)/4).upper() > arb("1e-20"):
        # allow tiny radius
        if abs(c - arb("3/4")).upper() > arb("1e-18"):
            raise RuntimeError(f"{name}: c={c} is not 3/4")

    # Seed the candidate from a known approximate argmin (refine.json), or a scan.
    seed = json.loads((HERE / "refine.json").read_text())[name]["argmin"]
    Iseed = unit([arb(seed[0]), arb(seed[1]), arb(seed[2])])
    choice_star, gaps = active_indices(Iseed, data)
    if choice_star is None:
        raise RuntimeError(f"{name}: seed is not in an open cell (tie)")
    Mstar = matrix_M(data, choice_star)
    lam = lam_max(Mstar)
    beta_star = c - lam
    # Verify the top eigenvector lies in the same open cell
    ev, R = Mstar.eig(right=True, algorithm="rump")
    # pick the column with largest real eigenvalue
    best_k, best_l = 0, ev[0].real
    for k, z in enumerate(ev):
        if z.real.lower() > best_l.lower() or (z.real.lower() >= best_l.lower() and z.real.mid() > best_l.mid()):
            # just use mid comparison among already-real ev
            pass
    ks = list(range(3))
    ks.sort(key=lambda k: float(ev[k].real.mid()), reverse=True)
    k = ks[0]
    if abs(ev[k].imag).upper() > arb("1e-20"):
        raise RuntimeError("top eigenvalue not real")
    # eigenvector column k, take real part, normalise
    v = [R[i, k].real for i in range(3)]
    # flip to match the seed
    if float(dot(v, Iseed).mid()) < 0:
        v = [-x for x in v]
    v = unit(v)
    choice_v, _ = active_indices(v, data)
    if choice_v != choice_star:
        raise RuntimeError(f"{name}: top eigenvector is not in the seed cell")
    beta_at_v = beta_of(v, data)
    if not beta_at_v.overlaps(beta_star):
        raise RuntimeError(f"{name}: β(v)={beta_at_v} does not match c-λmax={beta_star}")

    L = beta_star.lower()   # left endpoint of the seed enclosure
    U = beta_star.upper()
    # L_cert is a running rigorous lower bound: we prove β ≥ L_cert
    # everywhere.  It may drop a few ulps below L when an independent
    # enclosure of the same algebraic number is used as a floor.
    L_cert = arb(L)

    # Root isolation against the known minpoly, recorded for the report
    minpoly = {
        "2T": [12, -9, 1],            # 12β² - 9β + 1
        "2O": [-192, 288, -126, 13], # as in exact.json, high to low of β_min
        "2I": [46080, -138240, 165120, -98880, 30416, -4288, 181],
    }[name]
    # exact.json stored -192,288,-126,13 i.e. -192 x^3 + 288 x^2 - 126 x + 13 = 0
    # equivalent to 192 x^3 - 288 x^2 + 126 x - 13 = 0
    # arb_poly wants low to high
    coeffs_low_to_high = list(reversed(minpoly))
    # For 2O the stored poly is already high-to-low of a poly that has β* as root.
    poly = arb_poly([arb(ci) for ci in coeffs_low_to_high])
    # evaluate at the ball
    val = poly(beta_star)
    poly_ok = abs(val).upper() < arb("1e-20")

    stats = dict(lip=0, quad=0, split=0, depth_hist={})
    leftovers = []

    # BFS / stack of boxes: (face, x0,x1,y0,y1, depth)
    stack = []
    for face in (0, 1, 2):
        stack.append((face, -1.0, 1.0, -1.0, 1.0, 0))

    while stack:
        face, x0, x1, y0, y1, depth = stack.pop()
        stats["depth_hist"][depth] = stats["depth_hist"].get(depth, 0) + 1
        w = max(x1 - x0, y1 - y0)

        # Lipschitz test
        xc, yc = (x0 + x1) / 2, (y0 + y1) / 2
        I0 = I_of(face, xc, yc)
        b0 = beta_of(I0, data)
        r = geodesic_radius(face, x0, x1, y0, y1)
        # lb is a rigorous lower bound of min β on the box, itself enclosed.
        # The trusted real lower bound is lb.lower().  Discard only when
        # that bound is certainly ≥ L_cert.
        lb = b0.lower() - (LIP * r).upper()
        if (L_cert - lb.lower()).upper() <= 0:
            stats["lip"] += 1
            continue

        # Active-set / quadratic test
        ch = active_certified_on_box(data, face, x0, x1, y0, y1)
        if ch is not None:
            M = matrix_M(data, ch)
            lamc = lam_max(M)
            floor = c - lamc
            # β ≥ floor_true ≥ floor.lower().  Discard when this is
            # certainly ≥ L_cert, or when floor overlaps the seed
            # enclosure of β* (same algebraic value; take the more
            # conservative endpoint as the new certified floor).
            if (L_cert - floor.lower()).upper() <= 0:
                stats["quad"] += 1
                continue
            if floor.overlaps(beta_star):
                L_cert = arb.min(L_cert, floor.lower())
                stats["quad"] += 1
                continue
            # The cell's unconstrained floor is certified below L: either
            # v_max lies in the cell (a genuinely smaller critical value —
            # record a failure) or v_max is outside and we must subdivide
            # or use a tighter bound.
            ev, R = M.eig(right=True, algorithm="rump")
            ks = list(range(3))
            ks.sort(key=lambda k: float(ev[k].real.mid()), reverse=True)
            vmax = unit([R[i, ks[0]].real for i in range(3)])
            # also try -vmax
            # Is ±vmax's cube-face representative inside this rectangle?
            def in_this_box(I):
                # map I or -I onto a cube face
                # choose sign so the largest-abs coordinate is positive
                coords = [I[0], I[1], I[2]]
                # if the enclosure is too fat, return None
                absci = [abs(z) for z in coords]
                # mid-based face pick, verified with intervals
                mids = [float(z.mid()) for z in coords]
                am = [abs(t) for t in mids]
                k = max(range(3), key=lambda i: am[i])
                sgn = 1 if mids[k] >= 0 else -1
                if sgn < 0:
                    coords = [-z for z in coords]
                den = coords[k]
                if den.lower() <= 0:
                    return False
                # the two other coords / den should lie in the rectangle
                others = [i for i in range(3) if i != k]
                # face numbering: 0 means coord 0 is the '1' (i.e. k==0)
                if k != face:
                    return False
                xx = coords[others[0]] / den
                yy = coords[others[1]] / den
                # others order: for face 0, others=(1,2) → (x,y) = (I1/I0, I2/I0) matches place
                # face 1, others=(0,2) → (x,y)=(I0,I2)/I1 matches place
                # face 2, others=(0,1) → (x,y)=(I0,I1)/I2 matches place
                # interval not subset of [x0,x1]×[y0,y1] ⇒ not certified inside
                if xx.upper() < x0 or xx.lower() > x1 or yy.upper() < y0 or yy.lower() > y1:
                    return False
                if xx.lower() >= x0 and xx.upper() <= x1 and yy.lower() >= y0 and yy.upper() <= y1:
                    return True
                return None  # uncertain
            inside = in_this_box(vmax)
            if inside is False:
                inside = in_this_box([-z for z in vmax])
            if inside is True:
                leftovers.append(dict(reason="smaller_critical_in_cell", face=face,
                                      box=[x0,x1,y0,y1], depth=depth,
                                      c_minus_lmax=str(c-lamc)))
                continue
            # tighter bound if clearly outside: IᵀM I ≤ λ2 + (λmax-λ2) μ²
            # with μ = max |vmax · I| over the four corners (linear, so vertices)
            if inside is False:
                evs = [ev[k].real for k in ks]
                lam2 = evs[1]  # second largest
                mu = arb(0)
                for xx, yy in ((x0, y0), (x0, y1), (x1, y0), (x1, y1)):
                    Ic = I_of(face, xx, yy)
                    mu = arb.max(mu, abs(dot(vmax, Ic)))
                # also -vmax is the same |dot|
                quad_ub = lam2 + (evs[0] - lam2) * (mu * mu)
                lower2 = (c - quad_ub).lower()
                if not (arb(lower2) < arb(L)):
                    stats["quad"] += 1
                    continue

        # Split or give up
        if depth >= max_depth or w < (min_w or 2**(-max_depth)):
            leftovers.append(dict(reason="unresolved", face=face, box=[x0,x1,y0,y1],
                                  depth=depth, w=w, lb=str(lb)))
            continue
        xm, ym = (x0 + x1) / 2, (y0 + y1) / 2
        stats["split"] += 1
        stack.append((face, x0, xm, y0, ym, depth+1))
        stack.append((face, x0, xm, ym, y1, depth+1))
        stack.append((face, xm, x1, y0, ym, depth+1))
        stack.append((face, xm, x1, ym, y1, depth+1))

    out = {
        "group": name,
        "order": len(els),
        "n_classes_noncentral": len(data),
        "n_lines": [C["n_lines"] for C in data],
        "c": str(c),
        "beta_star": {"re": str(beta_star), "lower": str(L), "upper": str(U),
                      "certified_lower": str(L_cert),
                      "interval_width_upper": str((arb(U)-L_cert).upper())},
        "minpoly_high_to_low": minpoly,
        "minpoly_at_beta_star": str(val),
        "minpoly_vanishes": bool(poly_ok),
        "seed_choice": list(choice_star),
        "seed_min_gap": str(min(gaps)),
        "eigen_in_seed_cell": True,
        "certified_global": (len(leftovers) == 0) and ((arb(U)-L_cert).upper() < arb("1e-40")),
        "stats": {k: (v if k != "depth_hist" else {str(a): b for a, b in v.items()})
                  for k, v in stats.items()},
        "n_leftovers": len(leftovers),
        "leftovers": leftovers[:20],
        "seconds": time.time() - t0,
        "lipschitz_constant": "3/4",
        "domain": "three positive cube faces (fundamental domain for I ~ -I)",
        "dps": ctx.dps,
    }
    return out


def main():
    reports = []
    all_ok = True
    for name in ("2T", "2O", "2I"):
        print(f"==== certifying {name} ====", flush=True)
        rec = certify(name)
        reports.append(rec)
        print(json.dumps({k: rec[k] for k in
                          ("group", "beta_star", "minpoly_vanishes", "certified_global",
                           "n_leftovers", "stats", "seconds", "seed_min_gap")},
                         indent=2), flush=True)
        if not rec["certified_global"]:
            all_ok = False
    out = {
        "method": "Arb/FLINT interval branch-and-bound of β on the three positive cube faces, using the geodesic Lipschitz bound |β(I)-β(J)|≤(3/4) d_geo(I,J) and, where a unique active set of axes is certified on a box, the quadratic lower bound β ≥ 3/4 − λ_max(M).",
        "not_claimed": "No RH statement.  Only that the already-identified algebraic critical values of the group-theoretic exponent β are its global minima on the sphere.",
        "cases": reports,
        "all_certified": all_ok,
    }
    dest = HERE / "certify-global-results.json"
    dest.write_text(json.dumps(out, indent=2, default=str))
    print("wrote", dest)
    print("ALL CERTIFIED" if all_ok else "NOT ALL CERTIFIED")
    return 0 if all_ok else 1


if __name__ == "__main__":
    sys.exit(main())
