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

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

# Extensions of Finite Rings are Integral

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

Here's a classic definition: let $R\subseteq S$ be commutative rings. An element $s\in S$ is called integral over $R$ if $f(s)=0$ for some monic polynomial $f\in R[x]$. It's classic because appending the solutions of polynomials to base rings goes way back to the ancient pasttime of finding solutions to polynomial equations.

For example, consider $\Z\subseteq \Z[\sqrt{2}]$. Every element of $\Z[\sqrt{2}]$ is integral over $\Z$, which essentially comes down to the fact that $\sqrt{2}$ satisfies $x^2 – 2$. On the other hand, the only elements of $\Q$ integral over $\Z$ are the integers themselves.

The situation is much different for finite commutative rings. If $R\subseteq S$ are finite rings, then every element of $S$ is integral over $R$. Proof: suppose $s\in S$ and set $T = \{ f(s): f\in R[x]\}$. For each $t\in T$ fix a polynomial $f$ such that $f(s) = t$. The set of all such polynomials is finite so we can define $m$ as the maximum degree of all these polynomials. Then $s^{m+1}\in T$ and so there is an $f$ of degree at most $m$ such that $s^{m+1} – f(s) = 0$. Thus $s$ satisfies the monic polynomial $x^{m+1} – f(x)$. QED.

Cool right? However, this is just a more general case of the following theorem: let $R\subseteq S$ be commutative rings. Then $S$ is finitely generated as an $R$-module if and only if $S$ is finitely generated as an $R$-algebra and every element of $S$ is integral over $R$.

# Non-unique Factorisation: Part 2

Posted by Jason Polak on 15. April 2017 · Write a comment · Categories: commutative-algebra · Tags:

We are continuing the series on non-unique factorisation. For a handy table of contents, visit the Post Series directory.

In Part 1 of this series, we introduced for a commutative ring three types of relations:

1. Associaties: $a\sim b$ means that $(a) = (b)$
2. Strong associates: $a\approx b$ means that $a = ub$ for $u\in U(R)$
3. Very strong associates: $a\cong B$ means that $a\sim b$ and either $a = b=0$ or $a = rb$ implies that $r\in U(R)$

Here, $U(R)$ denotes the group of units of $R$. We have already seen in a ring with nontrivial idempotents like $\Z\times \Z$, a nontrivial idempotent $e$ will be satisfy $e\sim e$ and $e\approx e$, but $e\not\cong e$ because $e = ee$ and yet $e$ is not a unit and nonzero.

Therefore, $\cong$ is not an equivalence relation for all commutative rings. But it is symmetric:

Proof. Suppose $a\cong b$. Then $a\sim b$ and so $b\sim a$. If $a$ and $b$ are not both zero, write $a = sb, b = ta$. If $b = ra$ then $a = sra = s^2rb$. Since $a\cong b$, this implies that $s^2r$ is a unit and so $r$ is a unit. Hence $b\cong a$.

Guess what? The relation $\cong$ is also transitive. Since the proof is similarly short I'll leave the proof to the reader. So, $\cong$ is just missing being reflexive for all rings to be an equivalence relation for all rings. If $\cong$ is an equivalence relation for a ring $R$, then we say that $R$ is presimplifiable. We introduced this type of ring last time.
More »

# Non-unique Factorisation: Part 1

Posted by Jason Polak on 11. April 2017 · Write a comment · Categories: commutative-algebra · Tags:

If $F$ is a field then the polynomial ring $F[x]$ is a unique factorisation domain: that is, every nonunit can be written uniquely as a product of irreducible elements up to a unit multiple. So in $\Q[x]$ for example, you can be sure that the polynomial $x^2 – 2 = (x-2)(x+2)$ can't be factored any other way, and thus the only zeros of $x^2 – 2$ really are $\pm 2$.

If $F$ is not a field, then a polynomial might have a bunch of different factorisations. For example, in the ring $\Z/4[x]$ we can write $x^2 = (x)(x) = (x+2)(x+2)$. How can we make sense of factorisations in rings that are not unique factorisation domains? In order to do so, we first should make sure we understand what irreducible means in this context.

In the next several posts we'll look at non-unique factorisation more closely, following a paper of Anderson and Valdes-Leon [1], but keeping the posts self-contained. We'll start by looking at the concept of associates. One can in fact look at several different variations of associates. Here are three:
More »

# More about Ext Calculations with Regular Sequences

Posted by Jason Polak on 21. March 2017 · Write a comment · Categories: commutative-algebra · Tags:

This post is a continuation of this previous one, though I repeat the main definitions for convenience.

Let $R$ be a commutative ring and $A$ and $R$-module. We say that $x_1,\dots,x_n\in R$ is a regular sequence on $A$ if $(x_1,\dots,x_n)A\not = A$ and $x_i$ is not a zero divisor on $A/(x_1,\dots,x_{i-1})A$ for all $i$. Last time, we looked at the following theorem:

