dual2i_split.py

"""dual2i_split.py -- where exactly do base 2i's two ends part?

QUESTION. dual2i.py found that at base 2i (digits 0..3, Z[2i] = {x + 2yi}
in coordinates (x, y)) depth j of the trailing end reads an ideal I iff
(2i)^j is in I, span j of the leading end hides I iff the box
[0, A_j) x [0, B_j) equidistributes mod I, A_j = 4^ceil(j/2), B_j =
4^floor(j/2), read implies hidden, and at 10 of the 23 ideals of 2-power
index <= 256 the leading end hides one span before the trailing end
reads. Which ideals split, and by how much can they?

THE ARGUMENT (written before the engine). I = Z(a, 0) + Z(c, d),
0 <= c < a, n = ad, g = gcd(a, c); T(x, y) = (-4y, x) is multiplication
by 2i; X = I*/Z^2 the characters (alpha, beta); t the least depth, s
the least span; from j to j + 1 exactly one axis of the box grows by 4.
  (1) X is closed under T*: chi o T = (beta, -4 alpha). The x-coordinates
      of I are gZ and its y-coordinates dZ, so (A, 0) is in I iff a | A
      and (0, B) iff (ad/g) | B: t is the least j with a | A_j and
      (ad/g) | B_j. T* gives d | g | 4d; an ideal has d | a, d | c,
      a | 4d + c^2/d.
  (2) Hidden at j implies read at j + 1, at every ideal: were some chi
      unread at j + 1 on the axis that does not grow, it escapes on the
      other axis, and chi + T* chi, chi composed with 1 + 2i, escapes on
      neither; the growing axis is read through T* chi. With read
      implies hidden, t is s or s + 1.
  (3) At t - 1 one axis is short: for t even I is hidden at t - 1 iff
      d | B_(t-1), for t odd iff g | A_(t-1).
  (4) At 2-power index, s = t iff c = 0, I = aZ x dZ: a box ideal is
      unread at t - 1 by its own axis character; a non-box ideal hidden
      only at t would force (a, c, d) = (R, R/2, R/2) or (8d, 4d, d),
      which break a | 4d + c^2/d.
  (5) (2i) = 4Z x Z and {x + 2y = 0 mod 4} are hidden at span 1 and
      their meet 4Z x 2Z, index 8 against a box of 4, is not: no single
      ideal H with "hidden at span 1 iff H in I", where base b has b^j Z.

PREDICTIONS (frozen before the engine).
  C1 index <= 256: 23 ideals, gap t - s 0 at 13 and 1 at 10; (4, 2, 1)
     s 1 t 2; (8, 6, 1) s 2 t 3, as dual2i.py printed.
  P0 t = least j with a | A_j and (ad/g) | B_j, 0 off.
  P1 t - s in {0, 1} at every ideal of 2-power index <= 2^16, 0 off.
  P2 s = t - 1 iff (3), 0 off.
  P3 s = t iff c = 0, 0 off; 25 box ideals.
  P4 (5): (4, 0, 1) and (4, 2, 1) hidden at span 1, (4, 0, 2) not.
Plants, each must print > 0 off: P0 with ad/g -> d; P1 with the box
transposed (B_j x A_j); P2 with the parities swapped; P3 with the box
read as a = d.

KILL (frozen). Gap <= 1 dies if P1 prints an ideal off; the criterion
dies if P2 prints a disagreement; split iff non-box dies if P3 does. C1
is read first; a red control voids the run.

FINDINGS (entered after the run, from its printed output).
  C1 green: 23 ideals at index <= 256, gaps {0: 13, 1: 10}; (4, 2, 1)
     s 1 t 2; (8, 6, 1) s 2 t 3.
  P  47 ideals of 2-power index <= 2^16, three at each index 2^k for
     k = 2..16; least depth up to 9; gaps {0: 25, 1: 22}. The three
     are a property, by hand after the run: an ideal is a = dm,
     c = du, 0 <= u < m, with m | u^2 + 4, solved by u = 0 at m = 1
     and 2, u = 0, 2 at m = 4, u = 2, 6 at m = 8, and by none from
     m = 16 (u^2 = 12 mod 16 has no root); index d^2 m = 2^k fixes the
     parity of m's exponent, so 1 + 2 ideals at every k >= 2, one at
     k = 0 and at k = 1.
  P0 the closed form for t, 0 off; plant 10 off.
  P1 t - s in {0, 1}, 0 off; plant (transposed box) 12 off.
  P2 the criterion, 0 off; plant (parities swapped) 24 off.
  P3 s = t iff c = 0, 0 off, 25 box ideals; plant (a = d) 16 off.
  P4 (4, 0, 1) and (4, 2, 1) hidden at span 1, the meet (4, 0, 2) not.
  K  KILL MISSES on all three: the gap is at most 1 and the ends part
     exactly at the 22 ideals that are not boxes.

RUN RECORD. 11/11 checks, 0.5 s, peak commit 15.3 MB under a memory
guard. Rerun bare: 11/11 checks, 0.5 s, 15.7 MB.
"""

import sys

from dual2i import Lattice, box, hidden_by_count, read_at

CHECKS = []
KMAX = 16


def check(name, ok, detail=""):
    CHECKS.append(bool(ok))
    print(f"  {'PASS' if ok else 'FAIL'}  {name}" +
          (f"  ({detail})" if detail else ""))


def section(title):
    print()
    print(title)


