Reducing to $\mathbb{Z}$ -- Permanence and Concrete Proofs

05 May 2021

There are lots of ways in which good notation can make results seem obvious. There are also lots of ways in which “illegally” manipulating expressions can give a meaningful answer at the end of the day. It turns out that in many cases our illegal manipulations are actually justified, and this is codified in the principle of Permanence of Identities! This is one place where category theory and model theory conspire in a particularly beautiful (and powerful) way.

In this post we’ll talk about how to prove statements in general rings by proving analogous statements for polynomials with integer coefficients. This is nice because we often have access to ~bonus tools~ when working in $\mathbb{Z}$, and it doesn’t matter if we use these bonus tools to prove the general result!

I think this technique is best shown by example, so I’ll give a smattering of proofs using this idea. Hopefully by the end you’ll be convinced of its flexibility ^_^.

---

Example – The Binomial Theorem

Let’s start simple, and build from here. In any of my favorite rings $R$ (though I should mention all my favorite rings are commutative with $1$) we can take any two elements $a$ and $b$ and know that

$$(a+b{)}^n=\sum _k(\genfrac{}{}{0ex}{}{n}{k})a^k{b}^{n-k}$$

where we (as usual) interpret scaling by an integer as repeated addition.

Many authors prove this by saying something like “the usual proof goes through unchanged”, but we can actually be a bit cleverer.

$⌜$ First we prove this identity in $\mathbb{Z}[a,b]$. Then we notice there is a (unique) ring hom $\phi :\mathbb{Z}[a,b]\to R$ for each choice of $a$ and $b$ in $R$. This is the category theory at work, since $\mathbb{Z}[a,b]$ is the free (commutative) ring on two generators. Next, we use model theory: Homomorphisms preserve truth, and so the true equation $p(a,b)=q(a,b)$ in $\mathbb{Z}[a,b]$ must stay true after we hit it with $\phi$!

So since we proved $(a+b{)}^n=\sum _k(\genfrac{}{}{0ex}{}{n}{k})a^k{b}^{n-k}$ in $\mathbb{Z}[a,b]$, we actually get for free that the equation holds for every pair of elements in every ring! $⌟$

Notice that it doesn’t matter what “the usual proof” is! Maybe you like to prove the binomial theorem by looking at the taylor series of $(1+x{)}^n$ and remembering $\mathbb{Z}\subseteq \mathbb{R}$. This method is entirely unavailable in a general ring, but because we end up with a polynomial equality, we can conclude that the theorem is true in general rings anyways!

There are lots of situations where we run this same kind of argument.

---

Example – Sylvester’s Identity

This one is a favorite example of Bill Dubuque on mse. I’ve seen him evangelize it so often I felt obligated to include it. It helps that it’s such a great example! He actually has a fantastic explanation of this same princple here, which I definitely recommend reading if you’re interested!

Sylvester’s identity says that (for $n\times n$ matrices over any ring $R$)

$$\text{det}(1+AB)=\text{det}(1+BA)$$

$⌜$ How can we prove this? Well, let’s work in $\mathbb{Z}[a_{ij},b_{ij}]$, where we have one variable for each of the $2n^2$ matrix entires. Now we have

$$\text{det}(1+AB)\text{det}(A)=\text{det}(A+ABA)=\text{det}(A)\text{det}(1+BA)$$

Since the determinant is a polynomial in the entries of a matrix¹, this is really expressing the equality of polynomials with integer coefficients!

So we have a polynomial equation $fh=hg$, and we can happily cancel the nonzero polynomial $h$ from both sides, since $\mathbb{Z}[a_{ij},b_{ij}]$ is a domain! Here $h$ is the polynomial $\text{det}(A)$, and we get the claim. $⌟$

Notice that we’ve, again, used a special property of integer polynomials in this proof! We can cancel polynomials with reckless abandon because we’re working in a domain. Once we prove this polynomial identity, though, the result remains true after we evaluate! In particular, even if the specific $\text{det}(A)$ of interest is $0$, or the particular $R$ of interest is not a domain!

Whatever tools we want to use inside $\mathbb{Z}[a_{ij},b_{ij}]$ is totally ok, as long as we end our proof with a polynomial identity.

---

Example – Computing Inverses

I said we would be focusing on commutative rings in this post, and that’s true. But there’s a really cool noncommutative example that follows the same principle and is worth showing. I learned about this on mse (where else?) in a different excellent post by Bill Dubuque.

$⌜$ We want to work in the ring of noncommutative polynoimals $\mathbb{Z}⟨a,b⟩$, but it’s not quite big enough. We’re making an assumption that $(1-ab{)}^{-1}$ exists, but it actually doesn’t in $\mathbb{Z}⟨a,b⟩$. That said, we can freely add such an inverse – let’s work in

$$R=\mathbb{Z}⟨a,b,c⟩/(1-ab)c=1=c(1-ab).$$

Now for the clever trick: we can embed this into the ring of noncommutative power series $\mathbb{Z}⟨⟨a,b⟩⟩$. We send $a\mapsto a$, $b\mapsto b$, and $c\mapsto (1-ab{)}^{-1}$.

In $\mathbb{Z}⟨⟨a,b⟩⟩$, we can run the following argument (which, of course, would be nonsensical in other settings):

