# Tag Archives: analytic number theory

## Estimating the number of squarefree integers up to $X$

I recently wrote an answer to a question on MSE about estimating the number of squarefree integers up to $X$. Although the result is known and not too hard, I very much like the proof and my approach. So I write it down here.

First, let’s see if we can understand why this “should” be true from an analytic perspective.

We know that
$$\sum_{n \geq 1} \frac{\mu(n)^2}{n^s} = \frac{\zeta(s)}{\zeta(2s)},$$
and a general way of extracting information from Dirichlet series is to perform a cutoff integral transform (or a type of Mellin transform). In this case, we get that
$$\sum_{n \leq X} \mu(n)^2 = \frac{1}{2\pi i} \int_{(2)} \frac{\zeta(s)}{\zeta(2s)} X^s \frac{ds}{s},$$
where the contour is the vertical line $\text{Re }s = 2$. By Cauchy’s theorem, we shift the line of integration left and poles contribute terms or large order. The pole of $\zeta(s)$ at $s = 1$ has residue
$$\frac{X}{\zeta(2)},$$
so we expect this to be the leading order. Naively, since we know that there are no zeroes of $\zeta(2s)$ on the line $\text{Re } s = \frac{1}{2}$, we might expect to push our line to exactly there, leading to an error of $O(\sqrt X)$. But in fact, we know more. We know the zero-free region, which allows us to extend the line of integration ever so slightly inwards, leading to a $o(\sqrt X)$ result (or more specifically, something along the lines of $O(\sqrt X e^{-c (\log X)^\alpha})$ where $\alpha$ and $c$ come from the strength of our known zero-free region.

In this heuristic analysis, I have omitted bounding the top, bottom, and left boundaries of the rectangles of integration. But proceeding in a similar way as in the proof of the analytic prime number theorem, you could proceed here. So we expect the answer to look like
$$\frac{X}{\zeta(2)} + O(\sqrt X e^{-c (\log X)^\alpha})$$
using no more than the zero-free region that goes into the prime number theorem.

We will now prove this result, but in an entirely elementary way (except that I will refer to a result from the prime number theorem). This is below the fold.

## Calculations with a Gauss-type Sum

It’s been a while since I’ve posted – I’m sorry. I’ve been busy, perhaps working on a paper (let’s hope it becomes a paper) and otherwise trying to learn things. This post is very closely related to some computations that have been coming up in what I’m currently looking at (in particular, looking at h-th coefficients of Eisenstein series of half-integral weight). I hope to write a very expository-level article on this project that I’ve been working on, outsourcing but completely providing computations behind the scenes in posts such as this one.

I’d like to add that this post took almost no time to write, as I used some vim macros and latex2wp to automatically convert a segment of something I’d written into wordpress-able html containing the latex. And that’s pretty awesome.

There is a particular calculation that I’ve had to do repeatedly recently, and that I will mention and use again. In an effort to have a readable account of this calculation, I present one such account here. Finally, I cannot help but say that this (and the next few posts, likely) are all joint work with Chan and Mehmet, also from Brown University.

Let us consider the following generalized Gauss Sum:

$\displaystyle H_m(c’) : = \varepsilon_{c’} \sum_{r_1\bmod c’}\left(\frac{r_1}{c’}\right) e^{2 \pi i m\frac{r_1}{c’}} \ \ \ \ \ (1)$

where I let ${\left(\frac{\cdot}{\cdot}\right)}$ be the Legendre Symbol, and there ${\varepsilon_k}$ is the sign of the ${k}$th Gauss sum, so that it is ${1}$ if ${k \equiv 1 \mod 4}$ and it is ${i}$ if ${k \equiv 3 \mod 4}$. It is not defined for ${k}$ even.

Lemma 1 ${H_m(n)}$ is multiplicative in ${n}$.

Proof: Let ${n_1,n_2}$ be two relatively prime integers. Any integer ${a \bmod n_1n_2}$ can be written as ${a = b_2n_1 + b_1n_2}$, where ${b_1}$ runs through integers ${\bmod\, n_1}$ and ${b_2}$ runs ${\bmod\, n_2}$ with the Chinese Remainder Theorem. Then

$\displaystyle H_m(n_1n_2) = \varepsilon_{n_1n_2} \sum_{a \bmod n_1n_2} \left(\frac{a}{n_1n_2}\right) e^{2\pi i m \frac{a}{n_1n_2}}$

$\displaystyle = \varepsilon_{n_1n_2} \sum_{b_1 \bmod n_1} \sum_{b_2 \bmod n_2} \left(\frac{b_2n_1 +b_1n_2}{n_1n_2}\right) e^{2 \pi im\frac{b_2n_1 +b_1n_2}{n_1n_2}}$

$\displaystyle = \varepsilon_{n_1n_2} \sum_{b_1 \bmod n_1} \left(\frac{b_2n_1 +b_1n_2}{n_1}\right) e^{2\pi i m \frac{b_1n_2}{n_1n_2}} \sum_{b_2\bmod n_2} \left(\frac{b_2n_1 +b_1n_2}{n_2}\right) e^{2\pi im\frac{b_2n_1}{n_1n_2}}$

$\displaystyle = \varepsilon_{n_1n_2} \sum_{b_1 \bmod n_1} \left(\frac{b_1n_2}{n_1}\right) e^{2\pi i m \frac{b_1}{n_1}} \sum_{b_2\bmod n_2} \left(\frac{b_2n_1}{n_2}\right) e^{2\pi im\frac{b_2}{n_2}}$

$\displaystyle = \varepsilon_{n_1n_2}\left(\frac{n_2}{n_1}\right)\left(\frac{n_1}{n_2}\right)\sum_{b_1 \bmod n_1} \left(\frac{b_1}{n_1}\right) e^{2\pi i m \frac{b_1}{n_1}} \sum_{b_2\bmod n_2} \left(\frac{b_2}{n_2}\right) e^{2\pi im\frac{b_2}{n_2}}$

$\displaystyle = \varepsilon_{n_1n_2} \varepsilon_{n_1}^{-1} \varepsilon_{n_2}^{-1} \left(\frac{n_2}{n_1}\right)\left(\frac{n_1}{n_2}\right) H_m(n_1)H_{m}(n_2)$

Using quadratic reciprocity, we see that ${\varepsilon_{n_1n_2} \varepsilon_{n_1}^{-1} \varepsilon_{n_2}^{-1} \left(\frac{n_2}{n_1}\right)\left(\frac{n_1}{n_2}\right)= 1}$, so that ${H_m(n_1n_2) = H_m(n_1)H_m(n_2)}$. $\Box$

Let’s calculate ${H_m(p^k)}$ for prime powers ${p^k}$. Let ${\zeta = e^{2\pi i /p^k}}$ be a primitive ${p^k}$th root of unity. First we deal with the case of odd ${p}$, ${p\not |m}$. If ${k = 1}$, we have the typical quadratic Gauss sum multiplied by ${\varepsilon _p}$

$\displaystyle H_m(p) = \varepsilon_p \sum_{a \bmod p} e^{2\pi i m \frac a p}\left(\frac a p\right) = \varepsilon_p \left(\frac m p\right) \varepsilon_p \sqrt p = \left(\frac{-m} p\right) \sqrt p \ \ \ \ \ (2)$

For ${k > 1}$, we will see that ${H_m(p^k)}$ is ${0}$. We split into cases when ${k}$ is even or odd. If ${k}$ is even, then we are just summing the primitive ${p^k}$th roots of unity, which is ${0}$. If ${k>1}$ is odd,

$\displaystyle \sum_{a\bmod p^k} \zeta^a \left(\frac a {p^k}\right) = \sum_{a\bmod p^k} \zeta^a \left(\frac{a}{p}\right) = \sum_{b \bmod p}\sum_{c\bmod p^{k-1}} \zeta^{b+pc} \left(\frac b p\right)$

$\displaystyle = \sum_{b\bmod p} \zeta^b \left(\frac b p\right) \sum_{c\bmod p^{k-1}} \zeta^{pc} = 0, \ \ \ \ \ (3)$

since the inner sum is again a sum of roots of unity. Thus

$\displaystyle \left(1+ \frac{\left(\frac{-1^{k + 1/2}}{p}\right)H_m(p)}{p^{2s}} + \frac{\left(\frac{-1^{k + 1/2}}{p^2}\right)H_m(p^2)}{p^{4s}} + \cdots \right) =$

$\displaystyle = \left(1+ \frac{\left(\frac{-1^{k + 1/2}}{p}\right)H_m(p)}{p^{2s}}\right)$

$\displaystyle = \left(1+ \left(\frac {-m(-1)^{k + 1/2}}{p}\right)\frac{1}{p^{2s-\frac12}} \right)$

$\displaystyle = \left. \left(1-\frac1{p^{4s-1}}\right) \middle/ \left(1- \left(\frac{m(-1)^{k – 1/2}}{p}\right)\frac{1}{p^{2s-\frac12}}\right)\right.$

Notice that this matches up with the ${p}$th part of the Euler product for ${\displaystyle \frac{L(2s-\frac12,\left(\frac{m(-1)^{k – 1/2}}{\cdot}\right))}{\zeta(4s-1)}}$.

Now consider those odd ${p}$ such that ${p\mid m}$. Suppose ${p^l \parallel m}$. Then ${e^{2 \pi i m \ p^k} = \zeta^m}$ is a primitive ${p^{k-l}}$th root of unity (or ${1}$ if ${l \geq k}$). If ${l \geq k}$, then

$\displaystyle \sum_{a \bmod p^k} \zeta^{am} \left(\frac{a}{p^k}\right) = \sum_{a \bmod p^k} \left(\frac{a}{p^k}\right) = \begin{cases} 0 &\text{if } 2\not | k \\ \phi(p^k) &\text{if } 2 \mid k \end{cases} \ \ \ \ \ (4)$

If ${k=l+1}$ and ${k}$ is odd, then we essentially have a Gauss sum

$\displaystyle \sum_{a\bmod p^k} \zeta^{am} \left(\frac{a}{p^k}\right) = \sum_{a\bmod p^k}\zeta^{am} \left(\frac a p\right) =$

$\displaystyle = \sum_{c\bmod p^{k-1}} \zeta^{pcm} \sum_{b\bmod p} \zeta^{am} \left(\frac b p\right) = p^{k-1}\left(\frac{m/p^l}{p}\right)\varepsilon_p\sqrt p$

If ${k = l+1}$ and ${k}$ is even, noting that ${\zeta^m}$ is a ${p}$th root of unity,

$\displaystyle \sum_{a\bmod p^k} \zeta^{am}\left(\frac {a}{p^k}\right) = \sum_{\substack{a\bmod p^k\\(a,p) = 1}} \zeta^{am} =$

$\displaystyle = \sum_{a\bmod p^k}\zeta^{am} – \sum_{a\bmod p^{k-1}}\zeta^{pam} = 0 – p^{k-1} = -p^l.$

If ${k>l+1}$ then the sum will be zero. For ${k}$ even, this follows from the previous case. If ${k}$ is odd,

$\displaystyle \sum_{a\bmod p^k} \zeta^{am} \left(\frac a{p^k}\right) = \sum_{b\bmod p}\zeta^{bm} \left(\frac b p \right)\sum_{c\bmod p^{k-1}}\zeta^{pmc}= 0.$

Now, consider the Dirichlet series

$\displaystyle \sum_{c > 0, \tt odd} \frac{H_m(c)}{c^{2s}} = \prod_{p \neq 2} \left( 1 + \frac{H_m(p)}{p^{2s}} + \frac{H_m(p^2)}{p^{4s}} + \ldots\right)$.

Let us combine all these facts to construct the ${p}$th factor of the Dirichlet series in question, for ${p}$ dividing ${m}$. Assume first that ${p^l\parallel m}$ with ${l}$ even,

$\displaystyle 1 + \frac{\left(\frac{-1^{k + 1/2}}{p}\right)H_m(p)}{p^{2s}} + \frac{\left(\frac{-1^{k + 1/2}}{p^2}\right)H_m(p^2)}{p^{4s}}+ \cdots =$

$\displaystyle = \left( 1+ \varepsilon_{p^2}\frac{\phi(p^2)}{p^{4s}} + \cdots + \varepsilon_{p^l}\frac{\phi(p^l)}{p^{2ls}} + \varepsilon_{p^{l+1}}\frac{\left(\frac{(-1)^{k + 1/2}m/p^l}{p}\right)\varepsilon_p \sqrt p p^l}{p^{2(l+1)s}}\right)$

$\displaystyle = \left( 1+\frac{\phi(p^2)}{p^{4s}} + \frac{\phi(p^4)}{p^{8s}}+\cdots +\frac{\phi(p^{l})}{p^{2ls}} + \frac{\left(\frac{(-1)^{k – 1/2}m/p^l}{p}\right)p^{l+\frac12}}{p^{2(l+1)s}}\right)$

$\displaystyle = \left(1+ \frac{p^2 – p}{p^{4s}} + \cdots + \frac{p^{l}-p^{l-1}}{p^{2ls}} + \frac{\left(\frac{(-1)^{k – 1/2}m/p^l}{p}\right)p^{l+\frac12}}{p^{2(l+1)s}}\right)$

$\displaystyle = \left(1-\frac{1}{p^{4s-1}}\right)\left(1+\frac{1}{p^{4(s-\frac12)}} +\cdots + \frac{1}{p^{2(l-2)(s-\frac12)}}\right)+$

$\displaystyle +\frac{p^l}{p^{2ls}} \left(1+ \frac{\left(\frac{(-1)^{k – 1/2}m/p^l}{p}\right)}{p^{2s-\frac12}}\right)$

$\displaystyle = \left(1-\frac{1}{p^{4s-1}}\right) \left(1+ \frac{1}{p^{4(s-\frac12)}}+\cdots +\right.$

$\displaystyle + \left. \frac{1}{p^{2(l-2)(s-\frac12)}} + \frac{1}{p^{2l(s-\frac12)}}\left(1-\frac{\left(\frac{(-1)^{k – 1/2}m/p^l}{p}\right)}{p^{2s-\frac12}}\right)^{-1}\right)$

$\displaystyle = \left(1-\frac{1}{p^{4s-1}}\right) \left(\sum_{i=0}^{\lfloor \frac{l-1}{2} \rfloor} \frac{1}{p^{4(s-\frac12)i}} +\frac{1}{p^{2l(s-\frac12)}}\left(1-\frac{\left(\frac{(-1)^{k – 1/2}m/p^l}{p}\right)}{p^{2s-\frac12}}\right)^{-1} \right)$

because for even ${k}$, ${\varepsilon_{p^k} = 1}$, and for odd ${k}$, ${\varepsilon_{p^k} = \varepsilon_p}$. Similarly, for ${l}$ odd,

$\displaystyle 1+ \frac{\left(\frac{-1^{k + 1/2}}{p}\right)H_m(p)}{p^{2s}} +\frac{\left(\frac{-1^{k + 1/2}}{p^2}\right)H_m(p^2)}{p^{4s}}+ \cdots$

$\displaystyle = \left( 1+ \varepsilon_{p^2}\frac{\phi(p^2)}{p^{4s}} + \varepsilon_{p^4}\frac{\phi(p^4)}{p^{8s}} + \cdots + \varepsilon_{p^{l-1}}\frac{\phi(p^{l-1})}{p^{2(l-1)s}} + \varepsilon_{p^{l+1}}\frac{- p^l}{p^{2(l+1)s}}\right)\nonumber$

$\displaystyle = \left( 1+\frac{\phi(p^2)}{p^{4s}} + \frac{\phi(p^4)}{p^{8s}}+\cdots +\frac{\phi(p^{l-1})}{p^{2(l-1)s}} + \frac{-p^{l}}{p^{2(l+1)s}}\right) \nonumber$

$\displaystyle = \left(1+ \frac{p^2 – p}{p^{4s}} + \frac{p^4-p^3}{p^{8s}} + \cdots + \frac{p^{l-1}-p^{l-2}}{p^{2(l-1)s}} – \frac{p^l}{p^{2(l+1)s}}\right) \nonumber$

$\displaystyle = \left(1-\frac{1}{p^{4s-1}}\right)\left(\sum_{i=0}^{\frac{l-1}{2}} \frac{1}{p^{4(s-\frac12)i}}\right)$

Putting this together, we get that

$\displaystyle \prod_{p \neq 2} \left(\sum_{k=1}^\infty \frac{H_m(p)}{p^{2ks}}\right) = \frac{L_2(2s-\frac12,\left(\frac{m(-1)^{k – 1/2}}{\cdot}\right))}{\zeta_{2}(4s-1)} \times$

$\displaystyle \phantom{\sum \sum\sum\sum} \prod_{p^l \parallel m, p\neq 2} \left(\sum_{i=0}^{\lfloor \frac{l-1}{2} \rfloor} \frac{1}{p^{4(s-\frac12)i}} +\frac{\mathbf{1}_{2{\mathbb Z}}(l)}{p^{2l(s-\frac12)}}\left(1-\frac{\left(\frac{(-1)^{k – 1/2}m/p^l}{p}\right)}{p^{2s-\frac12}}\right)^{-1}\right) \ \ \ \ \ (5)$