5
$\begingroup$

While analysing the average runtime of an algorithm, I came across the following identity, and would like to know if anybody knows of any references for it?

For $i \in \mathbb{N}$, let $\bar{s}(i)$ denote the square-free part of $i$, eg., $\bar{s}(12) = 3$ (and $\bar{s}(1)=1$). Then $$ \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^{n} \bar{s}(i)}{n^2} = \frac{\pi^2}{30}. $$

Many thanks.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ You have $\prod_p (1+p/p^s+1/p^{2s}+p/p^{3s}+\cdots)$, alternately $1$ and $p$ in coefficients, and likely can write this as a $\zeta$ expression. $\endgroup$
    – Junkie
    Commented Jun 8, 2011 at 21:36
  • 1
    $\begingroup$ I guess it is $\zeta(2s)\zeta(s-1)/\zeta(2s-2)$. $\endgroup$
    – Junkie
    Commented Jun 8, 2011 at 21:46

2 Answers 2

Reset to default
1
$\begingroup$

The question asked for a reference, not a proof. A reference is Karl Greger, Square divisors and square-free numbers, Mathematics Magazine 51, No. 4 (Sept. 1978), 211-219. I make no claim that the result was unknown before Greger's paper.

Improve this answer
$\endgroup$
0
15
$\begingroup$

If my understanding is correct, for "squarefree part" can be "squarefree kernel" in other cases, the generating Dirichlet series is $${\zeta(2s)\zeta(s-1)\over\zeta(2s-2)}=\prod_p\biggl(1+{p\over p^s}+{1\over p^{2s}}+{p\over p^{3s}}+\cdots\biggr)=\sum_n{\bar s(n)\over n^s}$$ alternating $1$ and $p$ as the coefficients, which is a $\zeta$ quotient as indicated. The residue at $s=2$ is $\zeta(4)/\zeta(2)={\pi^4/90\over\pi^2/6}={\pi^2\over 15}$, so that by Perron's formula $$\sum_{n\le X} \bar s(n)={1\over 2\pi i}\int_{(\sigma)}{\zeta(2s)\zeta(s-1)\over\zeta(2s-2)}{X^s ds\over s} \sim {\zeta(4)\over 2\zeta(2)}X^2={\pi^4/90\over2\pi^2/6}X^2={\pi^2\over 30}X^2,$$ with usual conditions about convergence in vertical strips, which are OK here. Dividing by $X^2$ gives the desired limit.

Improve this answer
$\endgroup$
7
  • 3
    $\begingroup$ Junkie, by Perron's formula we have $$\sum_{n\le X} \bar s(n)=\int_{(3)}\frac{\zeta(2s)\zeta(s-1)}{\zeta(2s-2)}\frac{X^s}{s}\,ds\sim \frac{\pi^2}{30}X^2,$$ which is the limit conjectured by the OP. So there is no need to do any partial summation: the extra factor $2$ comes from the $s$ in the denominator of the integrand. $\endgroup$
    – GH from MO
    Commented Jun 8, 2011 at 22:41
  • $\begingroup$ Ah yes, you are right, and really there should be more fretting about convergence. $\endgroup$
    – Junkie
    Commented Jun 8, 2011 at 22:56
  • 1
    $\begingroup$ Thanks guys, but I was only asking if to anyones knowledge this had been considered before (hence reference request). It's sufficiently natural that I thought it must be classical? $\endgroup$
    – Granger
    Commented Jun 9, 2011 at 9:35
  • 1
    $\begingroup$ This is a standard exercise in analytic number theory, regardless if it had been considered before. You got a solution, use it and enjoy it. It is possible that there is a more elementary proof, using convolutions and the hyperbola method. $\endgroup$
    – GH from MO
    Commented Jun 11, 2011 at 4:20
  • 3
    $\begingroup$ @GH - I think it is standard etiquette (and saves space) to determine whether or not a result is already in print, before contributing a proof. Therefore whether a result has been considered before is important. I think you and Junkie misunderstood what I was asking. As it is, writing `this is a standard exercise' would have been a sufficient answer, so thank you. $\endgroup$
    – Granger
    Commented Jun 13, 2011 at 16:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .