Posted by Jason Polak on 01. December 2017 · Write a comment · Categories: opinion

Three things I would like to see happen with the practice of mathematics in the next ten years are:

Computer proof assistants…

…that are easy to use for the typical mathematician. Why? Mathematics is expanding tremendously and some areas are getting quite abstract. Some areas are so complex that I even wonder if anyone in some of these fields has time to verify important details. Proof assistants will probably become necessary, not just for the creation of new mathematics but to help us organize the amazing amount of existing mathematics.

Actually, there are several proof assistants that exist are and currently maintained. I’ve tried ones like Isabelle, Mizar, and Coq, but have not found them easy to use. Unfortunately making it possible to input typical mathematics into a computer so that it can be verified mechanically is a pretty difficult problem.

Blockchain Paper Publishing

This isn’t just for mathematics, but I think if anyone could adopt blockchain technology for journals, it would be mathematicians. Actually compared to other fields I think math has done pretty well with creating independent, open-access journals. However, we could go further and adopt blockchain technology.

If mathematicians used a single blockchain system (or maybe a few), every peer-review process could be recorded on the blockchain ledger. Traditional journals could still operate on this system, and in this case the name of the journal could be recorded in the blockchain ledger. In fact, this would be a benefit to journals because the book-keeping records would be in the blockchain and external hosting would not be necessary.

But one wouldn’t need a traditional ‘journal unit’; someone who writes a paper could send it off to a willing independent editor and that editor could just send the paper to be reviewed as usual. The result of this independent transaction would be recorded on the blockchain.

The upshot is that all peer-reviewed transactions would be recorded on a distributed blockchain and all paper-reviewing activities would receive a quantitative measure of credit.

De-emphasis of proving new results in mathematics

This relates back to the idea that mathematics today is progressing so quickly that theorems are being proved more quickly than people can understand them. So today you have hundreds of fields, some of them with only a few people inside them knowing what’s going on. That’s kind of a shame because mathematics would be enriched if there were a little more cross-disciplinary understanding.

Thus it would be great if more emphasis and credit were placed upon simplifying existing research and making it more accessible. This would help the next generation of mathematicians enter the field. But it would also alleviate the pressure that exists for many existing research to output theorem after theorem, which is probably not all that useful for developing the understanding of mathematics as a whole anyway.

I still think we should prove theorems, and there are many cool things that haven’t been done yet. But with a more varied approach to math, we could concentrate on fewer, more quality theorems rather than pure quantity.

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 · 2 comments · Categories: elementary · Tags:

The smallest number paradox goes like this: consider the natural numbers: 0,1,2,3,… . Each can be specified by a string of characters. For example, “0” itself specifies 0. However, on my computer there are only finitely many bits. Therefore, only finitely many numbers can be specified as a string on my computer. In other words, there are some very huge numbers that just cannot be represented as a string on my computer. Now, the string doesn’t have to be the longhand decimal expansion. For example, I might write “200!” for the number

7886578673647905035523632139321850622951359776871732632947425332443594499
6340334292030428401198462390417721213891963883025764279024263710506192662
4952829931113462857270763317237396988943922445621451664240254033291864131
2274282948532775242424075739032403212574055795686602260319041703240623517
0085879617892222278962370389737472000000000000000000000000000000000000000
0000000000

Because the natural numbers are well-ordered, there exists a smallest natural number $N$ that cannot be specified a a string on my computer. But wait, what about “the smallest natural number that cannot be represented as a string on my computer”? That string describes $N$. So there’s the paradox: I just wrote down a string on my computer specifying a number whose definition is that it cannot be described by any string.

Why is this not paradox? The problem is that the set $X$, defined by “the numbers that cannot be defined by a string on my computer” is just not well-defined. To define $X$, you need to specify in advance a set of valid strings, each of which represents a natural number in a formal system in which the natural numbers can be defined, like ZFC set theory. That’s because no string of characters means anything unless you have a predetermined meaning assigned to it: “43^2” might mean 1849 to a mathematician or 41 to a Python programmer.

