# Switching the order of summation

Posted by Jason Polak on 21. March 2017 · Write a comment · Categories: elementary, exposition

Characteristic functions have magical properties. For example, consider a double summation:
$$\sum_{k=1}^M\sum_{r=1}^k a_{r,k}.$$
How do you switch the order of summation here? A geometric way to think of this is arrange the terms out and “see” that this sum must be equal to
$$\sum_{r=1}^M\sum_{k=r}^M a_{r,k}.$$
I find this unsatisfactory because the whole point of good notation is that you shouldn’t have to think about what it actually means. I do think it’s very important to understand what the notation means, but in doing formal manipulations it’s nice not to have to do that all the time.

A superior proof that these two sums are equal would be to write
$$\sum_{k=1}^M\sum_{r=1}^k a_{r,k} = \sum_{k=1}^M\sum_{r=1}^M a_{r,k}\delta(r\leq k)$$
where $\delta(r\leq k)$ is the function of the variables $r$ and $k$ that equals one exactly when $r\leq k$ and zero otherwise. Then we can happily switch the order of summation to get
$$\sum_{r=1}^M\sum_{k=1}^M a_{r,k}\delta(r\leq k).$$
Now, it’s trivial to get rid of the $\delta(r\leq k)$ function by writing
$$\sum_{r=1}^M\sum_{k=r}^M a_{r,k}.$$

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

# Calculating Factorials in C

Posted by Jason Polak on 08. March 2017 · Write a comment · Categories: math

If $n \geq 0$ is an integer, define the number $n!$, pronounced “$n$ factorial”, as the number of bijections from an $n$-element set to itself. Therefore, $0! = 1$ and if $n > 0$ then
$$n! = 1\times \cdots\times n$$.
What’s the best way to calculate this quantity? The following “First Method” could possibly be the most straightforward method in the C language:

On other other hand, one might be tempted to reduce the number More »

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

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

I’d like to invite readers of this blog to download my latest paper, to appear in the Canadian Mathematical Bulletin:

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.

# Counting Bijective, Injective, and Surjective Functions

Posted by Jason Polak on 01. March 2017 · Write a comment · Categories: combinatorics

In this post we’ll give formulas for the number of bijective, injective, and surjective functions from one finite set to another. Although it’s not difficult, a formula for the number of surjective functions was one of the first problems I solved as an undergrad that got me interested in recurrence relations and combinatorics.

Let’s use the notation $[n] = \{ 1,2,\dots,n\}$ for an $n$-element set.
More »

# Top Words Appearing in arXiv Submissions

Posted by Jason Polak on 01. March 2017 · Write a comment · Categories: math

Number theory (NT) on the arXiv is a big section. In fact over the last two years, a little over 5700 papers have been posted there. Just for fun I wrote a Python program to help me find the most popular words in the titles and abstracts of the papers. Excluding common english words and common mathematical words such prove, function, and theorem, here are the top twenty keywords I found:

1. prime
2. group
3. integer
4. modular
5. rational
6. elliptic
8. series
9. polynomial
10. zeta
11. class
12. bound
13. galois
14. algebraic
15. abelian
16. representation
18. sequence
19. diophantine
20. linear

And how does this compare to algebraic geometry (AG), with almost the same number of papers posted?
More »

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

# A List of Commutative Algebra Books for Self Study

Posted by Jason Polak on 31. January 2017 · Write a comment · Categories: math

This post is a list of various books in commutative algebra (mostly called ‘Commutative Algebra’) with some comments. It is mainly geared towards students who might want to read about the subject on their own, though others might find it useful. It is not meant to be a comprehensive list, as it reflects the random process of my coming into contact with them.
More »

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

# Divisible By Arbitrary Powers? Not Noetherian

Posted by Jason Polak on 25. January 2017 · Write a comment · Categories: math

I’ve spent countless hours thinking about associative rings. Yet, during my research today I read a paper by C.U. Jensen [1] and came across this elementary fact that I never thought about: if $R$ is an integral domain and $x,y$ are nonunits with $y$ divisible by every positive power of $x$ then $R$ is not Noetherian. Perhaps I’ve used this unconsciously, but I had to take a second to prove it.

Here’s the proof: if $y = z_1x = z_2x^2 = \cdots$ then the ideal $(z_1,z_2,\cdots)$ cannot be finitely generated, because $z_n = r_1z_1 + \cdots + r_{n-1}z_{n-1}$ and $y = z_ix^i$ for all $i$ implies that $x$ is actually invertible.

This fact is curious, because it plays into constructing some nonstandard models of the integers as I learned from Jensen’s paper: If $\Ucl$ is a nonprincipal ultrafilter on the natural numbers $\N$, then the product $\Z^\N/\Ucl$ is one such nonstandard model: it satisfies precisely the same first-order sentences that $\Z$ does. Yet, it’s not Noetherian, because the element represented by $(2,4,8,16,32,64,…)$ is not a unit and divisible by every power of $2$.

In fact, not only is the ultraproduct $\Z^\N/\Ucl$ not Noetherian, it actually has global dimension two. So, neither Noetherian nor having global dimension one is expressible in first-order logic.

It’s amazing what basic facts you can still come across in this era. Perhaps someone should write the book 100 Quick Facts You Didn’t Know About Rings?!

[1] Jensen. Peano rings of arbitrary global dimension. Journal of the London Mathematical Society, 1980, 2, 39-44