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


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

  • 1
    $\begingroup$ 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$ $\endgroup$ – reuns Mar 12 at 1:31
  • $\begingroup$ 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. $\endgroup$ – 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;
    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;

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.