Theorem. Let $A$ and $B$ be $R$-modules and $x_1,\dots,x_n$ a regular sequence on $A$. If $(x_1,\dots,x_n)B = 0$ then
$${\rm Ext}_R^n(B,A) \cong {\rm Hom}_R(B,A/(x_1,\dots,x_n)A)$$

When $R$ is a Noetherian ring, $I$ a proper ideal of $R$, and $A$ a finitely-generated $R$-module, this theorem for $B = R/I$ says that the least integer $n$ such that ${\rm Ext}_R^n(R/I,A)\not= 0$ is exactly the length of a maximal regular sequence in $I$ on $A$.

The Noetherian and finitely generated hypotheses are crucial. Why is this? It's because you need to have control over zero divisors. In fact you can see this by looking at the case $n = 0$:

Theorem. Let $R$ be a Noetherian ring, $I$ a proper ideal of $R$, and $A$ a finitely-generated $R$-module. Then every element of $I$ is a zero divisor on $A$ if and only if ${\rm Hom}_R(R/I,A)\not= 0$.
Proof. Since $A$ is a finitely generated $R$-module, that every element of $I$ is a zero divisor on $A$ is equivalent to $I$ being contained in the annihilator of a single nonzero element $a\in A$, which is in turn equivalent to every element of $I$ being sent to zero under the homomorphism
$$R\to A\\ 1\mapsto a.$$
Such homomorphisms are the same as nonzero homomorphisms $R/I\to A$. QED.

Here we are using this crucial fact:

Cool Theorem. For a finitely generated module $A$ over a Noetherian ring $R$, the zero divisors $Z(A)$ of $A$ in $R$ are a union of prime ideals of $R$, each of which are ideals maximal with respect to the property of being in $Z(A)$. Furthermore, each such prime is the annihilator of a single nonzero element of $A$.

In general, primes that are equal to the annihilator of a single element of a module $M$ are called the associated primes of $M$, and of course the theory of associated primes and primary decomposition is much more vast than this simple 'Cool Theorem', as is evident from Eisenbud's 30-page treatment of them in his book Commutative Algebra. In practice however, I only ever seem to need this simple version of the 'Cool Theorem'.

# Paper Announcement: Separable Polynomials in Z/n[x]

Posted by Jason Polak on 05. March 2017 · Write a comment · Categories: commutative-algebra · Tags:

What is this paper about? It uses the theory of separable algebras to study separable polynomials in $\Z/n[x]$, which extends the usual definition of separability for polynomials over a field.

Let $d\geq 2$. A classical theorem of Leonard Carlitz says that for a prime $p$ with $q=p^k$, the number of monic separable polynomials of degree $d$ in $\F_q[x]$ is $q^d – q^{d-1}$. One can also define separable for polynomials in $\Z/n[x]$. In this case, since a polynomial cannot always be converted to a monic one by multiplying by a unit, it makes more sense count all separable polynomials. Deriving a formula for this number is exactly what my paper does.

Read the paper to see how it's done! Although it talks about separable algebras, you can actually read it without knowing anything about this more advanced stuff as the interface between separable algebra theory and the concrete combinatorics is pretty clean. Or, you can just look at the final answer: the number of separable polynomials in $\Z/n[x]$ of degree at most $d$ for $d\geq 1$ is given by
$$\phi(n)n^d\prod_{i=1}^m(1 + p_i^d)$$
where $n = p_1^{k_1}\cdots p_m^{k_m}$ is the prime factorization of $n$ and $\phi(n) = |(\Z/n)^\times|$ is Euler's phi function. The formulas in the paper have been checked mutliple times with Sage.

# Regular Sequences and Ext Calculations

Posted by Jason Polak on 22. February 2017 · Write a comment · Categories: commutative-algebra, homological-algebra · Tags:

Let $R$ be a commutative ring and $A$ and $R$-module. We say that $x_1,\dots,x_n\in R$ is a regular sequence on $A$ if $(x_1,\dots,x_n)A\not = A$ and $x_i$ is not a zero divisor on $A/(x_1,\dots,x_{i-1})A$ for all $i$. Regular sequences are a central theme in commutative algebra. Here's a particularly interesting theorem about them that allows you to figure out a whole bunch of Ext-groups:

Theorem. Let $A$ and $B$ be $R$-modules and $x_1,\dots,x_n$ a regular sequence on $A$. If $(x_1,\dots,x_n)B = 0$ then
$${\rm Ext}_R^n(B,A) \cong {\rm Hom}_R(B,A/(x_1,\dots,x_n)A)$$

