# Image factorisation in abelian categories

Let $R$ be a ring and $f:B\to C$ be a morphism of $R$-modules. The image of $f$ is of course
$${\rm im}(f) = \{ f(x) : x\in B \}.$$The image of $f$ is a submodule of $C$. It is pretty much self-evident that $f$ factors as
$$B\xrightarrow{e} {\rm im}(f)\xrightarrow{m} C$$where $e$ is a surjective homomorphism and $m$ is an injective homomorphism. In fact, there is nothing special about working in the category of $R$-modules at all. The same thing holds in the category of sets and a proof for the category of sets works perfectly well for the category of $R$-modules. This set-theoretic reasoning is very natural.

However, we can't always work with categories whose objects are sets with additional structure and whose morphisms are set functions that respect the additional structure (concrete categories). Sometimes we have to work with abelian categories. What's an abelian category? Briefly, it is a category $\Acl$ such that:
More »

# Art vs. science in mathematical discovery

Posted by Jason Polak on 31. July 2018 · Write a comment · Categories: math, opinion

Is mathematics science or art? Mathematics resembles science. In math, data and examples are collected and hypotheses made. There is a difference in the hypotheses of math versus science: in the former they can be proved, but that could be considered a small point. But I have met mathematicians who don't consider themselves scientists, and I think most mathematicians could probably understand this point of view. The underlying motivation of mathematics is often more artistic than scientific: that practitioners may seek out results they find elegant and beautiful, and not yield to justifications about understanding the world. However, mathematics sometimes struggles against its artistic roots and I have a feeling this is becoming a problem.

Science is beneficial to mathematics in numerous ways. But there is also a dangerous aspect to this relationship as well. If mathematics is too closely viewed as a science, it is treated as such in practical ways: how new results are supported, funded, and published. This danger is perhaps more relevant to pure mathematics, but it has serious implications for applied mathematics as well.
More »

# A little intro to the Jacobi symbol: Part 3

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

This is the final post on the Jacobi symbol. Recall that the Jacobi symbol $(m/n)$ for relatively prime integers $m$ and $n$ is defined to be the sign of the permutation $x\mapsto mx$ on the ring $\Z/n$. In the introductory post we saw this definition, some examples, and basic properties for calculation purposes.

In Part 2 we saw that for an odd prime $p$ and an integer $a$ that is relatively prime to $p$, the Jacobi symbol $(a/p) = 1$ if and only if $a$ is a square modulo $p$ (a "quadratic residue"). The basic properties of the Jacobi symbol then give the classic law of quadratic reciprocity.

Now, we're going to see one last application of the Jacobi symbol: primality testing in what's called the Solovay-Strassen primality test. How does it work? It starts with an observation we saw before: in the ring $\Z/p$, there exists a primitive element $g\in \Z/p$. It is an element that generates the multiplicative cyclic group $\Z/p^\times\cong \Z/(p-1)$.
More »

# A little intro to the Jacobi symbol: Part 2

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

In the last post, we examined the Jacobi symbol: for two relatively prime integers $m$ and $n$, we defined the Jacobi symbol $(m/n)$ to be the sign of the permutation $x\mapsto mx$ on the ring $\Z/n$.

It turns out that the Jacobi symbol plays a part in the theory of quadratic residues. For a number $n$, we say that an element $a\in \Z/n$ is a quadratic residue if it's a square in $\Z/n$.

When $n = p$ is a prime number, the question of which integers are quadratic residues goes back to the ancient days of Gauss. He realized that for an odd prime $p$, half the numbers in the list $1,2,\dots, p-1$ are quadratic residues, and the other half are not quadratic residues (a.k.a. quadratic nonresidues). Indeed, if $x^2 = y^2$ in the field $\Z/p$, then $(x+y)(x-y) = 0$. Therefore, if $x\not= y$, we must have $x=-y$. So it is clear that amongst the numbers $1^2,2^2,\dots,(p-1)^2$, there are exactly $(p-1)/2$ distinct numbers.

More »

# A little intro to the Jacobi symbol: Part 1

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

If $m$ and $n$ are relatively prime integers, the Jacobi symbol $(m/n)$ is defined as the sign of the permutation $x\mapsto mx$ on the set $\Z/n$. Let's give a simple example: $(7/5)$. The permutation on $\{1,2,3,4\}$ is given by $(1 2 4 3) = (1 2)(2 4)(4 3)$ which has an odd number of transpositions. Therefore, $(7/5) = -1$.

Note that as in this example, it is sufficient to compute the sign of the permutation on $\Z/n – \{0\}$, since multiplication always leaves zero fixed.

But what if we wanted to compute something like $(3/412871)$? These numbers aren't so big, so a computer could do it directly. However, there is a better way to do the computation of the Jacobi symbol $(m/n)$ if one of $m$ or $n$ is much larger than the other one. This method is good for computers too when one of the numbers is so large, that a direct computation even by a fast computer would be hopeless.
More »

# Poll: your favourite way to learn math

Posted by Jason Polak on 20. July 2018 · Write a comment · Categories: math · Tags: ,

What is your favourite way of learning math?

 Reading books Reading papers Classes or lectures Working out details with other people Vulcan mind meld

View Results

# Injective and p-injective

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.

# Sums of reciprocals of divisors, perfect numbers

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 »

# Ideal in a union of ideals

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.

# A Python 3 implementation of the MD5 Hash

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 »