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: deprecated: mathematics

Topic: Finite rigs of characteristic 0

Jean-Baptiste Vienney (Mar 15 2023 at 02:08):

Here is another puzzle on rigs. I don't know how to solve it or make a program to solve it but maybe some will be entertained to try.

Define the characteristic of a rig $R$ as the smallest integer $n \ge 1$ such that $n.1_{R}=0$ if there exists such a $n$ and $0$ if there doesn't exist such a $n$. The characteristic of a finite ring is always $>0$. But it is not the case for a finite rig. For instance $\mathbb{B}=\{0,1\}$ with $1+1=1$ is finite and of characteristic $0$, the only other rig of cardinal $2$ is $\mathbb{Z}_{2}$ and it is a ring so it is of characteristic $>0$ (it is $2$). The zero rig is also a ring of characteristic $> 0$ (it is $1$).

Question: Do we have a rig of cardinal $3$ of characteristic $0$? of cardinal $4$?... Can you list them?

Aaron David Fairbanks (Mar 15 2023 at 05:22):

Taking min and max as the addition and multiplication on $\{1, \ldots, n\}$ gives us an example for any $n$.

Jean-Baptiste Vienney (Mar 15 2023 at 05:41):

Excellent!

Jean-Baptiste Vienney (Mar 15 2023 at 05:43):

And it gives you $\mathbb{B}$ for $n=2$

Jean-Baptiste Vienney (Mar 15 2023 at 05:44):

Just a little thing: it doesn't work for $n=1$ since the zero ring is of characteristic $1$

Jean-Baptiste Vienney (Mar 15 2023 at 05:45):

But it's really funny examples

Tobias Fritz (Mar 15 2023 at 05:49):

You can also start with $\mathbb{N}$ and quotient it by the relation $3 = 4$. This gives $4 = 3 + 1 = 4 + 1 = 5$ etc, so all numbers $\ge 3$ are identified, while otherwise addition and multiplication work as usual. This is a finite semiring with four elements, and which has characteristic $0$ in your sense. Of course you can replace $3$ by any other number.

Jean-Baptiste Vienney (Mar 15 2023 at 05:53):

Hmm, that's interesting because it gives examples which are not additively idempotents (all of them are of characteristic $0$ except the zero ring) such as the ones of Aaron or more generally such that $1+1=1$ (which also works when $1 \neq 0$).

Jean-Baptiste Vienney (Mar 15 2023 at 05:59):

Thank you. I like your rigs.

Jean-Baptiste Vienney (Mar 15 2023 at 06:02):

So, maybe a challenge is to find one such that we don't have $n+1=n$ for all $n \ge N$ for some $N \ge 1$

Tobias Fritz (Mar 15 2023 at 06:31):

Jean-Baptiste Vienney said:

So, maybe a challenge is to find one such that we don't have $n+1=n$ for all $n \ge N$ for some $N \ge 1$

You can try to quotient e.g. by $3=5$. Then all even numbers $\ge 4$ are identified, and all odd numbers $\ge 3$ are identified, but $\{0,1,2,3,4\}$ are still distinct.

Jean-Baptiste Vienney (Mar 15 2023 at 07:35):

Thanks, finally now I wonder if not most the rigs are of characteristic $0$ in this sense, positive characteristic seems to be related to the abelian group structure of rings more than something about rigs and I guess that most rigs are not rings. So I would not be surprised that the proportion of rigs of cardinal less than $n$ which are of characteristic $0$ tends to $1$ when $n$ tends to $\infty$...

David Michael Roberts (Mar 15 2023 at 08:34):

Sounds like a good candidate for a pair of related OEIS entries: the number of rigs of size n, and the number of characteristic 0 rigs of size n.

Oscar Cunningham (Mar 15 2023 at 08:49):

Any rig has a canonical map from $\Bbb N$ that sends $n$ to $1+\dots+1$ ($n$ times). The image of this map is a quotient rig of $\Bbb N$. The possible quotients of $\Bbb N$ are all of the form 'quotient together $n$ and $n+p$ for all $n\geq N$' for some $p$ and $N$. I think it makes more sense to define the characteristic to be this $p$, rather than setting it to be $0$ whenever $N>0$.

