|
9
|
|
|
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.
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 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 do not need a result as strong as Baker, Harman and Pintz, we need only $$\pi(x+x^{\theta})-\pi(x)\sim \frac{x^\theta}{\log x}$$ for some $\theta<1$.<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.
|
|
|
|
|
8
|
|
edited May 16 2012 at 6:05 |
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.
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 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 second first row to the firstsecond, this means if we will try to show that 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{1}{7/12} frac{12}{7} \frac{n^{7/12}}{\log n},$$ which is evidently false.
Remark: We do not need a result as strong as Baker, Harman and Pintz, we need only $$\pi(x+x^{\theta})-\pi(x)\sim \frac{x^\theta}{\log x}$$ for some $\theta<1$.
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.
|
|
|
|
|
7
|
|
edited May 9 2012 at 18:05 |
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.
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 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 second row to the first, we will try to show that 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.) Baker, Harman and Pintz Heath-Brown showed that $$\pi(n+n^{0.525})-\pi(n)\sim $\pi(n+n^{7/12})-\pi(n)\sim \frac{n^{0.525}}{\log frac{n^{7/12}}{\log n},$$ (we can use a weaker result then this) so taking $x=n^{0.525}$ x=n^{7/12}$ we see there are $\frac{n^{0.525}}{\log \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^{0.525}}{\log n^{0.525}}$frac{n^{7/12}}{\log n^{7/12}}$, and this gives the asymptotic inequality $$\frac{n^{0.525}}{\log $\frac{n^{7/12}}{\log n} \gtrsim \frac{1}{0.525} frac{1}{7/12} \frac{n^{0.525}}{\log frac{n^{7/12}}{\log n},$$ which is evidently false.
Remark: We do not need a result as strong as Baker, Harman and Pintz, we need only $$\pi(x+x^{\theta})-\pi(x)\sim \frac{x^\theta}{\log x}$$ for some $\theta<1$.
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.
|
|
|
|
6
|
|
edited May 8 2012 at 21:46 |
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.
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 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 second row to the first, we will try to show that 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 first part of the second row interval $[n+1,n+x]$ will be much smaller then the density of the primes in $[1,x]$. Since $[n+1,n+x]$ is in the first part of second row, and $[1,x]$ is in the first row, implying a contradictionthis 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+2$ 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.) Baker, Harman and Pintz showed that $$\pi(n+n^{0.525})-\pi(n)\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 quantity 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.
Remark: We do not need a result as strong as Baker, Harman and Pintz, we need only $$\pi(x+x^{\theta})-\pi(x)\sim \frac{x^\theta}{\log x}$$ for some $\theta<1$.
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.
|
|
|
|
|
5
|
|
edited May 8 2012 at 20:11 |
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 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: We will use Since we must jump from the above second row to the first, we will try to show that we need there are at least the same number of primes in the second row as in the first. However, but this leads to a contradiction since the second row contains larger numbers, and the density of the primes decreases as we go to infinity. In particular, the second row's prime density of the primes in the first part of the second row will be much smaller then the density of the primes in the first rowspart of the first row, implying the resulta contradiction.
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. (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})-\pi(n)\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.
Remark: We do not need a result as strong as Baker, Harman and Pintz, we need only $$\pi(x+x^{\theta})-\pi(x)\sim \frac{x^\theta}{\log x}$$ for some $\theta<1$.
Remark 2: If we wanted only to prove the conjecture for Hamiltonian paths, we did not need to waste spend time removing the twin primes pairs for fear of double counting, since a Hamiltonian path implies we cannot double count.
Remark 3: It is quite likely that there is a clever elementary approach to solving the inequality immediatelyproblem when $n$ is even.
|
|
|
|
|
4
|
|
edited May 8 2012 at 20:00 |
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 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.
Idea: We will use the above to show that we need at least the same number of primes in the second row as in the first, but this leads to a contradiction since the density of the primes decreases as we go to infinity. In particular, the second row's prime density will be much smaller then the first rows, implying the result.
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 Assuming the path exists, we much must 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 $\pi(n+n^{0.525})-\pi(n)\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.
Remark: We do not need a result as strong as Baker, Harman and Pintz, we need only $$\pi(x+x^{\theta})-\pi(x)\sim \frac{x^\theta}{\log x}$$ for some $\theta<1$.
Remark: If we wanted only to prove the conjecture for Hamiltonian paths, we did not need to waste time removing the twin primes pairs for fear of double counting, since a Hamiltonian path implies the inequality immediately.
|
|
|
|
|
3
|
|
edited May 8 2012 at 19:55 |
$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 always jump over 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 columnsto the left, and up or down 1. (Going up two rows and over 1 column would lead us to an even square which is non-prime) the right. Idea: We will use the above to show that we need at least the same number of primes in the second row as in the first, but this leads to a contradiction since the density of the primes decreases as we go to infinity. In particular, the second row's prime density will be much smaller then the first rows, implying the result. 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. Remark: If we wanted only to prove the conjecture for Hamiltonian paths, we did not need to waste time removing the twin primes pairs for fear of double counting, since a Hamiltonian path implies the inequality immediately.
|
|
|
|
|
2
|
|
edited May 8 2012 at 19:48 |
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, and by the fact the knight must jump to a prime the next row, 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(x+x^{0.525})\sim $\pi(n+n^{0.525})\sim \frac{x^{0.525}}{\log x},$$ frac{n^{0.525}}{\log n},$$ (we can use a weaker result then this) and by so taking $x=n^{0.6}$ x=n^{0.525}$ we see that as there are $n\rightarrow \infty$ \frac{n^{0.525}}{\log n}$ primes in the interval $[n,n+x]$. However, we must have had bounded this below by $$\frac{n^{0.6}}{\log n}\sim |\mathcal{P}_x|\sim \frac{n^{0.6}}{0.6\log n}$$ 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.
|
|
|
|
|
1
|
|
answered May 8 2012 at 19:41 |
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. By the condition that we have no pairs of the form $p,p+2$, or $p,p+2$ in our set, and by the fact the knight must jump to a prime the next row, we see that among the integers $[n,n+x]$ we must have at least $|\mathcal{P}_x|$ primes. Baker, Harman and Pintz showed that $$\pi(x+x^{0.525})\sim \frac{x^{0.525}}{\log x},$$ (we can use a weaker result then this) and by taking $x=n^{0.6}$ we see that as $n\rightarrow \infty$ we must have $$\frac{n^{0.6}}{\log n}\sim \frac{n^{0.6}}{0.6\log n}$$ which is false.
|
|
|
