Reasoning with fractional parts and the Möbius function.

ceiling-and-floor-functionselementary-number-theoryfractional-partproof-verification

Let $S(p_k,x)$ be the set of all elements $s$ where $s \le x$ and gcd$(s,p_k\#)=1$ where $p_k$ is the $k$th prime and $p_k\#$ is the primorial for $p_k$.

Let $|S(p_k,x)|$ be the count of elements in $S(p_k,x)$ so that:

$$|S(p_k,x)| = \sum\limits_{i|p_k\#}\left\lfloor\frac{x}{i}\right\rfloor\mu(i)$$

where $\mu(i)$ is the Möbius function.

I am very interested in approximating this count using $\left(\prod\limits_{i=1}^k\dfrac{p_i-1}{p_i}\right)x$ and the fractional part since:

$$\left(\prod\limits_{i=1}^k\frac{p_i-1}{p_i}\right)x – \sum\limits_{i|p_k\#}\left\lfloor\frac{x}{i}\right\rfloor\mu(i) = \sum\limits_{i|p_k\#}\left(\frac{x}{i}\right)\mu(i) – \sum\limits_{i|p_k\#}\left\lfloor\frac{x}{i}\right\rfloor\mu(i) = \sum\limits_{i|p_k\#}\left\{\frac{x}{i}\right\}\mu(i)$$

To analyze the Möbius sum of the partial fractions, I used the following recurrence relations:

  • $f_2(x) = -\left\{\dfrac{x}{2}\right\}$

  • $f_{p_k}(x) = -\left\{\dfrac{x}{p_k}\right\} – \left(\dfrac{1}{p_k}\right)f_{p_{k-1}}(x)$

So that:

$\sum\limits_{i|p_k\#}\left\{\frac{x}{i}\right\}\mu(i) = \sum\limits_{i=1}^k f_{p_i}(x)$

It seems to me that for all $x$, it follows that $-1 < f_{p_k}(x) \le \dfrac{1}{p_k}$

  • $-\dfrac{1}{2} \le f_{2}(x) \le 0$

  • Assume that for $k\ge 1$, $-1 < f_{p_k}(x) \le \dfrac{1}{p_{k}}$

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

  • $f_{p_{k+1}}(x) < 0 – \dfrac{1}{p_{k+1}}(-1) = \dfrac{1}{p_{k+1}}$

Putting this all together offers the following bound independent of $x$:

$$\left(k + \frac{k}{p_k}\right) > \left(\prod\limits_{i=1}^k\frac{p_i-1}{p_i}\right)x – \sum\limits_{i|p_k\#}\left\lfloor\frac{x}{i}\right\rfloor\mu(i) > -\left(k+\frac{k}{p_k}\right)$$

Am I wrong? Did I make a mistake in any step with regard to the fractional part?

The result does seem too good to be true so I suspect that there is a mistake.

Edit 1:

I believe that I may have found the mistake in my reasoning.

$\sum\limits_{i|p_k\#}\left\{\frac{x}{i}\right\}\mu(i)$ is not always equal to $\sum\limits_{i=1}^k f_{p_i}(x)$

For example, consider $x=4, k=2$

$\sum\limits_{i|6}\left\{\frac{4}{i}\right\}\mu(i) = -\left\{\dfrac{1}{3}\right\} + \left\{\dfrac{2}{3}\right\} = \dfrac{1}{3}$

But:

$\sum\limits_{i=1}^2 f_{p_i}(4) = -\left\{\dfrac{1}{3}\right\} – \dfrac{1}{3}\left(-\left\{\dfrac{4}{2}\right\}\right) = -\dfrac{1}{3}$

Edit 2:

For completeness, I believe that these are the correct recurrence relations where $p_0=1$:

  • $f_1(x) = \left\{x\right\}$

  • $f_{p_k}(x) = -\sum\limits_{i=0}^{k-1}f_{p_i}\left(\dfrac{x}{p_k}\right)$

  • $\sum\limits_{i|p_k\#}\left\{\dfrac{x}{i}\right\}\mu(i) = \sum\limits_{i=0}^k f_{p_i}(x)$

For example:

$\sum\limits_{i=0}^2 f_{p_i}(4) = \{4\} -\left\{\dfrac{4}{2}\right\} + \left(-\left\{\dfrac{4}{3}\right\}+\left\{\dfrac{4}{6}\right\}\right)= \dfrac{1}{3}$

Edit 3:

Just wanted to call out that my upper bound is wrong when I put it all together. (See here for the argument)

$$\dfrac{1}{2} + \dfrac{1}{3} + \dots + \dfrac{1}{p_k} < \log_2(k)$$

Best Answer

https://octave-online.net/

    N = 300; mu = zeros(1,N); mu(1) = 1; for n = [1:N], mu(n+n:n:end) = mu(n+n:n:end)-mu(n); end;
    P = primes(N); L = length(P);
    X = zeros(L,N); X(1,:) = [1:N]; 
    for l = [2:L], p = P(l-1); X(l,1:p-1) = X(l-1,1:p-1); X(l,p:N) = X(l-1,p:N)-X(l-1,floor([p:N]/p)); end;
    plot(X(5:5:end,:).');
Related Question