In other words, take $0$ in your rig and start repeatedly adding $1$. If the values you get start to repeat then the characteristic is the period with which they repeat, and otherwise it's 0.

Oscar Cunningham (Mar 15 2023 at 08:51):

For example, this would make $\Bbb B$ have characteristic $1$ rather than $0$.

Jean-Baptiste Vienney (Mar 15 2023 at 17:29):

David Michael Roberts said:

Sounds like a good candidate for a pair of related OEIS entries: the number of rigs of size n, and the number of characteristic 0 rigs of size n.

That’s a good idea. We just need to find a good technique to compute these numbers. Finding the isomorphism classes of finite rigs with a brute force approach is very very quickly absolutely intractable. To see it, try to compute the number of possibilities for the operations and then the number of functions to check for potential isomorphisms. The first thing to do is to find isomorphism classes of finite commutative monoids for the little sizes. For rings, you can use all the classical stuff on groups to do that. But here, what to use? I don’t know such classical stuff for commutative monoids.

Jean-Baptiste Vienney (Mar 15 2023 at 17:43):

Oscar Cunningham said:

Any rig has a canonical map from $\Bbb N$ that sends $n$ to $1+\dots+1$ ($n$ times). The image of this map is a quotient rig of $\Bbb N$. The possible quotients of $\Bbb N$ are all of the form 'quotient together $n$ and $n+p$ for all $n\geq N$' for some $p$ and $N$. I think it makes more sense to define the characteristic to be this $p$, rather than setting it to be $0$ whenever $N>0$.

In other words, take $0$ in your rig and start repeatedly adding $1$. If the values you get start to repeat then the characteristic is the period with which they repeat, and otherwise it's 0.

That´s wonderful. It means that the positive characteristic phenomemon is not something restricted to rings and abelian groups, but also somewhat exists for rigs and commutative monoids. Now, I’m wondering if we can adapt some stuff to the situation without negatives. The abelian groups $\mathbb{Z}_{n}$ play a fundamental role when you have negatives, as you can see in the classification of finitely generated abelian groups and with the notion of order of an element in a group. Maybe could we define a kind of notion of order for an element of a monoid or maybe only for an element of a commutative monoid by using somewhat the rigs obtain from $\mathbb{N}$ by quotienting $n$ and $n+p$ for $n \ge N$ for some $N$ and $p$. Or maybe not. Maybe we could exercise by first choosing a notation for these rigs and compute the characteristic for a cartesian product of such rigs.

Morgan Rogers (he/him) (Mar 15 2023 at 18:11):

I have only just seen this, but I wish I had gotten here sooner: in my opinion the correct generalization of characteristic for rigs is the pair of numbers determining the subrig generated by 1, which is necessarily a quotient of $\N$. A nice indexing is for characteristic $(a,b)$ with $a\geq 1$ and $b\geq 0$ to denote $\{0,...,a+b-1\}$, with addition and multiplication reduced modulo $a$ into the range $\{b,...,a+b-1\}$. This is nice because it means that the existence of a rig homomorphism from a rig of characteristic $(a,b)$ to one of characteristic $(a',b')$ forces $a' | a$ and $b' \leq b$. We can extend this with characteristic $(1,\infty)$ for the case of the natural numbers embedding into the rig.

Morgan Rogers (he/him) (Mar 15 2023 at 18:14):

Note that this is not really consistent with the definition of characteristic 0 you gave earlier @Jean-Baptiste Vienney , but I don't think that definition gives you particularly detailed information about the rig.

Jean-Baptiste Vienney (Mar 15 2023 at 18:16):

Okay, no problem. It's a better definition.

Morgan Rogers (he/him) (Mar 15 2023 at 18:20):

