# 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.

# Poll: Features that would improve the arXiv

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?

 Commenting The ability to "favourite" papers and see the number of users who have done so for each paper Paper pages displaying download stats (total, total for month, etc) The arXiv doesn't need improvements

View Results

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

# Fibonacci sequence modulo m

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 »

# How to apply for jobs in math

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.

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 »

# What is a Liouville number?

Posted by Jason Polak on 04. November 2017 · 2 comments · Categories: elementary · Tags: ,

An irrational number $r$ is called a Liouville number if for every positive integer $n$ there exists integers $p$ and $q \gt 1$ such that
$$| r – p/q | \lt 1/q^n.$$
The requirement that $q \gt 1$ is crucial because otherwise, all irrational numbers would satisfy this definition. Liouville numbers are transcendental. In an intuitive way you could think of Liouville numbers as having pretty rapidly converging rational approximations. Here is an example of a Liouville number:
$$r = 0.1001000000000000000000000010\dots$$
The pattern might not be apparent but it is the number between $0$ and $1$ whose decimal expansion is all zeroes except ones in the $1^1,2^2,3^3,\dots$ places. More succintly, we can write
$$r = \sum_{k=1}^\infty 10^{-k^k}.$$
Let us prove that it is a Liouville number. Fix an $n$ and let
$$r_n = \sum_{k=1}^n 10^{-k^k}$$
Then $r_n$ is a rational number and can be written as $p/q$ with $q = 10^{-n^n}$. Then:
$$|r – r_n| = |r – p/q| \lt 1.1\times 10^{-(n+1)^{n+1}} \le 10^{-n^{n+1}} = 1/q^n$$
Therefore, $r$ is a Liouville number. This proof worked so well because I made the sequences of consecutive zeros increase very rapidly in length. Here’s another question:

Is the irrational number $M = \sum_{k=1}^\infty 10^{-k^2}$ a Liouville number?

If you tried the proof I just gave for this number $M$ (so-called because it is the first letter of mystery), it won’t work. But that doesn’t prove that $M$ is not a Liouville number. Maybe we just weren’t judicious enough in our choice of $p$ and $q$. Can you show that $M$ is or is not a Liouville number? I’ll leave this to the dear reader.

There are many of Liouville numbers in the sense of cardinality: the preceding proof works if you replace the $1$s with any nonzero numbers (you can replace some of them by zero too, but you can’t just replace all of them by zero). So we see the Liouville numbers have cardinality of the continuum. It’s also pretty easy to see that the set of Liouville numbers is dense.

On the other hand, Liouville numbers form a set of measure zero. Therefore, there are plenty of transcendentals that are not Liouville numbers. Can you write down a specific transcendental number that is not Liouville?

# All set endomorphisms of a finite field are polynomial

Posted by Jason Polak on 03. October 2017 · Write a comment · Categories: elementary · Tags: , ,

Let $F$ be a finite field. Did you know that given any function $\varphi:F\to F$, there exists a polynomial $p\in F[x]$ such that $\varphi(a) = p(a)$ for all $a\in F$? It’s not hard to produce such the required polynomial:
$$p(x) = \sum_{a\in F} \left( \varphi(a)\prod_{b\not= a}(x – b)\prod_{b\not=a}(a-b)^{-1} \prod \right)$$
This works because every nonzero element of $F$ is not a zerodivisor.

The same cannot be said of infinite fields. If $F$ is infinite, then there are functions $\varphi:F\to F$ that cannot be represented as polynomials. That’s because the cardinality of $F[x]$ is the same as that of $F$ when $F$ is infinite. However, the number of functions $F\to F$ is greater than the cardinality of $F$. Therefore, there simply aren’t enough polynomials.

But, one does not have to go to infinite fields. For any prime $q$, there are functions $\Z/q^2\to \Z/q^2$ that cannot be represented as a polynomial. This is true because if $\varphi$ is a polynomial function, then $\varphi(x + q)\equiv \varphi(x)$ modulo $q$. Therefore, any of the $q^{q-2}$ functions $\varphi:\Z/q^2\to\Z/q^2$ satisfying $\varphi(0) = 0$ and $\varphi(q) = 1$ cannot be represented by polynomial.

# First-order characterisations of free and flat…projective?

Posted by Jason Polak on 28. September 2017 · 3 comments · Categories: commutative-algebra, homological-algebra, modules

