MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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)}$. – Gerry Myerson Dec 13 '12 at 22:42
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. – George Lowther Dec 13 '12 at 22:47
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.$$ – George Lowther Dec 13 '12 at 23:47
up vote 15 down vote accepted

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.

share|cite|improve this answer
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)$? – Joel Moreira Dec 13 '12 at 23:37
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. – Peter Humphries Dec 13 '12 at 23:59
Also, you may be interested in the contents of this paper: – Peter Humphries Dec 14 '12 at 0:00
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)$. – Greg Martin Dec 14 '12 at 0:18
@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. – George Lowther Dec 14 '12 at 0:41

Your sequence is

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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