## Knight tour prime (conjecture)

Hello,

I have the following conjecture:

Write all numbers from $1$ to $n^2$ over an $n\times n$ board as usually. There not exists $n$ such that we can find a hamiltonian path on primes numbers with a knight.

Andres Sanchez Perez (Ecole Polytechnique, Paris, France) verified this conjecture for $3\leq n \leq 100$.

Any comments or reference will be appreciated.

-
I think you misunderstood the purpose of this site. Please read the FAQ. – Felipe Voloch May 8 2012 at 19:13
If $n$ is odd, you can color the board as a checkerboard. Note that odd squares will always be white, and even squares will always be black. Since the knight alternates colors on each jump, and there is only one even prime, the result is proven. Maybe there is a similar trick for $n$ even. – Eric Naslund May 8 2012 at 19:22
So, for each $n$, we have a graph whose vertices are the primes up to $n^2$, with two primes adjacent if they are a knight's move away from each other on an $n\times n$ board. The question was whether the graph is Hamiltonian, and Eric's answer, that there is no path at all, says it's not even connected. This suggests a few questions: how many components does the graph have (as a function of $n$)? How large is the largest component? How long is the longest path? Are there cycles for some/most/all large $n$? What is the size of the component containing 2? – Gerry Myerson May 8 2012 at 23:17
@Gerry Myerson: thanks for your new questions. – Roberto Bosch Cabrera May 8 2012 at 23:43
@Gerry Myerson: Intuition tells me that in some sense, the graph is extremely disconnected, but I am not sure how to state this correctly/prove it. – Eric Naslund May 9 2012 at 8:00

We can prove something stronger, that there is no path at all. (That is removing the Hamiltonian condition) What follows is a proof for sufficiently large $n$. The proof makes use of the prime number theorem, a corollary of the Selberg sieve, and a result concerning prime gaps.

$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 if we are on a white square, we must jump to a white square. If we are on the first row, this tells us that the knights next move must be a jump to the second row, either two to the left, or two to the right.

Key Idea: Since we must jump from the first row to the second, this means if we can avoid double counting, there are at least the same number of primes in the second row as in the first. However, the second row contains larger numbers, and the density of the primes decreases as we go to infinity. In particular, if $x<n$, the density of the primes in the interval $[n+1,n+x]$ will be smaller then the density of the primes in $[1,x]$. Since $[n+1,n+x]$ is in the second row, and $[1,x]$ is in the first row, this contradicts the fact that the second row should have more primes.

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}$. We throw out these pairs to avoid double counting. 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. Assuming the path exists, we must have a prime in the second row within jumping distance for each prime in the first row. By the condition that we have no pairs of the form $p,p+2$, or $p,p+4$ 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.) Heath-Brown showed that $$\pi(n+n^{7/12})-\pi(n)\sim \frac{n^{7/12}}{\log n},$$ (we can use a weaker result then this) so taking $x=n^{7/12}$ we see there are $\frac{n^{7/12}}{\log n}$ primes in the interval $[n,n+x]$. However, we had bounded this quantity below by $|\mathcal{P}_x|\sim \frac{n^{7/12}}{\log n^{7/12}}$, and this gives the asymptotic inequality $$\frac{n^{7/12}}{\log n} \gtrsim \frac{12}{7} \frac{n^{7/12}}{\log n},$$ which is evidently false.

Remark: We need only $$\pi(x+x^{\theta})-\pi(x)\sim \frac{x^\theta}{\log x}$$ for some $\theta<1$, $\theta=\frac{7}{12}$ is much stronger than what is required.

Remark 2: If we wanted only to prove the conjecture for Hamiltonian paths, we did not need to spend time removing the twin primes pairs for fear of double counting, since a Hamiltonian path by definition implies we cannot double count.

Remark 3: It is quite likely that there is a clever elementary approach to solving the problem when $n$ is even.

