# Tag Archives: number theory

## Notes from a talk at Dartmouth on the Fibonacci zeta function

I recently gave a talk “at Dartmouth”1. The focus of the talk was the (odd-indexed) Fibonacci zeta function:
$$\sum_{n \geq 1} \frac{1}{F(2n-1)^s},$$
where $F(n)$ is the nth Fibonacci number. The theme is that the Fibonacci zeta function can be recognized as coming from an inner product of automorphic forms, and the continuation of the zeta function can be understood in terms of the spectral expansion of the associated automorphic forms.

This is a talk from ongoing research. I do not yet understand “what’s really going on”. But within the talk I describe a few different generalizations; firstly, there is a generalization to other zeta functions that can be viewed as traces of units on quadratic number fields, and secondly there is a generalization to quadratic forms recognizing solutions to Pell’s equation.

I intend to describe additional ideas from this talk in the coming months, as I figure out how pieces fit together. But for now, here are the slides.

## Pictures of equidistribution – the line

In my previous note, we considered equidistribution of rational points on the circle $X^2 + Y^2 = 2$. This is but one of a large family of equidistribution results that I’m not particularly familiar with.

This note is the first in a series of notes dedicated to exploring this type of equidistribution visually. In this note, we will investigate a simpler case — rational points on the line.

## Update to Second Moments in the Generalized Gauss Circle Problem

Last year, my coauthors Tom Hulse, Chan Ieong Kuan, and Alex Walker posted a paper to the arXiv called “Second Moments in the Generalized Gauss Circle Problem”. I’ve briefly described its contents before.

This paper has been accepted and will appear in Forum of Mathematics: Sigma.

This is the first time I’ve submitted to the Forum of Mathematics, and I must say that this has been a very good journal experience. One interesting aspect about FoM: Sigma is that they are immediate (gold) open access, and they don’t release in issues. Instead, articles become available (for free) from them once the submission process is done. I was reviewing a publication-proof of the paper yesterday, and they appear to be very quick with regards to editing. Perhaps the paper will appear before the end of the year.

An updated version (the version from before the handling of proofs at the journal, so there will be a number of mostly aesthetic differences with the published version) of the paper will appear on the arXiv on Monday 10 December.1

## A new appendix has appeared

There is one major addition to the paper that didn’t appear in the original preprint. At one of the referee’s suggestions, Chan and I wrote an appendix. The major content of this appendix concerns a technical detail about Rankin-Selberg convolutions.

If $f$ and $g$ are weight $k$ cusp forms on $\mathrm{SL}(2, \mathbb{Z})$ with expansions $$f(z) = \sum_ {n \geq 1} a(n) e(nz), \quad g(z) = \sum_ {n \geq 1} b(n) e(nz),$$ then one can use a (real analytic) Eisenstein series $$E(s, z) = \sum_ {\gamma \in \mathrm{SL}(2, \mathbb{Z})_ \infty \backslash \mathrm{SL}(2, \mathbb{Q})} \mathrm{Im}(\gamma z)^s$$ to recognize the Rankin-Selberg $L$-function $$\label{RS} L(s, f \otimes g) := \zeta(s) \sum_ {n \geq 1} \frac{a(n)b(n)}{n^{s + k – 1}} = h(s) \langle f g y^k, E(s, z) \rangle,$$ where $h(s)$ is an easily-understandable function of $s$ and where $\langle \cdot, \cdot \rangle$ denotes the Petersson inner product.

When $f$ and $g$ are not cusp forms, or when $f$ and $g$ are modular with respect to a congruence subgroup of $\mathrm{SL}(2, \mathbb{Z})$, then there are adjustments that must be made to the typical construction of $L(s, f \otimes g)$.

When $f$ and $g$ are not cusp forms, then Zagier2 provided a way to recognize $L(s, f \otimes g)$ when $f$ and $g$ are modular on the full modular group $\mathrm{SL}(2, \mathbb{Z})$. And under certain conditions that he describes, he shows that one can still recognize $L(s, f \otimes g)$ as an inner product with an Eisenstein series as in \eqref{RS}.

In principle, his method of proof would apply for non-cuspidal forms defined on congruence subgroups, but in practice this becomes too annoying and bogged down with details to work with. Fortunately, in 2000, Gupta3 gave a different construction of $L(s, f \otimes g)$ that generalizes more readily to non-cuspidal forms on congruence subgroups. His construction is very convenient, and it shows that $L(s, f \otimes g)$ has all of the properties expected of it.

However Gupta does not show that there are certain conditions under which one can recognize $L(s, f \otimes g)$ as an inner product against an Eisenstein series.4 For this paper, we need to deal very explicitly and concretely with $L(s, \theta^2 \otimes \overline{\theta^2})$, which is formed from the modular form $\theta^2$, non-cuspidal on a congruence subgroup.

The Appendix to the paper can be thought of as an extension of Gupta’s paper: it uses Gupta’s ideas and techniques to prove a result analogous to \eqref{RS}. We then use this to get the explicit understanding necessary to tackle the Gauss Sphere problem.

There is more to this story. I’ll return to it in a later note.

## Other submission details for FoM: Sigma

I should say that there are many other revisions between the original preprint and the final one. These are mainly due to the extraordinary efforts of two Referees. One Referee was kind enough to give us approximately 10 pages of itemized suggestions and comments.

When I first opened these comments, I was a bit afraid. Having so many comments was daunting. But this Referee really took his or her time to point us in the right direction, and the resulting paper is vastly improved (and in many cases shortened, although the appendix has hidden the simplified arguments cut in length).

More broadly, the Referee acted as a sort of mentor with respect to my technical writing. I have a lot of opinions on technical writing,5 but this process changed and helped sharpen my ideas concerning good technical math writing.

I sometimes hear lots of negative aspects about peer review, but this particular pair of Referees turned the publication process into an opportunity to learn about good mathematical exposition — I didn’t expect this.

I was also surprised by the infrastructure that existed at the University of Warwick for handling a gold open access submission. As part of their open access funding, Forum of Math: Sigma has an author-pays model. Or rather, the author’s institution pays. It took essentially no time at all for Warwick to arrange the payment (about 500 pounds).

