# Replacing two idempotents with one

Posted by Jason Polak on 27. December 2017 · 2 comments · Categories: commutative-algebra · Tags:

Let $R$ be a commutative ring. Two idempotents $e$ and $f$ are called orthogonal if $ef = 0$. The archetypal example is $(0,1)$ and $(1,0)$ in a product ring $R\times S$.

Let $e$ and $f$ be orthogonal idempotents. Then the ideal $(e,f)$ is equal to the ideal $(e + f)$. To see, this first note that $(e + f)\subseteq (e,f)$. On the other hand:
$$(1-e)(e + f) = e + f – e – ef = f$$
Therefore $f \in (e + f)$. Switching $e$ and $f$ in this calculation shows that $e\in (e + f)$. Using the fact that $e + f$ is also an idempotent, we see that by induction, if $e_1,\dots,e_n$ are pairwise orthogonal idempotents, then the ideal $(e_1,\dots,e_n)$ is generated by the single element $e_1 + \dots e_n$.

Now suppose $e$ and $f$ are idempotents that are not necessarily orthogonal. Then $(e,f)$ is still a principal ideal. To see this, consider the element $e – ef$. The calculation
$$(e – ef)^2 = e – 2ef + ef = e – ef$$
shows that $e – ef$ is an idempotent. Furthermore, $(e,f) = (e – ef,f)$ and $e-ef$ and $f$ are orthogonal idempotents. By what we discussed in the previous paragraph, $(e,f) = (e-ef,f)$ is generated by $e – ef + f$.

Everything we did assumed $R$ was commutative. But what if we foray into the land of noncommutative rings? Is it still true that a left-ideal generated by finitely many idempotents is also generated by a single idempotent? Any ideas?

# Convergent or divergent?

Posted by Jason Polak on 24. December 2017 · Write a comment · Categories: analysis

Series hold endless fascination. To converge or not to converge? That is the question.

Let’s take the series $1 + 1/2 + 1/3 + \cdots$. It’s called the harmonic series, and it diverges. That’s because it is greater than the series
$$1 + 1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + \cdots = 1 + 1/2 + \cdots$$

The harmonic series diverges rather slowly, however. In fact, by comparing with the integral of $1/x$, we see that $1 + 1/2 + \cdots + 1/N$ can never be more than $\log(N) + 1$. For example, the sum of the first two hundred million terms is about 19.691044.

On the other hand, the sum of the reciprocals of the squares $1 + 1/4 + 1/9 + 1/16 + \cdots$ converges, which can be seen by comparing it to the integral of $1/x^2$ from one to infinity. In fact, $1 + 1/4 + 1/9 + \cdots = \pi^2/6$ as proved by Leonhard Euler. Here’s a question for you: does $\sum_{n=1}^\infty 1/n^s$ converge or diverge for $1 < s < 2$?

Even though the sum of reciprocals of squares converges, the sum of reciprocals of primes $1/2 + 1/3 + 1/5 + 1/7 + 1/11 + \cdots$ diverges. One could say by the convergence-divergence metric that the primes are more numerous than the squares. Also, in a similar vein to the harmonic series, the sum $1/2 + 1/3 + 1/5 + \cdots + 1/p – \log\log p$ is bounded.

Let’s go back to that harmonic series: $1 + 1/2 + 1/3 + 1/4 + \cdots$. Take this series, and delete every term whose denominator has the digit “9” somewhere in its decimal expansion. The resulting series converges! Can you prove it?

# Partitioning intervals in the real line

Posted by Jason Polak on 23. December 2017 · Write a comment · Categories: analysis · Tags: ,

Did you know that the closed interval $[0,1]$ cannot be partitioned into two sets $A$ and $B$ such that $B = A + t$ for some real number $t$? Of course, the half-open interval $[0,1)$ can so be partitioned: $A = [0,1/2)$ and $t = 1/2$. Why is this? I will leave the full details to the reader but I am sure they can be reconstructed without much difficulty using the following sketch:

Assume such a partition can be so made, and assume without loss of generality that $t \gt 0$. Then we must have $[0,t)\subseteq A$ and $(1-t,1]\subseteq B$. This shows that $t \lt 1/2$. Now, by assumption, $B = A + t$. Therefore, $[t,2t)\subseteq B$ since $[0,t)\subseteq A$ and similarly $(1-2t,1-t]\subseteq A$. Because $A$ and $B$ are disjoint, this implies that $t \lt 1/4$. We can continue to play this game, which shows that $t$ is strictly less than $1/(2n)$ for any $n$ and hence $t = 0$. This shows that such a partition cannot be made.

Pretty good. But did you know that the closed interval $[0,1]$ cannot be partitioned into two nonempty, disjoint open sets? Neither can any interval, whether open, closed, or half-open. In the language of topology, intervals of real numbers are connected. Proof?

# Number of irreducible polynomials over a finite field

Posted by Jason Polak on 20. December 2017 · Write a comment · Categories: commutative-algebra · Tags: ,

Over a finite field, there are of course only finitely many irreducible monic polynomials. But how do you count them? Let $q = p^n$ be a power of a prime and let $N_q(d)$ denote the number of monic irreducible polynomials of degree $d$ over $\F_q$. The key to finding $N_q(d)$ is the following fact: the product of all the monic, irreducible polynomials of degree $d$ with $d \mid n$ in the finite field $\mathbb{F}_q$ is the polynomial
$$x^{q^n} – x.$$
So let’s say $f_1,f_2,\dots, f_k$ are all the irreducible monic polynomials of degree $d$ with $d\mid n$. By taking degrees on both sides of the equation $x^{q^n} -x = f_1f_2\cdots f_k$, we get the formula
$$q^n = \sum_{d\mid n} dN_q(d).$$
Hey this is pretty good! For example, if $q = 2$ and $n = 3$ then the formula reads
$$8 = N_2(1) + 3N_2(3)$$
Now, $N_q(1)$ is always easy to figure out. All monic linear polynomials are irreducible so $N_q(1) = q$. Therefore, $N_2(3) = 2$. In fact, these two polynomials are: $x^3 + x + 1$ and $x^3 + x^2 + 1$. Okay, what about if $q = 3$ and $n = 6$? Then our formula tells us that
$$3^6 = N_3(1) + 2N_3(2) + 3N_3(3) + 6N_3(6).$$
So we now have to recursively compute: if we did that we would get that $N_3(1) = 1$, and this gives $2N_3(2) = 6$. Finally, $3N_3(3) = 24$. Therefore, we would calculate that $N_3(6) = 116$. It would not be too hard to write such a recursive algorithm and I encourage the reader to try it.
More »

# Three changes to mathematics I’d like to see

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 »

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

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 »