I am interested in the set $A$ of all positive integer numbers such that when factored into primes, the sum of the exponents is odd (I think of $A$ as the multiplicative odd numbers).

I want to know if it has positive upper density, more precisely $$\bar d(A):=\limsup_{n\to\infty}\frac{|A\cap[1,n]|}n$$ I think I read somewhere that it has density $1/2$ (and the $\lim$ exist, not just the $\limsup$), but I would be happy with a proof that $\bar d(A)>0$.

  • 2
    $\begingroup$ The number of prime factors of $n$, counted with multiplicities, is often denoted $\Omega(n)$. You are asking about $\sum_1^n(-1)^{\Omega(m)}$. $\endgroup$ Dec 13, 2012 at 22:42
  • 1
    $\begingroup$ It will indeed have density 1/2. Just looking at power of 2 factors shows that it is in the range [1/3,2/3]. Then looking at power of 3 factors will get a tighter range about 1/2, and so on. $\endgroup$ Dec 13, 2012 at 22:47
  • 3
    $\begingroup$ To explain my previous comment. Let $S$ be the set of numbers of the form $4^r(2s+1)$. This has density $(1/2)(1+1/4+1/4^2+\cdots)=2/3$. Write $f(n)=\lvert A\cap[1,n]\rvert$. The property that $\Omega(2n)=\Omega(n)+1$ gives $$\lvert A\cap[1,n/2]\cap S\rvert+\lvert A\cap[1,n]\cap S^c\rvert=\lvert S\cap[1,n/2]\rvert.$$ So, $f(n)=\lvert S\cap[1,n/2]\rvert+\lvert A\cap(n/2,n]\cap S\rvert$ giving the inequality $$1/3\le\liminf_{n\to\infty}f(n)/n\le\limsup_{n\to\infty}f(n)/n\le2/3.$$ $\endgroup$ Dec 13, 2012 at 23:47

2 Answers 2


Gerry has the right idea here: you are asking about the limiting behaviour of the sum $$\frac{1}{x} \sum_{n \leq x}{\frac{1 - (-1)^{\Omega(n)}}{2}}.$$ The arithmetic function $\lambda(n) = (-1)^{\Omega(n)}$ is known as Liouville's function. It is well-known (and equivalent to the prime number theorem!) that the summatory function of the Liouville function, $$L(x) = \sum_{n \leq x}{\lambda(n)},$$ satisfies the asymptotic $$L(x) = o(x)$$ as $x$ tends to infinity. (In fact, one can probably improve this slightly in the usual way to get better error terms in the prime number theorem.) So it is indeed true that $$d(A) = \lim_{x \to \infty} \frac{1}{x} \sum_{n \leq x}{\frac{1 - (-1)^{\Omega(n)}}{2}} = \frac{1}{2},$$ and with a little work you could actually say something slightly stronger about the rate at which this converges.

  • $\begingroup$ Thanks! So this seems to be well known among number theorists. Can you give a reference where I can find a proof that $L(x)=o(x)$? $\endgroup$ Dec 13, 2012 at 23:37
  • $\begingroup$ I don't know of a direct reference of such a proof, but this theorem is folklore and it's pretty easy to see why it's true: one can show (say, via comparing Euler products) that $\sum_{n=1}^{\infty}\lambda(n)n^{-s}=\zeta(2s)/\zeta(s)$ for $\Re(s)>1$, then use the fact that this extends meromorphically to the entire complex plane and has no poles in the region $\Re(s)>1-c/\log(|\Im(s)|+2)$. So basically the usual way of proving the prime number theorem, just with a different Dirichlet series. $\endgroup$ Dec 13, 2012 at 23:59
  • 1
    $\begingroup$ Also, you may be interested in the contents of this paper: staff.science.uu.nl/~dahme104/DistributionOmega.pdf $\endgroup$ Dec 14, 2012 at 0:00
  • 3
    $\begingroup$ For example, problem 11(b) in section 6.2 of Montgomery and Vaughan's book "Multiplicative Number Theory I" is to use the method of proof Peter described to prove that $|L(x)| \le Ax \exp({-}c\sqrt{\log x})$ for some positive constants $A$ and $c$. Interestingly, problem 11(c) suggests that it is easy to derive this bound from the corresponding bound for $M(x) = \sum_{n\le x} \mu(n)$, which might be easier to find in the literature. The link between the two functions is given by $\lambda(n) = \sum_{d\colon d^2\mid n} \mu(n/d^2)$. $\endgroup$ Dec 14, 2012 at 0:18
  • $\begingroup$ @Greg: So, you have $L(x)=\sum_d M(x/d^2)$ giving $\limsup_{x\to\infty}\lvert L(x)/x\rvert\le\limsup_{x\to\infty}\lvert M(x)/x\rvert\sum_d d^{-2}$ (=0). Similarly, $M(x)=\sum_d \mu(d)L(x/d^2)$, so you can go in either direction. $\endgroup$ Dec 14, 2012 at 0:41

Your sequence is http://oeis.org/A026424.

Define the zeta density of the set of integers $A$ as

$$ d(A) = \lim_{x \to 1+} \frac1{\zeta(x)} \sum_{k \in A} k^{-x}. $$

Then from results given at the OEIS, this is

$$ d(A) = \lim_{x \to 1+} {1 \over \zeta(x)} \left[ {\zeta(x)^2 - \zeta(2x) \over 2\zeta(x)} \right]. $$

After some simplifcation this is

$$ \lim_{x \to 1} \left( {1 \over 2} - {\zeta(2x) \over 2 \zeta(x)^2} \right) $$

and recalling that $\lim_{x \to 1} \zeta(x)$ is infinity while $\zeta(2) = \pi^2/6$, this is $1/2$.

Now, if a set has a natural density, then it has a zeta density, and the two densities are equal; see for example Chapter 2 of Diaconis' PhD dissertation. So we can conclude that if your set has a natural density, then that natural density is $1/2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.