Posted by Jason Polak on 29. November 2017 · Write a comment · Categories: number-theory · Tags: , ,

Lately I’ve been thinking about primes, and I’ve plotted a few graphs to illustrate some beautiful ideas involving primes. Even though you might not always associate with primes, they are always haunting quietly in the background.

Abundance of primes in an arithmetic progression

Let’s start out with the oddest prime of all: 2. Get it? But after that, all the odd primes are either of the form $4k + 1$ or $4k + 3$. For fixed $x$, are there more primes less than $x$ of the form $4k + 1$ or the second form $4k + 3$? Let’s write $\pi(4k + r,x)$ for the number of primes less than or equal to $x$ of the form $4k + r$. Here is a graph of the difference $\pi(4k+3,x) – \pi(4k+1,x)$:

Pretty neat right? It looks like this difference is wildly erratic, reaching zero after a short while with a bit of a fight and then for a really good long while the primes of the form $4k +3$ win out. So you might be tempeted to think that primes of the form $4k + 3$ become more and more abundant as $x$ increases. That would be wrong. In fact, John E. Littlewood proved that $\pi(4k +3,x)-\pi(4k + 1,x)$ switches sign infinitely often!

Of course, that must mean there are infinitely many primes of both types, and that’s true and a special case of Dirichlet’s theorem: there are infinitely many primes in any arithmetic progression $ax + b$ whenever $a$ and $b$ are relatively prime.
More »

Posted by Jason Polak on 26. November 2017 · Write a comment · Categories: number-theory · Tags: ,

Since the days of antiquity, we’ve always been looking for ways to determine whether a natural number is prime. Trial division up to the square root of a number quickly becomes tedious, thought it is worth noting that even on my fairly old laptop a slightly optimised trial-division algorithm will list all the primes under 10^7 in just under seven seconds.

Another method that sometimes works is Fermat’s little theorem:

Theorem. If $n$ is a prime number then for every $a$,
$$a^n\equiv_n a.$$

Here, I’m using the notation to mean $a^n – n$ is divisible by $n$. Let’s do some examples: 4^11 – 4 = 4194300, which is divisible by 11 (you can see this directly by using the alternating sum digit test: 4 – 1 + 9 – 4 + 3 = 11). On the other hand, $2^{69} – 2 = 590295810358705651710 \equiv_{69} 6$. Of course, from the nature of the theorem, if $a^n\equiv_n a$ is not true then $n$ is composite, so it can tell you for sure if a number is composite but not if a number is prime.
More »

Posted by Jason Polak on 25. November 2017 · Write a comment · Categories: number-theory · Tags: ,

If you write out all the $n$th powers of natural numbers for $n \gt 1$ (“higher powers”) in increasing order you get a sequence like this:

1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, …

If you keep computing more numbers in this sequence, once in a while you’ll find two consecutive terms quite close together. For instance:
$$1138^2 – 109^3 = 15$$
But no matter how far you go, it seems that the only two terms that are just one apart are 8 and 9. Eugène Catalan conjectured that 8 and 9 are the only two numbers in this sequence just one apart, and this conjecture became known as Catalan’s conjecture.

If you only allowed powers of 2 and 3 in the sequence, then the proof that 8 and 9 are the only consecutive powers is not difficult. In fact, it just requires the difference of squares identity: $a^2 – b^2 = (a – b)(a + b)$. Let’s see how it works! If only powers of 2 and 3 are allowed, then the question becomes: when is it possible that $3^m – 2^n = 1$ or that $2^n – 3^m = 1$?
More »

Posted by Jason Polak on 23. November 2017 · Write a comment · Categories: number-theory · Tags: , ,

A positive integer is called perfect if it is the sum of all its proper divisors. For example, the proper divisors of 6 are 1,2, and 3 and 1 + 2 + 3 = 6.

The $\sigma$-function is defined as $\sigma(n) = \sum_{d\mid n} d$. Therefore, $n$ is perfect if and only if $\sigma(n) = 2n$. If you plot the function $\sigma(n) – 2n$ on the Euclidean plane you get a fascinating picture:

Of course, there are so many data points that it’s impossible to see the perfect numbers 6, 28, 496, 8128,… that occur in this graph as well.

All the powers of 2 are nearly perfect: $\sigma(2^n) – 2^{n+1} = -1$. Is it possible for $\sigma(n) – 2n = -1$ when $n$ is not a power of $2$? Can it ever happen that $\sigma(n) – 2n = 1$? It can’t happen when $n$ is at most 10^6.
More »

In the abelian group $\Z/n$, the order of $m\in \Z/n$ can be calculated via the formula $n/{\rm gcd}(m,n)$. This number is just the smallest number you have to multiply $m$ by in order to get a multiple of $n$. So when $n = p$ is a prime, every we see that every nonzero element of $\Z/p$ has order $p$.

However, every nonzero element of $\Z/p$ is prime to $p$, and the nonzero elements of $\Z/p$ form the abelian multiplicative group $\Z/p^\times$ of invertible elements. Then the order of an element $m\in \Z/p^\times$ is a little more tricky to figure out, but we know by Fermat’s Little Theorem that it will be a factor of $p-1$.

Example. Consider the prime $p=11$. Then we know that $3^{10} = 1$ by Fermat’s Little Theorem. However, $3^5 = 1$ too. In fact the order of $~3$ is $~5$.

This example has a curious property that you may not know about. It is true that $3^5 = 1$ in $\Z/11$. But did you know that $3^5 = 1$ in $\Z/121$? What?! This leads to a natural question:

Question. Which primes $p$ have the property that there exists an element $m\in \Z/p^\times, m\not=1$ such that the order of $m$ in $\Z/p^\times$ is the same as the order of $m$ in ${\Z/p^2}^\times$?

