Question

I have been playing around with the Möbius Function and primorials and I am finding results that I am not yet able to understand which I suspect are very elementary.

Here's the current result which is I am working through. Any help is greatly appreciated!

Let $p_k$ be any prime. Let $x$ be any integer.

It seems based on my calculations that $\sum_{i | p_{k}\#} \lfloor{\frac{(x \% i) + (p_k \% i)}{i}}\rfloor\mu(i) \ge -1$

where % is the remainder so that $5 \% 3 = 2$ and $7 \% 3 = 1$

But if we let $x,y$ be any integer, we can find that there exists $x,y$ such that:

$\sum_{i | p_{k}\#} \lfloor{\frac{(x \% i) + (y \% i)}{i}}\rfloor\mu(i) < -1$

For example:

If $x=13$, $y=23$, $p_k = 5$ , then the sum is $-2$

Is there a well known explanation for this? Thanks.

Answer 1

Note that

$$ \lfloor \frac{a \% p + b \% p}{p} \rfloor = \lfloor \frac{a+b}{p} \rfloor - \lfloor \frac{a}{p} \rfloor - \lfloor \frac{b}{p} \rfloor$$

so your expression can be written as $F_{p_k\#}(x+p_k) - F_{p_k\#}(x) - F_{p_k\#}(p_k)$, where

$$ F_n(x) := \sum_{i|n} \lfloor \frac{x}{i} \rfloor \mu(i).$$

Now, the expression $F_n$ can be simplified by elementary number theoretic computations. Indeed, observe that

$$ \lfloor \frac{x}{i} \rfloor = \sum_{m \leq x: i|m} 1$$

and thus after interchanging summations,

$$ F_n(x) = \sum_{m \leq x} \sum_{i|n, i|m} \mu(i).$$

But by Mobius inversion, $\sum_{i|n, i|m} \mu(i)$ equals 1 when n,m are coprime and 0 otherwise. Thus $F_n(x)$ is nothing more than the number of natural numbers $m$ less than $x$ that are coprime to $n$. In particular, this gives

$$ F_{p_k\#}(x+p_k) \geq F_{p_k\#}(x)$$

and

$$ F_{p_k\#}(p_k) = 1$$

which explains your numerically observed phenomenon.

The quantities here are somewhat reminiscent of the quantity $\pi(x+y)-\pi(x)-\pi(y)$ that occurs in the second Hardy-Littlewood conjecture (which, by the way, is widely believed to be false). Indeed, the quantity $F_{p_k\#}(x)$ (that is, the number of natural numbers up to x that have no prime factor less than or equal to $p_k$) is more commonly denoted $\pi(x,p_k)$ in the analytic number theory literature.

EDIT: I also encountered some related expressions and inequalities in my paper http://arxiv.org/abs/0908.4323 (and with more advanced versions of these inequalities also in this paper of Granville and Soundararajan: http://arxiv.org/abs/math/0508361 ).