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.

  • $\begingroup$ Perhaps I'm misunderstanding your notation, but in the case $x=13,y=23,p=5$, I get that the sum is $1 + 1 - \lfloor (3 + 3) / 5 \rfloor = 1$. What is the significance of the #? $\endgroup$ – Daniel Loughran Jul 11 '12 at 16:13
  • $\begingroup$ Right, I see now. $p$# means the primorial of p. $\endgroup$ – Daniel Loughran Jul 11 '12 at 16:22

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


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

  • 1
    $\begingroup$ Thanks, Terry! I really appreciate your analysis! :-) I look forward to reading the articles you cited! Cheers, -Larry $\endgroup$ – Larry Freeman Jul 12 '12 at 15:43

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.