Here is an example of such a predetermined meaning: allow valid arithmetic expressions involving only the symbols 0,1,2,3,… for every natural number and addition (“+” symbol), multiplication (“*” symbol), and exponentiation (“^”). In this system “123^5123+5” is a valid string, but “two hundred” is not, even though there is another valid string “200” that represents 200.

Now, “the smallest number that cannot be represented as a string in the aforementioned system on my computer” is a meta-statement that makes sense; this string itself is not valid for representing numbers in our fixed system, and the paradox disappears.

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.

Posted by Jason Polak on 07. November 2017 · Write a comment · Categories: poll · Tags: ,

With the hundreds of papers released every day, I think it would be nice to have some ways to find the ones others find interesting. Vote in this poll for the features you might like:

Which of the following features would you most like to see on the arXiv?

View Results

Loading ... Loading ...

Note: I am not affiliated with the arXiv so this poll is just for fun.

The Fibonacci sequence is an infinite sequence of integers $f_0,f_1,f_2,\dots$ defined by the initial values $f_0 = f_1 = 1$ and the rule
$$f_{n+1} = f_n + f_{n-1}$$
In other words, to get the next term you take the sum of the two previous terms. For example, it starts off with:
$$1,1,2,3,5,8,13,21,34,55,\dots$$
You can define all sorts of recursive sequences this way and get a whole slew of interesting patterns. The Fibonacci sequence is one of the most well-known, as it is one of the simplest and has connections to the golden ratio:
$$\lim_{n\to \infty} f_n/f_{n-1} = \frac{1 + \sqrt{5}}{2}.$$
In fact, without too great an effort you could derive an exact, closed formula for $f_n$ (i.e. a formula that does not involve recursion, or calculating previous terms to get to the next one) in which appears the golden ratio.

A theme that’s been running through my research lately is looking at things modulo $m$ for some integer $m$. Reduction from $\Z$ to $\Z/m$ often happens in mathematics because there is some dictionary that tells you something about an object over $\Z$ if you know something mod $m$. So let’s look at the Fibonacci sequence in $\Z/5$. It goes like this:

1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1, 1,…

Very good looking sequence if you ask me. Notice how it starts to repeat, going right back to the beginning. Of course, it has to repeat eventually, because there are only $m^2$ elements in $\Z/m\times\Z/m$. What’s a little more interesting is that it goes right back to the beginning $1,1,\dots$, rather than repeating with some new pair that appears a little later.

Why is this? It is because of the recursive definition $f_{n+1} = f_n + f_{n-1}$. We could also write it $f_{n-1} = f_{n+1} – f_n$. Therefore, if two pairs are equal $(f_s,f_{s+1}) = (f_t,f_{t+1})$ with $s \gt t$ then $f_{s-1} = f_{t-1}$. Continuing backwards we see that $f_{s – t} = f_0$ and $f_{s-t+1} = f_1$. This fact was first proved by D.D. Wall of IBM.
More »

Posted by Jason Polak on 05. November 2017 · Write a comment · Categories: advice · Tags: , , ,

I’m getting close to the end of my postdoc and I’m applying for jobs again! So, I thought I’d write some basic guidelines that I found helpful in this process. I will update this guide as time goes by. Feel free to add your own advice in the comments.

Deadlines and reference letters

Most jobs start coming out around September for the following year. After that they keep trickling in all the way until May or even June. The first big set of application deadlines are in November, but some earlier ones are in October. Therefore, you should get your letters well before October. How many letters do you need?

  1. Around 80-90% of academic jobs need three letters. You can feel mostly relieved once you get three.
  2. Some jobs need four letters, and even specify “four or more”. If you can get more than three, which is not always easy, you can pretty much apply anywhere.
  3. Industry jobs usually do not require letters for your initial application but will still require the email addresses of a couple of references.

Almost all academic jobs require at least one letter to mention of your teaching abilities. Graduate students can typically get someone in their department to write this, based on their evaluations from either courses or tutorials.
More »