Category Archives: Math.NT

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.


Posted in Expository, Math.NT, Mathematics | Tagged , , , , | Leave a comment

Another proof of Wilson’s Theorem

While teaching a largely student-discovery style elementary number theory course to high schoolers at the Summer@Brown program, we were looking for instructive but interesting problems to challenge our students. By we, I mean Alex Walker, my academic little brother, and me. After a bit of experimentation with generators and orders, we stumbled across a proof of Wilson’s Theorem, different than the standard proof.

Wilson’s theorem is a classic result of elementary number theory, and is used in some elementary texts to prove Fermat’s Little Theorem, or to introduce primality testing algorithms that give no hint of the factorization.

Theorem 1 (Wilson’s Theorem) For a prime number $latex {p}$, we have $$ (p-1)! \equiv -1 \pmod p. \tag{1}$$

The theorem is clear for $latex {p = 2}$, so we only consider proofs for “odd primes $latex {p}$.”

The standard proof of Wilson’s Theorem included in almost every elementary number theory text starts with the factorial $latex {(p-1)!}$, the product of all the units mod $latex {p}$. Then as the only elements which are their own inverses are $latex {\pm 1}$ (as $latex {x^2 \equiv 1 \pmod p \iff p \mid (x^2 – 1) \iff p\mid x+1}$ or $latex {p \mid x-1}$), every element in the factorial multiples with its inverse to give $latex {1}$, except for $latex {-1}$. Thus $latex {(p-1)! \equiv -1 \pmod p.} \diamondsuit$

Now we present a different proof.

Take a primitive root $latex {g}$ of the unit group $latex {(\mathbb{Z}/p\mathbb{Z})^\times}$, so that each number $latex {1, \ldots, p-1}$ appears exactly once in $latex {g, g^2, \ldots, g^{p-1}}$. Recalling that $latex {1 + 2 + \ldots + n = \frac{n(n+1)}{2}}$ (a great example of classical pattern recognition in an elementary number theory class), we see that multiplying these together gives $latex {(p-1)!}$ on the one hand, and $latex {g^{(p-1)p/2}}$ on the other.

As $latex {g^{(p-1)/2}}$ is a solution to $latex {x^2 \equiv 1 \pmod p}$, and it is not $latex {1}$ since $latex {g}$ is a generator and thus has order $latex {p-1}$. So $latex {g^{(p-1)/2} \equiv -1 \pmod p}$, and raising $latex {-1}$ to an odd power yields $latex {-1}$, completing the proof $\diamondsuit$.

After posting this, we have since seen that this proof is suggested in a problem in Ireland and Rosen’s extremely good number theory book. But it was pleasant to see it come up naturally, and it’s nice to suggest to our students that you can stumble across proofs.

It may be interesting to question why $latex {x^2 \equiv 1 \pmod p \iff x \equiv \pm 1 \pmod p}$ appears in a fundamental way in both proofs.

This post appears on the author’s personal website and on the Math.Stackexchange Community Blog It is also available in pdf note form. It was typeset in \TeX, hosted on WordPress sites, converted using the utility, and displayed with MathJax.

Posted in Expository, Math.NT, Mathematics | Tagged , , , , , , | 1 Comment

Functional Equations for L-Functions arising from Modular Forms

In this note, I remind myself of the functional equations for the $latex {L}$-functions $latex {\displaystyle \sum_{n\geq 0} \frac{a(n)}{n^s}}$ and $latex {\displaystyle \sum_{n\geq 0} \frac{a(n)}{n^s}e(\frac{n\overline{r}}{c})}$, where $latex {\overline{r}}$ is the multiplicative inverse of $latex {r \bmod c}$.


Posted in Math.NT, Mathematics | Tagged , , , , | Leave a comment

Friendly Introduction to Sieves with a Look Towards Progress on the Twin Primes Conjecture