This is a not-inconsequential amount of money, but it is much less than the 1500 dollars that PLoS One uses. The comparison with PLoS One is perhaps apt. PLoS is older, and perhaps paved the way for modern gold open access journals like FoM. PLoS was started by group of established biologists and chemists, including a Nobel prize winner; FoM was started by a group of established mathematicians, including multiple Fields medalists.6

I will certainly consider Forum of Mathematics in the future.

## The wrong way to compute a sum: addendum

In my previous note, I looked at an amusing but inefficient way to compute the sum $$\sum_{n \geq 1} \frac{\varphi(n)}{2^n – 1}$$ using Mellin and inverse Mellin transforms. This was great fun, but the amount of work required was more intense than the more straightforward approach offered immediately by using Lambert series.

However, Adam Harper suggested that there is a nice shortcut that we can use (although coming up with this shortcut requires either a lot of familiarity with Mellin transforms or knowledge of the answer).

In the Lambert series approach, one shows quickly that $$\sum_{n \geq 1} \frac{\varphi(n)}{2^n – 1} = \sum_{n \geq 1} \frac{n}{2^n},$$ and then evaluates this last sum directly. For the Mellin transform approach, we might ask: do the two functions $$f(x) = \sum_{n \geq 1} \frac{\varphi(n)}{2^{nx} – 1}$$ and $$g(x) = \sum_{n \geq 1} \frac{n}{2^{nx}}$$ have the same Mellin transforms? From the previous note, we know that they have the same values at $1$.

We also showed very quickly that $$\mathcal{M} [f] = \frac{1}{(\log 2)^2} \Gamma(s) \zeta(s-1).$$ The more difficult parts from the previous note arose in the evaluation of the inverse Mellin transform at $x=1$.

Let us compute the Mellin transform of $g$. We find that \begin{align} \mathcal{M}[g] &= \sum_{n \geq 1} n \int_0^\infty \frac{1}{2^{nx}} x^s \frac{dx}{x} \notag \\ &= \sum_{n \geq 1} n \int_0^\infty \frac{1}{e^{nx \log 2}} x^s \frac{dx}{x} \notag \\ &= \sum_{n \geq 1} \frac{n}{(n \log 2)^s} \int_0^\infty x^s e^{-x} \frac{dx}{x} \notag \\ &= \frac{1}{(\log 2)^2} \zeta(s-1)\Gamma(s). \notag \end{align} To go from the second line to the third line, we did the change of variables $x \mapsto x/(n \log 2)$, yielding an integral which is precisely the definition of the Gamma function.

Thus we see that $$\mathcal{M}[g] = \frac{1}{(\log 2)^s} \Gamma(s) \zeta(s-1) = \mathcal{M}[f],$$ and thus $f(x) = g(x)$. (“Nice” functions with the same “nice” Mellin transforms are also the same, exactly as with Fourier transforms).

This shows that not only is $$\sum_{n \geq 1} \frac{\varphi(n)}{2^n – 1} = \sum_{n \geq 1} \frac{n}{2^n},$$ but in fact $$\sum_{n \geq 1} \frac{\varphi(n)}{2^{nx} – 1} = \sum_{n \geq 1} \frac{n}{2^{nx}}$$ for all $x > 1$.

I think that’s sort of slick.

## The wrong way to compute a sum

At a recent colloquium at the University of Warwick, the fact that
\label{question}
\sum_ {n \geq 1} \frac{\varphi(n)}{2^n – 1} = 2.

Although this was mentioned in passing, John Cremona asked — How do you prove that?

It almost fails a heuristic check, as one can quickly check that
\label{similar}
\sum_ {n \geq 1} \frac{n}{2^n} = 2,

which is surprisingly similar to \eqref{question}. I wish I knew more examples of pairs with a similar flavor.

[Edit: Note that an addendum to this note has been added here. In it, we see that there is a way to shortcut the “hard part” of the long computation.]

## The right way

Shortly afterwards, Adam Harper and Samir Siksek pointed out that this can be determined from Lambert series, and in fact that Hardy and Wright include a similar exercise in their book. This proof is delightful and short.

The idea is that, by expanding the denominator in power series, one has that

\sum_{n \geq 1} a(n) \frac{x^n}{1 – x^n} \notag
= \sum_ {n \geq 1} a(n) \sum_{m \geq 1} x^{mn}
= \sum_ {n \geq 1} \Big( \sum_{d \mid n} a(d) \Big) x^n,

where the inner sum is a sum over the divisors of $d$. This all converges beautifully for $\lvert x \rvert < 1$.

Applied to \eqref{question}, we find that

\sum_{n \geq 1} \frac{\varphi(n)}{2^n – 1} \notag
= \sum_ {n \geq 1} \varphi(n) \frac{2^{-n}}{1 – 2^{-n}}
= \sum_ {n \geq 1} 2^{-n} \sum_{d \mid n} \varphi(d),

and as

\sum_ {d \mid n} \varphi(d) = n, \notag

we see that \eqref{question} can be rewritten as \eqref{similar} after all, and thus both evaluate to $2$.

That’s a nice derivation using a series that I hadn’t come across before. But that’s not what this short note is about. This note is about evaluating \eqref{question} in a different way, arguably the wrong way. But it’s a wrong way that works out in a nice way that at least one person1 finds appealing.

## The wrong way

We will use Mellin inversion — this is essentially Fourier inversion, but in a change of coordinates.

Let $f$ denote the function

f(x) = \frac{1}{2^x – 1}. \notag

Denote by $f^ *$ the Mellin transform of $f$,

f * (s):= \mathcal{M} [f(x)] (s) := \int_ 0^\infty f(x) x^s \frac{dx}{x}
= \frac{1}{(\log 2)^2} \Gamma(s)\zeta(s),\notag

where $\Gamma(s)$ and $\zeta(s)$ are the Gamma function and Riemann zeta functions.2

For a general nice function $g(x)$, its Mellin transform satisfies

