# The Smallest Number Paradox

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.

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

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

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

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

# Is it a projective module?

Posted by Jason Polak on 19. September 2017 · Write a comment · Categories: homological-algebra, modules

Consider a field $k$. Define an action of $k[x,y]$ on $k[x]$ by $f*g = f(x,x)g(x)$ for all $f\in k[x,y]$ and $g\in k[x]$. In other words, the action is: multiply $f$ and $g$ and then replace every occurrence of $y$ by $x$.

Is $k[x]$ a projective $k[x,y]$-module? Consider first the map $k[x,y]\to k[x]$ given by $f\mapsto f(x,x)$. It’s easy to check that this map is in fact a $k[x,y]$-module homomorphism. It would be tempting to try and split this map with the inclusion map $k[x]\to k[x,y]$. But this doesn’t work: this inclusion is not a $k[x,y]$-module homomorphism.

In fact, the $k[x,y]$-module homomorphism $k[x,y]\to k[x]$ given by $f\mapsto f(x,x)$ cannot split simply because there are no nonzero $k[x,y]$-module homomorphisms $k[x]\to k[x,y]$. Therefore, $k[x]$ is not projective as a $k[x,y]$-module, using the module structure we gave it.

Here are two more ways to see this:

1. Through the notion of separability: by definition, $k[x]$ being a projective $k[x,y]\cong k[x]\otimes_k k[x]$-module under the structure that we have defined means that $k[x]$ is a separable $k$-algebra. However, all separable $k$-algebras are finite-dimensional as vector spaces over $k$, whereas $k[x]$ is infinite-dimensional.
2. Through Seshradi’s theorem: this theorem says that every finitely-generated projective module over $k[x,y]$ is actually free. Therefore, we just have to show that $k[x]$ is not free because $k[x]$ is certainly finitely-generated as a $k[x,y]$-module. But $(x^2y – xy^2)$ annihilates all elements of $k[x]$, which cannot happen in a free module.