2
$\begingroup$

I am working on an alternative argument for Bertrand's Postulate that depends on the following argument.

Please let me know if I made a mistake or if any point is unclear.

Let:

  • $p_k$ be the $k$th prime.
  • $p_k\#$ be the primorial for $p_k$
  • $\mu(i)$ be the möbius function
  • $r(m,d)$ be the remainder when an integer $m$ is divided by an integer $d$
  • $x \ge 2$ be an integer.

Then:

$\sum\limits_{i|\dfrac{p_k\#}{2}}\left(\left\lfloor\dfrac{2x}{i}\right\rfloor - 2\left\lfloor\dfrac{x}{i}\right\rfloor\right)\mu(i) = -1$ or $0$

Argument:

(1) For any divisor $i$:

  • if $r(x,i) > \dfrac{i-1}{2}$ then:

$-\left\lfloor\dfrac{2x}{i}\right\rfloor + 2\left\lfloor\dfrac{x}{i}\right\rfloor=\dfrac{-2x + r(2x,i) + 2x - 2r(x,i)}{i} = \dfrac{-i}{i} = -1$

  • if $r(x,i) \le \dfrac{i-1}{2}$ then:

$-\left\lfloor\dfrac{2x}{i}\right\rfloor + 2\left\lfloor\dfrac{x}{i}\right\rfloor=\dfrac{-2x + r(2x,i) + 2x - 2r(x,i)}{i} = 0$

(2) For any nonprime divisor $i$ with factors $f_1, \dots, f_n$:

  • if for any factor $f_j$, $r(x,f_j) \le \dfrac{f_j-1}{2}$, then:

$f_1 \dots \dfrac{f_j-1}{2} \dots f_n = \dfrac{(f_1 \dots f_j \dots f_n) - (f_1 \dots f_n)}{2} < \dfrac{f1 \dots f_j \dots f_n-1}{2}$

  • So, only if for all factors $f_j$ of $i$, $r(x,f_j) > \dfrac{f_j-1}{2}$ will:

$\left(\left\lfloor\dfrac{2x}{i}\right\rfloor - 2\left\lfloor\dfrac{x}{i}\right\rfloor\right)\mu(i) =\mu(i)$

(3) So, let $P$ be the set of odd primes $p_i$ such that $p_i \le p_k$ and $r(x,p_i) > \dfrac{p_i-1}{2}$

(4) For all $i | \dfrac{p_k\#}{2}$, if there exists $p_j \not\in P$ such that $p_j | i$, then:

$\left(\left\lfloor\dfrac{2x}{i}\right\rfloor - 2\left\lfloor\dfrac{x}{i}\right\rfloor\right)\mu(i) =0$

(5) It follows that if $|P| =$ the number of elements in $P$:

$\sum\limits_{i|\dfrac{p_k\#}{2}}\left(\left\lfloor\dfrac{2x}{i}\right\rfloor - 2\left\lfloor\dfrac{x}{i}\right\rfloor\right)\mu(i) = \sum\limits_{i=1}^{|P|}{{|P|}\choose{i}}(-1)^{i}$

(6) Using the Binomial Theorem, we know that:

$-1=(1-1)^{|P|} - 1 = \sum\limits_{i=0}^{|P|}{{|P|}\choose{i}}(-1)^i - 1= \sum\limits_{i=1}^{|P|}{{|P|}\choose{i}}(-1)^i$

(7) In conclusion:

  • If there are any primes $p_i \le p_k$ with $r(x,p_i) > \dfrac{p_i-1}{2}$, then:

$\sum\limits_{i|\dfrac{p_k\#}{2}}\left(\left\lfloor\dfrac{2x}{i}\right\rfloor - 2\left\lfloor\dfrac{x}{i}\right\rfloor\right)\mu(i) = -1$

  • If there are no primes $p_i \le p_k$ with $r(x,p_i) > \dfrac{p_i-1}{2}$, then:

$\sum\limits_{i|\dfrac{p_k\#}{2}}\left(\left\lfloor\dfrac{2x}{i}\right\rfloor - 2\left\lfloor\dfrac{x}{i}\right\rfloor\right)\mu(i) = 0$


Edit:

Step 2 is wrong which invalidates the argument.

I have added a definition for $x$

$\endgroup$
1
$\begingroup$

I have several comments. First, in what you're trying to show of

$\sum\limits_{i|\dfrac{p_k\#}{2}}\left(\left\lfloor\dfrac{2x}{i}\right\rfloor - 2\left\lfloor\dfrac{x}{i}\right\rfloor\right)\mu(i) = -1$ or $0$

you don't define what $x$ is. As such, for now, I will assume it can represent any integer.

Next, a minor issue is that in your argument (1), you are using the negative of $\left\lfloor\dfrac{2x}{i}\right\rfloor - 2\left\lfloor\dfrac{x}{i}\right\rfloor$ used in what you're trying to show. To me at least, it would be slightly less confusing to use the same expression instead to show the result is always $1$ or $0$.

With your argument (2), you say that the expression

$f_1 \dots \dfrac{f_j-1}{2} \dots f_n = \dfrac{(f_1 \dots f_j \dots f_n) - (f_1 \dots f_n)}{2} < \dfrac{f1 \dots f_j \dots f_n-1}{2}$

is true

if for any factor $f_j$, $r(x,f_j) \le \dfrac{f_j-1}{2}$

However, the expression is true in all cases where there are at least $2$ factors $\gt 1$ since the middle part is just expanding the left side, and the right side inequality is true as long as "$f_1 \dots f_n \gt 1$". Also, I also found the way you're expressing it to be a bit confusing. You are using "$f_1 \dots f_n$" to mean the product of all factors $f_i$ for $i$ from $1$ to $n$ except for $i = j$. I can see this from the context, but it is, as far as I know, not a standard or clear way to indicate this. Instead, I suggest you use product notation, with an indication to not include $i = j$ in the product where appropriate, to write your expression. In this case, it could be written instead as

$$\frac{f_j - 1}{2}\prod_{i=1,\; i\neq j}^n f_i = \frac{\prod_{i=1}^n f_i - \prod_{i=1,\; i\neq j}^n f_i}{2} \lt \frac{\prod_{i=1}^n f_i - 1}{2}$$

Next, you go on to state that:

So, only if for all factors $f_j$ of $i$, $r(x,f_j) > \dfrac{f_j-1}{2}$ will:

$\left(\left\lfloor\dfrac{2x}{i}\right\rfloor - 2\left\lfloor\dfrac{x}{i}\right\rfloor\right)\mu(i) =\mu(i)$

I don't see how you came to this conclusion. Also, note it doesn't always hold. For example, if $i = 15$ and $x = 25$, then $f_j = 3$ is a factor of $i$, with $r(25, 3) = 1$, but $\frac{3-1}{2} = 1$, so it's not true that $r(x,f_j) > \dfrac{f_j-1}{2}$ in this case. However, $\left\lfloor\dfrac{2x}{i}\right\rfloor - 2\left\lfloor\dfrac{x}{i}\right\rfloor = \left\lfloor\dfrac{50}{15}\right\rfloor - 2\left\lfloor\dfrac{25}{15}\right\rfloor = 3 - 2 \times 1 = 1$.

However, the logic in the rest of the proof seems to be correct based on the second part of your (2) being true.

If I've misunderstood or misrepresented anything, please let me know. Thanks.

$\endgroup$
  • $\begingroup$ Your comments are spot on. I believe that you have identified a mistake in my reasoning which I need to think more about! :-) I will update my question to make it less confusing based on your comments! $\endgroup$ – Larry Freeman Apr 18 at 1:25
2
$\begingroup$

First of all $\sum_{d=1}^x \mu(d) \lfloor x/d \rfloor = 1$ so if $\prod_{p \le x} p$ divides $n$ then $\sum_{d | n}\mu(d) \lfloor x/d \rfloor = 1$.

Otherwise let $x = kn+a$ with $a \in [0,n)$. $$\sum_{d | n} \mu(d) \lfloor x/d \rfloor = \sum_{m \le x, gcd(m,n)=1}1 = \phi(n) \lfloor x/n\rfloor + \sum_{m =1, gcd(m,n)=1}^a 1$$

If $a \in [0,n/2)$ then

$$\sum_{d | n} \mu(d) (\lfloor 2x/d \rfloor - 2\lfloor x/d \rfloor)=\sum_{m =1 ,gcd(m,n)=1}^{2a}1 -2\sum_{m =1, gcd(m,n)=1}^a 1$$

$\lfloor 2x/d \rfloor - 2\lfloor x/d \rfloor \in \{0,1\}$ so we have the bound $\sum_{d | n, d \le x} 1$

If $n= \prod_{p \le k} p$ with $k > \sqrt{2a}$ then $$\sum_{d | n} \mu(d) (\lfloor 2x/d \rfloor - 2\lfloor x/d \rfloor)= \max(0,\pi(2a)-\pi(k)) - 2\max(0,\pi(a)-\pi(k))$$

And $\sum_{d | \frac{n}2} \mu(d) (\lfloor 2x/d \rfloor=\sum_{m =1 ,gcd(m,\frac{n}{2})=1}^{2a}1 = \sum_{l \ge 0} \sum_{m =0 ,gcd(2m+1,n)=1}^{a / 2^l-1}1$

If $a \in [n/2,n)$ it is $\sum_{d | n} \mu(d) (\lfloor 2x/d \rfloor - 2\lfloor x/d \rfloor)=\phi(n)+\sum_{m =1 ,gcd(m,n)=1}^{2a-n}1 -2\sum_{m =1, gcd(m,n)=1}^a 1$

$\endgroup$
  • $\begingroup$ Your thinking is very educational for me! Thank you very much for the analysis! $\endgroup$ – Larry Freeman Apr 18 at 1:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.