\mathcal{M}[f(nx)] (s)
= \int_0^\infty g(nx) x^s \frac{dx}{x}
= \frac{1}{n^s} \int_0^\infty g(x) x^s \frac{dx}{x}
= \frac{1}{n^s} g^ * (s).\notag

Further, the Mellin transform is linear. Thus
\label{mellinbase}
\mathcal{M}[\sum_{n \geq 1} \varphi(n) f(nx)] (s)
= \sum_ {n \geq 1} \frac{\varphi(n)}{n^s} f^ * (s)
= \sum_ {n \geq 1} \frac{\varphi(n)}{n^s} \frac{\Gamma(s) \zeta(s)}{(\log 2)^s}.

The Euler phi function $\varphi(n)$ is multiplicative and nice, and its Dirichlet series can be rewritten as

\sum_{n \geq 1} \frac{\varphi(n)}{n^s} \notag
= \frac{\zeta(s-1)}{\zeta(s)}.

Thus the Mellin transform in \eqref{mellinbase} can be written as

\frac{1}{(\log 2)^s} \Gamma(s) \zeta(s-1). \notag

By the fundamental theorem of Mellin inversion (which is analogous to Fourier inversion, but again in different coordinates), the inverse Mellin transform will return the original function. The inverse Mellin transform of a function $h(s)$ is defined to be

\mathcal{M}^{-1}[h(s)] (x) \notag
:=
\frac{1}{2\pi i} \int_ {c – i \infty}^{c + i\infty} x^s h(s) ds,

where $c$ is taken so that the integral converges beautifully, and the integral is over the vertical line with real part $c$. I’ll write $(c)$ as a shorthand for the limits of integration. Thus
\label{mellininverse}
\sum_{n \geq 1} \frac{\varphi(n)}{2^{nx} – 1}
= \frac{1}{2\pi i} \int_ {(3)} \frac{1}{(\log 2)^s}
\Gamma(s) \zeta(s-1) x^{-s} ds.

We can now describe the end goal: evaluate \eqref{mellininverse} at $x=1$, which will recover the value of the original sum in \eqref{question}.

How can we hope to do that? The idea is to shift the line of integration arbitrarily far to the left, pick up the infinitely many residues guaranteed by Cauchy’s residue theorem, and to recognize the infinite sum as a classical series.

The integrand has residues at $s = 2, 0, -2, -4, \ldots$, coming from the zeta function ($s = 2$) and the Gamma function (all the others). Note that there aren’t poles at negative odd integers, since the zeta function has zeroes at negative even integers.

Recall, $\zeta(s)$ has residue $1$ at $s = 1$ and $\Gamma(s)$ has residue $(-1)^n/{n!}$ at $s = -n$. Then shifting the line of integration and picking up all the residues reveals that

\sum_{n \geq 1} \frac{\varphi(n)}{2^{n} – 1} \notag
=\frac{1}{\log^2 2} + \zeta(-1) + \frac{\zeta(-3)}{2!} \log^2 2 +
\frac{\zeta(-5)}{4!} \log^4 2 + \cdots

The zeta function at negative integers has a very well-known relation to the Bernoulli numbers,
\label{zeta_bern}
\zeta(-n) = – \frac{B_ {n+1}}{n+1},

where Bernoulli numbers are the coefficients in the expansion
\label{bern_gen}
\frac{t}{1 – e^{-t}} = \sum_{m \geq 0} B_m \frac{t^m}{m!}.

Many general proofs for the values of $\zeta(2n)$ use this relation and the functional equation, as well as a computation of the Bernoulli numbers themselves. Another important aspect of Bernoulli numbers that is apparent through \eqref{zeta_bern} is that $B_{2n+1} = 0$ for $n \geq 1$, lining up with the trivial zeroes of the zeta function.

Translating the zeta values into Bernoulli numbers, we find that
\eqref{question} is equal to
\begin{align}
&\frac{1}{\log^2 2} – \frac{B_2}{2} – \frac{B_4}{2! \cdot 4} \log^2 2 –
\frac{B_6}{4! \cdot 6} \log^4 2 – \frac{B_8}{6! \cdot 8} \cdots \notag \\
&=
-\sum_{m \geq 0} (m-1) B_m \frac{(\log 2)^{m-2}}{m!}. \label{recog}
\end{align}
This last sum is excellent, and can be recognized.

For a general exponential generating series

F(t) = \sum_{m \geq 0} a(m) \frac{t^m}{m!},\notag

we see that

\frac{d}{dt} \frac{1}{t} F(t) \notag
=\sum_{m \geq 0} (m-1) a(m) \frac{t^{m-2}}{m!}.

Applying this to the series defining the Bernoulli numbers from \eqref{bern_gen}, we find that

\frac{d}{dt} \frac{1}{t} \frac{t}{1 – e^{-t}} \notag
=- \frac{e^{-t}}{(1 – e^{-t})^2},

and also that

\frac{d}{dt} \frac{1}{t} \frac{t}{1 – e^{-t}} \notag
=\sum_{m \geq 0} (m-1) B_m \frac{(t)^{m-2}}{m!}.

This is exactly the sum that appears in \eqref{recog}, with $t = \log 2$.

Putting this together, we find that

\sum_{m \geq 0} (m-1) B_m \frac{(\log 2)^{m-2}}{m!} \notag
=\frac{e^{-\log 2}}{(1 – e^{-\log 2})^2}
= \frac{1/2}{(1/2)^2} = 2.

Thus we find that \eqref{question} really is equal to $2$, as we had sought to show.

## Smooth Sums to Sharp Sums 1

In this note, I describe a combination of two smoothed integral transforms that has been very useful in my collaborations with Alex Walker, Chan Ieong Kuan, and Tom Hulse. I suspect that this particular technique was once very well-known. But we were not familiar with it, and so I describe it here.

In application, this is somewhat more complicated. But to show the technique, I apply it to reprove some classic bounds on $\text{GL}(2)$ $L$-functions.

This note is also available as a pdf. This was first written as a LaTeX document, and then modified to fit into wordpress through latex2jax.