This is an extension and background to a talk I gave on 9 October 2013 to the Brown Graduate Student Seminar, called `A friendly intro to sieves with a look towards recent progress on the twin primes conjecture.’ During the talk, I mention several sieves, some with a lot of detail and some with very little detail. I also discuss several results and built upon many sources. I’ll provide missing details and/or sources for additional reading here.

Furthermore, I like this talk, so I think it’s worth preserving.

1. Introduction

We talk about sieves and primes. Long, long ago, Euclid famously proved the infinitude of primes ($latex {\approx 300}$ B.C.). Although he didn’t show it, the stronger statement that the sum of the reciprocals of the primes diverges is true:

$latex \displaystyle \sum_{p} \frac{1}{p} \rightarrow \infty, $

where the sum is over primes.

Proof: Suppose that the sum converged. Then there is some $latex {k}$ such that

$latex \displaystyle \sum_{i = k+1}^\infty \frac{1}{p_i} < \frac{1}{2}. $

Suppose that $latex {Q := \prod_{i = 1}^k p_i}$ is the product of the primes up to $latex {p_k}$. Then the integers $latex {1 + Qn}$ are relatively prime to the primes in $latex {Q}$, and so are only made up of the primes $latex {p_{k+1}, \ldots}$. This means that

$latex \displaystyle \sum_{n = 1}^\infty \frac{1}{1+Qn} \leq \sum_{t \geq 0} \left( \sum_{i > k} \frac{1}{p_i} \right) ^t < 2, $

where the first inequality is true since all the terms on the left appear in the middle (think prime factorizations and the distributive law), and the second inequality is true because it’s bounded by the geometric series with ratio $latex {1/2}$. But by either the ratio test or by limit comparison, the sum on the left diverges (aha! Something for my math 100 students), and so we arrive at a contradiction.

Thus the sum of the reciprocals of the primes diverges. $latex \diamondsuit$


Posted in Expository, Math.NT, Mathematics | Tagged , , , , , , , , , , , , | Leave a comment

Response to bnelo12’s question on Reddit (or the Internet storm on $1 + 2 + \ldots = -1/12$)

bnelo12 writes (slightly paraphrased)

Can you explain exactly how $latex {1 + 2 + 3 + 4 + \ldots = – \frac{1}{12}}$ in the context of the Riemann $latex {\zeta}$ function?

We are going to approach this problem through a related problem that is easier to understand at first. Many are familiar with summing geometric series

$latex \displaystyle g(r) = 1 + r + r^2 + r^3 + \ldots = \frac{1}{1-r}, $

which makes sense as long as $latex {|r| < 1}$. But if you’re not, let’s see how we do that. Let $latex {S(n)}$ denote the sum of the terms up to $latex {r^n}$, so that

$latex \displaystyle S(n) = 1 + r + r^2 + \ldots + r^n. $

Then for a finite $latex {n}$, $latex {S(n)}$ makes complete sense. It’s just a sum of a few numbers. What if we multiply $latex {S(n)}$ by $latex {r}$? Then we get

$latex \displaystyle rS(n) = r + r^2 + \ldots + r^n + r^{n+1}. $

Notice how similar this is to $latex {S(n)}$. It’s very similar, but missing the first term and containing an extra last term. If we subtract them, we get

$latex \displaystyle S(n) – rS(n) = 1 – r^{n+1}, $

which is a very simple expression. But we can factor out the $latex {S(n)}$ on the left and solve for it. In total, we get

$latex \displaystyle S(n) = \frac{1 – r^{n+1}}{1 – r}. \ \ \ \ \ (1)$

This works for any natural number $latex {n}$. What if we let $latex {n}$ get arbitrarily large? Then if $latex {|r|<1}$, then $latex {|r|^{n+1} \rightarrow 0}$, and so we get that the sum of the geometric series is

$latex \displaystyle g(r) = 1 + r + r^2 + r^3 + \ldots = \frac{1}{1-r}. $

But this looks like it makes sense for almost any $latex {r}$, in that we can plug in any value for $latex {r}$ that we want on the right and get a number, unless $latex {r = 1}$. In this sense, we might say that $latex {\frac{1}{1-r}}$ extends the geometric series $latex {g(r)}$, in that whenever $latex {|r|<1}$, the geometric series $latex {g(r)}$ agrees with this function. But this function makes sense in a larger domain then $latex {g(r)}$.

People find it convenient to abuse notation slightly and call the new function $latex {\frac{1}{1-r} = g(r)}$, (i.e. use the same notation for the extension) because any time you might want to plug in $latex {r}$ when $latex {|r|<1}$, you still get the same value. But really, it’s not true that $latex {\frac{1}{1-r} = g(r)}$, since the domain on the left is bigger than the domain on the right. This can be confusing. It’s things like this that cause people to say that

$latex \displaystyle 1 + 2 + 4 + 8 + 16 + \ldots = \frac{1}{1-2} = -1, $

simply because $latex {g(2) = -1}$. This is conflating two different ideas together. What this means is that the function that extends the geometric series takes the value $latex {-1}$ when $latex {r = 2}$. But this has nothing to do with actually summing up the $latex {2}$ powers at all.

So it is with the $latex {\zeta}$ function. Even though the $latex {\zeta}$ function only makes sense at first when $latex {\text{Re}(s) > 1}$, people have extended it for almost all $latex {s}$ in the complex plane. It just so happens that the great functional equation for the Riemann $latex {\zeta}$ function that relates the right and left half planes (across the line $latex {\text{Re}(s) = \frac{1}{2}}$) is

$latex \displaystyle \pi^{\frac{-s}{2}}\Gamma\left( \frac{s}{2} \right) \zeta(s) = \pi^{\frac{s-1}{2}}\Gamma\left( \frac{1-s}{2} \right) \zeta(1-s), \ \ \ \ \ (2)$

where $latex {\Gamma}$ is the gamma function, a sort of generalization of the factorial function. If we solve for $latex {\zeta(1-s)}$, then we get

$latex \displaystyle \zeta(1-s) = \frac{\pi^{\frac{-s}{2}}\Gamma\left( \frac{s}{2} \right) \zeta(s)}{\pi^{\frac{s-1}{2}}\Gamma\left( \frac{1-s}{2} \right)}. $

If we stick in $latex {s = 2}$, we get

$latex \displaystyle \zeta(-1) = \frac{\pi^{-1}\Gamma(1) \zeta(2)}{\pi^{\frac{-1}{2}}\Gamma\left( \frac{-1}{2} \right)}. $

We happen to know that $latex {\zeta(2) = \frac{\pi^2}{6}}$ (this is called Basel’s problem) and that $latex {\Gamma(\frac{1}{2}) = \sqrt \pi}$. We also happen to know that in general, $latex {\Gamma(t+1) = t\Gamma(t)}$ (it is partially in this sense that the $latex {\Gamma}$ function generalizes the factorial function), so that $latex {\Gamma(\frac{1}{2}) = \frac{-1}{2} \Gamma(\frac{-1}{2})}$, or rather that $latex {\Gamma(\frac{-1}{2}) = -2 \sqrt \pi.}$ Finally, $latex {\Gamma(1) = 1}$ (on integers, it agrees with the one-lower factorial).

Putting these together, we get that

$latex \displaystyle \zeta(-1) = \frac{\pi^2/6}{-2\pi^2} = \frac{-1}{12}, $

which is what we wanted to show. $latex {\diamondsuit}$

The information I quoted about the Gamma function and the zeta function’s functional equation can be found on Wikipedia or any introductory book on analytic number theory. Evaluating $latex {\zeta(2)}$ is a classic problem that has been in many ways, but is most often taught in a first course on complex analysis or as a clever iterated integral problem (you can prove it with Fubini’s theorem). Evaluating $latex {\Gamma(\frac{1}{2})}$ is rarely done and is sort of a trick, usually done with Fourier analysis.

As usual, I have also created a paper version. You can find that here.

Posted in Expository, Math.NT, Mathematics | Tagged , , , , | 4 Comments

Response to fattybake’s question on Reddit

We want to understand the integral

$\displaystyle \int_{-\infty}^\infty \frac{\mathrm{d}t}{(1 + t^2)^n}. \ \ \ \ \ (1)$

Although fattybake mentions the residue theorem, we won’t use that at all. Instead, we will be very clever.

We will do a technique that was once very common (up until the 1910s or so), but is much less common now: let’s multiply by $latex {\displaystyle \Gamma(n) = \int_0^\infty u^n e^{-u} \frac{\mathrm{d}u}{u}}$. This yields

$latex \displaystyle \int_0^\infty \int_{-\infty}^\infty \left(\frac{u}{1 + t^2}\right)^n e^{-u}\mathrm{d}t \frac{\mathrm{d}u}{u} = \int_{-\infty}^\infty \int_0^\infty \left(\frac{u}{1 + t^2}\right)^n e^{-u} \frac{\mathrm{d}u}{u}\mathrm{d}t, \ \ \ \ \ (2)$

where I interchanged the order of integration because everything converges really really nicely. Do a change of variables, sending $latex {u \mapsto u(1+t^2)}$. Notice that my nicely behaving measure $latex {\mathrm{d}u/u}$ completely ignores this change of variables, which is why I write my $latex {\Gamma}$ function that way. Also be pleased that we are squaring $latex {t}$, so that this is positive and doesn’t mess with where we are integrating. This leads us to

$\displaystyle \int_{-\infty}^\infty \int_0^\infty u^n e^{-u + -ut^2} \frac{\mathrm{d}u}{u}\mathrm{d}t = \int_0^\infty \int_{-\infty}^\infty u^n e^{-u + -ut^2} \mathrm{d}t\frac{\mathrm{d}u}{u},$

where I change the order of integration again. Now we have an inner $latex {t}$ integral that we can do, as it’s just the standard Gaussian integral (google this if this doesn’t make sense to you). The inner integral is

$latex \displaystyle \int_{-\infty}^\infty e^{-ut^2} \mathrm{d}t = \sqrt{\pi / u}. $

Putting this into the above yields

$latex \displaystyle \sqrt{\pi} \int_0^\infty u^{n-1/2} e^{-u} \frac{\mathrm{d}u}{u}, \ \ \ \ \ (4)$

which is exactly the definition for $latex {\Gamma(n-\frac12) \cdot \sqrt \pi}$.

But remember, we multiplied everything by $latex {\Gamma(n)}$ to start with. So we divide by that to get the result:

$latex \displaystyle \int_{-\infty}^\infty \frac{\mathrm{d}t}{(1 + t^2)^n} = \dfrac{\sqrt{\pi} \Gamma(n-\frac12)}{\Gamma(n)} \ \ \ \ \ (5)$

Finally, a copy of the latex file itself.

Posted in Math.NT, Mathematics | Tagged , , | 1 Comment

Chinese Remainder Theorem (SummerNT)

This post picks up from the previous post on Summer@Brown number theory from 2013.

Now that we’d established ideas about solving the modular equation $latex ax \equiv c \mod m$, solving the linear diophantine equation $latex ax + by = c$, and about general modular arithmetic, we began to explore systems of modular equations. That is, we began to look at equations like

Suppose $latex x$ satisfies the following three modular equations (rather, the following system of linear congruences):

$latex x \equiv 1 \mod 5$

$latex x \equiv 2 \mod 7$

$latex x \equiv 3 \mod 9$

Can we find out what $latex x$ is? This is a clear parallel to solving systems of linear equations, as is usually done in algebra I or II in secondary school. A common way to solve systems of linear equations is to solve for a variable and substitute it into the next equation. We can do something similar here.

From the first equation, we know that $latex x = 1 + 5a$ for some $latex a$. Substituting this into the second equation, we get that $latex 1 + 5a \equiv 2 \mod 7$, or that $latex 5a \equiv 1 \mod 7$. So $latex a$ will be the modular inverse of $latex 5 \mod 7$. A quick calculation (or a slightly less quick Euclidean algorithm in the general case) shows that the inverse is $latex 3$. Multiplying both sides by $latex 3$ yields $latex a \equiv 3 \mod 7$, or rather that $latex a = 3 + 7b$ for some $latex b$. Back substituting, we see that this means that $latex x = 1+5a = 1+5(3+7b)$, or that $latex x = 16 + 35b$.

Now we repeat this work, using the third equation. $latex 16 + 35b \equiv 3 \mod 9$, so that $latex 8b \equiv 5 \mod 9$. Another quick calculation (or Euclidean algorithm) shows that this means $latex b \equiv 4 \mod 9$, or rather $latex b = 4 + 9c$ for some $latex c$. Putting this back into $latex x$ yields the final answer:

$latex x = 16 + 35(4 + 9c) = 156 + 315c$

$latex x \equiv 156 \mod 315$

And if you go back and check, you can see that this works. $latex \diamondsuit$

There is another, very slick, method as well. This was a clever solution mentioned in class. The idea is to construct a solution directly. The way we’re going to do this is to set up a sum, where each part only contributes to one of the three modular equations. In particular, note that if we take something like $latex 7 \cdot 9 \cdot [7\cdot9]_5^{-1}$, where this inverse means the modular inverse with respect to $latex 5$, then this vanishes mod $latex 7$ and mod $latex 9$, but gives $latex 1 \mod 5$. Similarly $latex 2\cdot 5 \cdot 9 \cdot [5\cdot9]_7^{-1}$ vanishes mod 5 and mod 9 but leaves the right remainder mod 2, and $latex 5 \cdot 7 \cdot [5\cdot 7]_9^{-1}$ vanishes mod 5 and mod 7, but leaves the right remainder mod 9.

Summing them together yields a solution (Do you see why?). The really nice thing about this algorithm to get the solution is that is parallelizes really well, meaning that you can give different computers separate problems, and then combine the things together to get the final answer. This is going to come up again later in this post.

These are two solutions that follow along the idea of the Chinese Remainder Theorem (CRT), which in general says that as long as the moduli are relative prime, then the system

$latex a_1 x \equiv b_1 \mod m_1$

$latex a_2 x \equiv b_2 \mod m_2$

$latex \cdots$

$latex a_k x \equiv b_k \mod m_k$

will always have a unique solution $latex \mod m_1m_2 \ldots m_k$. Note, this is two statements: there is a solution (statement 1), and the statement is unique up to modding by the product of this moduli (statement 2). Proof Sketch: Either of the two methods described above to solve that problem can lead to a proof here. But there is one big step that makes such a proof much easier. Once you’ve shown that the CRT is true for a system of two congruences (effectively meaning you can replace them by one congruence), this means that you can use induction. You can reduce the n+1st case to the nth case using your newfound knowledge of how to combine two equations into one. Then the inductive hypothesis carries out the proof.

Note also that it’s pretty easy to go backwards. If I know that $latex x \equiv 12 \mod 30$, then I know that $latex x$ will also be the solution to the system

$latex x \equiv 2 \mod 5$

$latex x \equiv 0 \mod 6$

In fact, a higher view of the CRT reveals that the great strength is that considering a number mod a set of relatively prime moduli is the exact same (isomorphic to) considering a number mod the product of the moduli.

The remainder of this post will be about why the CRT is cool and useful.

Application 1: Multiplying Large Numbers

Firstly, the easier application. Suppose you have two really large integers $latex a,b$ (by really large, I mean with tens or hundreds of digits at least – for concreteness, say they each have $latex n$ digits). When a computer computes their product $latex ab$, it has to perform $latex n^2$ digit multiplications, which can be a whole lot if $latex n$ is big. But a computer can calculate mods of numbers in something like $latex \log n$ time, which is much much much faster. So one way to quickly compute the product of two really large numbers is to use the Chinese Remainder Theorem to represent each of $latex a$ and $latex b$ with a set of much smaller congruences. For example (though we’ll be using small numbers), say we want to multiply $latex 12$ by $latex 21$. We might represent $latex 12$ by $latex 12 \equiv 2 \mod 5, 5 \mod 7, 1 \mod 11$ and represent $latex 21$ by $latex 21 \equiv 1 \mod 5, 0 \mod 7, 10 \mod 11$. To find their product, calculate their product in each of the moduli: $latex 2 \cdot 1 \equiv 2 \mod 5, 5 \cdot 0 \equiv 0 \mod 7, 1 \cdot 10 \equiv 10 \mod 11$. We know we can get a solution to the resulting system of congruences using the above algorithm, and the smallest positive solution will be the actual product.

This might not feel faster, but for much larger numbers, it really is. As an aside, here’s one way to make it play nice for parallel processing (which vastly makes things faster). After you’ve computed the congruences of $latex 12$ and $latex 21$ for the different moduli, send the numbers mod 5 to one computer, the numbers mod 7 to another, and the numbers mod 11 to a third (but also send each computer the list of moduli: 5,7,11). Each computer will calculate the product in their modulus and then use the Euclidean algorithm to calculate the inverse of the product of the other two moduli, and multiply these together. Afterwards, the computers resend their data to a central computer, which just adds the result and takes it mod $latex 5 \cdot 7 \cdot 11$ (to get the smallest positive solution). Since mods are fast and all the multiplication is with smaller integers (no bigger than the largest mod, ever), it all goes faster. And since it’s parallelized, you’re replacing a hard task with a bunch of smaller easier tasks that can all be worked on at the same time. Very powerful stuff!

I have actually never seen someone give the optimal running time that would come from this sort of procedure, though I don’t know why. Perhaps I’ll look into that one day.

Application 2: Secret Sharing in Networks of People

This is really slick. Let’s lay out the situation: I have a secret. I want you, my students, to have access to the secret, but only if at least six of you decide together that you want access. So I give each of you a message, consisting of a number and a modulus. Using the CRT, I can create a scheme where if any six of you decide you want to open the message, then you can pool your six bits together to get the message. Notice, I mean any six of you, instead of a designated set of six. Further, no five people can recover the message without a sixth in a reasonable amount of time. That’s pretty slick, right?

The basic idea is for me to encode my message as a number $latex P$ (I use P to mean plain-text). Then I choose a set of moduli, one for each of you, but I choose them in such a way that the product of any $latex 5$ of them is smaller than $latex P$, but the product of any $latex 6$ of them is greater than $latex P$ (what this means is that I choose a lot of primes or near-primes right around the same size, all right around the fifth root of $latex P$). To each of you, I give you the value of $latex P \mod m_i$ and the modulus $latex m_i$, where $latex m_i$ is your modulus. Since $latex P$ is much bigger than $latex m_i$, it would take you a very long time to just happen across the correct multiple that reveals a message (if you ever managed). Now, once six of you get together and put your pieces together, the CRT guarantees a solution. Since the product of your six moduli will be larger than $latex P$, the smallest solution will be $latex P$. But if only five of you get together, since the product of your moduli is less than $latex P$, you don’t recover $latex P$. In this way, we have our secret sharing network.

To get an idea of the security of this protocol, you might imagine if I gave each of you moduli around the size of a quadrillion. Then missing any single person means there are hundreds of trillions of reasonable multiples of your partial plain-text to check before getting to the correct multiple.

A similar idea, but which doesn’t really use the CRT, is to consider the following problem: suppose two millionaires Alice and Bob (two people of cryptological fame) want to see which of them is richer, but without revealing how much wealth they actually have. This might sound impossible, but indeed it is not! There is a way for them to establish which one is richer but with neither knowing how much money the other has. Similar problems exist for larger parties (more than just 2 people), but none is more famous than the original: Yao’s Millionaire Problem.

Alright – I’ll see you all in class.

Posted in Brown University, Expository, Math.NT, Mathematics | Tagged , , , , , , , , , , , | Leave a comment

Notes on the first week (SummerNT)

We’ve covered a lot of ground this first week! I wanted to provide a written summary, with partial proof, of what we have done so far.

We began by learning about proofs. We talked about direct proofs, inductive proofs, proofs by contradiction, and proofs by using the contrapositive of the statement we want to prove. A proof is a justification and argument based upon certain logical premises (which we call axioms); in contrast to other disciplines, a mathematical proof is completely logical and can be correct or incorrect.

We then established a set of axioms for the integers that would serve as the foundation of our exploration into the (often fantastic yet sometimes frustrating) realm of number theory. In short, the integers are a non-empty set with addition and multiplication [which are both associative, commutative, and have an identity, and which behave as we think they should behave; further, there are additive inverses], a total order [an integer is either bigger than, less than, or equal to any other integer, and it behaves like we think it should under addition and multiplication], and satisfying the deceptively important well ordering principle [every nonempty set of positive integers has a least element].

With this logical framework in place, we really began number theory in earnest. We talked about divisibility [we say that $latex a$ divides $latex b$, written $latex a mid b$, if $latex b = ak$ for some integer $latex k$]. We showed that every number has a prime factorization. To do this, we used the well-ordering principle.

Suppose that not all integers have a prime factorization. Then there must be a smallest integer that does not have a prime factorization: call it $latex n$. Then we know that $latex n$ is either a prime or a composite. If it’s prime, then it has a prime factorization. If it’s composite, then it factors as $latex n = ab$ with $latex a,b < n$. But then we know that each of $latex a, b$ have prime factorizations since they are less than $latex n$. Multiplying them together, we see that $latex n$ also has a prime factorization after all. $latex diamondsuit$

Our first major result is the following:

There are infinitely many primes

There are many proofs, and we saw 2 of them in class. For posterity, I’ll present three here.

First proof that there are infinitely many primes

Take a finite collection of primes, say $latex p_1, p_2, ldots, p_k$. We will show that there is at least one more prime not mentioned in the collection. To see this, consider the number $latex p_1 p_2 ldots p_k + 1$. We know that this number will factor into primes, but upon division by every prime in our collection, it leaves a remainder of $latex 1$. Thus it has at least one prime factor different than every factor in our collection. $latex diamondsuit$

This was a common proof used in class. A pattern also quickly emerges: $latex 2 + 1 = 3$, a prime. $latex 2cdot3 + 1 = 7$, a prime. $latex 2 cdot 3 cdot 5 + 1 = 31$, also a prime. It is always the case that a product of primes plus one is another prime? No, in fact. If you look at $latex 2 cdot 3 cdot 5 cdot 7 cdot 11 cdot 13 + 1=30031 = 59cdot 509$, you get a nonprime.

Second proof that there are infinitely many primes

In a similar vein to the first proof, we will show that there is always a prime larger than $latex n$ for any positive integer $latex n$. To see this, consider $latex n! + 1$. Upon dividing by any prime less than $latex n$, we get a remainder of $latex 1$. So all of its prime factors are larger than $latex n$, and so there are infinitely many primes. $latex diamondsuit$

I would also like to present one more, which I’ve always liked.

Third proof that there are infinitely many primes

Suppose there are only finitely many primes $latex p_1, ldots, p_k$. Then consider the two numbers $latex n = p_1 cdot dots cdot p_k$ and $latex n -1$. We know that $latex n – 1$ has a prime factor, so that it must share a factor $latex P$ with $latex n$ since $latex n$ is the product of all the primes. But then $latex P$ divides $latex n – (n – 1) = 1$, which is nonsense; no prime divides $latex 1$. Thus there are infinitely many primes. $latex diamondsuit$

We also looked at modular arithmetic, often called the arithmetic of a clock. When we say that $latex a equiv b mod m$, we mean to say that $latex m | (b – a)$, or equivalently that $latex a = b + km$ for some integer $latex m$ (can you show these are equivalent?). And we pronounce that statement as ” $latex a$ is congruent to $latex b$ mod $latex m$.” We played a lot with modular arithmetic: we added, subtracted, and multiplied many times, hopefully enough to build a bit of familiarity with the feel. In most ways, it feels like regular arithmetic. But in some ways, it’s different. Looking at the integers $latex mod m$ partitions the integers into a set of equivalence classes, i.e. into sets of integers that are congruent to $latex 0 mod m, 1 mod m, ldots$. When we talk about adding or multiplying numbers mod $latex mod m$, we’re really talking about manipulating these equivalence classes. (This isn’t super important to us – just a hint at what’s going on beneath the surface).

We expect that if $latex a equiv b mod m$, then we would also have $latex ac equiv bc mod m$ for any integer $latex c$, and this is true (can you prove this?). But we would also expect that if we had $latex ac equiv bc mod m$, then we would necessarily have $latex a equiv b mod m$, i.e. that we can cancel out the same number on each side. And it turns out that’s not the case. For example, $latex 4 cdot 2 equiv 4 cdot 5 mod 6$ (both are $latex 2 mod 6$), but ‘cancelling the fours’ says that $latex 2 equiv 5 mod 6$ – that’s simply not true. With this example in mind, we went about proving things about modular arithmetic. It’s important to know what one can and can’t do.

One very big and important observation that we noted is that it doesn’t matter what order we operate, as in it doesn’t matter if we multiply an expression out and then ‘mod it’ down, or ‘mod it down’ and then multiply, or if we intermix these operations. Knowing this allows us to simplify expressions like $latex 11^4 mod 12$, since we know $latex 11 equiv -1 mod 12$, and we know that $latex (-1)^2 equiv 1 mod 12$, and so $latex 11^4 equiv (-1)^{2cdot 2} equiv 1 mod 12$. If we’d wanted to, we could have multiplied it out and then reduced – the choice is ours!

Amidst our exploration of modular arithmetic, we noticed some patterns. Some numbers  are invertible in the modular sense, while others are not. For example, $latex 5 cdot 5 equiv 1 mod 6$, so in that sense, we might think of $latex frac{1}{5} equiv 5 mod 6$. More interestingly but in the same vein, $latex frac{1}{2} equiv 6 mod 11$ since $latex 2 cdot 6 equiv 1 mod 11$. Stated more formally, a number $latex a$ has a modular inverse $latex a^{-1} mod m$ if there is a solution to the modular equation $latex ax equiv 1 mod m$, in which case that solution is the modular inverse. When does this happen? Are these units special?

Returning to division, we think of the greatest common divisor. I showed you the Euclidean algorithm, and you managed to prove it in class. The Euclidean algorithm produces the greatest common divisor of $latex a$ and $latex b$, and it looks like this (where I assume that $latex b > 1$:

$latex b = q_1 a + r_1$

$latex a = q_2 r_1 + r_2$

$latex r_1 = q_3 r_2 + r_3$

$latex cdots$

$latex r_k = q_{k+2}r_{k+1} + r_{k+2}$

$latex r_{k+1} = q_{k+3}r_{k+2} + 0$

where in each step, we just did regular old division to guarantee a remainder $latex r_i$ that was less than the divisor. As the divisors become the remainders, this yields a strictly decreasing remainder at each iteration, so it will terminate (in fact, it’s very fast). Further, using the notation from above, I claimed that the gcd of $latex a$ and $latex b$ was the last nonzero remainder, in this case $latex r_{k+2}$. How did we prove it?

Proof of Euclidean Algorithm

Suppose that $latex d$ is a common divisor (such as the greatest common divisor) of $latex a$ and $latex b$. Then $latex d$ divides the left hand side of $latex b – q_1 a = r_1$, and thus must also divide the right hand side. So any divisor of $latex a$ and $latex b$ is also a divisor of $latex r_1$. This carries down the list, so that the gcd of $latex a$ and $latex b$ will divide each remainder term. How do we know that the last remainder is exactly the gcd, and no more? The way we proved it in class relied on the observation that $latex r_{k+2} mid r_{k+1}$. But then $latex r_{k+2}$ divides the right hand side of $latex r_k = q_{k+2} r_{k+1} + r_{k+2}$, and so it also divides the left. This also carries up the chain, so that $latex r_{k+2}$ divides both $latex a$ and $latex b$. So it is itself a divisor, and thus cannot be larger than the greatest common divisor. $latex diamondsuit$

As an aside, I really liked the way it was proved in class. Great job!

The Euclidean algorithm can be turned backwards with back-substitution (some call this the extended Euclidean algorithm,) to give a solution in $latex x,y$ to the equation $latex ax + by = gcd(a,b)$. This has played a super important role in our class ever since. By the way, though I never said it in class, we proved Bezout’s Identity along the way (which we just called part of the Extended Euclidean Algorithm). This essentially says that the gcd of $latex a$ and $latex b$ is the smallest number expressible in the form $latex ax + by$. The Euclidean algorithm has shown us that the gcd is expressible in this form. How do we know it’s the smallest? Observe again that if $latex c$ is a common divisor of $latex a$ and $latex b$, then $latex c$ divides the left hand side of $latex ax + by = d$, and so $latex c mid d$. So $latex d$ cannot be smaller than the gcd.

This led us to explore and solve linear Diophantine equations of the form $latex ax + by = c$ for general $latex a,b,c$. There will be solutions whenever the $latex gcd(a,b) mid c$, and in such cases there are infinitely many solutions (Do you remember how to see infinitely many other solutions?).

Linear Diophantine equations are very closely related a linear problems in modular arithmetic of the form $latex ax equiv c mod m$. In particular, this last modular equation is equivalent to $latex ax + my = c$ for some $latex y$.(Can you show that these are the same?). Using what we’ve learned about linear Diophantine equations, we know that $latex ax equiv c mod m$ has a solution iff $latex gcd(a,m) mid c$. But now, there are not infinitely many incongruent (i.e. not the same $latex mod m$) solutions. This is called the ‘Linear Congruence Theorem,’ and is interestingly the first major result we’ve learned with no proof on wikipedia.

Theorem: the modular equation $latex ax equiv b mod m$ has a solution iff $latex gcd(a,m) mid b$, in which case there are exactly $latex gcd(a,m)$ incongruent solutions.


We can translate a solution of $latex ax equiv b mod m$ into a solution of $latex ax + my = b$, and vice-versa. So we know from the Extended Euclidean algorithm that there are only solutions if $latex gcd(a,m) mid b$. Now, let’s show that there are $latex gcd(a,m)$ solutions. I will do this a bit differently than how we did it in class.

First, let’s do the case when $latex gcd(a,m)=1$, and suppose we have a solution $latex (x,y)$ so that $latex ax + my = b$. If there is another solution, then there is some perturbation we can do by shifting $latex x$ by a number $latex x’$ and $latex y$ by a number $latex y’$ that yields another solution looking like $latex a(x + x’) + m(y + y’) = b$. As we already know that $latex ax + my = b$, we can remove that from the equation. Then we get simply $latex ax’ = -my’$. Since $latex gcd(m,a) = 1$, we know (see below the proof) that $latex m$ divides $latex x’$. But then the new solution $latex x + x’ equiv x mod m$, so all solutions fall in the same congruence class – the same as $latex x$.

Now suppose that $latex gcd(a,m) = d$ and that there is a solution. Since there is a solution, each of $latex a,m,$ and $latex b$ are divisible by $latex d$, and we can write them as $latex a = da’, b = db’, m = dm’$. Then the modular equation $latex ax equiv b mod m$ is the same as $latex da’ x equiv d b’ mod d m’$, which is the same as $latex d m’ mid (d b’ – d a’x)$. Note that in this last case, we can remove the $latex d$ from both sides, so that $latex m’ mid b’ – a’x$, or that $latex a’x equiv b mod m’$. From the first case, we know this has exactly one solution mod $latex m’$, but we are interested in solutions mod $latex m$. Just as knowing that $latex x equiv 2 mod 4$ means that $latex x$ might be $latex 2, 6, 10 mod 12$ since $latex 4$ goes into $latex 12$ three times, $latex m’$ goes into $latex m$ $latex d$ times, and this gives us our $latex d$ incongruent solutions. $latex diamondsuit.$

I mentioned that we used the fact that we’ve proven 3 times in class now in different forms: if $latex gcd(a,b) = 1$ and $latex a mid bc$, then we can conclude that $latex a mid c$. Can you prove this? Can you prove this without using unique factorization? We actually used this fact to prove unique factorization (really we use the statement about primes: if $latex p$ is a prime and $latex p mid ab$, then we must have that $latex p mid a$ or $latex p mid b$, or perhaps both). Do you remember how we proved that? We used the well-ordered principle to say that if there were a positive integer that couldn’t be uniquely factored, then there is a smaller one. But choosing two of its factorizations, and finding a prime on one side – we concluded that this prime divided the other side. Dividing both sides by this prime yielded a smaller (and therefore unique by assumption) factorization. This was the gist of the argument.

The last major bit of the week was the Chinese Remainder Theorem, which is awesome enough (and which I have enough to say about) that it will get its own post – which I’m working on now.

I’ll see you all in class tomorrow.

Posted in Brown University, Expository, Math.NT, Mathematics | Tagged , , , , , , , , , , , , , , | 1 Comment

Recent developments in Twin Primes, Goldbach, and Open Access

It has been a busy two weeks all over the math community. Well, at least it seemed so to me. Some of my friends have defended their theses and need only to walk to receive their PhDs; I completed my topics examination, Brown’s take on an oral examination; and I’ve given a trio of math talks.

Meanwhile, there have been developments in a relative of the Twin Primes conjecture, the Goldbach conjecture, and Open Access math journals.

1. Twin Primes Conjecture

The Twin Primes Conjecture states that there are infinitely many primes $latex p$ such that $latex p+2$ is also a prime, and falls in the the more general Polignac’s Conjecture, which says that for any even $latex n$, there are infinitely many prime $latex p$ such that $latex p+n$ is also prime. This is another one of those problems that is easy to state but seems tremendously hard to solve. But recently, Dr. Yitang Zhang of the University of New Hampshire has submitted a paper to the Annals of Mathematics (one of the most respected and prestigious journals in the field). The paper is reputedly extremely clear (in contrast to other recent monumental papers in number theory, i.e. the phenomenally technical papers of Mochizuki on the ABC conjecture), and the word on the street is that it went through the entire review process in less than one month. At this time, there is no publicly available preprint, so I have not had a chance to look at the paper. But word is spreading that credible experts have already carefully reviewed the paper and found no serious flaws.

Dr. Zhang’s paper proves that there are infinitely many primes that have a corresponding prime at most $latex 70000000$ or so away. And thus in particular there is at least one number $latex k$ such that there are infinitely many primes such that both $latex p$ and $latex p+k$ are prime. I did not think that this was within the reach of current techniques. But it seems that Dr. Zhang built on top of the work of Goldston, Pintz, and Yildirim to get his result. Further, it seems that optimization of the result will occur and the difference will be brought way down from $latex 70000000$. However, as indicated by Mark Lewko on MathOverflow, this proof will probably not extend naturally to a proof of the Twin Primes conjecture itself. Optimally, it might prove the $latex p$ and $latex p+16$ – primes conjecture (which is still amazing).

One should look out for his paper in an upcoming issue of the Annals.

2. Goldbach Conjecture

I feel strangely tied to the Goldbach Conjecture, as I get far more traffic, emails, and spam concerning my previous post on an erroneous proof of Goldbach than on any other topic I’ve written about. About a year ago, I wrote briefly about progress that Dr. Harald Helfgott had made towards the 3-Goldbach Conjecture. This conjecture states that every odd integer greater than five can be written as the sum of three primes. (This is another easy to state problem that is not at all easy to approach).

One week ago, Helfgott posted a preprint to the arxiv that claims to complete his previous work and prove 3-Goldbach. Further, he uses the circle method and good old L-functions, so I feel like I should read over it more closely to learn a few things as it’s very close to my field. (Further still, he’s a Brandeis alum, and now that my wife will be a grad student at Brandeis I suppose I should include it in my umbrella of self-association). While I cannot say that I read the paper, understood it, and affirm its correctness, I can say that the method seems right for the task (related to the 10th and most subtle of Scott Aaronson’s list that I love to quote).

An interesting side bit to Helfgott’s proof is that it only works for numbers larger than $latex 10^{30}$ or so. Fortunately, he’s also given a computer proof for numbers less than than on the arxiv, along with David Platt. $latex 10^{30}$ is really, really, really big. Even that is a very slick bit.

3. FoM has opened

I care about open access. Fortunately, so do many of the big names. Two of the big attempts to create a good, strong set of open access math journals have just released their first articles. The Forum of Mathematics Sigma and Pi journals have each released a paper on algebraic and complex geometry. And they’re completely open! I don’t know what it takes for a journal to get off the ground, but I know that it starts with people reading its articles. So read up!

The two articles are


and, in Pi

Posted in Expository, Math.NT, Mathematics | Tagged , , , , , , , , , , , | 1 Comment

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:

$latex \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 $latex {\left(\frac{\cdot}{\cdot}\right)}$ be the Legendre Symbol, and there $latex {\varepsilon_k}$ is the sign of the $latex {k}$th Gauss sum, so that it is $latex {1}$ if $latex {k \equiv 1 \mod 4}$ and it is $latex {i}$ if $latex {k \equiv 3 \mod 4}$. It is not defined for $latex {k}$ even.

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

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

$latex \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}}$

$latex \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}}$

$latex \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}}$

$latex \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}}$

$latex \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}}$

$latex \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 $latex {\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 $latex {H_m(n_1n_2) = H_m(n_1)H_m(n_2)}$. $latex \Box$

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

$latex \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 $latex {k > 1}$, we will see that $latex {H_m(p^k)}$ is $latex {0}$. We split into cases when $latex {k}$ is even or odd. If $latex {k}$ is even, then we are just summing the primitive $latex {p^k}$th roots of unity, which is $latex {0}$. If $latex {k>1}$ is odd,

$latex \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) $

$latex \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

$latex \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) =$

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

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

$latex \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 $latex {p}$th part of the Euler product for $latex {\displaystyle \frac{L(2s-\frac12,\left(\frac{m(-1)^{k – 1/2}}{\cdot}\right))}{\zeta(4s-1)}}$.

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

$latex \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 $latex {k=l+1}$ and $latex {k}$ is odd, then we essentially have a Gauss sum

$latex \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) = $

$latex \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 $latex {k = l+1}$ and $latex {k}$ is even, noting that $latex {\zeta^m}$ is a $latex {p}$th root of unity,

$latex \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} =$

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

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

$latex \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

$latex \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 $latex {p}$th factor of the Dirichlet series in question, for $latex {p}$ dividing $latex {m}$. Assume first that $latex {p^l\parallel m}$ with $latex {l}$ even,

$latex \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 = $

$latex \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)$

$latex \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) $

$latex \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)$

$latex \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)+$

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

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

$latex \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)$

$latex \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 $latex {k}$, $latex {\varepsilon_{p^k} = 1}$, and for odd $latex {k}$, $latex {\varepsilon_{p^k} = \varepsilon_p}$. Similarly, for $latex {l}$ odd,

$latex \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 $

$latex \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$

$latex \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$

$latex \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$

$latex \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

$latex \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 $

$latex \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)$

Posted in Math.NT, Mathematics | Tagged , , , , , , , , | Leave a comment