# Help estimating an exponential sum

If $\sum_{p\mid n} 1=\omega(n)$, with $1\leq t\leq q-1$ an integer, and $q$ an arbitrary prime.

Then what known asymptotics or bounds can be obtained for $\sum_{n\leq x}e^{2\pi i t\omega(n)/q}$

More specifically I am looking for an estimate on,

$$\sum_{p\leq x}\frac{1}{p}\sum_{n\leq x}\sum_{t=1}^{p-1}e^{2\pi i t \omega(n)/p}$$

I am aware that for a fixed constant $c$ that , $e^{c\omega(n)}$ is multiplicative if that helps at all, so that

$$\sum_{n=1}^\infty\frac{e^{2\pi i t\omega(n)/q}}{n^s}=\prod_{p}(1+\frac{e^{2\pi i t/q}}{p^s-1})$$

-
It seems to me that you are trying to estimate the summatory function for $\omega(\omega(n))$. – Gerry Myerson Aug 16 '13 at 1:16
Yes, but I would also be interested in estimates on the partial sums of $\zeta^{\omega(n)}$. – Ethan Aug 16 '13 at 1:49

The sum $\sum_{n\le x} e^{2\pi i t \omega(n)/q}$ is the sum of a multiplicative function whose value at a prime $p$ is $e^{2\pi i t/q}$. Asymptotics for partial sums of multiplicative functions $f$ with $f(p)=z$, a given number, are well understood by work of Selberg and Delange. The answer is $$\sim C x (\log x)^{z-1}/\Gamma(z),$$ where $C = C(f)$ is the limiting value of $(\sum_{n=1}^{\infty} f(n)/n^s) \zeta(s)^{-z}$ as $s\to 1$, and $\Gamma(z)$ is the usual $\Gamma$ function.

See Selberg's paper Note on a paper of L.G. Sathe; or Tenenbaum's book on analytic and probabilistic number theory for more on this topic.

One can also understand the sum of $\omega(\omega(n))$ for $n\le x$ more directly. Almost all numbers up to $x$ have about $\log \log x$ prime factors (up to deviations of about $\sqrt{\log \log x}$), and then a number of size $\log \log x$ would have about $\log \log \log \log x$ prime factors. So I would guess this answer to be about $x \log \log \log \log x$.

-
I wouldn't be so sure about that estimate for $\omega(\omega(n))$ for example similar heuristics wouldn't work on the sum, $$\sum_{n\leq x} \omega(d(n))=x\ln(\ln(x))+O(x)$$ Also I can't seem to find the paper, could you post a link please. – Ethan Aug 16 '13 at 3:50

As Lucia says, in order to estimating $\sum_{n\le x} v^{\omega(n)}$ the key phrase is Selberg-Delange method (there is a chapter about it in Tenenbaum's book "Intro to analytic and probabilistic number theory").

As far as estimating $S(x) =\sum_{n\le x} \omega(\omega(n))$ is concerned, which is what you actually want to do, it is be possible to apply a more direct approach, as Lucia also indicates. I shall elaborate on this below. (Note that this approach is more direct only on the surface, as it depends on results derived via the Selberg-Delange method.) The starting point is the identity $$S(x) = \sum_{r\ge1} \omega(r) \pi_r(x) ,$$ where $$\pi_r(x)=\#\{n\le x: \omega(n)=r\}.$$ Now, we know that \begin{align*} \pi_r(x) &=\left( \lambda\left(\frac{r-1}{\log\log x} \right) + O\left(\frac{r}{(\log\log x)^2}\right)\right)\frac{x}{\log x} \frac{(\log\log x)^{r-1}}{(r-1)!} \\ &\asymp \frac{x}{\log x} \frac{(\log\log x)^{r-1}}{(r-1)!}, \end{align*} uniformly for $r\le 10\log\log x$, where $$\lambda(z) = \frac{1}{\Gamma(z+1)} \prod_p\left(1+\frac{z}{p-1}\right)\left(1-\frac1p\right)^{z}$$ (This is Theorem 4 in page 205 of Tenenbaum's book, 1995 english edition). Larger $r$ should contribute very little to $S(x)$. One can use the Hardy-Ramanujan theorem to bound their contribution, which says that $$\pi_r(x) \le \frac{Ax}{\log x} \frac{(\log\log x+B)^{r-1}}{(r-1)!},$$ for two absolute constants $A$ and $B$ (and all $r\ge1$ and $x\ge3$). So we essentially have that \begin{align*} S(x) &\sim \sum_{r\le 10\log\log x} \omega(r) \pi_r(x) \\ &\sim \sum_{r\le 10\log\log x} \omega(r) \lambda\left(\frac{r-1}{\log\log x} \right) \frac{x}{\log x} \frac{(\log\log x)^{r-1}}{(r-1)!} . \end{align*} Most of the contribution to this sum should come from integers $r=\log\log x+O(\sqrt{\log\log x})$ which have about $\log\log\log\log x$ prime factors. Also, for such $r$ we have that $\lambda((r-1)/\log\log x)\sim1$. The sum of $(\log\log x)^{r-1}/(r-1)!$ over such $r$ should be $\sim \log x$ (this is a baby version of the Central Limit Theorem). So it seems that $S(x)\sim x\log\log\log\log x$.

You might be able to obtain this result using your initial approach too, you have to be careful about the dependence of your estimates on $p$ though.

-