Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: What "IS" a Base Representation?

John Onstead (Jan 09 2025 at 12:32):

I was recently thinking about new things I could apply the category theory lens to, and I realized it would be fun to use something that you learn at the end of your mathematical education journey (category theory and categorical algebra) to understand something from the very beginning- the addition, subtraction, multiplication, and division problems you work on in elementary school! Immediately, my first thought was that all that was happening in the ring of integers (we'll stick with talking about integers for now, before we add in any complexity from fractions or decimals). But there was an immediate problem with this thought- if we worked directly with these objects, their elements would all be represented by different symbols, and so addition and multiplication would all be completed in a single step. While that may seem to make things easier, it means a lot more memorization! That's when I realized that the multi-step process of solving an addition or multiplication problem was not inherent at all to the ring of integers- it was instead coming from our specific choice of representation of these elements, in terms of base 10! Which then got me thinking: what IS a base representation (a "positional number system") like base 10 in the category theory POV?

John Onstead (Jan 09 2025 at 12:35):

This is something I've thought about a lot for the past few days. My answers included vector spaces, via the analogy of how any number can be written as a sum of numbers times a power of ten, like how any vector is a sum of scalar products of basis vectors. This failed however as vector addition did not include any "carrying" operation. I also thought maybe it could be some sort of presentation of the ring of integers in terms of generators and relations, but I wasn't sure exactly how to get this to work. I also considered upgrading the vector space into some algebra based on the integers where one could interconvert between an integer (the scalars) and its base 10 representation (the "vectors"). A possibility I like is to take the set of digits from zero to nine and find the list monad on that, which is the set of strings of digits, and thus nicely encodes the positional nature of the positional number system. You might still have to do some quotient (for instance, the string 00045 is "the same as" 45). But the problem is that the list monad gives just a set, and of course the free monoid on the set of digits only has concatenation, not addition or multiplication, as its operation.

Anyways, I'm out of ideas. So I wanted to turn to you and ask you: what mathematical structure, from a foundational, axiomatic, structualist, category theoretic viewpoint, IS a base representation/positional number system? When someone is solving an addition problem in base 10, which precise mathematical structure are they actually working within, and what are the characteristics of the category of such mathematical structures (IE, is it monadic, etc.) It's really surprising to me that this doesn't seem to be something that is commonly thought about! Or maybe I'm just not looking in the right place/using the right internet keywords. Thanks!

Nathanael Arkor (Jan 09 2025 at 12:41):

I'm reminded of James Dolan's article Carrying Is a 2-Cocycle (see also [[carrying]]).

Mike Shulman (Jan 09 2025 at 16:32):

Exactly! A group-theoretic way to think about it is to consider the tower of quotient abelian groups

$$\cdots \to \mathbb{Z}/10^n \to \cdots \to \mathbb{Z}/1000 \to \mathbb{Z}/100 \to \mathbb{Z}/10 \to 0.$$

You can think about this as a sort of "Postnikov tower", where the fiber (= kernel) of each map is $\mathbb{Z}/10$. The quotient maps $\mathbb{Z} \to \mathbb{Z}/10^n$ commute with the projections, so any element of $\mathbb{Z}$ is uniquely determined by an element in each fiber, i.e. an infinite sequence of digits stretching off to the left. Each abelian group extension

$$0 \to \mathbb{Z}/10 \to \mathbb{Z}/10^{n+1} \to \mathbb{Z}/10^n \to 0$$

is determined by a "carrying" cocycle, and so addition of these infinite digit sequences is governed by putting together all of those cocycles, which gives you the standard addition-by-carrying algorithm.

Of course, the digit sequences arising from a nonnegative element of $\mathbb{Z}$ are eventually zero on the left. But you can use this recipe even for digit sequences that aren't eventually zero; this means talking about the limit group $\lim_n \mathbb{Z}/10^n$, which is known as the "10-adic integers" $\mathbb{Z}_{10}$. Negative elements of $\mathbb{Z}$ give you such infinite sequences, such as $\cdots 99999$ for $-1$, and you can check that adding $\cdots 99999$ to $1$ with the usual addition-by-carrying method gives you $\cdots 00000$. So another way to describe addition-by-carrying is to say that there's a group homomorphism $\mathbb{Z} \to \mathbb{Z}_{10}$ and you're working in its image.

Mike Shulman (Jan 09 2025 at 16:32):

I'm not as clear about how this works for multiplication. The groups $\mathbb{Z}/10^n$ are rings, and the quotients are ring homomorphisms, and this determines the multiplication on $\mathbb{Z}_{10}$ and the ring homomorphism $\mathbb{Z} \to \mathbb{Z}_{10}$, that's all fine. But I'm not sure how "ring cohomology" works to classify ring extensions, although the nLab has a stub [[ring extension]] with a few references.

Mike Shulman (Jan 09 2025 at 16:34):

A slightly icky fact is that $\mathbb{Z}_{10}$ contains zero-divisors, essentially because 10 is not prime. So people tend to put more attention on its analogues $\mathbb{Z}_p$ for primes $p$, which are integral domains and have fields of fractions $\mathbb{Q}_{p}$ called the $p$-adic numbers.

Mike Shulman (Jan 09 2025 at 16:49):

There is also a ring of 10-adic numbers $\mathbb{Q}_{10}$, which I believe you can think of as decimal expansions that are finite to the right of the decimal point and possibly infinite to the left. But it's not a field either, since it inherits the zero-divisors of $\mathbb{Z}_{10}$, although all ordinary integers are invertible in it.

John Onstead (Jan 09 2025 at 21:49):

Nathanael Arkor said:

I'm reminded of James Dolan's article Carrying Is a 2-Cocycle (see also [[carrying]]).

Wow that's very interesting! My favorite part of the article is when he says "I admit that some people claim to have mastered the art of adding two-digit numbers without any explicit introduction to the concept of 2-cocycle". It's a very mathematician kind of humor!

John Onstead (Jan 09 2025 at 21:59):

Mike Shulman said:

is determined by a "carrying" cocycle, and so addition of these infinite digit sequences is governed by putting together all of those cocycles, which gives you the standard addition-by-carrying algorithm.

I was certainly not expecting cocycles to appear, and I would never have come up with this on my own. But after looking at it a bit it does make sense!

Mike Shulman said:

which is known as the "10-adic integers"

It's very interesting to encounter the "adic integers" here, although in some way it is expected since as mentioned they can be thought of as infinite sequences of digits.

Mike Shulman said:

I'm not as clear about how this works for multiplication.

This is another good question, as the multiplication algorithm is more complex than that for addition. Generally it's a two step process- multiply a digit in the "bottom" number by all digits in the top number (and add a zero at the right for every position you move to the left on the lower number), and then add up all the results when that process is finished.

Madeleine Birchfield (Jan 10 2025 at 04:23):

John Onstead said:

This is another good question, as the multiplication algorithm is more complex than that for addition. Generally it's a two step process- multiply a digit in the "bottom" number by all digits in the top number (and add a zero at the right for every position you move to the left on the lower number), and then add up all the results when that process is finished.

Multiplication of $n$-adic integers is similar to multiplication of power series and convolution of sequences.

Mike Shulman (Jan 10 2025 at 05:20):

Right: the $n^{\rm th}$ digit times the $k^{\rm th}$ digits affects the value of the $(n+k)^{\rm th}$ and $(n+k+1)^{\rm st}$ digits. Which is why it's not clear to me how to represent this using cocycles attached to the ring extensions $\mathbb{Z}/p \to \mathbb{Z}/p^{n+1} \to \mathbb{Z}/p^{n}$., since those only know about the $n^{\rm th}$ and $(n+1)^{\rm st}$ digits.

Madeleine Birchfield (Jan 10 2025 at 13:38):

The other thing is that we have a sequence of modules

$$\mathbb{Z}_{n} \to n^{-1} \mathbb{Z}_{n} \to n^{-2} \mathbb{Z}_{n} \to n^{-3} \mathbb{Z}_{n} \to \ldots \to n^{-k} \mathbb{Z}_{n} \to \ldots$$

where $n^{-k} \mathbb{Z}_{n}$ is the module of $n$-adic rationals with $k$ digits to the right of the decimal point. The sequential colimit of this diagram is the module consisting of base $n$ digits extending infinitely out in both directions, with addition given by the usual 2-cocycle. However, this module is not a ring for the same reason why complex Laurent series do not form a ring, since there is no infinite sum function

$$\sum_{i = -\infty}^{\infty} (-)_i:(\mathbb{Z} \to \mathbb{Z} / n \mathbb{Z}) \to \mathbb{Z} / n \mathbb{Z}$$

for any positive $n \gt 1$ and thus no convolution on functions $\mathbb{Z} \to \mathbb{Z} / n \mathbb{Z}$.