Skip to main content
2 of 9
added 259 characters in body; added 111 characters in body; added 193 characters in body
Eric Naslund
  • 11.4k
  • 1
  • 66
  • 106

We can prove something stronger, that there is no path at all. (That is removing the Hamiltonian condition) What follows is a proof that the conjecture is true for sufficiently large $n$.

Proof: We proceed by contradiction.

$n$ odd: If $n=2k+1$, then we may color the board as a checkerboard. Note that odd squares will always be the same color, and even squares will always be the same color. Since the knight alternates colors on each jump, and there is only one even prime, the result follows.

$n$ even: If $n=2k$, we similarly color the odd squares white, and the even squares black. Ignore the prime 2, so that all primes we are dealing with are odd. This means that we must always jump over two columns, and up or down 1. (Going up two rows and over 1 column would lead us to an even square which is non-prime)

Consider the set $\mathcal{P}_x$ to be the set primes less then $x$ where we have thrown out all pairs of primes $p,p+2\in \mathcal{P}$ and $p,p+4\in \mathcal{P}$. By using the Selberg sieve results, we know that are $\ll \frac{x}{\log^2 x}$ such pairs, and so it follows that $$|\mathcal{P}_x| \sim \frac{x}{\log x}$$ as $x\rightarrow \infty$. Now, choose $x\leq n$ so that all the elements of $\mathcal{P}_x$ lie in the first row. Assume the path exists, we much have a prime in the second row within jumping distance for each prime in the first row. (The knight cannot jump from first row to third) By the condition that we have no pairs of the form $p,p+2$, or $p,p+2$ in our set, we see that among the integers $[n,n+x]$ we must have at least $|\mathcal{P}_x|$ primes. (The condition regarding prime pairs makes sure that no prime in the second row is used as the jumping point for two distinct primes in the first row.) Baker, Harman and Pintz showed that $$\pi(n+n^{0.525})\sim \frac{n^{0.525}}{\log n},$$ (we can use a weaker result then this) so taking $x=n^{0.525}$ we see there are $\frac{n^{0.525}}{\log n}$ primes in the interval $[n,n+x]$. However, we had bounded this below by $|\mathcal{P}_x|\sim \frac{n^{0.525}}{\log n^{0.525}}$, and this gives the asymptotic inequality $$\frac{n^{0.525}}{\log n} \gtrsim \frac{1}{0.525} \frac{n^{0.525}}{\log n},$$ which is evidently false.

Eric Naslund
  • 11.4k
  • 1
  • 66
  • 106