Reasoning about $\left(\left\lfloor\frac{2x}{i}\right\rfloor -2\left\lfloor\frac{x}{i}\right\rfloor\right)$

ceiling-and-floor-functionsmobius-functionprime numbersproof-verification

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$

Best Answer

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.

Related Question