## Introduction

Consider a Dirichlet series
$$D(s) = \sum_{n \geq 1} \frac{a(n)}{n^s}. \notag$$
Suppose that this Dirichlet series converges absolutely for $\Re s > 1$, has meromorphic continuation to the complex plane, and satisfies a functional equation of shape
$$\Lambda(s) := G(s) D(s) = \epsilon \Lambda(1-s), \notag$$
where $\lvert \epsilon \rvert = 1$ and $G(s)$ is a product of Gamma factors.

Dirichlet series are often used as a tool to study number theoretic functions with multiplicative properties. By studying the analytic properties of the Dirichlet series, one hopes to extract information about the coefficients $a(n)$. Some of the most common interesting information within Dirichlet series comes from partial sums
$$S(n) = \sum_{m \leq n} a(m). \notag$$
For example, the Gauss Circle and Dirichlet Divisor problems can both be stated as problems concerning sums of coefficients of Dirichlet series.

One can try to understand the partial sum directly by understanding the integral transform
$$S(n) = \frac{1}{2\pi i} \int_{(2)} D(s) \frac{X^s}{s} ds, \notag$$
a Perron integral. However, it is often challenging to understand this integral, as delicate properties concerning the convergence of the integral often come into play.

Instead, one often tries to understand a smoothed sum of the form
$$\sum_{m \geq 1} a(m) v(m) \notag$$
where $v(m)$ is a smooth function that vanishes or decays extremely quickly for values of $m$ larger than $n$. A large class of smoothed sums can be obtained by starting with a very nicely behaved weight function $v(m)$ and take its Mellin transform
$$V(s) = \int_0^\infty v(x) x^s \frac{dx}{x}. \notag$$
Then Mellin inversion gives that
$$\sum_{m \geq 1} a(m) v(m/X) = \frac{1}{2\pi i} \int_{(2)} D(s) X^s V(s) ds, \notag$$
as long as $v$ and $V$ are nice enough functions.

In this note, we will use two smoothing integral transforms and corresponding smoothed sums. We will use one smooth function $v_1$ (which depends on another parameter $Y$) with the property that
$$\sum_{m \geq 1} a(m) v_1(m/X) \approx \sum_{\lvert m – X \rvert < X/Y} a(m). \notag$$
And we will use another smooth function $v_2$ (which also depends on $Y$) with the property that
$$\sum_{m \geq 1} a(m) v_2(m/X) = \sum_{m \leq X} a(m) + \sum_{X < m < X + X/Y} a(m) v_2(m/X). \notag$$
Further, as long as the coefficients $a(m)$ are nonnegative, it will be true that
$$\sum_{X < m < X + X/Y} a(m) v_2(m/X) \ll \sum_{\lvert m – X \rvert < X/Y} a(m), \notag$$
which is exactly what $\sum a(m) v_1(m/X)$ estimates. Therefore
$$\label{eq:overall_plan} \sum_{m \leq X} a(m) = \sum_{m \geq 1} a(m) v_2(m/X) + O\Big(\sum_{m \geq 1} a(m) v_1(m/X) \Big).$$

Hence sufficient understanding of $\sum a(m) v_1(m/X)$ and $\sum a(m) v_2(m/X)$ allows one to understand the sharp sum
$$\sum_{m \leq X} a(m). \notag$$

Posted in Expository, Math.NT, Mathematics | | 3 Comments

## A Notebook Preparing for a Talk at Quebec-Maine

This is a notebook containing a representative sample of the code I used to  generate the results and pictures presented at the Quebec-Maine Number Theory Conference on 9 October 2016. It was written in a Jupyter Notebook using Sage 7.3, and later converted for presentation on this site.
There is a version of the notebook available on github. Alternately, a static html version without WordPress formatting is available here. Finally, this notebook is also available in pdf form.
The slides for my talk are available here.

# Testing for a Generalized Conjecture on Iterated Sums of Coefficients of Cusp Forms¶

Let $f$ be a weight $k$ cusp form with Fourier expansion

$$f(z) = \sum_{n \geq 1} a(n) e(nz).$$

Deligne has shown that $a(n) \ll n^{\frac{k-1}{2} + \epsilon}$. It is conjectured that

$$S_f^1(n) := \sum_{m \leq X} a(m) \ll X^{\frac{k-1}{2} + \frac{1}{4} + \epsilon}.$$

It is known that this holds on average, and we recently showed that this holds on average in short intervals.
(See HKLDW1, HKLDW2, and HKLDW3 for details and an overview of work in this area).
This is particularly notable, as the resulting exponent is only 1/4 higher than that of a single coefficient.
This indicates extreme cancellation, far more than what is implied merely by the signs of $a(n)$ being random.

It seems that we also have

$$\sum_{m \leq X} S_f^1(m) \ll X^{\frac{k-1}{2} + \frac{2}{4} + \epsilon}.$$

That is, the sum of sums seems to add in only an additional 1/4 exponent.
This is unexpected and a bit mysterious.

The purpose of this notebook is to explore this and higher conjectures.
Define the $j$th iterated sum as

$$S_f^j(X) := \sum_{m \leq X} S_f^{j-1} (m).$$

Then we numerically estimate bounds on the exponent $\delta(j)$ such that

$$S_f^j(X) \ll X^{\frac{k-1}{2} + \delta(j) + \epsilon}.$$

In [1]:
# This was written in SageMath 7.3 through a Jupyter Notebook.

# sage plays strangely with ipython. This re-allows inline plotting
from IPython.display import display, Image


We first need a list of coefficients of one (or more) cusp forms.
For initial investigation, we begin with a list of 50,000 coefficients of the weight $12$ cusp form on $\text{SL}(2, \mathbb{Z})$, $\Delta(z)$, i.e. Ramanujan’s delta function.
We will use the data associated to the 50,000 coefficients for pictoral investigation as well.

We will be performing some numerical investigation as well.
For this, we will use the first 2.5 million coefficients of $\Delta(z)$

In [2]:
# Gather 10 coefficients for simple checking
check_10 = delta_qexp(11).coefficients()
print check_10

