← Notes on Rieg Theory
Older Versions__2023_07_23Ver__CharacteristicOfRieg.tex
\section{Characteristic and Modulo arithmetic}\label{SectionCharacteristics}
\memo{The most non-trival theorem in this section is a known result}
\subsection{Chracteristics}
Recall that a characteristic of a ring is a minimum positive integer $n$ such that
\[0=\underbrace{1+1+\dots +1}_{n \text{ times}},\]
if such $n$ exists, and otherwise $0$.
We will define similar notion to riegs. However, the exactly same definition does not work, since if we have a positive integer $n$ such that $0=n$, then $n-1$ is the additive inverse of $1$ and the rieg should be isomorphic to the trivial rieg (Proposition \ref{PropositionMinusOne}).
We adopt a relaxed definition:
\begin{definition}[Characteristic]
For a rieg $R$, its characteristic $\ch R$ is a minimum pair \memo{Clarify the meaning of \dq{minimum.} But I think there is no room for confusion...?} $(a,b)$ of non-negative integer $a$ and a positive integer $b$ such that
\[
\underbrace{1+\dots +1}_{a \text{ times}}=
\underbrace{1+\dots +1}_{a \text{ times}}+
\underbrace{1+\dots +1}_{b \text{ times}}.
\]
If there does not exists such a pair, the characteristic is defined to be $\chz$.
\end{definition}
\begin{example}[Trivial rieg]
The characteristic of the trivial rieg is $(0,1)$. Conversely, if the characteristic of a rieg $R$ is $(0,1)$, then $0=1$ and $R$ turns out to be trivial.
More generally, if the characteristic of $R$ is $(0,b)$, then we have $0=1+\dots+1$ and $b-1 =-1$. Then we can conclude that $R$ is trivial and $b=1$. No rieg has characteristic $(0,b)$ for $b\geq2$.
\end{example}
\begin{example}[Overflow riegs]
\memo{later!}
\end{example}
\begin{example}[Parity riegs]
\memo{later!}
\end{example}
After reading the definition and examples, you may ask two questions: \dq{Is this definiton natural?} and \dq{Which pair $(a,b)$ can be realized as a characteristic of a rieg?} In the remaining part of this subsection, we will focus on the first question. The second question is the main topic of the next subsection.\memo{This turned out to be a known result.}
\subsubsection*{Is this definiton natural?}
From an abstract point of view, this defnition is quite natural. In fact, we can \dq{deduce} this definition from a general setting. For an arbitrary equational theory $T$, we can define a notion of \dq{characteristic} of $T$-algebra as follows. Recall that the category of $T$-algebras admits the (surjection, injection) factorization system, or (regular epi, mono) factorization in terms of category theory. \memo{reference}
% and the initial object $I$.
Therefore, for each $T$-model $A$, we can canonically associate a quotient $Q$ of the initial $T$-algebra $I$ obtained by factorizing the unique homomorphism
\[I\twoheadrightarrow Q \rightarrowtail A.\]
In the case of rings, the associated quotient is $\Z /n\Z$, where $n$ is the characteristic of the given ring $A$. So this abstract definition is a generalization of the notion of characteristics. \memo{I don't claim that this is the most natural gereralization.}
In the case of pointed groups, which are groups with a distingished element, the characteristic of a pointed group $(G,g)$ is $\Z /n \Z$, where $n$ is the order of the element $g\in G$. In the case of pointed $\Q$-algebras, the characteristics of the pointed $\Q$-algebra $(\overline{\Q},\alpha)$ is $\Q[x]/(f(x))$, where $f(x)$ is the minimum polynomial of $\alpha$.
Then, how about the case of riegs? The initail rieg is the rieg of natural numbers.
\begin{proposition}
The rieg of natural numbers $\N$ is the initial object in the category of riegs.
\end{proposition}
Therefore, what we need to do is classify the quoteits of $\N$.
The starting point is the classification of quotients of the additive monoid $\N$.
% By the classification of quotients of the additive monoid $(\N,0,+)$,
It is known that all non-trivial congruence $\sim$ on $(\N,0,+)$ is of the form
\[n \sim m \iff (n=m)\lor ((n,m\geq a) \land (n\equiv m \mod{b})) \]
% \[n \sim m \iff (n\equiv m \mod{b})\land ((n=m)\lor (n,m\geq a)) \]
with $a\geq0$ and $b>0$. \memo{reference} Let $\Mr{a}{b}$ denote the quotient additive monoid. It is quicker to look at the picture of $\Mr{3}{4}$ than to look at the logical symbols (Figure \ref{PictureModuleRieg}).
\begin{figure}
\begin{shaded}
\centering
\begin{tikzpicture} [scale = 2]
\fill[black] (0,2) circle (0.06) node[above]{};
\fill[black] (1,2) circle (0.06) node[above]{};
\fill[black] (2,2) circle (0.06) node[above]{};
\fill[black] (3,2) circle (0.06) node[above]{};
\fill[black] (4-0.36,1+0.36) circle (0.06) node[above]{};
\fill[black] (3,0+0.36+0.36) circle (0.06) node[above]{};
\fill[black] (2+0.36,1+0.36) circle (0.06) node[above]{};
\draw[black, thick](3,1+0.36) circle (0.64);
\draw[black, thick] (0,2) -- (3,2);
\end{tikzpicture}
\caption{Picture of $\Mr{3}{4}$}
\label{PictureModuleRieg}
\end{shaded}
\end{figure}
For example, (the underlying additive monoid of) the trivial rieg is $\Mr{0}{1}$, the truth value rieg $\2$ is $\Mr{1}{1}$, and the parity rieg is $\Mr{1}{2}$. \memo{Overflow riegs}
\begin{proposition}
For any $a\geq 0$ and $b>0$, $\Mr{a}{b}$ admits the unique rig structure such that the canonical surjection $\N \twoheadrightarrow \Mr{a}{b}$ is a rig homomorphism.
The rieg structure on the rig $\Mr{a}{b}$ is unique, if it exists.
Every quotient of $\N$ is $\N$ itself or otherwise of the form of $\Mr{a}{b}$ for some $a\geq 0$ and $b>0$.
\end{proposition}\memo{Modify this later..}
\begin{proof}
\end{proof}
With those proof, we can rephrase the definition of the characteristics.
% \begin{proposition}
% For a rieg $R$ with characteristic $\ch R =(a,b)$, the unique rieg homomorphism $\N \to R$ is factored as
% \[\N\twoheadrightarrow \Mr{a}{b} \rightarrowtail R.\]
% The characteristic of $R$ is $0$ if and only if $\N \to R$ is injetive.
% \end{proposition}
\begin{proposition}[Chraracteristic, in terms of the quotients of $\N$]
For a rieg $R$ and the (surjection, injection) factorization of the unique morphism $\N \to \R$,
\[\N\twoheadrightarrow Q \rightarrowtail R,\]
\begin{itemize}
\item $Q\cong \Mr{a}{b} \iff \ch R = (a,b)$
\item $Q \cong \N \iff \ch R = \chz.$
\end{itemize}
\end{proposition}
% \memo{Uniqueness of rieg structure on $\Mr{a}{b}$, if it exists.}
\subsubsection*{Which pair $(a,b)$ can be realized as a characteristic of a rieg?}
\memo{For semirings, every value can be realized.}
% \begin{remark}[Is this definition natural?]
% \end{remark}
% For example, a rieg $R$ with characteristic $\ch R= (0,1)$ is a rieg with $0=1$, which is the trivial rieg.
\subsection{Classification of the quotients of $\N$}
\memo{On the terminology \dq{modulo riegs}}
Before we get into the theoretical considerations, let us list a few examples.
\begin{example}[$\N$ itself]
$\N$ itself is a trivial modulo rieg.
\end{example}
\begin{example}[Trivial rieg]
A singleton $\{\ast\}$ has a unique rieg structure. We call it \emph{trivial rieg}. It is the terminal rieg and can be regarded as a modulo rieg by the unique homomorphism $\N \to \{\ast\}$.
\end{example}
\begin{example}[Truth value rieg]
As we will see later, the set of truth values $\2 = \{\bot, \top\}$ has a natural rieg structure, as $(\2, \bot, \top, \lor, \land, \leftarrow)$.
% \begin{itemize}
% \item $0$ is the $\bot$
% \item $1$ is $\top$
% \item $x+y$ is $x \lor y$
% \item $xy$ is $x\land y$
% \item $x^y$ is $y \to x$
% \end{itemize}
The proposition
\[\text{IsPositive}\colon \N \twoheadrightarrow \2\]
is a surjection and defines a modulo rieg.
% The set $\{\text{zero},\text{positive}\}$ and the natural surjection $\N \to \{\text{zero},\text{positive}\}$ induces a rieg structure on $\{\text{zero},\text{positive}\}$.
% For several reasons, we call this rieg $\2$.
\end{example}
\begin{example}[Parity rieg]
As a bit more non-trivial example, the natural surjection
\[\N \twoheadrightarrow \{0, \text{positive odd}, \text{positive even} \}\]
induces a modulo rieg. We call it the \emph{parity rieg}.
\end{example}
Before stating the classification theorem, we introduce two terminologies.
\begin{definition}[Tame number]
A positive integer $n$ is said to be \emph{tame} if, for any prime factor $p$ of $n$, $p-1$ also divides $n$.
\end{definition}
The list of tame numbers begins as:
\[1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 32, 36, 40, 42, 48, 54, 60, 64, 72, 80, 84, 96, 100, 108, \dots.\]
Notice that there are infinitely many tame numbers since $2^k$ is tame.
The reason for considering tame numbers is the following algebraic paraphrase.
Simply put, \dq{$n$ is tame if and only if exponentials are also well-defined by $\mod{n}$.}
\begin{lemma}[Algebraic characterization of tame numbers]\label{LemmaAlgebraicCharacterizationOfTameNumbers}
For a positive integer $n$, the following conditions are equivalent:
\begin{enumerate}
\item $n$ is tame.
\item for any $x \in (\Z/n\Z)^{\times}$, $x^n \equiv 1 \mod{n}.$
\end{enumerate}
\end{lemma}
\begin{proof}
First, we will prove (2), assuming (1).
Let $n={p_1}^{k_1}\dots {p_l}^{k_l}$ be the prime factorization of $n$.
Then we have a group isomorphism
\[
(\Z/n\Z)^{\times} \cong (\Z/ {p_1}^{k_1} \Z)^{\times}\times \dots \times (\Z/ {p_l}^{k_l} \Z)^{\times}.
\]
Therefore, it is enough to prove that, for any $1\leq i \leq l$ and $x \in (\Z/ {p_i}^{k_i} \Z)^{\times}$, $x^n \equiv 1 \mod{{p_i}^{k_i}}$. But this immediately follows from tameness of $n$, since $\# (\Z/ {p_i}^{k_i} \Z)^{\times} = (p-1)p^{k_i -1}$, which divide $n$.
Conversely, we will prove (1) from (2). Let $p$ be an odd prime factor of $n$. (The case where $p=2$ is obvious.) The multiplicative group $(\Z/n\Z)^{\times}$ has a element $x$ whose order is $p-1$, because $(\Z/ {p}^{k} \Z)^{\times}$ is cyclic. \footnote{This is not obvious by definition, but well-known.} By the assumption $x^n \equiv 1 \mod n$, we have $p-1 \mid n$.
% \[(\Z/ p^{k_l} \Z)^{\times} \simeq \Z/(p-1)p^{}\]
\end{proof}
\begin{remark}[Carmichael numbers]
This is reminiscent of Carmichael numbers, which are defined as a positive integer $n$ that satisfies
\begin{itemize}
\item for any $x \in (\Z/n\Z)^{\times}$, $x^{n-1} \equiv 1 \mod{n}.$
\end{itemize}
Although the definitions are very similar, the only tame Carmichael numbers are obviously only trivial ones, namely $1$ and $2$. In light of these facts, rather than the boring name \dq{tame numbers,} perhaps we should call them anti-Carmichael numbers (?)
\end{remark}
\begin{definition}[Dimention]
A \emph{dimension} of a positive integer $n$ is the maximum value of the exponent that appears in the prime factorization of $n$. It is denoted by $\di(n)$.
\end{definition}
For example, the dimentions of small numbers are $\di(1)=0, \di(2)=1, \di(3)=1, \di(4)=2, \di(5) = 1, \di(6)=1, \di(7)=1, \di(8)=3$.
\begin{remark}[Radical]\label{RemarkRadical}
A dimension is inextricably linked to the notion of \emph{radicals} of positive integers.
\memo{ABC conjecture} Recall that the radical of a positive integer $n$, often denoted by $\rad(n)$, is a positive integer obtained by replacing all exponents in the prime factorization of $n$ by $1$. For example, $\rad(5400)=\rad(2^3\cdot 3^3\cdot 5^2)=2\cdot 3\cdot 5 = 30$.
The dimension $\dim(n)$ is the minimum $d$ such that $n$ divide $\rad(n)^d$, and conversely $\rad(n)$ is the maximum $1$-dimensional divisor of $n$.
\end{remark}
\begin{theorem}[Classification of modulo riegs \cite{burris1993tarski}]\label{TheoremPossibleChar}
For $a\geq 0$ and $b>0$, $\Mr{a}{b}$ has a rieg structure if and only if $b$ is a tame number whose dimension is at most $a$.
% \begin{enumerate}
% \item $a\geq \di(b)$
% \item $b$ is tame.
% \end{enumerate}
\end{theorem}
\begin{proof}
Assuming $\Mr{a}{b}$ has a rieg structure, we will prove $b$ is a tame number whose dimension is at most $a$. Let $[x] \in \Mr{a}{b}$ denote the equivalence class that contains $x\in \N$. For an arbitrary natural number $x$ that is coprime with $b$, we have
\[
[x^{a+b}]=[x]^{[a+b]}=[x]^{[a]}=[x^{a}],
\]
hence \[x^{a+b} \equiv x^{a} \mod{b},\] and \[x^b \equiv 1 \mod{b}.\] By Lemma \ref{LemmaAlgebraicCharacterizationOfTameNumbers}, $b$ is tame. Next, we move on to the dimension of $b$. For any non-negative integer $m\geq 0$, we have
\[[\rad(b) ^a]=[\rad(b)]^{[a]}=[\rad(b)]^{[a+mb]}=[\rad(b)^{a+mb}],\]
and \[\rad(b) ^a\equiv \rad(b) ^{a+mb} \mod{b}.\]
By taking a sufficiently large $m$ such that $a+mb\geq \dim(b)$, we obtain \[\rad(b) ^a\equiv 0 \mod{b},\] equivalently, $a\geq \dim(b)$.
Conversely, assuming that $b$ is a tame number whose dimension is at most $a$, we will prove the rig $\Mr{a}{b}$ has a rieg structure. It is enough to prove that $\ex$ is well-defined.\footnote{Here, we implicitly use the fact of universal algebra: if an equivalence relation is compatible with all operations, then its quotient set has the unique (same type of) algebraic structure such that the canonical surjection is homomorphic.} If $a=0$, then $b=1$, and this case is trivial. In the rest of the proof, we assume $a>0$.
We begin with the easier case: assuming $[x_0]=[x_1]$, we will prove $[{x_0} ^{y}]=[{x_1}^{y}]$. If $x_0 = x_1$ or $y=0$, this is trivial. Suppose $x_0 < x_1$ and $y>0$. Since $x_0 \neq x_1$, we have $a\leq x_0,x_1$ and ${x_0} \equiv {x_1} \mod{b}$. Since $y>0$, we have $a\leq x_0,\leq {x_0}^y\leq {x_1}^{y}$. As a result, we obtian $a\leq {x_0}^y, {x_1}^{y}$ and ${x_0}^y \equiv {x_1}^{y}\mod{b}$, which mean $[{x_0} ^{y}]=[{x_1}^{y}]$.
Lastly, assuming $[y_0]=[y_1]$, we will prove $[x ^{y_0}]=[x^{y_1}]$. If $y_0=y_1$, this is trivial. Therefore, we can assume $0<a\leq y_0, y_1$ and $y_0\equiv y_1 \mod{b}$. Since the cases where $x=0,1$ are trivial, \footnote{For $x=0$ case, we used $0< y_0,y_1$.} we can also assume $x\geq 2$. Under those assumptions, because we have $a\leq y_0 \leq x^{y_0}$ and $a\leq y_1 \leq x^{y_1}$, it is enough to prove
\[x^{y_0}\equiv x^{y_1} \mod{b}.\]
Take an arbitrary prime factor $p$ of $b$ and let $k$ be the number of times that $p$ divides $b$. We prove
\[x^{y_0}\equiv x^{y_1} \mod{p^k}.\]
If $p$ divides $x$, both sides of the equation are equal to zero, because \[k\leq \dim(b) \leq a \leq y_0,y_1.\]
If $x$ is coprime with $p$, it follows from tameness of $b$ and $\# (\Z/p^k \Z)^{\times} = (p-1)p^{k-1}$.
The proof is complete.
\end{proof}
As a result, we obtain the complete (infinite) list of modulo riegs (Figure \ref{PictureListOfModuloRiegs}).
\begin{figure}
\centering
\begin{shaded}
\begin{align*}
a=0 &:\ \Mr{0}{1}\\
a=1 &:\ \Mr{1}{1},\Mr{1}{2},\Mr{1}{6},\Mr{1}{42},\Mr{1}{1806}\\
a=2 &:\ \Mr{2}{1},\Mr{2}{2},\Mr{2}{4},\Mr{2}{6},\Mr{2}{12},\Mr{2}{18},\Mr{2}{20},\Mr{2}{36},\Mr{2}{42},\Mr{2}{60},\Mr{2}{84},\dots \\
a=3 &:\ \Mr{3}{1},\Mr{3}{2},\Mr{3}{4},\Mr{3}{6},\Mr{3}{8},\Mr{3}{12},\Mr{3}{18},\Mr{3}{20},\Mr{3}{24},\Mr{3}{36},\Mr{3}{40}, \dots \\
a=4 &:\ \Mr{4}{1},\Mr{4}{2},\Mr{4}{4},\Mr{4}{6},\Mr{4}{8},\Mr{4}{12},\Mr{4}{16},\Mr{4}{18},\Mr{4}{20},\Mr{4}{24},\Mr{4}{36}, \dots \\
\vdots&\\
\dq{a=\infty}&:\ \N
\end{align*}
\caption{The complete list of modulo riegs}
\label{PictureListOfModuloRiegs}
\end{shaded}
\end{figure}
As promised, this classification theorem implies non-trivial properties about general riegs. The following corollary is particularly impressive.
% As a corollary of the classification theorem, we obtain the following proposition:
\begin{corollary}[Classification of characteristics, case $a=1$ \cite{burris1993tarski}]\label{CorollaryClassificationOfCharacteristics}
For a rieg $R$, if there exists the minimum positive integer $n$ such that
\[1=1+\underbrace{1+\dots +1}_{n},\]
then there are only five possible values of $n$, $n=1,2,6,42,1806$.
\end{corollary}\memo{I thought this might be a new result.}
\begin{proof}
This is equivalent to saying that $1,2,6,42,1806$ are the only tame numbers of dimension at most $1$. If $n$ is a $1$-dimensional tame number and $p$ is the maximum prime factor, then $n/p$ is also a ($0$ or $1$-dimensional) tame number and $p-1$ is a divisor of $n/p$. Therefore, we can inductively generate all $1$-dimensional tame numbers. By concrete calculations, we can check that the inductive procedure stops when $n=1806$.
The concrete calculation is conducted as follows:
Start with $n=1$. Adding $1$ to the divisor of $n=1$ and checking if it is prime, we find prime $1+1=2$ and newly obtain $n=1*2=2$.
Again, adding $1$ to the divisors of (newly obtained) $n=2$ and checking if they are prime, we find two prime numbers $2$ and $3$. Thus we obtain a new number $n=2*3=6$.
We repeat this procedure.
Adding $1$ to the divisors of $n=6$ and checking if they are prime, we find prime numbers $2, 3$, and $7$ and obtain $n=6*7=42$.
Again, adding $1$ to the divisors of $n=42$ and checking if they are prime, we find primes $2, 3, 7$, and $43$ and newly obtain $n=42*43=1806$. Adding $1$ to the divisors of $n=1806$ and checking if they are prime, we find only the already found primes $2,3,7,43$. (For example, $86+1=3\cdot 29$, $301+1=2\cdot 151$, and $1806+1 = 13\cdot 139$.) Thus this procedure is over, and all possible $n$ are $1,2,6,42,1806$.
\end{proof}
\memo{Sylvester's sequence}
\begin{conjecture}
There are infinitely many 2-dimensional tame numbers.
\end{conjecture}
\cite{OEISsyl}\cite{burris1993tarski}
By a computer calculation, we know there is a $2$-dimensional tame number bigger than $10^{10000}$.
\memo{In the case of $1$-dimensional tame numbers, there are only $4$ different prime number appear, $p=2,3,7,43$. By computer calculation, we observed that at least $1000$ prime numbers appear in $2$-dimensional tame numbers.}
\begin{example}
For any non-negative integer $n$, $1$ is a tame number whose dimension is $n$. Thus we obtain a rieg $\Mr{n}{1}$, which is isomorphic to the overflow rieg. \memo{ref, 2-adic and n=3 case}
\end{example}
\begin{example}
For any non-negative integer $n$, $2^n$ is a tame number whose dimension is $n$. Thus we obtain a rieg $\Mr{n}{2^n}$. \memo{ref}
\end{example}
\begin{example}
How about $10^n$? For $n=1$, $10$ is not a tame number. That means we cannot do modular arithmetic only with
% $\mod{10}$, i.e.,
the last digits. For example, $3^3=7 \mod 10$ but $3^{13}=3 \mod 10$.
% For example, $3^3=27 \equiv 7 \mod 10$ but $3^{13}=1594323\equiv 3$)
However, for $n\geq 2$, $10^n$ is a tame number whose dimension is $n$. Thus we obtain a rieg $\Mr{n}{10^n}$. Later, we utilize those riegs to define a profinite riegs. \memo{ref}
\end{example}
\begin{example}
For any non-negative integer $n$, its factorial $n!$ is tame. Furthermore, its dimension is at most $n$. It is because, for any prime number $p$, the number that $p$ divides $n!$ is given by Legendre's formula
\[
\sum_{k=1}^{\infty} \left\lfloor {\frac{n}{p^k}}\right\rfloor
\]
and is bounded from above by $n$ as follows:
\[
\sum_{k=1}^{\infty} \left\lfloor {\frac{n}{p^k}}\right\rfloor
\leq
\sum_{k=1}^{\infty} \frac{n}{p^k}
=\frac{n}{p-1}
\leq n.
\]
Therefore, we obtain a rieg $\Mr{n}{n!}$. \memo{ref}
\end{example}
% However, not all $\Mr{a}{b}$ has a rieg structure. The obvious restriction is
% \begin{itemize}
% \item $a=0 \implies b=1$,
% \end{itemize} and for something a bit more non-trivial,
% \begin{itemize}
% % \item the order of elements of $(\Z/b\Z)^{\times}$ must be divisors of $b$.
% \item if a prime number $p$ divides $b$, then $p-1$ must divide $b$.
% \end{itemize}
% As we will see later, for $a=1$, there are exactly five possible $b$, namely $1,2,6,42,1806$.
% \subsection{Characteristics of riegs}
% \begin{definition}
% The \emph{characteristic} of a rieg is \memo{write}
% \end{definition}
% \memo{Solve some Diophantus equation utilizing those riegs}
% \begin{definition}\label{DefinitionOrderCharacteristics}
% \end{definition}
% \section{Relation to other algebraic structures}
\subsection{Application: riegs of three elements}
$n=1,2$: Unique
\memo{Utilize characteristics theory}
% \subsection{profinite constructions and topological rieg}\label{SubsectionProfinite}
% \memo{Interpret LTE lemma}
% \memo{We can do analysis, using topology. For example, something like an infinite tower of exponential}
% \memo{Are there infinitely many solutions for $x^x =x$ in $\Mr{\infty}{10^{\infty}}$?}
% % (related question: how about in $\Mr{\infty}{p^{\infty}}$)? This does not even exist!}
% % \newpage
% % \input{2023_07_23Ver/riegsOfPropositions0729}