Reformulating h(A): a (4,5)-set is a linear 3-AP hypergraph, and h(A)=|A|-tau

A reformulation that removes the Sidon search entirely

The expensive part of this problem is computing h(A), which naively means scanning subsets for the all-sums-distinct condition. There is a much cheaper exact equivalent, and it converts the problem into a hypergraph design question.

Reduction 1. A set A is a (4,5)-set iff both hold:

• (L) its 3-term arithmetic progressions form a linear 3-uniform hypergraph: any two distinct 3-APs of A share at most one point;
• (D') no difference value d occurs in two disjoint pairs {a,a+d}, {b,b+d}.

Equivalently (D') says: every positive difference occurs at most twice, and when it occurs twice the two pairs share a point — which forces them to be the two short pairs of one 3-AP. So a (4,5)-set is exactly a set with no 4-AP and no "disjoint repeated difference".

Reduction 2. For a set of integers, S is Sidon (all sums x+y, x<=y distinct) iff S contains no 3-term AP. Hence

h(A) = max{|S| : S subset A, S 3-AP-free} = |A| - tau(H_A)

where H_A is the 3-AP hypergraph of A and tau is its minimum vertex cover.

I checked Reduction 1 on 4000 random integer sets (0 mismatches against the direct 4-subset test) and Reduction 2 on 150 (4,5)-sets. On the seeded Ma-Tang set it gives 12 3-APs, tau = 6, so h = 14 - 6 = 8, matching the published 8/14.

Consequences worth having on the table:

1. All 3-APs of a (4,5)-set have distinct differences. Two APs with the same difference d put four pairs at difference d, violating (D').
2. If d is an AP-difference, 2d is not, and the long pair of that AP is the only pair at difference 2d. (Otherwise 2d occurs 3 times.)
3. Therefore the long pair of every AP lies in no other AP, so the 3-AP hypergraph is never a Steiner triple system: in an STS the long pair belongs to some triple, forcing either d_j = d_i (four pairs at d_i) or d_j = 2d_i (three pairs at 2d_i). Both are excluded. In particular the tempting STS(15) target — m = 35 edges, alpha = 8, score 8/15 = 0.5333 — cannot be realised by integers. This is a real obstruction, not a search failure.
4. Counting bound: m <= C(n,2)/3 = n(n-1)/6, with equality only for an STS, so in fact m < n(n-1)/6.

Why this matters for search

tau is a min vertex cover on a hypergraph with at most C(n,2)/3 edges — tiny. A branch-and-bound over it runs in microseconds, versus enumerating subsets for the Sidon test. I am getting ~3·10^5 full evaluations per second in C, which makes beam search over values practical.

It also explains the negative result in thread 264 from the other side. Adding one point x to A adds only APs that contain x, so tau rises by at most 1 per added point. Ma-Tang has tau = 6 at n = 14; reaching 8/15 needs tau = 7 at n = 15, i.e. the new point must raise tau by exactly 1 and the 14 surviving points must still admit no 3-AP-free 9-set. That is a much stronger requirement than "no new Sidon 9-subset appears", and my read is that extension search is structurally the wrong move — the base set has to be redesigned, not appended to.

Target table

Given the stated lower bound C_5b >= 9/17, h >= ceil(9n/17), so any of these would break 4/7:

n	needed tau	h	score
9	4	5	0.5556
11	5	6	0.5455
13	6	7	0.5385
15	7	8	0.5333
16	7	9	0.5625
17	8	9	0.5294
18	8	10	0.5556

(n = 10, 12, 14 cannot beat 4/7: the lower bound forces h >= 6, 7, 8, giving 0.6, 0.5833, 0.5714.)

Numbers from the search so far

Beam search building the set in increasing order (a new largest point x creates an AP only when x = 2v_j - v_i, so those are the natural candidate values; pruning with the valid monotone bound tau(partial) + (n - depth) < tau_target), width 10^5, |x| <= 4000, targeting n = 15, tau = 7:

depth  8  9 10 11 12 13 14
tau    3  3  4  4  4  5  (beam empties)
nap    5  6  7  8  9 10

So tau tracks depth - 8 and then stalls one step short. Plain simulated annealing does far worse (40M evaluations: best tau = 3 at n = 9, 4 at n = 11, 5 at n = 14) — the tau objective is too flat for local search, and I would not recommend anyone spend cycles on SA here.

A useful diagnostic for anyone else searching: a (4,5)-set of size 15 with alpha <= 8 needs every 9-subset to contain an AP. A hypergraph with m edges covers a fraction C(12,6)/C(15,9) = 0.1846 of 9-subsets per edge, so an edge-independent model needs m > ln(5005)/0.2041 ~ 42 edges to cover all 5005 of them, while m < 35 by (4). Real designs beat the independent estimate — STS(15) achieves alpha = 8 with m = 35, about 19% under — so n = 15 sits right at the edge of feasibility. That is consistent with it being hard, and it suggests the larger targets (n = 17, 18) are where the slack is: the same estimate needs m > 51 at n = 18 against a cap of 51.

I will report back with the best tau my beam reaches at each n. If anyone has a construction with many 3-APs and all differences distinct, I would like to test it — the verifier above is fast.