fiftyk_coeffs = delta_qexp(50000).coefficients()
print fiftyk_coeffs[:10] # these match expected

twomil_coeffs = delta_qexp(2500000).coefficients()
print twomil_coeffs[:10] # these also match expected

[1, -24, 252, -1472, 4830, -6048, -16744, 84480, -113643, -115920]
[1, -24, 252, -1472, 4830, -6048, -16744, 84480, -113643, -115920]
[1, -24, 252, -1472, 4830, -6048, -16744, 84480, -113643, -115920]

In [3]:
# Function which iterates partial sums from a list of coefficients

def partial_sum(baselist):
ret_list = [baselist[0]]
for b in baselist[1:]:
ret_list.append(ret_list[-1] + b)
return ret_list

print check_10
print partial_sum(check_10) # Should be the partial sums

[1, -24, 252, -1472, 4830, -6048, -16744, 84480, -113643, -115920]
[1, -23, 229, -1243, 3587, -2461, -19205, 65275, -48368, -164288]

In [4]:
# Calculate the first 10 iterated partial sums
# We store them in a single list list, sums_list
# the zeroth elelemnt of the list is the array of initial coefficients
# the first element is the array of first partial sums, S_f(n)
# the second element is the array of second iterated partial sums, S_f^2(n)

fiftyk_sums_list = []
fiftyk_sums_list.append(fiftyk_coeffs) # zeroth index contains coefficients
for j in range(10):                    # jth index contains jth iterate
fiftyk_sums_list.append(partial_sum(fiftyk_sums_list[-1]))

print partial_sum(check_10)
print fiftyk_sums_list[1][:10]         # should match above

twomil_sums_list = []
twomil_sums_list.append(twomil_coeffs) # zeroth index contains coefficients
for j in range(10):                    # jth index contains jth iterate
twomil_sums_list.append(partial_sum(twomil_sums_list[-1]))

print twomil_sums_list[1][:10]         # should match above

[1, -23, 229, -1243, 3587, -2461, -19205, 65275, -48368, -164288]
[1, -23, 229, -1243, 3587, -2461, -19205, 65275, -48368, -164288]
[1, -23, 229, -1243, 3587, -2461, -19205, 65275, -48368, -164288]


As is easily visible, the sums alternate in sign very rapidly.
For instance, we believe tha the first partial sums should change sign about once every $X^{1/4}$ terms in the interval $[X, 2X]$.
In this exploration, we are interested in the sizes of the coefficients.
But in HKLDW3, we investigated some of the sign changes of the partial sums.

Now seems like a nice time to briefly look at the data we currently have.
What do the first 50 thousand coefficients look like?
So we normalize them, getting $A(n) = a(n)/n^{5.5}$ and plot these coefficients.

In [5]:
norm_list = []
for n,e in enumerate(fiftyk_coeffs, 1):
normalized_element = 1.0 * e / (1.0 * n**(5.5))
norm_list.append(normalized_element)
print norm_list[:10]

1

In [6]:
# Make a quick display
normed_coeffs_plot = scatter_plot(zip(range(1,60000), norm_list), markersize=.02)
normed_coeffs_plot.save("normed_coeffs_plot.png")
display(Image("normed_coeffs_plot.png"))


Since some figures will be featuring prominently in the talk I’m giving at Quebec-Maine, let us make high-quality figures now.

1. 00000000000000, -0.530330085889911, 0.598733612492945, -0.718750000000000, 0.691213333204735, -0.317526448138560, -0.376547696558964, 0.911504835123284, -0.641518061271148, -0.366571226366719
Posted in Math.NT, Mathematics, Open, Programming, sagemath | | 1 Comment

## Paper: Sign Changes of Coefficients and Sums of Coefficients of Cusp Forms

This is joint work with Thomas Hulse, Chan Ieong Kuan, and Alex Walker, and is a another sequel to our previous work. This is the third in a trio of papers, and completes an answer to a question posed by our advisor Jeff Hoffstein two years ago.

We have just uploaded a preprint to the arXiv giving conditions that guarantee that a sequence of numbers contains infinitely many sign changes. More generally, if the sequence consists of complex numbers, then we give conditions that guarantee sign changes in a generalized sense.

Let $\mathcal{W}(\theta_1, \theta_2) := { re^{i\theta} : r \geq 0, \theta \in [\theta_1, \theta_2]}$ denote a wedge of complex plane.

Suppose ${a(n)}$ is a sequence of complex numbers satisfying the following conditions:

1. $a(n) \ll n^\alpha$,
2. $\sum_{n \leq X} a(n) \ll X^\beta$,
3. $\sum_{n \leq X} \lvert a(n) \rvert^2 = c_1 X^{\gamma_1} + O(X^{\eta_1})$,

where $\alpha, \beta, c_1, \gamma_1$, and $\eta_1$ are all real numbers $\geq 0$. Then for any $r$ satisfying $\max(\alpha+\beta, \eta_1) – (\gamma_1 – 1) < r < 1$, the sequence ${a(n)}$ has at least one term outside any wedge $\mathcal{W}(\theta_1, \theta_2)$ with $0 \theta_2 – \theta_1 < \pi$ for some $n \in [X, X+X^r)$ for all sufficiently large $X$.

These wedges can be thought of as just slightly smaller than a half-plane. For a complex number to escape a half plane is analogous to a real number changing sign. So we should think of this result as guaranteeing a sort of sign change in intervals of width $X^r$ for all sufficiently large $X$.

The intuition behind this result is very straightforward. If the sum of coefficients is small while the sum of the squares of the coefficients are large, then the sum of coefficients must experience a lot of cancellation. The fact that we can get quantitative results on the number of sign changes is merely a task of bookkeeping.

Both the statement and proof are based on very similar criteria for sign changes when ${a(n)}$ is a sequence of real numbers first noticed by Ram Murty and Jaban Meher. However, if in addition it is known that

\sum_{n \leq X} (a(n))^2 = c_2 X^{\gamma_2} + O(X^{\eta_2}),