def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def two_power_ideals(kmax):
    """Every ideal of Z[2i] of index 2^k, k <= kmax: a, d powers of 2,
    c over all of range(a)."""
    for ea in range(kmax + 1):
        for ed in range(kmax - ea + 1):
            a, d = 1 << ea, 1 << ed
            for c in range(a):
                L = Lattice(a, c, d)
                if L.ideal():
                    yield L


def least_depth(L):
    jmax = 2 * L.n.bit_length() + 1
    t = next((j for j in range(jmax + 1) if read_at(L, j)), None)
    assert t is not None, (L.a, L.c, L.d)
    return t


def least_span(L, t, transpose=False):
    """Least j <= t + 1 hidden by box count; None if none."""
    for j in range(t + 2):
        A, B = box(j)
        if transpose:
            A, B = B, A
        if A * B >= L.n and hidden_by_count(L, A, B):
            return j
    return None


def least_formula(L, q):
    """Least j with a | A_j and q | B_j."""
    j = 0
    while True:
        A, B = box(j)
        if A % L.a == 0 and B % q == 0:
            return j
        j += 1


def criterion(L, t, swap=False):
    if t == 0:
        return False
    A, B = box(t - 1)
    g = gcd(L.a, L.c)
    if (t % 2 == 0) != swap:
        return B % L.d == 0
    return A % g == 0


def main():
    rows = []
    for L in two_power_ideals(KMAX):
        t = least_depth(L)
        s = least_span(L, t)
        assert s is not None, (L.a, L.c, L.d)
        rows.append((L, s, t))

    section("C  control: index <= 256 against dual2i.py")
    small = [(L, s, t) for L, s, t in rows if L.n <= 256]
    gaps = {}
    for L, s, t in small:
        gaps[t - s] = gaps.get(t - s, 0) + 1
    by = {(L.a, L.c, L.d): (s, t) for L, s, t in rows}
    print(f"  {len(small)} ideals, gaps {dict(sorted(gaps.items()))}; "
          f"(4, 2, 1) {by[(4, 2, 1)]}; (8, 6, 1) {by[(8, 6, 1)]}")
    ok = (len(small) == 23 and gaps == {0: 13, 1: 10}
          and by[(4, 2, 1)] == (1, 2) and by[(8, 6, 1)] == (2, 3))
    check("C1 the table at index <= 256 is dual2i.py's", ok)
    if not ok:
        print("  a red control voids the run")
        return 1

    section(f"P  every ideal of 2-power index <= 2^{KMAX}")
    gaps, top = {}, {}
    for L, s, t in rows:
        gaps[t - s] = gaps.get(t - s, 0) + 1
    print(f"  {len(rows)} ideals, least depth up to "
          f"{max(t for _, _, t in rows)}, gaps "
          f"{dict(sorted(gaps.items()))}")
    for L, s, t in rows:
        k = L.n.bit_length() - 1
        top[k] = top.get(k, 0) + 1
    print(f"  ideals by k (index 2^k): {dict(sorted(top.items()))}")

    off = plant = 0
    for L, s, t in rows:
        q = L.a * L.d // gcd(L.a, L.c)
        off += least_formula(L, q) != t
        plant += least_formula(L, L.d) != t
    check("P0 t = least j with a | A_j and (ad/g) | B_j", off == 0,
          f"{off} off")
    check("P0 plant (ad/g -> d) is caught", plant > 0, f"{plant} off")

    off = sum(t - s not in (0, 1) for L, s, t in rows)
    plant = 0
    for L, s, t in rows:
        sp = least_span(L, t, transpose=True)
        plant += sp is None or t - sp not in (0, 1)
    check("P1 t - s in {0, 1} at every ideal", off == 0, f"{off} off")
    check("P1 plant (box transposed) is caught", plant > 0,
          f"{plant} off")

    off = sum((s == t - 1) != criterion(L, t) for L, s, t in rows)
    plant = sum((s == t - 1) != criterion(L, t, swap=True)
                for L, s, t in rows)
    check("P2 s = t - 1 iff the one short axis hides at t - 1", off == 0,
          f"{off} off")
    check("P2 plant (parities swapped) is caught", plant > 0,
          f"{plant} off")

    boxes = sum(L.c == 0 for L, s, t in rows)
    off = sum((s == t) != (L.c == 0) for L, s, t in rows)
    plant = sum((s == t) != (L.a == L.d) for L, s, t in rows)
    check("P3 s = t iff I = aZ x dZ", off == 0,
          f"{off} off, {boxes} box ideals")
    check("P3 box count is 25", boxes == 25)
    check("P3 plant (box read as a = d) is caught", plant > 0,
          f"{plant} off")

    section("P4  no least ideal hidden at span 1")
    A, B = box(1)
    hs = [hidden_by_count(Lattice(*abc), A, B)
          for abc in ((4, 0, 1), (4, 2, 1), (4, 0, 2))]
    print(f"  span 1, box {A} x {B}: (4, 0, 1) {hs[0]}, (4, 2, 1) {hs[1]}, "
          f"meet (4, 0, 2) {hs[2]}")
    check("P4 two ideals hidden at span 1 whose meet is not",
          hs == [True, True, False]
          and Lattice(4, 0, 2).ideal())

    section("K  the kill")
    print(f"  gap <= 1, the criterion, split iff non-box: "
          f"{'all HOLD' if all(CHECKS) else 'a claim DIES'}")
    print()
    print(f"{sum(CHECKS)}/{len(CHECKS)} checks pass")
    return 0 if all(CHECKS) else 1


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