Can 17 positive integers *in arithmetic progression* be found such that that no four of them have, pairwise, a common divisor greater than 1, but, likewise, no four of them are, pairwise, relatively prime?


Because R(4,4)=18, 18 such numbers are impossible.


At <https://puzzling.stackexchange.com/questions/100391/seventeen-positive-integers/100477#100477> it has been shown that 17 numbers with the required property, but not necessarily in arithmetic progression, can be easily found based on Paley's graph of order 17. The question arises: could those 17 numbers be in arithmetic progression?



Ramsey's number R(4,4) with arithmetic progressions
No, there cannot be 17 such numbers in arithmetic progression (and there cannot be 5 such numbers with the corresponding property for triples).


Suppose we have such an arithmetic progression of length $k$, say $x,x+d,\ldots,x+(k-1)d$. I claim that if a prime $p$ divides any two of them then either it divides all of them (which cannot be the case), or else $p<k$.


Indeed, if $p\mid x+id$ and $p\mid x+jd$ for $0\leq i<j<k$ then $p\mid \ell d$ for some $1\leq \ell<k$. If $p\mid d$ then $p\mid x$ and so all members of the AP are divisible by $p$. Therefore $p\mid \ell$ for some $1\leq \ell <k$, and hence $p<k$.


When $k=5$, the only possibilities are $p=2$ or $p=3$. Consider the graph on these 5 numbers. If there is no triangle/anti-triangle in this graph, every vertex has degree exactly two, and in particular must be divisible by either 2 or 3. By the pigeonhole principle at least 3 of the numbers are divisible by one of them, so there are three numbers with a common non-trivial divisor, contradiction.


Similarly, when $k=17$, the only primes are $2,3,5,7,11,13$. If we draw a graph as above, then to avoid a monochromatic 4-clique it must be the Paley graph of order 17, and in particular every vertex has degree at least one. Colour each vertex by the primes out of $2,3,5,7,11,13$ which divide that vertex, so this is a 6-colouring of the vertices (where a vertex may receive multiple colours). Clearly no colour can appear on more than 3 such vertices, and each vertex receives at least one colour.


It is easy to see that 5 of the colours must appear on exactly 3 of the vertices (since $2\times 2+4\times 3<17$), and the remaining colour appears on the remaining 2 vertices and at most one of the other 15 vertices. Choosing one vertex from each of the 4 colour classes of size 3 that don't receive this 6th colour produces 4 vertices that are pairwise jointly divisible by none of the primes $2,3,5,7,11,13$, and hence pairwise have no common divisor.