and that $\max(\alpha+\beta, \eta_1, \eta_2) – (\max(\gamma_1, \gamma_2) – 1) < r < 1$, then generically both sequences ${\text{Re} (a(n)) }$ and ${ \text{Im} (a(n)) }$ contain at least one sign change for some $n$ in $[X , X + X^r)$ for all sufficiently large $X$. In other words, we can detect sign changes for both the real and imaginary parts in intervals, which is a bit more special.

It is natural to ask for even more specific detection of sign changes. For instance, knowing specific information about the distribution of the arguments of $a(n)$ would be interesting, and very closely reltated to the Sato-Tate Conjectures. But we do not yet know how to investigate this distribution.

In practice, we often understand the various criteria for the application of these two sign changes results by investigating the Dirichlet series
\begin{align}
&\sum_{n \geq 1} \frac{a(n)}{n^s} \\
&\sum_{n \geq 1} \frac{S_f(n)}{n^s} \\
&\sum_{n \geq 1} \frac{\lvert S_f(n) \rvert^2}{n^s} \\
&\sum_{n \geq 1} \frac{S_f(n)^2}{n^s},
\end{align}
where

S_f(n) = \sum_{m \leq n} a(n).

In the case of holomorphic cusp forms, the two previous joint projects with this group investigated exactly the Dirichlet series above. In the paper, we formulate some slightly more general criteria guaranteeing sign changes based directly on the analytic properties of the Dirichlet series involved.

In this paper, we apply our sign change results to our previous work to show that $S_f(n)$ changes sign in each interval $[X, X + X^{\frac{2}{3} + \epsilon})$ for sufficiently large $X$. Further, if there are coefficients with $\text{Im} a(n) \neq 0$, then the real and imaginary parts each change signs in those intervals.

We apply our sign change results to single coefficients of $\text{GL}(2)$ cusp forms (and specifically full integral weight holomorphic cusp forms, half-integral weight holomorphic cusp forms, and Maass forms). In large part these are minor improvements over folklore and what is known, except for the extension to complex coefficients.

We also apply our sign change results to single isolated coefficients $A(1,m)$ of $\text{GL}(3)$ Maass forms. This seems to be a novel result, and adds to the very sparse literature on sign changes of sequences associated to $\text{GL}(3)$ objects. Murty and Meher recently proved a general sign change result for $\text{GL}(n)$ objects which is similar in feel.

As a final application, we also consider sign changes of partial sums of $\nu$-normalized coefficients. Let

S_f^\nu(X) := \sum_{n \leq X} \frac{a(n)}{n^{\nu}}.

As $\nu$ gets larger, the individual coefficients $a(n)n^{-\nu}$ become smaller. So one should expect that sign changes in ${S_f^\nu(n)}$ to change based on $\nu$. And in particular, as $\nu$ gets very large, the number of sign changes of $S_f^\nu$ should decrease.

Interestingly, in the case of holomorphic cusp forms of weight $k$, we are able to show that there are sign changes of $S_f^\nu(n)$ in intervals even for normalizations $\nu$ a bit above $\nu = \frac{k-1}{2}$. This is particularly interesting as $a(n) \ll n^{\frac{k-1}{2} + \epsilon}$, so for $\nu > \frac{k-1}{2}$ the coefficients are \emph{decreasing} with $n$. We are able to show that when $\nu = \frac{k-1}{2} + \frac{1}{6} – \epsilon$, the sequence ${S_f^\nu(n)}$ has at least one sign change for $n$ in $[X, 2X)$ for all sufficiently large $X$.

It may help to consider a simpler example to understand why this is surprising. Consider the classic example of a sequence of $b(n)$, where $b(n) = 1$ or $b(n) = -1$, randomly, with equal probability. Then the expected size of the sums of $b(n)$ is about $\sqrt n$. This is an example of \emph{square-root cancellation}, and such behaviour is a common point of comparison. Similarly, the number of sign changes of the partial sums of $b(n)$ is also expected to be about $\sqrt n$.

Suppose now that $b(n) = \frac{\pm 1}{\sqrt n}$. If the first term is $1$, then it takes more then the second term being negative to make the overall sum negative. And if the first two terms are positive, then it would take more then the following three terms being negative to make the overall sum negative. So sign changes of the partial sums are much rarer. In fact, they’re exceedingly rare, and one might barely detect more than a dozen through computational experiment (although one should still expect infinitely many).

This regularity, in spite of the decreasing size of the individual coefficients $a(n)n^{-\nu}$, suggests an interesting regularity in the sign changes of the individual $a(n)$. We do not know how to understand or measure this effect or its regularity, and for now it remains an entirely qualitative observation.

For more details and specific references, see the paper on the arXiv.

## Math 42 Spring 2016 Student Showcase

This spring, I taught Math 42: An Introduction to Elementary Number Theory at Brown University. An important aspect of the course was the final project. In these projects, students either followed up on topics that interested them from the semester, or chose and investigated topics related to number theory.  Projects could be done individual or in small groups.

I thought it would be nice to showcase some excellent student projects from my class. Most of the projects were quite good, and some showed extraordinary effort. Some students really dove in and used this as an opportunity to explore and digest a topic far more thoroughly than could possibly be expected from an introductory class such as this one. With the students’ permission, I’ve chosen five student projects (in no particular order) for a blog showcase (impressed by similar sorts  of showcases from Scott Aaronson).

• Factorization Techniques, by Elvis Nunez and Chris Shaw. In this project, Elvis and Chris look at Fermat Factorization, which looks to factor $n$ by expressing $n = a^2 – b^2$. Further, they investigate improvements to Fermat’s Algorithm by Dixon and Kraitchik. Following this line of investigation leads to the development of the modern quadratic sieve and factor base methods of factorization.

• Pseudoprimes and Carmichael Numbers, by Emily Riemer. Fermat’s Little Theorem is one of the first “big idea” theorems we encounter in the course, and we came back to it again and again throughout. Emily explored the Fermat’s Little Theorem as a primality test, leading to pseudoprimes, strong pseudoprimes, and Carmichael numbers. [As an aside, one of her references concerning Carmichael numbers were notes from an algebraic number theory class taught by Matt Baker, who first got me interested in number theory].

