An $R$-module $M$ is called injective if the functor $\Hom_R(-,M)$ is exact. The well-known Baer criterion states that an $R$-module $M$ is injective if and only if for every ideal $I$ of $R$, every map $I\to M$ can actually be extended to a map $R\to M$.

For example, $\Q$ is an injective $\Z$-module.

If every $R$-module is injective, then it turns out that every $R$-module is also projective. That's just because every $R$-module being projective or injective is just another way of saying that every short exact sequence of $R$-modules splits.

What about if we weaken the Baer criterion? Let's say that an $R$-module $M$ is called p-injective if the Baer criterion holds for principal ideals. That is, $M$ is p-injective if for every principal left ideal $I$ of $R$, every map $I\to M$ extends to a map $R\to M$.

Every injective $R$-module is also p-injective, but the converse is not true. Indeed: it was R. Yue Chi Ming that noticed that a ring $R$ has every module p-injective if and only if $R$ is von Neumann regular. I've talked about this rings before because they're cool.

Briefly, a ring $R$ is called von Neumann regular if for each $a\in R$ there exists an $x\in R$ such that $axa = a$. Let's suppose we have one of these von Neumann regular rings $R$. Let $M$ be an $R$-module. We claim it's p-injective. Indeed, suppose $g:Rb\to M$ is a map from a principal left ideal $Rb$ to $M$. Choose an $x\in R$ such that $bxb = b$. Such an $x$ exists by definition. Then $G:R\to M$ defined by $G(r) = rg(xb)$ is an extension of $g$. Therefore, $M$ is p-injective.

Therefore, every $R$-module is p-injective if $R$ is von Neumann regular. The converse is similar, and I'll leave it as an exercise.

Let's take an example: an infinite product of fields. Such a ring is easily verified to be von Neumann regular. Therefore, every module is p-injective. But such a ring is not semisimple, and therefore some of its modules are not injective.

Posted by Jason Polak on 08. July 2018 · Write a comment · Categories: number-theory · Tags:

A perfect number is a positive integer $n$ such that
$$\sum_{d|n} d = 2n.$$
Put another way, $n$ is the sum of its proper divisors. Check out a a quick intro to perfect numbers that I wrote last November. The first three perfect numbers are $6, 28,$ and $496$. Currently, the largest perfect number, corresponding to the largest Mersenne prime is
$$(2^{77232917} – 1)\cdot 2^{77232916}$$
This perfect number is over 46 million digits long!
More »

Posted by Jason Polak on 24. June 2018 · Write a comment · Categories: commutative-algebra · Tags:

Suppose $I$ is an ideal in a ring $R$ and $J,K$ are ideals such that $I\subseteq J\cup K$. Then either $I\subseteq J$ or $I\subseteq K$. Indeed, suppose that there is some $x\in I$ such that $x\not\in J$. If $y\in I$ is arbitrary and $y\not\in K$ then $x + y$ is in neither $J$ nor $K$. Thus, $y\in K$ and so $I\subseteq K$.

In other words, if there is some element of $I$ that is not in $J$, then $I$ is contained entirely in $K$.

A generalisation for commutative rings is as follows: if $J_1,J_2,\dots,J_n\subseteq R$ are ideals such that at most two of them are not prime ideals, and $I$ is an ideal such that $I\subseteq \cup_i J_i$ then $I\subseteq J_k$ for some $k$. Of course, one does not need the hypothesis that at most two of the $J_1,\dots,J_n$ are not prime if $I$ is principal.

If one drops the hypothesis that at most two of the ideals $J_1,\dots,J_n$ are not prime, then the conclusion no longer holds in general, though.

For example, consider the ring $R = \Z/2[x,y]/(x^2,y^2)$. It is a ring with sixteen elements. In $R$, the ideal $(x,y)$ has eight elements. Furthermore,
$$(x,y)\subseteq (x)\cup (y)\cup (x+y).$$
However, each of the ideals $(x), (y),$ and $(x+y)$—none of which are prime—only has four elements, and so $(x,y)$ is not contained in any of them.

Posted by Jason Polak on 19. June 2018 · Write a comment · Categories: computer-science · Tags: , ,

Today we'll see a Python 3 implementation of the MD5 hashing algorithm, which was originally designed by Ron Rivest. Even though the MD5 algorithm has been compromised and is not longer secure, it is still in use today. For example, CS ISOs of Linux distributions often provide MD5 sums in addition to SHA256 sums.

There are a lot of C implementations of MD5 out there. However, they are not easy to read, especially for someone who is not used to C. Python 3, being closer to "math" rather than the computer, reads more like a definition of the algorithm. Of course, the Python implementation is slower than the C one.

This Python implementation is ideal for experimenting with MD5 and learning about it. The code I give below is not the most compact possible, but I believe it is easy to understand.
More »

Posted by Jason Polak on 03. June 2018 · 2 comments · Categories: elementary · Tags:

