# A partition identity

Posted by Jason Polak on 07. April 2018 · Write a comment · Categories: number-theory · Tags: ,

There is a cool way to express 1 as a sum of unit fractions using partitions of a fixed positive integer. What do we mean by partition? If $n$ is such an integer then a partition is just a sum $e_1d_1 + \cdots + e_kd_k = n$ where $d_i$ are positive integers. For example,

7 = 4 + 1 + 1 = 4 + 2(1)

The order of the partition is not very interesting and so we identify partitions up to order. Thus, here are all the 15 partitions of 7:

7
6+1
5+2
5+1+1
4+3
4+2+1
4+1+1+1
3+3+1
3+2+2
3+2+1+1
3+1+1+1+1
2+2+2+1
2+2+1+1+1
2+1+1+1+1+1
1+1+1+1+1+1+1

Group the same numbers together so that each partition is written as $n = \sum e_id_i$ where there are $e_i$ appearances of $d_i$ (or vice-versa, it's symmetric). Then it's a theorem that:
$$1 = \sum (e_1!\cdots e_k!\cdot d_1^{e_1}\cdots d_k^{e_k})^{-1}.$$
This partition identity has a bunch of proofs. A neat one appears in the paper "Using Factorizations to Prove a Partition Identity" by David Dobbs and Timothy Kilbourn. In their proof, they used an asympotitc expression for the number of irreducible polynomials over a finite field of a given degree $n$ (the same $n$ that appears in the partition).

Here are some examples of this identity. For n=5, we have:

1 = 1/5 + 1/4 + 1/6 + 1/6 + 1/8 + 1/12 + 1/120

For n=7:

1 = 1/7 + 1/6 + 1/10 + 1/10 + 1/12 + 1/8 + 1/24 + 1/18
+ 1/24 + 1/12 + 1/72 + 1/48 + 1/48 + 1/240 + 1/5040

And for n=11

1 = 1/11 + 1/10 + 1/18 + 1/18 + 1/24 + 1/16 + 1/48 + 1/28 + 1/21
+ 1/56 + 1/28 + 1/168 + 1/30 + 1/24 + 1/36
+ 1/36 + 1/48 + 1/72 + 1/720 + 1/50 + 1/40 + 1/40
+ 1/90 + 1/30 + 1/90 + 1/240 + 1/80 + 1/240
+ 1/3600 + 1/96 + 1/64 + 1/192 + 1/72 + 1/96 + 1/48
+ 1/288 + 1/192 + 1/192 + 1/960 + 1/20160 + 1/324
+ 1/324 + 1/144 + 1/216 + 1/2160 + 1/1152 + 1/288 + 1/576
+ 1/4320 + 1/120960 + 1/3840 + 1/2304
+ 1/5760 + 1/40320 + 1/725760 + 1/39916800

# On normal numbers and e

Posted by Jason Polak on 30. January 2018 · Write a comment · Categories: number-theory · Tags: ,
A real number is simply normal in base $b$ if the frequency of each base $b$ digit in the first $n$ digits tends to a limit as $n$ goes to infinity, and each of these limits is the same.

In other words, a real number is simply normal in base $b$ if each digit appears with equal frequency. It may not be the case of course that the frequency is well-defined: as you keep computing more and more decimal digits of a number, the frequency of any given digit could keep oscillating.

A real number is normal in base $b$ if the frequency of each length $k$ string of numbers exists and is equal to $1/b^k$.

A rational number can be simply normal in some base. For example, 0.12345678901234567890…. is simply normal in base ten. Rational numbers can't be normal, since their decimals repeat. Irrational numbers can be normal, and in fact almost every number is normal in the sense of the Lebesgue measure. Champernowne proved that the number

0.123456789101121314…

is normal to every base. Mathematicians believe that $e$ and $\pi$ are normal but no one has ever proved it, or found a proof that they are not normal. It's tempting to look at some numerical evidence. For example, here are the frequencies of the digits in the first 301029 decimal digits of $e$:

 0 30057 1 30283 2 29785 3 30316 4 30206 5 30044 6 30375 7 30065 8 30055 9 29843

Counting these took about 2.4 seconds. Looks like the digit '6' occurs the most often, whereas '2' occurs the least often. Is this about what we'd expect? Here's the result of a $\chi^2$-test for goodness of fit, the null hypothesis being that the probability of each digit is the same:

X-squared = 11.309, df = 9, p-value = 0.2551

Looks like there's no reason to be alarmed. Of course, since the normality and simple normality of a number depends only on the "tail" of its expansion, just testing a finite number of digits can be misleading. The rational number defined by the first 301029 digits of $e$ is not normal or simply normal.

The frequencies for all two digit combinations starts off like this:

 00 2957 01 3035 02 3040 03 2978

You probably don't want to look at the other 96 frequencies. But a $\chi^2$-test reveals the following:

X-squared = 108.06, df = 99, p-value = 0.2506

Although this is rather convincing that $e$ is normal, none of this proves anything. If it is, you'd expect 12345 to occur about three times in the first 301029 digits. In fact it does, the first time starting at the 166412th digit. The sequence 99999 only occurs once, starting at the 290471st digit. Even though the odds are against it, the starting six digit sequence 271828 actually does occur once, at the 252474th digit. Maybe that will help you memorise $e$?

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 »

# Carmichael numbers

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 »

# Catalan's conjecture

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 »

# What is a perfect number?

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 »

# Same multiplicative order modulo p and p^2

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.

# Booker's Extension of the Selberg Class

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 »

# Calculation of an Orbital Integral

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 »

# Graph: Class Numbers of Imaginary Quadratic Fields

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):

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.