Reasoning with fractional parts and the Möbius function.

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)$$

• Why not plot your functions. The recurrence is $f_{k+1}(x) = f_k(x)-f_k(x/p_{k+1}) = \sum_{d | \# p_{k+1}} \mu(d) \{x/d\}$, $g_{k+1}(x) = g_k(x)-g_k(x/p_{k+1}) = \sum_{d | \# p_{k+1}} \mu(d) \lfloor x/d\rfloor = -f_{k+1}(x) + x \sum_{d | \# p_{k+1}} \mu(d)/d$ – reuns Mar 12 at 1:31
• Thanks very much! I'll try that out. Do you have any recommendations for graphing software? I've avoided graphing primarily because I don't have a graphing tool other than Excel but you are right. At this point, I'm wasting my time if I don't use it as part of my analysis before posting. – Larry Freeman Mar 12 at 1:36

    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;