I've been thinking a long time about Legendre's Conjecture.

A few nights ago, I came across the following argument which is of course too simple to be true.

I would greatly appreciate if someone could help me understand what is wrong.

I apologize for the length of the argument. Please let me know if any point is unclear or when you find a mistake in the reasoning.

(1) Let:

  • $p_k$ be the $k$th prime so that $p_1 = 2, p_2 = 3, p_3 =5, \dots$

  • $c_1 = \dfrac{1}{2}$, $d_1 = 0$

  • $c_k = c_{k-1} + \dfrac{d_{k-1}}{p_k}$

  • $d_k = d_{k-1} + \dfrac{c_{k-1}}{p_k}$

Note 1: My goal here is to count the number of integers in a sequence of consecutive integers less than or equal to $n$ where the least prime factor is greater than $x$.

Note 2: Surprisingly close to the correct answer is the fraction: $\prod\limits_{i=1}^{k}\left(\dfrac{p_i-1}{p_i}\right)n$ where $p_k$ is the largest prime less than or equal to $x$.

Note 3: $c_k, d_k$ are bounds on the error term between the actual count and the fraction in note 2. This is very easy to figure out for $p_1 = 2$ and I seemingly found a way to extend it which I am a bit suspicious of.

Note 4: Both $c_k$ and $d_k$ are larger than the error term with $d_k < c_k$. But I found that that I needed both to get the complete the inductive proof.

(2) $\prod\limits_{i=1}^{k}\left(\dfrac{p_i-1}{p_i}\right)p_k > c_k + d_k +1$

Note: This is needed to complete the argument in step (8). Ultimately the difference comes down to the fraction versus the error term. This argument, if valid, shows that even with the error term, there is at least one prime that must exist.

  • Here are the recurrent values for $c_k,d_k$ up to $k=5$ where $c_1 = \dfrac{1}{2}$ and $d_1 = 0$:

$$c_2 = \frac{1}{2} + \frac{0}{3} = \frac{1}{2}, d_2 = 0 + \frac{\frac{1}{2}}{3} = \frac{1}{6}$$

$$c_3 = \frac{1}{2} + \frac{\frac{1}{6}}{5} = \frac{8}{15}, d_3 = \frac{1}{6} + \frac{\frac{1}{2}}{5} = \frac{4}{15}$$

$$c_4 = \frac{8/15} + \frac{\frac{4}{15}}{7} = \frac{4}{7}, d_4 = \frac{4/15} + \frac{\frac{8}{15}}{7} = \frac{12}{35}$$

$$c_5 = \frac{4}{7} + \frac{\frac{12}{35}}{11} = \frac{232}{385}, d_5 = \frac{12}{35} + \frac{\frac{4}{7}}{11} = \frac{152}{385}$$

  • For $k=5$:

$$\prod\limits_{i=1}^{5}\left(\frac{p_i-1}{p_i}\right)11 > 2.28 > 1.998 > \frac{232}{385} + \frac{152}{385} + 1 = \frac{384}{385} + 1$$

  • Assume $\prod\limits_{i=1}^{k}\left(\dfrac{p_i-1}{p_i}\right)p_k > c_k + d_k +1$

  • $p_{k+1}\left(p_{k+1} - p_k -1\right) > p_k$ for $k \ge 2$

  • $(p_{k+1} - 1) - p_k > \dfrac{p_k}{p_{k+1}}$

  • $\left(\dfrac{p_{k+1}-1}{p_{k+1}}\right)p_{k+1} - p_k > \dfrac{p_k}{p_{k+1}}$

  • $\left(\prod\limits_{i=1}^k\dfrac{p_i-1}{p_i}\right)\left[\left(\dfrac{p_{k+1}-1}{p_{k+1}}\right)p_{k+1} - p_k\right] > \dfrac{\left(\prod\limits_{i=1}^k\dfrac{p_i-1}{p_i}\right)p_k}{p_{k+1}}$

  • $\left(\prod\limits_{i=1}^k\dfrac{p_i-1}{p_i}\right)\left[\left(\dfrac{p_{k+1}-1}{p_{k+1}}\right)p_{k+1} - p_k\right]=\left(\prod\limits_{i=1}^{k+1}\dfrac{p_i-1}{p_i}\right)p_{k+1} - \left(\prod\limits_{i=1}^k\dfrac{p_i-1}{p_i}\right)p_k$

  • Adding $\left(\prod\limits_{i=1}^k\dfrac{p_i-1}{p_i}\right)p_k$ to both sides:

$$\left(\prod\limits_{i=1}^{k+1}\dfrac{p_i-1}{p_i}\right)p_{k+1} > \left(\prod\limits_{i=1}^k\dfrac{p_i-1}{p_i}\right)p_k + \dfrac{\left(\prod\limits_{i=1}^k\dfrac{p_i-1}{p_i}\right)p_k}{p_{k+1}}$$

  • By the assumption, $\dfrac{\left(\prod\limits_{i=1}^k\dfrac{p_i-1}{p_i}\right)p_k}{p_{k+1}} > \dfrac{c_k + d_k}{p_{k+1}}$ so that:

$$\left(\prod\limits_{i=1}^{k+1}\dfrac{p_i-1}{p_i}\right)p_{k+1} > c_k + d_k + \dfrac{c_k + d_k}{p_{k+1}} + 1$$

$\left(\prod\limits_{i=1}^{k+1}\dfrac{p_i-1}{p_i}\right)p_{k+1} > \left(c_k + \dfrac{d_k}{p_{k+1}}\right) + \left(d_k + \dfrac{c_k}{p_{k+1}}\right) = c_{k+1} + d_{k+1} + 1$

(3) Let:

Note: The purpose behind these definitions is just to define $|S(x,n)|$ which is the count of integers in the consecutive sequence of $\{1, 2, ..., n\}$ that are either $1$ or have a least prime factor greater than $x$.

  • $𝑥\#$ be the primorial of $𝑥$ so that $6\#=5\#=30$ and $7\#=210$

  • gcd$(a,b)$ be the greatest common divisor of $a$ and $b$.

  • $S(𝑥,𝑛)$ be the set of integers such that $𝑠 \in 𝑆(𝑥,𝑛)$ if and only if gcd$(𝑠,𝑥\#)=1$ and $𝑠\le 𝑛$

  • $|𝑆(𝑥,𝑛)|$ be the number of elements in the set $𝑆(𝑥,𝑛)$

  • $C_x(n)=|S(x,n)|$ be a function equal to $|S(x,n)|$

(4) $C_{p_k}(n) = C_{p_{k-1}}(n) - C_{p_k{k-1}}\left(\frac{n}{p_k}\right)$

Note 1: This is the major insight of the whole argument. It is what enables me to complete the inductive proofs used. It shows how the count of integers in $\{1,2,\dots,n\}$ that have a least prime factor greater than $p_k$ can be derived from the count of integers in $\{1,2,\dots,n\}$ that have a least prime factor greater than $p_{k-1}$.

Note 2: This count includes $1$ which gets subtracted out in step (8). So, to be clear, $C_x(n) = |S(x,n)|$ = the count of integers with.a least prime factor greater than $x$ plus $1$.

  • Let $T \subset S(p_{k-1},n)$ be the set of elements divisible by $p_k$.

  • $S(p_k,n) = S(p_{k-1},n) - T$

  • Clearly, $t \in T$ if and only if $\dfrac{t}{p_k} \in S(p_{k-1},\frac{n}{p_k})$

(5) Let:

Note: the upper bound function $U_k(n)$ and the lower bound function $L_k(n)$ consist of the fraction mentioned in step (1) and the error terms $c_k, d_k$ defined in step(1).

  • $U_k(n) = \prod\limits_{i=1}^{k}\left(\dfrac{p_i-1}{p_i}\right)n + c_k$

  • $L_k(n) = \prod\limits_{i=1}^{k}\left(\dfrac{p_i-1}{p_i}\right)n - d_k$

(6) For any integer $n,w$ such that $\dfrac{n}{w} \ge 1$:

$$\frac{U_k(n)}{w} \ge C_{p_k}\left(\frac{n}{w}\right) - v \ge \frac{L_k(n)}{w} \text{ where } 0 \le v \le 1$$

  • $C_2\left(\dfrac{n}{w}\right) = \left\lfloor\dfrac{\frac{n}{w}+1}{2}\right\rfloor = \left\lfloor\dfrac{n+w}{2w}\right\rfloor$

  • For $k=1$,

$$\frac{U_1(n)}{w} = \frac{\frac{n}{2} + \frac{1}{2}}{w} = \frac{n+1}{2w} > \frac{n+w-w}{2w} > \left\lfloor\dfrac{n+w}{2w}\right\rfloor - 1$$

  • So, clearly, since $U_1(n) > L_1(n)$, there exists $v$ such that:

$$\frac{U_1(n)}{w} \ge C_2\left(\dfrac{n}{w}\right) - v \ge \frac{L_1(n)}{w}$$

  • Assume for $\dfrac{n}{w} \ge 1$ there exists $0 \le v \le 1$ so that:

$$\dfrac{U_k(n)}{w} \ge C_{p_k}\left(\frac{n}{w}\right)- v \ge \dfrac{L_k(n)}{w}$$

  • From Step(4):

$$C_{p_{k+1}}\left(\frac{n}{w}\right) = C_{p_k}\left(\frac{n}{w}\right) - C_{p_k}\left(\frac{n}{wp_{k+1}}\right) \le \frac{U_k(n)}{w} + v - \frac{L_k(n)}{w p_{k+1}} = \frac{n\prod\limits_{i=1}^{k}\left(\frac{p_i-1}{p_i}\right)\left(1 - \frac{1}{p_{k+1}}\right) + c_k + \frac{d_k}{p_{k+1}}}{w} + v = \frac{U_{k+1}(n)}{w} + v$$

$$C_{p_{k+1}}\left(\frac{n}{w}\right) = C_{p_k}\left(\frac{n}{w}\right) - C_{p_k}\left(\frac{n}{wp_{k+1}}\right) \ge \frac{L_k(n)}{w} + v - \frac{U_k(n)}{w p_{k+1}} - v = \frac{n\prod\limits_{i=1}^{k}\left(\frac{p_i-1}{p_i}\right)\left(1 - \frac{1}{p_{k+1}}\right) - d_k - \frac{c_k}{p_{k+1}}}{w} = \frac{L_{k+1}(n)}{w}$$

  • Let:

$$r = \frac{U_{k+1}(n)}{w} + v - C_{p_{k+1}}\left(\frac{n}{w}\right)\text{ where }r \ge 0$$

$$s = \frac{U_{k+1}(n)}{w} - \frac{L_{k+1}(n)}{w}\text{ where }s > 0$$

$$t = C_{p_{k+1}}\left(\frac{n}{w}\right) - \frac{L_{k+1}(n)}{w}\text{ where } t \ge 0$$

  • If $r \le s$, then:

$$\frac{U_{k+1}}{w} \ge C_{p_{k+1}}\left(\frac{n}{w}\right) - v \ge \frac{L_{k+1}}{w}\text{ where }0\le v\le 1$$

  • If $r > s$ and $v \le r$, then:

$$\frac{U_{k+1}}{w} \ge C_{p_{k+1}}\left(\frac{n}{w}\right) \ge \frac{L_{k+1}}{w}\text{ where }v=0$$

  • If $r > s$ and $v > r$, then:

$$C_{p_{k+1}}\left(\frac{n}{w}\right) > \frac{U_{k+1}}{w} > \frac{L_{k+1}}{w}\ge C_{p_{k+1}}\left(\frac{n}{w}\right) - v \text{ where }0\le v\le 1$$

  • So that, $0 < s < v < 1$ and it has been show than:

$$\frac{U_{k+1}}{w} > C_{p_{k+1}}\left(\frac{n}{w}\right) - s \ge \frac{L_{k+1}}{w}\text{ where }0 < s < 1$$

(7) $U_k(n) \ge C_{p_k}(n) \ge L_k(n)$

Follows from step (6) when $w=1$

(8) For $x \ge 11$, there is always a prime between $(x^2+x)$ and $x^2$

  • Let $p_k$ be the highest prime less than or equal to $x$

  • $C_x(x^2+x) - C_x(x^2) = C_{p_k}(x^2+x) - C_{p_k}(x^2) \ge L_k(x^2+x) - U_k(x^2) - v \ge \prod\limits_{i=1}^{k}\left(\dfrac{p_i-1}{p_i}\right)(x^2+x) - \prod\limits_{i=1}^{k}\left(\dfrac{p_i-1}{p_i}\right)(x^2) - c_k - d_k- 1 = \prod\limits_{i=1}^{k}\left(\dfrac{p_i-1}{p_i}\right)(x)- c_k - d_k - 1 \ge \prod\limits_{i=1}^{k}\left(\dfrac{p_i-1}{p_i}\right)(p_k)- c_k - d_k -1$

  • From Step (2):

$$\prod\limits_{i=1}^{k}\left(\dfrac{p_i-1}{p_i}\right)(p_k)- c_k - d_k -1 > 0$$

(9) Legendre's Conjecture is true for $x < 11$ since:

  • $2^2 < 5 < 2^2+2$
  • $3^2 < 11 < 3^2+3$
  • $4^2 < 17 < 4^2+4$
  • $5^2 < 29 < 5^2+5$
  • $6^2 < 37 < 6^2+6$
  • $7^2 < 53 < 7^2+7$
  • $8^2 < 67 < 8^2+8$
  • $9^2 < 83 < 9^2+9$
  • $10^2 < 101 < 10^2+10$

Edit 1:

Based on feedback, I have added additional details to step (2) to make it easier to find the mistake.

Please let me know in the comments if any other steps need clarification.

Below is an overview of thinking behind the main argument at step(8):

  • $|S(x,n)|$ is the count of positive numbers less than or equal to $n$ with a least prime factor greater than $x$.

  • $|S(x,x^2+x)| - |S(x,x^2)|$ is the count of positive numbers in the range $[x^2,x^2+x]$ that have a least prime factor greater than $x$.

  • Any number less than $(x+1)^2$ that has a least prime factor greater than $x$ must be prime.

  • Since the count is discrete, if the estimate is greater than $0$ it must be at least $1$.

  • If my argument were valid, $U_k(n)$ would be an upper bound on the count of numbers less than or equal to $n$ that have a least prime factor greater than $p_k$, the $k$th prime.

  • Likewise, $L_k(n)$ would be the lower bound on the count of numbers less than or equal to $n$ that have least prime factor greater than $p_k$.

  • Let $p_k$ be the highest prime less than or equal to $x$.

  • Then, it follows that the number of primes in $[x^2,x^2+x] = |S(x,x^2+x)| - |S(x,x^2)| = |S(p_k,x^2+x)| - |S(p_k,x^2)| \ge L_k(x^2+x) - U_k(x^2)$

  • The last part of step(8) if valid would show that $L_k(x^2+x) - U_k(x^2) > 0$ which would imply that $|S(x,x^2+x)| - |S(x,x^2)| \ge 1$.

Edit 2:

I have been asked in the comments to include the motivation for this argument and an introduction to each of the abstractions.

My purpose in this argument was to see if it is possible to find a very tight upper and lower bound on the count of the integers with a least prime factor greater than $x$ in a given range such as $[x^2,x^2+x]$ that does not depend on floor functions.

The argument attempts to take advantage of a single insight (see step 4):

  • Let $p_k$ be the $k$th prime.
  • Let $|S(p_k,n)|$ be the count of integers less than or equal to $n$ with a least prime factor greater than $p_k$.


$$|S(p_{k+1},n)| = |S(p_k,n)| - |S(p_k,\frac{n}{p_{k+1}})|$$

The argument then defines 2 functions (U_k(n),L_k(n)) and 2 recurrence relations to establish a tight upper and lower bound.

$c_k,d_k$ are bounds on the difference between the fraction $\prod\limits_{I=1}^{k}\left(\dfrac{p_i-1}{p_i}\right)$ and the actual count.

What surprised me was that using simple inductive proof, I the relationship between $U_k(n),L_k(n)$ and $|S(p_k,n)|$ seems to hold so that:

$$U_k(n) \ge |S(p_k,n)| \ge L_k(n)$$

Further, it appeared that I could show that for $|S(x,x^2+x)| - |S(x,x^2)|$:

$$L_k(x^2+x) - U_k(x^2) > 0$$.

I have added more details to the argument. I hope that it helps to show my motivation and make it easier to identify the problem with the argument.

Edit 3:

I found the mistake. It is the basis step in step (6) since:

$\dfrac{n+1}{2w} \le \dfrac{\frac{n}{w}+1}{2} = \dfrac{n+w}{2w}$

If for example $n=25,w=5$

$$\dfrac{n+1}{2w}=\dfrac{26}{10} = 2.6 \le \left\lfloor\dfrac{n+w}{2w}\right\rfloor = \left\lfloor\dfrac{30}{10}\right\rfloor = 3$$

Edit 4:

I believe that I fixed the mistake found in Edit 3.

To make the argument easier to follow, I am using a function $C_{x}(n) = |S(x,n)|$ and have removed the argument for Step (7) since it is implied by Step(6) when $w=1$.

While the basis step is not valid for $k=1$ in the original proof, it is greater or equal to $C_2\left(\dfrac{n}{w}\right)-1$ so that an update to step(2) that $\prod\limits_{i=1}^{k}\left(\dfrac{p_i-1}{p_i}\right)p_k > c_k + d_k + 1$, which I believe can be shown, may fix the issue in Edit 3.

Please take a look and let me know if I have failed to fix the previous mistake or if you can find the other mistakes.

Update: Step (6) is wrong.

The basis step was not fixed by my previous edits.

Analysis on why the basis step is beyond repair is provided by @reuns in the comments.

  • $\begingroup$ Let $|S(x,n)| = \sum_{m \le n,gcd(m,\# x)=1} 1 $. For $n \in [x,x^2]$, $|S(x,n)| = \pi(n)-\pi(x)$. Legendre's conjecture is saying that $\pi(x^2)-\pi((x-1)^2) = |S(x,x^2)|-|S(x,(x-1)^2)| \ge 1$. That $|S(x,\# x)| = x\prod_{p\le x} (1-p^{-1})$ and $|S(x,n)| = n \prod_{p \le x}(1-p^{-1}) - O(2^{1+\pi(x)})$ is of no help. Do you see why this answers your question ? The error term $O(2^{1+\pi(x)})$ is way too large in the range $n \in [x,x^2]$. $\endgroup$ – reuns Feb 14 at 22:46
  • 2
    $\begingroup$ @reuns What does ANT mean in this context ? $\endgroup$ – Peter Feb 15 at 12:45
  • 2
    $\begingroup$ @LarryFreeman The proof appears quite complex to me, so you might add some explanations with words to make it easier to follow the proof. $\endgroup$ – Peter Feb 15 at 13:01
  • 2
    $\begingroup$ You are making big deal of $n\prod_{p \le x} (1-p^{-1}) \ge c_k+d_k+1$ but who cares of that in the context of my latter comment ? If you can explain that I will be able to help. $C_{p_k}(n) = C_{p_{k-1}}(n) - C_{p_k{k-1}}\left(\frac{n}{p_k}\right)$ is correct but you need to be clear it is $\lfloor n/p_k \rfloor$ not just $n/p_k$ (solving the recursion gives $\sum_{l | \# x} \mu(l) \lfloor n/l\rfloor$ not $\sum_{l | \# x} \mu(l) n/l$) $\endgroup$ – reuns Feb 16 at 22:23
  • 1
    $\begingroup$ @daniel, reuns is right. I reviewed Step(6) and it is beyond repair for the very reasons that reuns points out. My attempt to fix it just moved the mistake to another place. $\endgroup$ – Larry Freeman Feb 17 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.