dual2i.py
Checks: DUAL: The two ends of a quadratic base criterion.
Cited on: DUAL.
To run it: save dual2i.py; standard library only.
"""dual2i.py -- do the two ends of base 2i exchange what they read?
QUESTION. Base 2i, digits 0..3. The two-ends law of base b says depth j
of the trailing end reads m exactly where span j at the leading end
hides it exactly: one condition, m | b^j. Does it carry to the residue
rings of Z[2i], the integers base 2i writes?
THE ARGUMENT (written before the engine).
(1) THE DIGITS. (2i)^(2k) = (-4)^k and (2i)^(2k+1) = 2i(-4)^k, so
sum d_k (2i)^k = a + 2bi, a the even places read in base -4 and b
the odd ones. Base -4 with digits 0..3 writes every integer once,
so base 2i writes Z[2i] = {x + 2yi} once each; coordinates (x, y).
(2) THE TILES. A base -4 tile of j digits is 4^j consecutive
integers, so the span-j leading tile is a translate of the box
[0, A) x [0, B), A = 4^ceil(j/2), B = 4^floor(j/2), and the
depth-j trailing tile is a coset of (2i)^j Z[2i] = AZ x BZ.
(3) THE CRITERION. An ideal I of Z[2i] is a lattice closed under
T(x, y) = (-4y, x), multiplication by 2i. READ at depth j iff
(2i)^j is in I iff every character (alpha, beta) of Z^2/I has
A alpha and B beta in Z. HIDDEN at span j iff every nontrivial
character sums to 0 on the box, the sum a product of two
geometric sums: A alpha in Z with alpha not, or B beta in Z with
beta not. So read implies hidden at the same j; on one axis they
coincide, and a character killed by one axis alone splits them.
(4) THE WITNESS. Z[2i] -> Z/8, 2i -> 2 (2^2 + 4 = 8), kernel
I8 = {x + 2y = 0 mod 8}: its characters (s/8, 2s/8) die on the
4 x 4 box by beta at odd s and by alpha at even s, so I8 is hidden
from span 2, and (2i)^2 -> 4, (2i)^3 -> 0 read it from depth 3.
For mZ[2i] the characters (1/m, 0) and (0, 1/m) need both axes.
PREDICTIONS (frozen before the engine).
C1 strings of length <= 8 hit distinct points of Z[2i], and every
span-j leading tile of a string of length 7 or 8, leading digit
nonzero, is a translate of the A x B box.
C2 one axis: the same counter says an interval of 4^j hides m iff
m | 4^j, m = 2..64, j = 0..4.
P1 read at depth j implies hidden at span j, every ideal of index
<= 256 and j = 0..6.
P2 hidden by box count iff the character criterion, the same range.
P3 I8 hidden from span 2, read from depth 3.
P4 I = mZ[2i]: least span = least depth, every m <= 16.
P5 least depth - least span >= 0 at every ideal of 2-power index,
> 0 at some (the gap's distribution printed); an ideal whose index
has an odd prime is neither read nor hidden at j <= 6.
Planted break: the criterion with A and B swapped must miss P2.
KILL (frozen). "The two-ends law carries to base 2i as one condition"
dies if an ideal of 2-power index prints a least span different from
its least depth. The character reading dies if P2 prints a
disagreement. C1 and C2 are read first; a red control voids the run.
FINDINGS (entered after the run, from its printed output).
C both controls green: 65536 strings of length <= 8 hit distinct
points; 81915 leading tiles at lengths 7 and 8, j = 0..6, are each
a translate of the A x B box; on one axis 4^j consecutive integers
hide m iff m | 4^j at every m = 2..64, j = 0..4.
P1 read implies hidden at every ideal and j, 0 off; 297 ideals of
index <= 256, 23 of 2-power index.
P2 the box count and the character criterion agree, 0 off; the plant
(A and B swapped) disagrees 8 times.
P3 I8 = (8, 0), (6, 1): least span 2, least depth 3.
P4 mZ[2i], m <= 16: least span = least depth, 0 off (at odd m both
are none to j = 6, so P4 reads the even m).
P5 least depth - least span over the 23 ideals of 2-power index:
0 at 13, 1 at 10, never negative, no 'beyond 6' key printed; an odd prime
in the index: neither read nor hidden, 0 off. The least split
ideal is (4, 0), (2, 1), {x + 2y = 0 mod 4}, index 4: hidden at
span 1, read at depth 2.
K KILL FIRES on one condition: the ends part at 10 ideals.
RUN RECORD. 10 checks, 0.6 s. Rerun bare: 10/10 checks, 0.6 s,
44.1 MB.
"""
import sys
from fractions import Fraction
from itertools import product
CHECKS = []
JMAX = 6
NMAX = 256
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 box(j):
"""The span-j leading box: A = 4^ceil(j/2), B = 4^floor(j/2)."""
return 4 ** ((j + 1) // 2), 4 ** (j // 2)
def point(digits):
"""sum d_k (2i)^k, digits least significant first, as (x, y)."""
re = im = 0
pr, pi = 1, 0
for d in digits:
re, im = re + d * pr, im + d * pi
pr, pi = -2 * pi, 2 * pr
assert im % 2 == 0
return re, im // 2
class Lattice:
"""L = Z(a, 0) + Z(c, d), 0 <= c < a: every full-rank sublattice of
Z^2 once."""
def __init__(self, a, c, d):
self.a, self.c, self.d = a, c, d
self.n = a * d
def __contains__(self, v):
x, y = v
if y % self.d:
return False
return (x - (y // self.d) * self.c) % self.a == 0
def key(self, x, y):
q, r = divmod(y, self.d)
return (x - q * self.c) % self.a, r
def ideal(self):
return (0, self.a) in self and (-4 * self.d, self.c) in self
def characters(self):
"""The dual L* modulo Z^2, from M^-1 with M's rows the basis."""
a, c, d = self.a, self.c, self.d
w1 = (Fraction(1, a), Fraction(-c, a * d))
w2 = (Fraction(0), Fraction(1, d))
out = set()
for k1 in range(a):
for k2 in range(d):
al = (k1 * w1[0] + k2 * w2[0]) % 1
be = (k1 * w1[1] + k2 * w2[1]) % 1
out.add((al, be))
assert len(out) == self.n
return out
def ideals(nmax):
for a in range(1, nmax + 1):
for d in range(1, nmax // a + 1):
for c in range(a):
L = Lattice(a, c, d)
if L.ideal():
yield L
def power(j):
v = (1, 0)
for _ in range(j):
v = (-4 * v[1], v[0])
return v
def read_at(L, j):
return power(j) in L
def hidden_by_count(L, A, B):
if (A * B) % L.n:
return False
counts = {}
for x in range(A):
for y in range(B):
k = L.key(x, y)
counts[k] = counts.get(k, 0) + 1
return len(counts) == L.n and len(set(counts.values())) == 1
def hidden_by_characters(chars, A, B):
for al, be in chars:
if al == 0 and be == 0:
continue
if not ((al != 0 and (A * al) % 1 == 0)
or (be != 0 and (B * be) % 1 == 0)):
return False
return True
def least(pred):
return next((j for j in range(JMAX + 1) if pred(j)), None)
def two_power(n):
return n & (n - 1) == 0
def section_controls():
section("C controls: the digit map and the tiles; one axis")
seen, clash = {}, 0
for L in range(0, 9):
for ds in product(range(4), repeat=L):
if L and ds[-1] == 0:
continue
p = point(ds)
clash += p in seen
seen[p] = ds
bad = tiles = 0
for L in (7, 8):
for j in range(0, JMAX + 1):
A, B = box(j)
groups = {}
for ds in product(range(4), repeat=L):
if ds[-1] == 0:
continue
groups.setdefault(ds[j:], []).append(point(ds))
for pts in groups.values():
tiles += 1
x0 = min(p[0] for p in pts)
y0 = min(p[1] for p in pts)
want = {(x0 + x, y0 + y) for x in range(A) for y in range(B)}
bad += set(pts) != want
check("C1 strings of length <= 8 hit distinct points", clash == 0,
f"{len(seen)} points, {clash} clashes")
check("C1 every span-j leading tile is a translate of the A x B box",
bad == 0, f"{tiles} tiles at lengths 7, 8 and j = 0..6, "
f"{bad} off")
off = 0
for m in range(2, 65):
L = Lattice(m, 0, 1)
for j in range(5):
off += hidden_by_count(L, 4 ** j, 1) != (4 ** j % m == 0)
check("C2 one axis: 4^j consecutive integers hide m iff m | 4^j",
off == 0, f"m = 2..64, j = 0..4, {off} off")
return clash == 0 and bad == 0 and off == 0
def section_ideals():
section(f"P every ideal of Z[2i] of index <= {NMAX}, j = 0..{JMAX}")
all_ideals = list(ideals(NMAX))
two = [L for L in all_ideals if two_power(L.n)]
print(f" {len(all_ideals)} ideals, {len(two)} of 2-power index")
p1 = p2 = plant = 0
rows = []
for L in all_ideals:
hid, red = [], []
chars = L.characters()
for j in range(JMAX + 1):
A, B = box(j)
h = hidden_by_count(L, A, B)
r = read_at(L, j)
p1 += r and not h
p2 += h != hidden_by_characters(chars, A, B)
plant += h != hidden_by_characters(chars, B, A)
hid.append(h)
red.append(r)
rows.append((L, least(lambda j: hid[j]), least(lambda j: red[j])))
check("P1 read at depth j implies hidden at span j", p1 == 0,
f"{p1} off")
check("P2 hidden by count iff the character criterion", p2 == 0,
f"{p2} off")
check("Bp the plant (A and B swapped) misses P2", plant > 0,
f"{plant} disagreements")
return rows
def section_split(rows):
section("P3-P5 where the two ends part")
by = {(L.a, L.c, L.d): (s, t) for L, s, t in rows}
s, t = by[(8, 6, 1)]
print(f" I8 = (8, 0), (6, 1): least span {s}, least depth {t}")
check("P3 I8 hidden from span 2, read from depth 3", (s, t) == (2, 3))
off = 0
for m in range(1, 17):
s, t = by[(m, 0, m)]
off += s != t
check("P4 mZ[2i]: least span = least depth, m <= 16", off == 0,
f"{off} off")
gaps, neg, odd = {}, 0, 0
for L, s, t in rows:
if two_power(L.n):
if s is None or t is None:
gaps["beyond 6"] = gaps.get("beyond 6", 0) + 1
continue
neg += t < s
gaps[t - s] = gaps.get(t - s, 0) + 1
else:
odd += s is not None or t is not None
print(f" 2-power index, least depth - least span: "
f"{dict(sorted(gaps.items(), key=str))}")
check("P5 the gap is >= 0 everywhere and > 0 somewhere",
neg == 0 and any(isinstance(g, int) and g > 0 for g in gaps),
f"{neg} negative")
check("P5 an odd prime in the index: neither read nor hidden", odd == 0,
f"{odd} off")
print(" 2-power index <= 64: (a, c, d) index span depth")
for L, s, t in rows:
if two_power(L.n) and L.n <= 64:
mark = " <-- splits" if s != t else ""
print(f" ({L.a}, {L.c}, {L.d}) {L.n:>4} {s} {t}{mark}")
return gaps
def main():
if not section_controls():
print(" a red control voids the run")
return 1
rows = section_ideals()
gaps = section_split(rows)
section("K the kill")
split = sum(v for g, v in gaps.items() if isinstance(g, int) and g > 0)
print(f" ideals of 2-power index where the ends part: {split}; "
f"one condition {'DIES' if split else 'HOLDS'}")
print()
print(f"{sum(CHECKS)}/{len(CHECKS)} checks pass")
return 0 if all(CHECKS) else 1
if __name__ == "__main__":
sys.exit(main())