# -*- coding: utf-8 -*- # Verification of the "cube" family (corner pattern P = [[1,0],[1,1]], matrices of row span one). # Plain Python, no external module, parameters fixed below. Run as is. import time CAS = [(2, 2), (3, 3), (4, 4), (5, 5), (6, 2), (7, 1)] # pairs (q, s) ; we take p = s TEMPS_MAX = 420.0 # seconds ; remaining cases are skipped def autotest(): ok = (2 + 3 == 5) and (7 * 6 == 42) and (2 ** 10 == 1024) and ((5 & 3) == 1) and ((5 | 3) == 7) and ((1 << 4) == 16) and (17 // 5 == 3) and (17 % 5 == 2) if not ok: print("ARITHMETIC SELF-TEST FAILED: stopping.", flush=True) input("Press Enter...") raise SystemExit print("Arithmetic self-test: passed.", flush=True) def cube(q, s, p): """Rows (integers, bit x = column x), row names, dictionary of columns, width.""" col = {} w = 0 for l in range(q): for i in range(q): col[('xi', i, l)] = list(range(w, w + p)); w += p for l in range(q): for j in range(q): col[('lam', j, l)] = list(range(w, w + p)); w += p for i in range(q): for l in range(q): col[('mu', i, l)] = list(range(w, w + p)); w += p for j in range(q): for l in range(q): col[('c', i, j, l)] = [w]; w += 1 col[('B', i, j)] = list(range(w, w + p)); w += p for l in range(q): col[('e', i, j, l)] = [w]; w += 1 def C(a, b, l): return col[('c', a, b, l)][0] def E(a, b, l): return col[('e', a, b, l)][0] def bloc(a, b): return [C(a, b, l) for l in range(q)] + col[('B', a, b)] + [E(a, b, l) for l in range(q)] def rangee(a): r = [] for l in range(q): r += col[('mu', a, l)] for b in range(q): r += bloc(a, b) return r def queue(i, j): r = [] for b in range(j + 1, q): r += bloc(i, b) for a in range(i + 1, q): r += rangee(a) return r def masque(S): m = 0 for x in S: m = m | (1 << x) return m L = []; noms = [] for i in range(q): for j in range(q): v = masque(col[('B', i, j)] + queue(i, j)) for _ in range(s): L.append(v); noms.append(('V', i, j)) for l in range(q): L.append(masque(col[('xi', i, l)] + [C(i, b, l) for b in range(j + 1)] + col[('B', i, j)] + queue(i, j))); noms.append(('U', i, j, l)) L.append(masque(col[('lam', j, l)] + [C(a, j, l) for a in range(i)] + col[('mu', i, l)] + [E(i, b, l) for b in range(j)] + [C(i, j, l), E(i, j, l)] + queue(i, j))); noms.append(('W', i, j, l)) for l in range(q): suite = [] for a in range(i + 1, q): suite += rangee(a) k = masque(col[('xi', i, l)] + [C(i, b, l) for b in range(q)] + suite) for _ in range(s): L.append(k); noms.append(('K', i, l)) for l in range(q): for j in range(q): z = masque(col[('lam', j, l)] + [C(a, j, l) for a in range(q)]) for _ in range(s): L.append(z); noms.append(('J', j, l)) for l in range(q): for i in range(q): z = masque(col[('mu', i, l)] + [E(i, b, l) for b in range(q)]) for _ in range(s): L.append(z); noms.append(('R', i, l)) return L, noms, col, w def compatible(x, y): """x above y: no copy of P <=> x & y is a final segment of y.""" m = x & y if m == 0: return True bas = (m & (-m)).bit_length() - 1 return ((y >> bas) << bas) == m def nombre_copies(x, y, w): com = x & y; trous = y & (~x); nb = 0 for c in range(w): if (com >> c) & 1: nb += bin(trous >> (c + 1)).count('1') return nb def bit(x, c): return (x >> c) & 1 def verifie(q, s): p = s L, noms, col, w = cube(q, s, p); n = len(L) defauts = 0; conflits = 0 # 1. all pairs of rows: P-free, except the q**3 adjacent pairs (U, W), which carry exactly one copy for a in range(n): xa = L[a]; na = noms[a] for b in range(a + 1, n): if na[0] == 'U' and noms[b][0] == 'W' and na[1:] == noms[b][1:]: conflits += 1 c = col[('c',) + na[1:]][0]; e = col[('e',) + na[1:]][0] if not (b == a + 1 and nombre_copies(xa, L[b], w) == 1 and bit(xa, c) and bit(L[b], c) and bit(L[b], e) and not bit(xa, e) and c < e): defauts += 1 elif not compatible(xa, L[b]): defauts += 1 # 2. the entries used in the lower bound manques = 0 pos = {} for a in range(n): pos.setdefault(noms[a], []).append(a) for i in range(q): for j in range(q): for l in range(q): u = pos[('U', i, j, l)][0]; wv = pos[('W', i, j, l)][0]; c = col[('c', i, j, l)][0]; e = col[('e', i, j, l)][0] tests = [(('J', j, l), col[('lam', j, l)], c, wv, 'below'), (('K', i, l), col[('xi', i, l)], c, u, 'below'), (('R', i, l), col[('mu', i, l)], e, wv, 'below')] for (nomz, liens, cible, ligne, sens) in tests: Z = pos[nomz] if len(Z) != s or len(liens) != p: manques += 1 for z in Z: if not (z > ligne and bit(L[z], cible)): manques += 1 for x in liens: if not (x < cible and bit(L[z], x) and bit(L[ligne], x)): manques += 1 Z = pos[('V', i, j)]; liens = col[('B', i, j)] if len(Z) != s or len(liens) != p: manques += 1 for z in Z: if not (z < u and not bit(L[z], e)): manques += 1 for x in liens: if not (x < e and bit(L[z], x) and bit(L[u], x)): manques += 1 # 3. the uniform repair: every row U loses its columns B and gains its column e ; cost q**3 (p + 1), output P-free N = list(L); cout = 0 for a in range(n): if noms[a][0] == 'U': i, j, l = noms[a][1], noms[a][2], noms[a][3] for x in col[('B', i, j)]: N[a] = N[a] & (~(1 << x)); cout += 1 N[a] = N[a] | (1 << col[('e', i, j, l)][0]); cout += 1 libre = True for a in range(n): xa = N[a] for b in range(a + 1, n): if not compatible(xa, N[b]): libre = False if not (libre and cout == q ** 3 * (p + 1)): manques += 1 return n, w, conflits, defauts, manques, cout def main(): autotest() t0 = time.time(); recap = [] print("Cube family: side n = 2 q**3 + 4 q**2 s, q**3 one-copy conflicts, exact distance D = q**3 (s + 1) (theorem and proposition of the note).", flush=True) for (q, s) in CAS: if time.time() - t0 > TEMPS_MAX: print("q =", q, "s =", s, ": skipped (time).", flush=True); recap.append((q, s, "skipped")); continue t1 = time.time() n, w, conflits, defauts, manques, cout = verifie(q, s) attendu = 2 * q ** 3 + 4 * q * q * s ok = (n == attendu and w == attendu and conflits == q ** 3 and defauts == 0 and manques == 0) borne = q ** 3 * (s + 1) print("q =", q, "s = p =", s, "| matrix", n, "x", w, "| conflicts", conflits, "| bad pairs", defauts, "| missing proof entries", manques, "| D = q**3 (s+1) =", borne, "| repair of cost", cout, "| S =", q ** 3, "| %s" % ("PASS" if ok else "FAIL"), "| %.1f s" % (time.time() - t1), flush=True) recap.append((q, s, "PASS" if ok else "FAIL")) print("", flush=True) print("SUMMARY", flush=True) for r in recap: print(" q =", r[0], " s =", r[1], " :", r[2], flush=True) print("Total time: %.1f s" % (time.time() - t0), flush=True) input("Press Enter...") main()