The sum of squares of two integers can be an integer. For example, $3^2 + 4^2 = 25^2$. Those are also the legs of a right-angle triangle. This example is special in that the numbers $3$ and $4$ are consecutive integers!

Can you find a sum of squares of three consecutive integers that make a square?

No, it's not possible. If $n$ is any integer, then the sum
$$n^2 + (n+1)^2 + (n+2)^2 = 3n^2 + 6n + 5.$$
Now, modulo three, any number squared is either 0 or 1. But this polynomial always outputs integers that are 2 mod 3. Therefore, the sum of three consecutive integers cannot be a perfect square.

Exercise: prove that the sum of squares of four consecutive integers cannot be a perfect square.

Maybe, you might be inclined to think that 2 is somehow special, and that a sum of squares of $k$ consecutive integers cannot be a perfect square if $k \gt 2$. But then you would be surprised at this sum of squares of fifty consecutive integers:
$$7^2 + 8^2 + 9^2 + \cdots + 55^2 + 56^2 = 60025 = 245^2.$$
Cool, right? This is by no means the smallest example. Here is another example of 407 consecutive integers:

$$183^2 + 184^2 + \cdots + 589^2 = 8140^2.$$

But are there infinitely many such examples?

Posted by Jason Polak on 01. June 2018 · Write a comment · Categories: computer-science · Tags: ,

This is a continuation of the OpenMP tutorial. Last time we wrote the following program:

It gives a proof that the number $N = 770948605618065977$ is prime by testing all the possible factors up to the integer part of the square root of $N$. To recap, this program creates two threads and tests half the possible factors on one thread, and half the possible factors on another thread. Wouldn't it be nice to have the program split the loop work up automatically instead of having to do it manually?
More »

Posted by Jason Polak on 30. May 2018 · Write a comment · Categories: computer-science · Tags: , , , ,

Today, I'll give you a simple and practical example of using OpenMP with gcc. What's OpenMP? It's a C/C++/Fortran library for writing multithreaded applications. What's that? Most computers these days have multiple cores so that multiple tasks can be done in parallel. With multiple cores, you can edit pictures and listen to music at the same time without a noticeable slowdown. The intensive editing computations and music decoding happen on separate cores. It's a little more complicated than that, but that's the basic idea.

If your computer has multiple cores, it can use them in a single program. That's where OpenMP comes in. For concreteness, let's say you want to test whether the number 770948605618065977 is prime. If you're sane you'd just use the Miller-Rabin test like we've been discussing on this blog, and be happy with a 99.99999% probability that the number is prime. However, let's say you want to prove this number prime by trying all the numbers up to the integer part of its square root, which is 878036790.

Here is a minimal C program to do this:
More »

Posted by Jason Polak on 25. May 2018 · 1 comment · Categories: math · Tags:

I'm hoping readers can take the time to answer this important poll. I am trying to determine the current educational background of my readers so I can better target future posts of this blog with a sufficient amount of detail.

What is your highest current level of mathematical education?

View Results

Loading ... Loading ...
Posted by Jason Polak on 25. May 2018 · Write a comment · Categories: life · Tags:

Over the years I have tried many systems to keep math notes: paper notebooks, offline WordPress installation, LaTeX files in folders, and random papers that get left on my desk for too long. None of these were ideal for all purposes. Here are the main drawbacks of each system:

  1. Paper notebooks are actually good for learning things. For reading material like books or papers in detail, paper notebooks are the best system for keeping myself on-track of going through every detail, line by line. However, the linear fashion of notebooks makes them hard to consult for main ideas. Additionally, they take up significant space.
  2. My offline WordPress installation consists of WordPress installed on Apache running on my laptop. I found it pretty terrible for notes. The blog format is good for presenting self-contained ideas over time but not so good for consulting old notes because it is not built for organising systematic knowledge. Note however, that I still use my offline WordPress installation to test-drive posts for this blog before they go live.
  3. Using LaTeX is the obvious solution to writing mathematical notes. And for large works, like complete books or papers, it is the best. However, for a general mathematical notebook, a bunch of random LaTeX documents are not easy to organize or search.
  4. Using random loose sheets of paper works for taking notes to help me learn. In this case, writing is just a tool for learning and not for storing information. After I just recycle them.

However, I've finally found system for taking notes that works. More »

Posted by Jason Polak on 23. May 2018 · Write a comment · Categories: elementary · Tags: ,

Consider the following series:
\begin{align*}
a_1 &= \frac{4}{3}\\
a_2 &= \frac{4}{3}\frac{9}{8}\\
&\vdots\\
a_n &= \frac{4}{3}\frac{9}{8}\cdots\frac{(n+1)^2}{(n+1)^2-1}
\end{align*}
In other words, $a_n$ is the product of all the numbers of the form $n^2/(n^2 – 1)$ for $n=2,\dots, n+1$.

Does $\lim_{n\to\infty} a_n$ exist? More »