Not all primes have this property. Consider $p = 5$. Then $3^4 = 1$ in $\Z/5$. However, $3^4 = 6$ in $\Z/25$. In fact, none of the elements $2,3,4$ have the same order in both $\Z/5^\times$ and $\Z/25^\times$. Here are some primes that do have such elements:

11, 29, 37, 43, 59, 71, 79, 97, 103, 109, 113, 127, …

So, there are quite a few of them and maybe there are infinitely many. One can go further with this question: what about primes for which there are non-trivial elements in $\Z/p^\times$ with the same order in $\Z/p^\times, {\Z/p^2}^\times,$ and ${\Z/p^3}^\times$? There are fewer of these. But they exist. For example, the identity
$$68^{112} = 1$$
Holds in $\Z/113^k$ for $k=1,2,3$ (but not for $k=4$). This is the only example I know of and maybe it is the only possible example? But I probably just haven’t looked far enough. I wrote the original program to find it in Python but I plan to rewrite it in C with the gmp library to expand the search.

Briefly, the Selberg class is a set of functions $F:\C\to\C$ such that $f(s)$ can be written as a Dirichlet series for $\Re(s) > 1$ and that satisfies a form of analytic continuation, a functional equation, a Ramanujan hypothesis bound on coefficients of the Dirichlet series, and an Euler product formula.

Andrew Booker in [1] has extended the Selberg class in a different way, in the notion of an $L$-datum. In this post, we’ll state Booker’s definition of an $L$-datum, state his converse theorem, and explain his corollary that the completed $L$-function of a unitary cuspidal automorphic representation of $\GL_3(\A_\Q)$ has infinitely many zeroes of odd order.
More »

Posted by Jason Polak on 25. August 2015 · Write a comment · Categories: algebraic-geometry, number-theory · Tags: ,

In the Arthur-Selberg trace formula and other formulas, one encounters so-called ‘orbital integrals’. These integrals might appear forbidding and abstract at first, but actually they are quite concrete objects. In this post we’ll look at an example that should make orbital integrals seem more friendly and approachable. Let $k = \mathbb{F}_q$ be a finite field and let $F = k( (t))$ be the Laurent series field over $k$. We will denote the ring of integers of $F$ by $\mathfrak{o} := k[ [t]]$ and the valuation $v:F^\times\to \mathbb{Z}$ is normalised so that $v(t) = 1$.

Let $G$ be a reductive algebraic group over $\mathfrak{o}$. Orbital integrals are defined with respect to some $\gamma\in G(F)$. Often, $\gamma$ is semisimple, and regular in the sense that the orbit $G\cdot\gamma$ has maximal dimension. One then defines for a compactly supported smooth function $f:G(F)\to \mathbb{C}$ the orbital integral
$$
\Ocl_\gamma(f) = \int_{I_\gamma(F)\backslash G(F)} f(g^{-1}\gamma g) \frac{dg}{dg_\gamma}.
$$
More »

Posted by Jason Polak on 14. April 2014 · Write a comment · Categories: number-theory

Here’s a cool picture I made with Sage and R of class numbers of $\mathbb{Q}(\sqrt{-D})$ where $D$ is squarefree. It consists of the first five thousand such $D$ (click image to enlarge):

Rplot001

The even class numbers are shown in red +-signs and the odd class numbers are shown as blue disks. If you look carefully at the bottom left-hand corner where the points start, you’ll see a small conglomeration of blue dots that consist of the only nine imaginary quadratic fields that have class number one.

Posted by Jason Polak on 08. June 2013 · Write a comment · Categories: number-theory · Tags: , ,

frame8

Have you ever tried to visualise the graph of a complex function $ f:\mathbb{C}\to\mathbb{C}$? The problem with complex functions is that usually we graph a complex number as an ordered pair $ (x,y)$ on a Euclidean plane, which corresponds to $ z = x + iy$. Unfortunately, this means that if we want to graph complex functions as we do real functions, we need to draw the graph in four-dimensional space! Some people have actually claimed the ability to visualise this, but I do not!

However, if we use time as a dimension, we could represent four dimensions as a moving three-dimensional image in time, like a movie. Sometimes, it’s hard to draw three dimensions in two dimensions, though we don’t actually lose too much because we can only see a two-dimensional picture of a three-dimensional scene at any given time.

There are a few animations in this post; they may take a few seconds to load, or a few minutes on a slower connection.
More »

Mostly to take a break from marking exams, I thought I’d start a new recurring series here about mathematics papers and books that I find, both new and old. The “new” will consist mainly of preprints that look interesting (to encourage me to browse the arXiv) and the “old” will consists of papers I will likely read (to encourage me to read, or at least skim, more papers).

New Preprints

  1. Clark Barwick, “On the algebraic K-theory of higher categories”: For a while I’ve wanted to learn a bit about higher category theory, but I’ve not yet found any application or motivation for it in something I’m already really interested in (including the stuff here). Perhaps this paper by Barwick will change my mind: algebraic K-theory may be best viewed as a functor with a universal property that generalises the well-known universal properties known for the classical K groups.
  2. Booker, Hiary, and Keating, Detecting squarefree numbers”: Under the Generalised Riemann Hypothesis the authors propose an algorithm to test whether an integer is squarefree, without needing the number’s factorisation.
  3. Shalit, “A sneaky proof of the maximum modulus principle”: This is a proof of the maximum modulus principle in complex analysis, now with even less complex analysis! This paper also appeared in the American Mathematical Monthly and the author wrote a blog post about it as well.

View the whole post to reveal the hidden classic:
More »