This theorem tells us we can calculate the Ext-group ${\rm Ext}_R^n(B,A)$ simply by finding a regular sequence of length $n$, and calculating a group of homomorphisms. We get two cool things out of this theorem: first, a corollary of this theorem is that any two maximal regular sequences on $A$ have the same length if they are both contained in some ideal $I$ such that $IA\not= A$, and second, it enapsulates a whole range of Ext-calculations in an easy package.

For example, let's say we wanted to calculate ${\rm Ext}_\Z^1(\Z/2,\Z)$. Well, $2\in\Z$ is a regular sequence, and so the above theorem tells us that this Ext-group is just ${\rm Hom}_\Z(\Z/2,\Z/2) \cong\Z/2$.

Another example: is ${\rm Ext}_{\Z[x]}^1(\Z,\Z[x])\cong\Z$.

Of course, the above theorem is really just a special case of a Koszul complex calculation. However, it can be derived without constructing the Koszul complex in general, and so offers an instructive and minimalist way of seeing that for Noetherian rings and finitely generated modules, the notion of length of a maximal regular sequence is well-defined.

# An Abelian Group of Endoprojective Dimension One

Posted by Jason Polak on 25. January 2017 · Write a comment · Categories: commutative-algebra, homological-algebra

We already saw that an abelian group with a $\Z$-direct summand is projective over its endomorphism ring. Finitely generated abelian groups are also projective over their endomorphism rings by essentially the same argument. What's an example of an abelian group that is not projective over its endomorphism ring?

Here's one: the multiplicative group $Z(p^\infty)$ of all $p$-power roots of unity. Another way to define this group is $\Z[p^{-1}]/\Z$. What is the endomorphism ring of this group? In fact it is the $p$-adic integers $\Z_p$. Indeed, an endomorphism $Z(p^\infty)\to\Z(p^\infty)$ has to send $1/p$ to an element $a_1$ such that $pa_1 = 0$. So we have the choice of the elements $0/p, 1/p,\cdots, (p-1)/p$, which form the cyclic subgroup $\Z/p$.

Similarly, $1/p^2$ has to be sent to an element $a_2$ such that $p^2a_2 = 0$, but also $pa_2 = a_1$. So $a_2$ has to be of the form $n/p^2$ where $n\in \Z$; in other words, $a_2$ can be in the cyclic subgroup $\Z/p^2$ generated by $1/p^2$. Hence, an endomorphism of $Z(p^\infty)$ is specified by an element of the inverse system $\cdots\to \Z/p^3\to \Z/p^2\to \Z/p$ where the transition maps are multiplication by $p$: in other words the $p$-adic integers $\Z_p$.

Now, we see that $Z(p^\infty)$ cannot be a projective $\Z_p$-module. Indeed, $\Z_p$ is a local ring and hence any projective $\Z_p$-module is in fact free (Kaplansky's theorem) and in particular torsionfree. However, $Z(p^\infty)$ has nothing but torsion! In fact we can say more: since $\Z_p$ is a principal ideal domain, it has global dimension one, so the projective dimension of $Z(p^\infty)$ as a $\Z_p$-module is one.

# An abelian group projective over its endomorphism ring

Posted by Jason Polak on 16. January 2017 · Write a comment · Categories: commutative-algebra · Tags:

An abelian group $A$ is a left $E = {\rm End}(A)$-module via $f*a = f(a)$. If $B$ is a direct summand of $A$ as an abelian group, then ${\rm Hom}(B,A)$ is also a left $E$-module and is in fact a direct summand of $E$ as an $E$-module, so it is $E$-projective. In particular, if $B = \Z$, then ${\rm Hom}(B,A)\cong A$ as $E$-modules. Thus $A$ is a projective $E$-module whenever $A$ has $\Z$ as a direct-summand.

These observations allow us to construct projective modules that often aren't free over interesting rings. Take the abelian group $A = \Z\oplus \Z$ for instance. Its endomorphism ring $E$ is the ring $M_2(\Z)$ of $2\times 2$ matrices with coefficients in $\Z$. As we have remarked, $\Z\oplus \Z$ must be projective as an $M_2(\Z)$-module.

Is $\Z\oplus\Z$ free as an $M_2(\Z)$-module? On the surface, it seems not to be, but of course we need proof. And here it is: for each element of $\Z\oplus \Z$, there exists an element of $M_2(\Z)$ annihilating it. Such a thing can't happen for free modules.

One might wonder, is every $M_2(\Z)$-module projective? Or in other words, is $M_2(\Z)$ semisimple? Let's hope not! But $M_2(\Z)$ is thankfully not semisimple: $\Z/2\oplus\Z/2$ is a $M_2(\Z)$-module that is not projective: any nonzero element of $M_2(\Z)$ spans a submodule of infinite order, and therefore so must any nonzero element of a nonzero projective.