Here is an interesting question involving free, projective, and flat modules that I will leave to the readers of this blog for now.

First, consider free modules. If $R$ is a ring, then every $R$-module is free if and only if $R$ is a division ring. The property of $R$ being a division ring can be expressed in terms of first-order logic in the language of rings: $\forall x[x\not=0 \rightarrow \exists y(xy = 1)]$.

The meat of this first-order statement is the equation $xy = 1$. Now, multiply by $x$ on the right to get the equation $xyx = x$. Now we can put this in a first-order sentence: $\forall x\exists y[xyx = x]$. Notice how we removed the condition $x\not=0$ from this one. That’s because $x=0$ satisfies $xyx = x$ for any $y$ in all rings. Rings that model $\forall x\exists y[xyx = x]$ are called von Neumann regular. More importantly, these are exactly the rings for which every $R$-module is flat.

By weakening the statement that $R$ is a division ring, we got a statement equivalent to the statement that every $R$-module is flat. One might wonder: where did the projective modules go? Is there a first-order sentence (or set of sentences perhaps) in the language of rings whose models are exactly those rings $R$ for which every $R$-module is projective? Diagrammatically:

Can we replace the question mark with a first-order sentence, or a set of them?

My initial thoughts are no because of ultraproducts, but I have not yet come up with a rigorous argument.

# Poll: Have your say in the future topics of this blog

Posted by Jason Polak on 23. September 2017 · Write a comment · Categories: opinion

I’ve decided to add more interactivity to this blog. As a first step, I’d like to know what kinds of posts readers would like to see. So click an option and vote!

What kinds of posts would you like to see in the future on this blog?

View Results

# On a characterisation of Krull dimension zero rings

Posted by Jason Polak on 21. September 2017 · Write a comment · Categories: modules · Tags:

Here is one characterisation of commutative rings of Krull dimension zero:

Theorem. A commutative ring $R$ has Krull dimension zero if and only if every element of the Jacobson radical ${\rm Jac}(R)$ of $R$ is nilpotent and the quotient ring $R/{\rm Jac}(R)$ is von Neumann regular.

Recall that a ring $R$ is von Neumann regular if for every $x\in R$ there exists a $y\in R$ such that $xyx = x$. This odd property is equivalent to saying that every $R$-module is flat.

Here are two examples of what happens when we drop various assumptions in the “if” direction of the theorem:

1. The ring $\Z_{(p)}$ of integers localised away from the prime $(p)$ is an example of a ring such that $R/{\rm Jac}(R)$ is von Neumann regular but ${\rm Jac}(R)$ has no nontrivial nilpotent elements. The ring $\Z_{(p)}$ has Krull dimension one.
2. Another type of example is given by $\Z[[t]]/t^n$ where $\Z[[t]]$ denotes the power series ring with integer coefficients. Unlike our first example, the Jacobson radical of this ring is the ideal $(t)$, which is also the nilradical (=set of nilpotent elements), but $R/{\rm Jac}(R) = \Z$, which is not von Neumann regular and has Krull dimension one.

Note that we were forced look for counterexamples to dropped assumptions in the class of infinite rings. That’s because every finite commutative ring has Krull dimension zero.

# Dimension zero rings for three types of dimension

There are all sorts of notions of dimension that can be applied to rings. Whatever notion you use though, the ones with dimension zero are usually fairly simple compared with the rings of higher dimension. Here we’ll look at three types of dimension and state what the rings of zero dimension look like with respect to each type. Of course, several examples are included.

All rings are associative with identity but not necessarily commutative. Some basic homological algebra is necessary to understand all the definitions.

## Global Dimension

The left global dimension of a ring $R$ is the supremum over the projective dimensions of all left $R$-modules. The right global dimension is the same with “left” replaced by “right”. And yes, there are rings where the left and right global dimensions differ.

However, $R$ has left global dimension zero if and only if it has right global dimension zero. So, it makes sense to say that such rings have global dimension zero. Here is their characterisation:

A ring $R$ has global dimension zero if and only if it is semisimple; that is, if and only if it is a finite direct product of full matrix rings over division rings.

Examples of such rings are easy to generate by this characterisation:

1. Fields and finite products of fields
2. $M_2(k)$, the ring of $2\times 2$ matrices over a division ring $k$
3. etc.