$$\begin{array}{rl}(1-ba{)}^{-1}& =1+ba+(ba{)}^2+(ba{)}^3+\dots \\ & =1+ba+baba+bababa+\dots \\ & =1+b(1+ab+abab+\dots )a\\ & =1+b(1-ab{)}^{-1}a\end{array}$$

But this means in $\mathbb{Z}⟨⟨a,b⟩⟩$ we have the identity

$$(1-ba)(1+b(1-ab{)}^{-1}a)=1=(1+b(1-ab{)}^{-1}a)(1-ba)$$

which, under our embedding, gives us the following identity in $R$:

$$(1-ba)(1+bca)=1=(1+bca)(1-ba)$$

But then since this ring is initial among all noncommutative rings with $2$ free variables and an inverse for $(1-ab)$, we find the identity holds in every (noncommutative) ring $R$! $⌟$

Notice the extra power we got, both by using quotient rings to model some hypotheses in our theorem and by passing to formal power series. This is part of what’s so nice about embeddings! They let us prove statements in some smaller setting by using techniques from a bigger setting³. We’ve been implicitly using this idea throughout the post, but I wanted to make it explicit at least once. After all, once we’re aware of it, we can intentionally use it in other settings as well⁴.

---

A Sentimental Interlude – Seven Trees in One

The first paper I ever read⁵ opens with the following beautiful passage:

Consider the following absurd argument concerning planar, binary, rooted, unlabelled trees. Every such tree is either the trivial tree or consists of a pair of trees joined together at the root, so the set $T$ of trees is isomorphic to $1+T^2$. Pretend that $T$ is a complex number and solve the quadratic $T=1+T^2$ to find that $T$ is a primitive sixth root of unity and so $T^6=1$. Deduce that $T^6$ is a one-element set; realize immediately that this is wrong. Notice that $T^7\cong T$ is, however, not obviously wrong, and conclude that it is therefore right. In other words, conclude that there is a bijection $T^7\cong T$ built up out of copies of the original bijection $T\cong 1+T^2$: a tree is the same as seven trees. The point of this paper is to show that ‘nonsense proofs’ of this kind are, actually, valid.

You can see that we’ve “proven” a claim about trees by proving a polynomial implication in $\mathbb{C}$. That is, the authors show

$$T=1+T^2⟹T^7=T.$$

In the paper, the authors show that homomorphisms of certain polynomial implications are also preserved⁶ for rigs (that is, rings without negatives). Here $\mathbb{N}[T]$ plays the role of the initial rig, which embeds in $\mathbb{C}[T]$. Then we use complex analysis to show the above implication holds in $\mathbb{C}[T]$ and thus in $\mathbb{N}[T]$.

Since the objects of a category (up to isomorphism) with products and coproducts forms a rig, this tells us there is a hom from $\mathbb{N}[T]$ to the category of, say, algebraic datatypes (up to isomorphism).

Since this polynomial implication is of the variety that’s preserved, and in the category of datatypes we have $T\cong 1+T^2$, we are allowed to conclude $T\cong T^7$!

This follows the spirit of what we’re doing in this post, but is a bit more detailed because general homomorphisms don’t preserve all implications. A model theorist might jump straight to elementary embeddings, but that’s far too restrictive for our purposes here. The authors of the above paper do a great job finding (only slightly technical) conditions which make this argument go through. I’ve included it both to show what’s possible when you extend the ideas in this post, and also because it was my first paper and I feel a certain amount of love for it.

---

Example – Mutliplicative Determinants

Say we want to prove that $\text{det}(AB)=\text{det}(A)\text{det}(B)$. When we’re working over a field, there are slick basis-dependent arguments to show this. See, for instance, Knapp’s “Basic Algebra” (ch. II.7)⁷.

These arguments don’t go through for a general ring $R$, though, so you might think we should drink some caffeine, look up the definition of the determinant (for the second time this blog post… nobody really remembers it, right?), and just hit this problem with some honest computation.

Of course, once we remember $\mathbb{Z}\subseteq \mathbb{Q}$, we we might think of a better way (especially since we’ve seen the rest of the post).

$⌜$ We again look at $\mathbb{Z}[a_{ij},b_{ij}]$.

We first note that the entries of $AB$ are polynomials in the entries of $A$ and $B$ (if this isn’t clear, you should check it).

But since the determinant is a polynomial in the entries, we see the equation

$$\text{det}((a_{ij})(b_{ij}))=\text{det}((a_{ij}))\text{det}((b_{ij}))$$

is actually a polynomial equation (albeit a complicated one) in the $a_{ij}$ and $b_{ij}$. So it suffices to show that it’s true in our polynomial ring.

But $\mathbb{Z}[a_{ij},b_{ij}]\subseteq \mathbb{Q}(a_{ij},b_{ij})$, and we know the formula is true for matrices over a field! So the formula is true for us, and the claim follows for all rings. $⌟$

---

This is a fun and powerful technique, and it’s really useful in a lot of situations! Here are some quick exercises for you to play around with, but I encourage you to look for your own as well!

---

As one last aside, I’m really interested in figuring out when we can do this with power series. Over a year ago now I asked a question about this, though I accepted the answer too quickly (and in hindsight it isn’t really the kind of answer I was looking for).

With the extra year to think about it, though, I think I have a better idea how to make it work. I meant this to be a kind of prequel where we work in the simpler setting of polynomials to get practice before we jump into proving identities with power series.

---