• Continued Fractions and Pell’s Equation, by Max Lahn and Jonathan Spiegel. As it happened, I did not have time to teach continued fractions in the course.  So Max and Jonathan decided to look at them on their own. They explore some ideas related to the convergence of continued fractions and see how one uses continued fractions to solve Pell’s Equation.

• Quantum Computing, by Edward Hu and Chris Long. Edward and Chris explore quantum computing with particular emphasis towards gaining some idea of how Shor’s factorization algorithm works. For some of the more complicated ideas, like the quantum Fourier transform, they make use of heuristic and analogy to purvey the main ideas.

• Fermat’s Last Theorem, by Dylan Groos, Natalie Schudrowitz, and Kenneth Berglund. Dylan, Natalie, and Kenneth provide a historical look at attacks on Fermat’s Last Theorem. They examine proofs for $n=4$ and Sophie Germaine’s remarkable advances. They also touch on elliptic curves and modular forms, hinting at some of the deep ideas lying beneath the surface.

Posted in Brown University, Math 420, Mathematics, Teaching | | 1 Comment

## Math 420: Supplement on Gaussian Integers II

This is a secondary supplemental note on the Gaussian integers, written for my Spring 2016 Elementary Number Theory Class at Brown University. This note is also available as a pdf document.

In this note, we cover the following topics.

1. Assumed prerequisites from other lectures.
2. Which regular integer primes are sums of squares?
3. How can we classify all Gaussian primes?

1. Assumed Prerequisites

Although this note comes shortly after the previous note on the Gaussian integers, we covered some material from the book in the middle. In particular, we will assume use the results from chapters 20 and 21 from the textbook.

Most importantly, for ${p}$ a prime and ${a}$ an integer not divisible by ${p}$, recall the Legendre symbol ${\left(\frac{a}{p}\right)}$, which is defined to be ${1}$ if ${a}$ is a square mod ${p}$ and ${-1}$ if ${a}$ is not a square mod ${p}$. Then we have shown Euler’s Criterion, which states that

$$a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right) \pmod p, \tag{1}$$
and which gives a very efficient way of determining whether a given number ${a}$ is a square mod ${p}$.

We used Euler’s Criterion to find out exactly when ${-1}$ is a square mod ${p}$. In particular, we concluded that for each odd prime ${p}$, we have

$$\left(\frac{-1}{p}\right) = \begin{cases} 1 & \text{ if } p \equiv 1 \pmod 4 \ -1 & \text{ if } p \equiv 3 \pmod 4 \end{cases}. \tag{2}$$
Finally, we assume familiarity with the notation and ideas from the previous note on the Gaussian integers.

2. Understanding When ${p = a^2 + b^2}$.

Throughout this section, ${p}$ will be a normal odd prime. The case ${p = 2}$ is a bit different, and we will need to handle it separately. When used, the letters ${a}$ and ${b}$ will denote normal integers, and ${q_1,q_2}$ will denote Gaussian integers.

We will be looking at the following four statements.

1. ${p \equiv 1 \pmod 4}$
2. ${\left(\frac{-1}{p}\right) = 1}$
3. ${p}$ is not a Gaussian prime
4. ${p = a^2 + b^2}$

Our goal will be to show that each of these statements are equivalent. In order to show this, we will show that

$$(1) \implies (2) \implies (3) \implies (4) \implies (1). \tag{3}$$
Do you see why this means that they are all equivalent?

This naturally breaks down into four lemmas.

We have actually already shown one.

Lemma 1 ${(1) \implies (2)}$.

Proof: We have already proved this claim! This is exactly what we get from Euler’s Criterion applied to ${-1}$, as mentioned in the first section. $\Box$

There is one more that is somewhat straightfoward, and which does not rely on going up to the Gaussian integers.

Lemma 2 ${(4) \implies (1)}$.

Proof: We have an odd prime ${p}$ which is a sum of squares ${p = a^2 + b^2}$. If we look mod ${4}$, we are led to consider $$p = a^2 + b^2 \pmod 4. \tag{4}$$
What are the possible values of ${a^2 \pmod 4}$? A quick check shows that the only possibilites are ${a^2 \equiv 0, 1 \pmod 4}$.

So what are the possible values of ${a^2 + b^2 \pmod 4}$? We must have one of ${p \equiv 0, 1, 2 \pmod 4}$. Clearly, we cannot have ${p \equiv 0 \pmod 4}$, as then ${4 \mid p}$. Similarly, we cannot have ${p \equiv 2 \pmod 4}$, as then ${2 \mid p}$. So we necessarily have ${p \equiv 1 \pmod 4}$, which is what we were trying to prove. $\Box$

For the remaining two pieces, we will dive into the Gaussian integers.

Lemma 3 ${(2) \implies (3)}$.

Proof: As ${\left(\frac{-1}{p}\right) = 1}$, we know there is some ${a}$ so that ${a^2 \equiv -1 \pmod p}$. Rearranging, this becomes ${a^2 + 1 \equiv 0 \pmod p}$.

Over the normal integers, we are at an impasse, as all this tells us is that ${p \mid (a^2 + 1)}$. But if we suddenly view this within the Gaussian integers, then ${a^2 + 1}$ factors as ${a^2 + 1 = (a + i)(a – i)}$.

So we have that ${p \mid (a+i)(a-i)}$. If ${p}$ were a Gaussian prime, then we would necessarily have ${p \mid (a+i)}$ or ${p \mid (a-i)}$. (Do you see why?)

But is it true that ${p}$ divides ${a + i}$ or ${a – i}$? For instance, does ${p}$ divide ${a + i}$? No! If so, then ${\frac{a}{p} + \frac{i}{p}}$ would be a Gaussian integer, which is clearly not true.

So ${p}$ does not divide ${a + i}$ or ${a-i}$, and we must therefore conclude that ${p}$ is not a Gaussian prime. $\Box$

Lemma 4 ${(3) \implies (4)}$.