-
I think you misquoted the result of Baker-Harman-Pintz: they only show the right order of magnitude for the primes in the interval, not an asymptotic formula. As far as I know, the best asymptotic result is still Huxley's theorem from the early 70s: any $\theta>7/12$ is admissible in your first "Remark". – GH May 8 2012 at 22:42
@Eric Naslund: thanks a lot for your comments. The case when $n$ is odd is easy, as you noted, I'm not wrote precisely my comment to conjecture, it must be $n$ even between $4$ and $100$, I'm sorry. Your improve to path in general is good, we need a bound for $n$ such that we can use a computer. – Roberto Bosch Cabrera May 8 2012 at 22:56
@GH Heath-Brown (1980s) used sieve methods to improve on Huxley's result slightly, to show that $\theta=7/12$ is admissible. In fact he proved that we may choose $\theta=7/12-w(x)$ for any function such that $w(x)=o(1)$. – Johan Andersson May 9 2012 at 14:05
@Johan: Thank you, I was not aware of this improvement by Heath-Brown. – GH May 9 2012 at 20:16
show 1 more comment

An argument for even $n$: Suppose that $n\geq16$ is even, and consider the first two rows, consisting of $1,\ldots n$ and $n+1,\ldots,2n$, respectively. Since $3$, $7$, and $11$ are primes, in order for them to be reachable, at least $3$ of $n+1$, $n+5$, $n+9$, and $n+13$ must be primes. Modulo $3$ these are $n+1$, $n+2$, $n$, and $n+1$, so there is at least one composite number among these $4$ numbers. Hence one has to choose one of the following two triples: $(n+1,n+5,n+13)$ or $(n+1,n+9,n+13)$. In the first case, it leaves each of $7$ and $11$ reachable from only one square in the second row ($n+5$ and $n+13$), and similarly in the second case, each of $3$ and $7$ would be reachable from only one second-row square ($n+1$ and $n+9$). In any case, this means that each of the remaining primes in the first row must be reachable from two second-row squares, in order for a Hamiltonian path to exist. Now we look at the primes $5$ and $13$, which are in the first row, and conclude that $n+3$, $n+7$, $n+11$, and $n+15$ must all be primes. Modulo $3$, these are $n$, $n+1$, $n+2$, and $n$, making it clear that there is at least one composite number among them.

A different argument for even $n$, assuming that $2$ is not a prime:

Color the odd squares white, and the even squares black, as in Eric's answer. Since $n$ is even, this would mean simply that the odd columns are white, and the even columns are black. We do not want the knight falling on a black square, so we can remove the black columns, and assume that the knight moves diagonally. If we colour this board in checkerboard pattern, then a knight started on a white square must stay on white squares, and a knight started on a black square must stay on black squares. So essentially half of the odd numbers are forbidden, no matter where the knight's initial position is. Now, we note that $3$ and $5$ are in different groups (if $n\geq6$), so at least one of them is unreachable.

When we relax the assumption that $2$ is not a prime, there is a way to switch colour for the knight by going through $2$. But this is the only way, and it requires $2n+1$ and $2n+3$ be both primes.

-
 @ timur:(update) Thank you, your argument is good, but you are considering that $3,5,7,11,13$ are intermediate or re-entry nodes for the hamiltonian path. What occurs if the path begin in $3$ for example?(similarly for $5,7,11,13$). – Roberto Bosch Cabrera May 9 2012 at 2:19 @Roberto: The argument covers all cases. If I was considering only intermediate nodes, i.e., if I was trying to rule out Hamiltonian cycles instead of paths, it would have been enough to look at only the numbers $3$ and $5$. – timur May 9 2012 at 4:28 @Timur: I quite like your second argument, you don't need to add this condition about $2$ by the way. – Eric Naslund May 19 2012 at 9:15 @Eric: Thanks for the comments. Can you please elaborate a bit on how to treat 2? – timur May 19 2012 at 18:30