What does $\sum \mu(d)\lfloor{\frac{x}{d}}\rfloor$ count?

Question

Where the sum is over all $d$, where $d$ only has prime factors $\leq \sqrt{x}$. I'm trying to determine, in plain English, precisely what this sum is counting.

I know the Möbius function will be 0 if $p^2|x$ when $p|x$, and $(-1)^{k}$ when $x$ is the product of $k$ distinct primes. Further, I understand that $\lfloor{\frac{x}{d}}\rfloor$ determines the number of multiples of $d\leq x$, I'm just struggling to put these functions together in my head. I know that the only such $d$'s that will contribute to the sum will be the product of distinct primes, to the exponent 1, where the primes are less than or equal to $\sqrt{x}$.

I know that my question is related to Legendre's formula ($\pi (x) = -1 + \pi(\sqrt x) + \sum \mu (d)\lfloor \frac {x}{d}\rfloor$,), but I'd like to understand it more combinatorially.

Answer 1

The sum counts the positive integers $\leqslant x$ that are not divisible by any prime $\leqslant \sqrt{x}$. Those integers are $1$ (not divisible by any prime whatsoever) and the primes $\sqrt{x} < p \leqslant x$ (for every composite $1 < n \leqslant x$ is divisible by a prime $q \leqslant \sqrt{n} \leqslant \sqrt{x}$). Accepting this assertion for the moment without proof, we see that $$\sum_{d \mid P} \mu(d)\biggl\lfloor \frac{x}{d}\biggr\rfloor = 1 + \bigl(\pi(x) - \pi(\sqrt{x})\bigr)$$ where $P$ is the product of all primes $\leqslant \sqrt{x}$.

To see that the sum is indeed counting what I claimed, let's begin with taking a look at the inclusion-exclusion principle. If we have a finite set $U$ and a finite family $\{A_{\kappa} : \kappa \in K\}$ of subsets of $U$, the IE-principle gives us a formula for the cardinality of $$U \setminus \bigcup_{\kappa \in K} A_{\kappa}\,.$$ For a more compact notation, let us define $$V_J = \bigcap_{\kappa \in J} A_{\kappa}$$ for all $J \subseteq K$. Since $U$ is our universe of discourse, $V_{\varnothing} = U$ (this is a convention, but like the conventions for empty sums and empty products, it's a convention supported by good practical reasons).

Then the IE-principle says $$\Biggl\lvert\, U \setminus \bigcup_{\kappa \in K} A_{\kappa}\Biggr\rvert = \sum_{J \subseteq K} (-1)^{\lvert J\rvert}\cdot \lvert V_J\rvert = \sum_{r = 0}^{\lvert K\rvert} (-1)^r\sum_{\substack{J \subseteq K \\ \lvert J\rvert = r}} \lvert V_J\rvert\,.$$ The counting on the right hand side goes: First we count the elements of $U$ ($r = 0$). Then we subtract the sizes of all the $A_{\kappa}$ ($r = 1$). But the elements belonging to two $A_{\kappa}$ have been subtracted twice, so we must re-add their number once ($r = 2$). But the elements belonging to three $A_{\kappa}$ have now been subtracted thrice, and re-added thrice, so effectively haven't been subtracted at all. Therefore we subtract their count ($r = 3$). But the elements belonging to four $A_{\kappa}$ have been subtracted $\binom{4}{1}$ times, then re-added $\binom{4}{2}$ times, and subtraced again $\binom{4}{3}$ times. Thus overall they've been subtracted $4 - 6 + 4 = 2$ times, and we must re-add them once ($r = 4$). And so on.

In total, an element belonging to exactly $m$ of the $A_{\kappa}$ is counted $$\sum_{r = 0}^{m} \binom{m}{r} (-1)^r = (1 - 1)^m = \begin{cases}1 &\text{if } m = 0 \\ 0 &\text{if } m > 0 \end{cases}$$ times in this formula.

Here, our universe is the set of positive integers not exceeding $x$, thus $U = \{ n \in \mathbb{N} : 1 \leqslant n \leqslant x\}$. The index set is the set of primes not exceeding $\sqrt{x}$, i.e. $K = \{ p \in \mathbb{N} : p \leqslant \sqrt{x} \text{ and } p \text{ is prime}\}$, and $A_p$ is the set of multiples of $p$ in $U$. For $J \subseteq K$ we have $$V_J = \{n \in U : p \in J \implies p \mid n\}\,,$$ and since distinct primes are pairwise coprime we can also write this as $$V_J = \{n \in U : d_J \mid n\}$$ where $$d_J = \prod_{p \in J} p\,.$$ In this form it is easy to see $$\lvert V_J\rvert = \biggl\lfloor \frac{x}{d_J}\biggr\rfloor$$ and the inclusion-exclusion formula gives us $$1 + \bigl(\pi(x) - \pi(\sqrt{x})\bigr) = \sum_{J \subseteq K} (-1)^{\lvert J\rvert} \lvert V_J\rvert = \sum_{J \subseteq K} (-1)^{\lvert J\rvert}\biggl\lfloor \frac{x}{d_J}\biggr\rfloor\,.$$ Now it only remains to observe that $J \mapsto d_J$ is a bijection between the subsets of $K$ and the divisors of $d_K$, and that for each divisor we have $(-1)^{\lvert J\rvert} = \mu(d_J)$. With this observation, it is clear that $$\sum_{d \mid P} \mu(d)\biggl\lfloor \frac{x}{d}\biggr\rfloor$$ is exactly the sum in the inclusion-exclusion formula counting the positive integers $\leqslant x$ not divisible by any prime $\leqslant \sqrt{x}$.

Answer 2

Since Mobius function is zero as long as the input number is divisible by some squares. Hence, that summation sums over the $M$, product of all primes less $\le\sqrt x$. Hence, the original sum in the question is equivalent to finding

$$ \begin{aligned} \sum_{d|M}\mu(d)\left\lfloor\frac xd\right\rfloor &=\sum_{r=0}^{\pi(\sqrt x)}(-1)^r\sum_{1\le i_1<\cdots<i_r\le\pi(\sqrt x)}\left\lfloor x\over p_{i_1}\cdots p_{i_r}\right\rfloor \end{aligned} $$

wherein $\left\lfloor\frac xm\right\rfloor$ denotes number of multiples of $m$ (including itself) within $x$, and let's denote the set of integer-multiple of $m$ within $x$ by $S_{x,m}$, then for any $(a,b)=1$ we have

$$ \left\lfloor x\over ab\right\rfloor=|S_a\cap S_b| $$

As a result, we can rewrite the sum above by

$$ \sum_{d|M}\mu(d)\left\lfloor\frac xd\right\rfloor=1+\sum_{r=0}^{\pi(x)}(-1)^{r-1}\sum_{1\le i_1<i_r\le\pi(\sqrt x)}\left|\bigcap_{k=1}^rS_{p_{i_r}}\right| $$

wherein the last sum, by inclusion-exclusion principle, represents the number of primes within $x$ but greater than $\sqrt x$. Therefore,

$$ \sum_{d|M}\mu(d)\left\lfloor\frac xd\right\rfloor=1+\pi(x)-\pi(\sqrt x) $$

Rewriting this identity gives a formula for the prime-counting function:

$$ \pi(x)=\pi(\sqrt x)+1+\sum_{d|M}\mu(d)\left\lfloor\frac xd\right\rfloor $$