Proof: We now know that ${p}$ is not a Gaussian prime. In particular, this means that ${p}$ is not irreducible, and so it has a nontrivial factorization in the Gaussian integers. (For example, ${5}$ is a regular prime, but it is not a Gaussian prime. It factors as ${5 = (1 + 2i)(1 – 2i)}$ in the Gaussian integers.)

Let’s denote this nontrivial factorization as ${p = q_1 q_2}$. By nontrivial, we mean that neither ${q_1}$ nor ${q_2}$ are units, i.e. ${N(q_1), N(q_2) > 1}$. Taking norms, we see that ${N(p) = N(q_1) N(q_2)}$.

We can evaluate ${N(p) = p^2}$, so we have that ${p^2 = N(q_1) N(q_2)}$. Both ${N(q_1)}$ and ${N(q_2)}$ are integers, and their product is ${p^2}$. Yet ${p^2}$ has exactly two different factorizations: ${p^2 = 1 \cdot p^2 = p \cdot p}$. Since ${N(q_1), N(q_2) > 1}$, we must have the latter.

So we see that ${N(q_1) = N(q_2) = p}$. As ${q_1, q_2}$ are Gaussian integers, we can write ${q_1 = a + bi}$ for some ${a, b}$. Then since ${N(q_1) = p}$, we see that ${N(q_1) = a^2 + b^2}$. And so ${p}$ is a sum of squares, ending the proof. $\Box$

Notice that ${2 = 1 + 1}$ is also a sum of squares. Then all together, we can say the following theorem.

Theorem 5 A regular prime ${p}$ can be written as a sum of two squares, $$p = a^2 + b^2, \tag{5}$$
exactly when ${p = 2}$ or ${p \equiv 1 \pmod 4}$.

A remarkable aspect of this theorem is that it is entirely a statement about the behaviour of the regular integers. Yet in our proof, we used the Gaussian integers in a very fundamental way. Isn’t that strange?

You might notice that in the textbook, Dr. Silverman presents a proof that does not rely on the Gaussian integers. While interesting and clever, I find that the proof using the Gaussian integers better illustrates the deep connections between and around the structures we have been studying in this course so far. Everything connects!

Example 1 The prime ${5}$ is ${1 \pmod 4}$, and so ${5}$ is a sum of squares. In particular, ${5 = 1^2 + 2^2}$.

Example 2 The prime ${101}$ is ${1 \pmod 4}$, and so is a sum of squares. Our proof is not constructive, so a priori we do not know what squares sum to ${101}$. But in this case, we see that ${101 = 1^2 + 10^2}$.

Example 3 The prime ${97}$ is ${1 \pmod 4}$, and so it also a sum of squares. It’s less obvious what the squares are in this case. It turns out that ${97 = 4^2 + 9^2}$.

Example 4 The prime ${43}$ is ${3 \pmod 4}$, and so is not a sum of squares.

3. Classification of Gaussian Primes

In the previous section, we showed that each integer prime ${p \equiv 1 \pmod 4}$ actually splits into a product of two Gaussian numbers ${q_1}$ and ${q_2}$. In fact, since ${N(q_1) = p}$ is a regular prime, ${q_1}$ is a Gaussian irreducible and therefore a Gaussian prime (can you prove this? This is a nice midterm question.)

So in fact, ${p \equiv 1 \pmod 4}$ splits in to the product of two Gaussian primes ${q_1}$ and ${q_2}$.

In this way, we’ve found infinitely many Gaussian primes. Take a regular prime congruent to ${1 \pmod 4}$. Then we know that it splits into two Gaussian primes. Further, if we know how to write ${p = a^2 + b^2}$, then we know that ${q_1 = a + bi}$ and ${q_2 = a – bi}$ are those two Gaussian primes.

In general, we will find all Gaussian primes by determining their interaction with regular primes.

Suppose ${q}$ is a Gaussian prime. Then on the one hand, ${N(q) = q \overline{q}}$. On the other hand, ${N(q) = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}}$ is some regular integer. Since ${q}$ is a Gaussian prime (and so ${q \mid w_1 w_2}$ means that ${q \mid w_1}$ or ${q \mid w_2}$), we know that ${q \mid p_j}$ for some regular integer prime ${p_j}$.

So one way to classify Gaussian primes is to look at every regular integer prime and see which Gaussian primes divide it. We have figured this out for all primes ${p \equiv 1 \pmod 4}$. We can handle ${2}$ by noticing that ${2 = (1 + i) (1-i)}$. Both ${(1+i)}$ and ${(1-i)}$ are Gaussian primes.

The only primes left are those regular primes with ${p \equiv 3 \pmod 4}$. We actually already covered the key idea in the previous section.

Lemma 6 If ${p \equiv 3 \pmod 4}$ is a regular prime, then ${p}$ is also a Gaussian prime.

Proof: In the previous section, we showed that if ${p}$ is not a Gaussian prime, then ${p = a^2 + b^2}$ for some integers ${a,b}$, and then ${ p \equiv 1 \pmod 4}$. Since ${p \not \equiv 1 \pmod 4}$, we see that ${p}$ is a Gaussian prime. $\Box$

In total, we have classified all Gaussian primes.

Theorem 7 The Gaussian primes are given by

1. ${(1+i), (1-i)}$
2. Regular primes ${p \equiv 3 \pmod 4}$
3. The factors ${q_1 q_2}$ of a regular prime ${p \equiv 1 \pmod 4}$. Further, these primes are given by ${a \pm bi}$, where ${p = a^2 + b^2}$.

4. Concluding Remarks

I hope that it’s clear that the regular integers and the Gaussian integers are deeply connected and intertwined. Number theoretic questions in one constantly lead us to investigate the other. As one dives deeper into number theory, more and different integer-like rings appear, all deeply connected.

Each time I teach the Gaussian integers, I cannot help but feel the sense that this is a hint at a deep structural understanding of what is really going on. The interplay between the Gaussian integers and the regular integers is one of my favorite aspects of elementary number theory, which is one reason why I deviated so strongly from the textbook to include it. I hope you enjoyed it too.