Erdős #1212 · number theory / primes

Herzog and Stewart studied the graph $G$, which they called visible lattice points, and proved that there is only one infinite component, and conjectured that if $p$ is prime and $p\nmid a$ then $(a,p)$ always belongs to the infinite component. (This is according to [Er80]; I can find no such results of Herzog and Stewart, who have a paper [HeSt71] on which finite patterns appear in the set of visible lattice points, but does not address this question.)

Erdős originally asked this question with just the condition that $\min(x,y)>1$ and (as he recounts in [Er80]) 'foolishly offered 25 dollars for a proof. In the evening Stewart gave the simple proof: $(p_k,p_{k+1})$ can be joined to $(p_{k+1},p_{k+2})$'. Indeed, if $p_k$ is the $k$th prime then there is a path

This is permissible provided $[p_{k+1},p_{k+2}]$ contains no multiple of $p_k$, which is true provided $p_{k+2}<2p_{k}$, which is true for all $k\geq 4$.

One could further demand that the path be monotone (i.e. every step increases the distance from the origin). Is there a monotone path where we change direction after a bounded number of steps?

The first $50\times 50$ block of the graph $G$ restricted to those vertices $(x,y)$ with both $x,y>1$ and at least one of $x$ or $y$ composite is shown here.

The source labels this entry OPEN in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.