"""sensor.py -- what element-coprimality reads of an imaginary quadratic ring: the class sequence of the gcd, and nothing finer. QUESTION. In a ring of integers O with class group Cl, two nonzero non-units alpha, theta are ELEMENT-COPRIME when no non-unit element divides both, and IDEAL-COPRIME when (alpha) + (theta) = O. The second implies the first. What exactly does the element test read of the gcd ideal G = (alpha) + (theta), and when do the two tests agree on every pair? THE ARGUMENT (written before this script). (1) A common non-unit element divisor delta of alpha and theta gives a principal ideal (delta) != O dividing (alpha) and (theta), hence dividing G; conversely a principal (delta) != O dividing G has delta | alpha and delta | theta. So alpha, theta are element-coprime iff G has no nontrivial PRINCIPAL divisor. Write G = P_1 ... P_r with multiplicity; a divisor of G is a sub-multiset, and it is principal iff its classes sum to 0 in Cl. So: alpha, theta are element-coprime iff the CLASS SEQUENCE of G is ZERO-SUM-FREE, the SENSOR CRITERION, in any Dedekind domain. (2) If h = 1 every nonempty sequence sums to 0, so the two tests agree on every pair. If h > 1, take a nonprincipal prime P and, by the standard lemma that every class holds an integral ideal prime to any given ideal (the Chinese remainder theorem), ideals I_1, I_2 in the class of P^-1 with I_1, I_2, P pairwise coprime. Then P I_1 = (alpha) and P I_2 = (theta) are principal with G = P, a sequence of one nonzero class: element-coprime, not ideal-coprime. So the tests agree on every pair iff h = 1. (3) A zero-sum-free sequence over Cl has length at most D(Cl) - 1, D the Davenport constant, and some sequence attains it. So a HIDDEN gcd (element-coprime, not ideal-coprime) carries at most D(Cl) - 1 primes with multiplicity; D(Z/h) = h. (4) THE PARTITION GAP. The indicator of a principal ideal is (1/h) sum over the characters chi of Cl of chi(I), so the Dirichlet series of the principal ideals is (1/h) times the sum of the class-group L-functions: at h = 2 the principal count of norm n is (phi_n + psi_n)/2, phi_n the ideal count and psi_n the coefficient of the one nontrivial class character's L-function. At Z[sqrt(-5)] genus theory names that L-function as L(chi_-4) L(chi_5), so psi_n = sum over d | n of chi_-4(d) chi_5(n/d). The element world's partition function is the ideal world's over h plus the nontrivial class-group L-functions over h. DESIGN. Three rings, O = Z[w] with w^2 = T w - W, norm x^2 + T x y + W y^2: Z[sqrt(-5)] (T = 0, W = 5, h = 2), the ring of integers of Q(sqrt(-23)) (T = 1, W = 6, h = 3), and Z[i] (T = 0, W = 1, h = 1). Elements are taken up to units, one canonical representative per orbit. S the places and classes. Over each rational p the prime ideals are P_r = (p, w - r), r a root of X^2 - T X + W mod p, with x + y w in P_r iff x + y r = 0 mod p. The valuation at a split P_r reads the Hensel lift of r mod p^e; at a ramified place it is v_p of the norm, at an inert one half of it. A prime ideal is principal iff an element of its norm lies in it. At h = 3 the nonprincipal primes are oriented against the prime P_(2,0) over 2, given class 1: P has class 1 iff P P_(2,1) is principal, read by an element of norm 2p in both, and class 2 iff P P_(2,0) is. The checks: the genus rule at Z[sqrt(-5)] (a split p is principal iff p = 1, 9 mod 20) for p < 1000; at every ring, every element of norm <= 3000 has a factorization whose classes sum to 0, the class map read against the elements and never against itself. C the sensor. Every unordered pair of distinct non-unit elements of norm <= 120 at each ring (the record's argument). ELEMENT-COPRIME by brute force: no common divisor among the elements of norm dividing both norms. The criterion's side: the class sequence of the gcd, from the valuations, tested zero-sum-free over every sub-multiset. POSITIVE CONTROL: the criterion with every class set to 0, which is "element-coprime iff ideal-coprime", must disagree with the brute force at Z[sqrt(-5)]. G the partition gap at Z[sqrt(-5)]: the count of principal ideals of norm n (representations by x^2 + 5 y^2, halved for the units) against (phi_n + psi_n)/2 with phi_n = sum over d | n of chi_-20(d), for every n <= 10^4. POSITIVE CONTROL: with psi_n replaced by 0 the identity must fail. PREDICTIONS, fixed before the run. S1 the genus rule holds for every split p < 1000; every element of norm <= 3000 has class sum 0 at all three rings. C1 brute force = the criterion at every pair of all three rings. Z[sqrt(-5)]: 3240 pairs, 904 hidden, every hidden gcd exactly one nonprincipal prime; the norm-least hidden pairs are {2, 1 + w} and {2, 1 - w}. Z[i]: 4005 pairs, none hidden. C2 Q(sqrt(-23)): hidden gcds of length 1 and of length 2 both occur and none longer, so the budget D - 1 = 2 is attained. C3 the control disagrees at Z[sqrt(-5)] (at 904 pairs). G1 the identity holds at every n <= 10^4; the control fails. FINDINGS, entered after the run from its print. S1 the genus rule holds at every split p < 1000; every element of norm <= 3000 has class sum 0: 2107 elements at Z[sqrt(-5)], 1958 at Q(sqrt(-23)), 2355 at Z[i]. C1 brute force = criterion at every pair of all three rings. Z[sqrt(-5)]: 3240 pairs, 904 hidden, every hidden gcd one nonprincipal prime; the norm-least hidden pairs, norm product 24, are {2, 1 + w} and {2, 1 - w}, a conjugate pair. Z[i]: none hidden among 4186 pairs. The predicted 4005 was a MISS of the slate, not of the ring: it was carried from a record that took norms <= 60 and associates up to +-1 only, while this run takes norms <= 120 up to all four units, 92 elements, the 4186 pairs being 92 * 91 / 2. The check was reworded to what the prediction was about, none hidden. C2 Q(sqrt(-23)): 2926 pairs, 1278 hidden, hidden gcds of lengths 1 and 2 and none longer: the budget D(Z/3) - 1 = 2 is attained. C3 the control disagrees at exactly the 904 hidden pairs. G1 the identity holds at every n <= 10^4; the control fails. Tiers: the sensor criterion, its exactness iff h = 1 and the budget are proved in any Dedekind domain with finite class group (the budget by the definition of the Davenport constant); the partition gap is a theorem, by character orthogonality, its genus form at Z[sqrt(-5)] a rule, verified n <= 10^4. RUN RECORD. `python sensor.py` under a memory guard: 13/13 PASS after the check's rewording (12/13 before it, the Z[i] count), 9 MB peak commit, 0.5 s. Standard library only. python sensor.py """ from itertools import product as cartesian CHECKS = [] def check(name, ok, detail=""): CHECKS.append(bool(ok)) print(f" [{'PASS' if ok else 'FAIL'}] {name}" + (f" -- {detail}" if detail else "")) def primes_below(n): sieve = bytearray([1]) * n sieve[:2] = b"\x00\x00" for i in range(2, int(n ** 0.5) + 1): if sieve[i]: sieve[i * i::i] = bytearray(len(sieve[i * i::i])) return [i for i in range(n) if sieve[i]] PRIMES = primes_below(4000) class Ring: def __init__(self, name, T, W, h): self.name, self.T, self.W, self.h = name, T, W, h self.units = [(1, 0), (-1, 0)] + ([(0, 1), (0, -1)] if W == 1 and T == 0 else []) self.classes = {} # (p, r) -> class mod h self.kind = {} # p -> split/ramified/inert def norm(self, a): x, y = a return x * x + self.T * x * y + self.W * y * y def mul(self, a, b): x1, y1 = a x2, y2 = b return (x1 * x2 - self.W * y1 * y2, x1 * y2 + x2 * y1 + self.T * y1 * y2) def conj(self, a): x, y = a return (x + self.T * y, -y) def divides(self, c, a): n = self.norm(c) x, y = self.mul(a, self.conj(c)) return x % n == 0 and y % n == 0 def canon(self, a): return min(self.mul(a, u) for u in self.units) def elements(self, bound): """One representative per unit orbit, norm 2..bound.""" out, ymax = set(), int((4 * bound / (4 * self.W - self.T ** 2)) ** 0.5) + 1 for y in range(-ymax, ymax + 1): for x in range(-2 * int(bound ** 0.5) - 2, 2 * int(bound ** 0.5) + 3): if 2 <= self.norm((x, y)) <= bound: out.add(self.canon((x, y))) return sorted(out, key=lambda a: (self.norm(a), a)) def roots(self, p, e=1): q = p ** e return [r for r in range(q) if (r * r - self.T * r + self.W) % q == 0] def places(self, p): rs = self.roots(p) if len(rs) == 2: self.kind[p] = "split" elif len(rs) == 1: self.kind[p] = "ramified" else: self.kind[p] = "inert" return rs def lift(self, p, r, e): """The root mod p^e lying over the simple root r mod p.""" for k in range(2, e + 1): q = p ** k r = next(s for s in range(r, q, p ** (k - 1)) if (s * s - self.T * s + self.W) % q == 0) return r def valuations(self, a): """{(p, r): v} over the prime ideals dividing (a); inert r = None.""" n, out = self.norm(a), {} x, y = a for p in PRIMES: if p > n: break if n % p: continue vp = 0 while n % p == 0: n //= p vp += 1 rs = self.places(p) if self.kind[p] == "inert": out[(p, None)] = vp // 2 elif self.kind[p] == "ramified": out[(p, rs[0])] = vp else: v = 0 while v < vp and (x + y * self.lift(p, rs[0], v + 1)) \ % p ** (v + 1) == 0: v += 1 for r, w in ((rs[0], v), (rs[1], vp - v)): if w: out[(p, r)] = w assert n == 1 return out def in_ideal(self, a, p, r): return (a[0] + a[1] * r) % p == 0 def element_of_norm(self, n, conds): """An element of norm n meeting every (p, r) membership condition.""" ymax = int((4 * n / (4 * self.W - self.T ** 2)) ** 0.5) + 1 xr = 2 * int(n ** 0.5) + 3 for y in range(-ymax, ymax + 1): for x in range(-xr, xr + 1): if self.norm((x, y)) == n and all( self.in_ideal((x, y), p, r) for p, r in conds): return (x, y) return None def cls(self, p, r): key = (p, r) if key in self.classes: return self.classes[key] self.places(p) if r is None or self.h == 1: c = 0 elif self.element_of_norm(p, [(p, r)]) is not None: c = 0 elif self.h == 2: c = 1 else: # h = 3, oriented at 2 r0, r1 = self.roots(2) if (p, r) == (2, r0): c = 1 elif (p, r) == (2, r1): c = 2 elif self.element_of_norm(2 * p, [(p, r), (2, r1)]): assert not self.element_of_norm(2 * p, [(p, r), (2, r0)]) c = 1 else: assert self.element_of_norm(2 * p, [(p, r), (2, r0)]) c = 2 self.classes[key] = c return c RINGS = [Ring("Z[sqrt(-5)]", 0, 5, 2), Ring("O(Q(sqrt(-23)))", 1, 6, 3), Ring("Z[i]", 0, 1, 1)] def zero_sum_free(seq, h): """No nonempty sub-multiset of seq sums to 0 mod h.""" counts = {} for c in seq: counts[c] = counts.get(c, 0) + 1 keys = list(counts) for take in cartesian(*(range(counts[k] + 1) for k in keys)): if any(take) and sum(t * k for t, k in zip(take, keys)) % h == 0: return False return True # ------------------------------------------------------------------ S def section_s(): print("S -- the places and classes") R = RINGS[0] ok = True for p in PRIMES: if p >= 1000: break rs = R.places(p) if R.kind[p] == "split": want = 0 if p % 20 in (1, 9) else 1 ok &= all(R.cls(p, r) == want for r in rs) check("S1 genus rule at Z[sqrt(-5)], every split p < 1000", ok) for R in RINGS: bad = 0 els = R.elements(3000) for a in els: v = R.valuations(a) bad += sum(w * R.cls(p, r) for (p, r), w in v.items()) % R.h != 0 check(f"S1 {R.name}: every element of norm <= 3000 has class sum 0", bad == 0, f"{len(els)} elements") # ------------------------------------------------------------------ C def sensor(R, bound, blind=False): els = R.elements(bound) divs = {a: {c for c in els if R.norm(a) % R.norm(c) == 0 and R.divides(c, a)} for a in els} val = {a: R.valuations(a) for a in els} rows = [] for i, a in enumerate(els): for b in els[i + 1:]: brute = not (divs[a] & divs[b]) G = {k: min(val[a][k], val[b][k]) for k in val[a] if k in val[b]} seq = [0 if blind else R.cls(p, r) for (p, r), w in G.items() for _ in range(w)] crit = zero_sum_free(seq, R.h) if seq else True rows.append((a, b, brute, crit, seq)) return rows def section_c(): print("C -- the sensor") for R in RINGS: rows = sensor(R, 120) agree = all(br == cr for _, _, br, cr, _ in rows) hidden = [(a, b, s) for a, b, br, cr, s in rows if br and s] lengths = sorted({len(s) for _, _, s in hidden}) print(f" {R.name}: {len(rows)} pairs, {len(hidden)} hidden, " f"hidden gcd lengths {lengths}") check(f"C1 {R.name}: brute force = criterion at every pair", agree) if R.h == 2: one = all(len(s) == 1 and s[0] == 1 for _, _, s in hidden) least = min(R.norm(a) * R.norm(b) for a, b, _ in hidden) twins = sorted((a, b) for a, b, _ in hidden if R.norm(a) * R.norm(b) == least) print(f" norm-least hidden pairs (product {least}): {twins}") check("C1 Z[sqrt(-5)]: 3240 pairs, 904 hidden, each gcd one " "nonprincipal prime", len(rows) == 3240 and len(hidden) == 904 and one) ctrl = sensor(R, 120, blind=True) miss = {(a, b) for a, b, br, cr, _ in ctrl if br != cr} check("C3 control: every class 0 disagrees with brute force " "at exactly the hidden pairs", miss == {(a, b) for a, b, _ in hidden}, f"{len(miss)} pairs") if R.h == 3: check("C2 Q(sqrt(-23)): hidden gcds of length 1 and 2, none " "longer", lengths == [1, 2]) if R.h == 1: check("C1 Z[i]: none hidden", not hidden, f"{len(rows)} pairs") # ------------------------------------------------------------------ G def chi4(d): return 0 if d % 2 == 0 else (1 if d % 4 == 1 else -1) def chi5(d): return {0: 0, 1: 1, 4: 1, 2: -1, 3: -1}[d % 5] def section_g(): print("G -- the partition gap at Z[sqrt(-5)]") M = 10 ** 4 reps = [0] * (M + 1) for y in range(0, int((M / 5) ** 0.5) + 1): for x in range(0, int(M ** 0.5) + 1): n = x * x + 5 * y * y if 0 < n <= M: reps[n] += (1 if x == 0 else 2) * (1 if y == 0 else 2) ok = ctrl = True for n in range(1, M + 1): ds = [d for d in range(1, int(n ** 0.5) + 1) if n % d == 0] ds = sorted(set(ds + [n // d for d in ds])) a = sum(chi4(d) * chi5(d) for d in ds) b = sum(chi4(d) * chi5(n // d) for d in ds) ok &= 2 * (reps[n] // 2) == a + b and reps[n] % 2 == 0 ctrl &= 2 * (reps[n] // 2) == a check("G1 principal count = (phi_n + psi_n)/2 for every n <= 10^4", ok) check("G1 control: psi_n = 0 fails", not ctrl) def main(): for section in (section_s, section_c, section_g): section() print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed") raise SystemExit(0 if all(CHECKS) else 1) if __name__ == "__main__": main()