(Not to criticize the puzzle, though, it's fun to figure out how rigs can differ from rings and building intuition about them)

Jean-Baptiste Vienney (Mar 15 2023 at 18:22):

No problem ahah. I'm interested by how you can find analogues of the $\mathbb{Z}_{n}$ without negatives. So, here are precise questions:

• First your $a,b$ are in $\mathbb{N} \cup \{\infty\}$, right?
• Can you define a simple rig which has characteristic $(a,b)$ for every $a,b$?
• Is the commutative monoid generated by an element of a commutative monoid of this form?

Morgan Rogers (he/him) (Mar 15 2023 at 18:30):

You need $0<a<\infty$; $b$ can take the extreme values but consider the infinite case separately. Consider the congruence on $\N$ generated by the relation $b \sim a+b$. This produces the rig I described above, so every characteristic is possible.

Notice that any congruence on $\N$ is principal, so adding the case $(0,\infty)$ gives all possibilities. Also note that this is true whether we consider $\N$ as a rig or as an additive monoid, which I think gives some indication of the answer to your third question.

Jean-Baptiste Vienney (Mar 15 2023 at 18:50):

I've just understood something by reading the nlab entry characteristic. If a rig has characteristic $\neq 0$ with my first definition, then $1_{R}$ is invertible in $(R,+,0)$ and so every element of the rig also and so it is a ring. So every rig which is not a ring verifies that $n.1_{R} \neq 0$ for every $n \ge 1$ and is of characteristic $0$ with this first definition. Now a ring can also be of characteristic $0$ so it doesn't separate rigs which are rings and those which are not.

David Michael Roberts (Mar 15 2023 at 20:52):

But restricting to finite rigs...?

Jean-Baptiste Vienney (Mar 15 2023 at 21:01):

Right! Finite rings are always of positive characteristic so yes, finite rigs which are not rings are exactly the ones of characteristic $0$ in this sense!

David Michael Roberts (Mar 16 2023 at 01:22):

I agree with @Morgan Rogers (he/him), but would tentatively go further and define the characteristic to be the sub-rig additively generated by 1, since it is uniquely determined up to isomorphism (if I haven't made a mistake) by the pair of numbers, much as the characteristic of a field is equivalent to knowing the prime field it contains, or similarly for the characteristic of a ring.

And we should have a nice notation for these rigs. For instance, a cumbersome and silly notation is $[0,b)+\mathbb{Z}/a$, and that doesn't quite capture the case of $\mathbb{N}$ ($[0,\infty)+\mathbb{Z}/1$??). But it indicates a little of what is going on. More streamlined yet opaque notations like $\mathbb{N}_{(a,b)}$ are of course possible.

David Michael Roberts (Mar 16 2023 at 01:24):

Morgan Rogers (he/him) said:

You need $0<a<\infty$; $b$ can take the extreme values but consider the infinite case separately. Consider the congruence on $\N$ generated by the relation $b \sim a+b$. This produces the rig I described above, so every characteristic is possible.

Notice that any congruence on $\N$ is principal, so adding the case $(0,\infty)$ gives all possibilities.

Should that last sentence have $(1,\infty)$, given the first sentence?

Jean-Baptiste Vienney (Mar 16 2023 at 03:33):

These rigs make me think to the Pollards's rho algorithm.

Jean-Baptiste Vienney (Mar 16 2023 at 03:35):

If you take any function $f:X \rightarrow X$ where $X$ is a finite set, then $f^{n}(x)$, $n \ge 1$ for any fixed $x \in X$ makes a rho like when you do $+1$ in these rigs.

Jean-Baptiste Vienney (Mar 16 2023 at 03:38):

I never understood well this algorithm but it makes the same rhos and works with numbers modulo $n$ so who knows.

Morgan Rogers (he/him) (Mar 16 2023 at 13:35):

David Michael Roberts said:

And we should have a nice notation for these rigs. For instance, a cumbersome and silly notation is $[0,b)+\mathbb{Z}/a$, and that doesn't quite capture the case of $\mathbb{N}$ ($[0,\infty)+\mathbb{Z}/1$??). But it indicates a little of what is going on. More streamlined yet opaque notations like $\mathbb{N}_{(a,b)}$ are of course possible.

I've mentioned in the topic on my work that I'm writing a paper on multiplicatively idempotent rigs (I've decided to call these mirigs), where I indeed introduce the notation $\N_{a,b}$ similar to what you suggest, since $\N_{2,2}$ is the free mirig on 0 generators (and I observe that $\N_{2,6}$ is the free rig on zero generators satisfying $x^3 = x$). It's coming soon, I'm in the process of computing the size of the free mirig on three generators so that I have a concrete original result to lay claim to. (In writing this I realise that I used the opposite convention on the ordering of the indices in my paper, though)