\documentclass{amsart} \usepackage[left=2cm, right=2cm]{geometry} \usepackage[utf8]{inputenc} \usepackage{amsfonts, amsthm, amssymb, mathtools,etoolbox} \usepackage{blindtext} \usepackage[colorlinks=true, urlcolor=blue, linkcolor=blue, citecolor=blue]{hyperref} \usepackage{tikz,tikz-cd} \usepackage{cleveref} \usepackage{xcolor} \usepackage{array} \usepackage{enumitem} \usepackage[style=alphabetic,sorting=nyt, maxnames=4]{biblatex} % \usepackage[style=authoryear, maxnames=4]{biblatex} \renewbibmacro{in:}{} % \addbibresource{biblio.bib} \addbibresource{CommonBiblio20240922.bib} \tikzset{pullback/.style={minimum size=1.2ex,path picture={ \draw[opacity=1,black,-,#1] (-0.5ex,-0.5ex) -- (0.5ex,-0.5ex) -- (0.5ex,0.5ex);% }}} \usetikzlibrary{calc} \usepackage{framed} \tikzset{pullback/.style={minimum size=1.2ex,path picture={ \draw[opacity=1,black,-,#1] (-0.5ex,-0.5ex) -- (0.5ex,-0.5ex) -- (0.5ex,0.5ex);% }}} \usepackage{pgfplots} \pgfplotsset{compat=1.18} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[subsection] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{todo}[theorem]{Todo} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{fact}[theorem]{Fact} \newtheorem{claim}{Claim}[theorem] \crefname{claim}{Claim}{Claims} \renewcommand{\theclaim}{\thetheorem.\alph{claim}} \newtheorem{question}[theorem]{Question} \newtheorem{problem}[theorem]{Problem} \newtheorem*{answer}{Answer} \theoremstyle{definition} \newtheorem{example}[theorem]{Example} \newtheorem{definition}[theorem]{Definition} \newtheorem{remark}[theorem]{Remark} \newtheorem{notation}[theorem]{Notation} \newtheorem{puzzle}[theorem]{Puzzle} \newtheorem{idea}[theorem]{Idea} \newtheorem{exercise}[theorem]{Exercise} \newcommand{\dq}[1]{``#1"} \newcommand{\memo}[1]{\textcolor{red}{memo: #1}} % \newcommand{\invmemo}[1]{\textcolor{blue}{memo: #1}} \newcommand{\invmemo}[1]{} \newcommand{\horamemo}[1]{\textcolor{green!70!black}{hora: #1}} \newcommand{\para}[1]{\paragraph{\textbf{#1}}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathcal{C}} \newcommand{\D}{\mathcal{D}} \newcommand{\E}{\mathcal{E}} \newcommand{\F}{\mathbf{F}} \newcommand{\G}{\mathcal{G}} \renewcommand{\L}{\mathcal{L}} \newcommand{\id}{\mathrm{id}} \newcommand{\op}{\mathrm{op}} \newcommand{\ob}{\mathrm{ob}} \newcommand{\Set}{\mathbf{Set}} \newcommand{\sSet}{\mathbf{sSet}} \newcommand{\FinSet}{\mathbf{FinSet}} \newcommand{\PSh}{\mathbf{PSh}} \newcommand{\Sh}{\mathbf{Sh}} \newcommand{\Cont}{\mathbf{Cont}} \newcommand{\Func}[2]{[#1,#2]} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\demph}[1]{\textit{#1}} \font\maljapanese=dmjhira at 2.5ex \newcommand{\yo}{\textrm{\!\maljapanese\char"48}} \newcommand{\Pow}{\mathcal{P}} \newcommand{\Aut}{\mathrm{Aut}} \newcommand{\Po}[1]{\mathcal{P}(#1)} \newcommand{\Top}{\mathrm{Top}} \newcommand{\HeyAlg}{\mathrm{HeyAlg}} \newcommand{\Rieg}{\mathbf{Riegs}} \newcommand{\Ring}{\mathbf{Rings}} \newcommand{\Rig}{\mathbf{Rigs}} \newcommand{\ti}{\times} \newcommand{\ex}{\uparrow} \newcommand{\co}{\mathrm{c}} \newcommand{\2}{\mathbf{2}} \newcommand{\1}{\mathbf{1}} \newcommand{\mult}[1]{\mathrm{mult}(#1)} \newcommand{\mN}{\mult{\N}} \renewcommand{\H}{H} \newcommand{\rad}{\mathrm{rad}} \newcommand{\Mr}[2]{\N_{#1,#2}} \newcommand{\End}{\mathrm{End}} \newcommand{\Groupoid}{\mathrm{Groupoid}} \newcommand{\Groupoidfin}{\Groupoid_{\mathrm{fin}}} \newcommand{\TB}{\star} \newcommand{\ep}{\varepsilon} \newcommand{\loga}{log-able} \newcommand{\ch}{\mathrm{char}} \newcommand{\TV}{\Omega} \newcommand{\chz}{(\infty, 0)} % \newcommand{\RigCh}{\mathbb{T}\mathrm{ame}} \newcommand{\N}{\mathbb{N}} \newcommand{\Nd}{\N^{\mathrm{div}}} % \newcommand{\Nd}{\N^*} % \newcommand{\Ndp}{\Nd_{>}} % \newcommand{\Ndp}{\N^*} \newcommand{\Np}{\N^*} \newcommand{\Ch}{\mathfrak{C}} % \newcommand{\RigfCh}{\N \times \Np} % \newcommand{\RigCh}{\overline{\N\times \Np}} % \newcommand{\RiegCh}{\mathbb{C}\mathrm{har}} \newcommand{\RigCh}{\Ch_{\mathrm{rig}}} \newcommand{\RigfCh}{{\RigCh^*}} \newcommand{\RiegCh}{\Ch_{\mathrm{rieg}}} \newcommand{\RiegfCh}{{\RiegCh^*}} % \newcommand{\RiegfCh}{\mathrm{f}\mathbb{C}\mathrm{har}} % \newcommand{\RigCh}{\overline{\N\times \Np}} % \newcommand{\chz}{(\infty, 0)} \newcommand{\K}[1]{#1 / \hspace{-1pt} \scalebox{0.7}{$\cong$}} \newcommand{\biK}[1]{#1 / \hspace{-1pt} \scalebox{0.7}{$\simeq$}} \newcommand{\lcm}{\mathrm{lcm}} \newcommand{\pro}[1]{\widehat{#1}} \newcommand{\proN}{\pro{\mathbb{N}}} \newcommand{\proZ}{\pro{\mathbb{Z}}} \newcommand\binuparrow{\mathbin{\uparrow}} \newcommand{\powow}{\binuparrow \binuparrow} \newcommand{\Image}{\mathrm{Im}} \newcommand{\OF}{\mathrm{OverFlow}} \newcommand{\T}{\mathbb{T}} \newcommand{\TAlg}{\mathrm{Alg}_{\T}} \newcommand{\finTAlg}{\mathrm{finAlg}_{\T}} \newcommand{\TTAlg}{\Top\TAlg} % \newcommand{\TTAlg}{\mathrm{Top}\T\text{-}\mathrm{Alg}} \newcommand{\Quo}{\mathrm{Q}} \newcommand{\fQuo}{\Quo_{\mathrm{fin}}} \renewcommand{\j}{\mathfrak{j}} \newcommand{\p}{\mathfrak{p}} \newcommand{\B}{\mathbf{B}} \newcommand{\BN}{\B\N} \newcommand{\BZ}{\B\Z} \title[Rieg theory]{Notes on Rieg theory: semiring with exponentials in logic, profinite arithmetic, enumerative combinatorics, and category theory} \author{Ryuya Hora} \address{Graduate School of Mathematical Sciences, University of Tokyo, Tokyo, Japan} \email{hora@ms.u-tokyo} \date{\today} \subjclass[2020]{} \keywords{h} \begin{document} \definecolor{shadecolor}{gray}{0.9} \begin{abstract} In this paper, we introduce the notion of a \textit{rieg}, that is, a semiring equipped with a binary operation called exponentiation, and present its basic theory along with numerous examples. We begin by reviewing the classification of quotient riegs over $\mathbb{N}$ given by Burris and Lee. Then, through concrete examples, we propose how riegs can appear in (pro)finite arithmetic, category theory, enumerative combinatorics, and logic. Typical examples of a rieg include the rieg of natural numbers $\N$, quotient riegs of $\mathbb{N}$, the profinite completion $\N \rightarrowtail\mathbb{N} \cup \widehat{\mathbb{Z}}$, the cardinal arithmetic, the rieg of truth values $\{\bot, \top\}$, heyting algebras, the rieg of finite directed graphs, the Burnside rieg of a finite group, the rieg of rooted trees, the rieg of isomorphism classes of finite groups, and decategorified topoi. \end{abstract} \maketitle \tableofcontents \section{Introduction} The aim of the present paper is to popularise an algebraic structure, which we will call \demph{riegs}, by providing several theorems and examples. As a \demph{rig} defined as a \dq{ring without negatives} (\cite{schanuel1990negative}) a \demph{rieg} is a \dq{rig with exponentials.} In other words, a rieg is a ring-like structure that has $0,1,+,\ti,$ and a binary operation $\ex$ (\Cref{def:rieg}). The prototypical example of a rieg is the rieg of natural numbers. Of course, the idea of considering ring-like structures with exponentials is not new. In the context of algebras, \memo{write about rings with unary exponentials} In the context of objective number theory, \memo{write} In the context of ($p$-adic) dynaical systems, \memo{write} In the context of category theory, \cite{birkhoff1942generalized} \begin{quote}\cite{schanuel2000objective} Objective number theory is the study of addition and multiplication (and eventually exponentiation) of objects in suitable categories. \end{quote} Fiore \cite{fiore2006remarks} To the best of the author’s knowledge, the field in which rigs with (binary) exponentiation have been most actively studied is (finite) model theory. The Tarski High School problem concerns the theory of the positive integers with addition, multiplication, and exponentiation. Even after this problem was resolved, research on small models continued to progress. The story until 2005 is summarized in \cite{burris2005saga}. In the context of (finite) model theory, \memo{write} \para{Acknowledgement} The author would like to thank his supervisor Ryu Hasegawa for helpful discussions and suggestions. He was supported by JSPS KAKENHI Grant Number JP24KJ0837 and FoPM, WINGS Program, the University of Tokyo. \para{Survey} \begin{itemize} \item[1942] One can see the idea of an algebra of structures, with exponential in \cite{birkhoff1942generalized}. \item[1980] Wilkie gives a solution to Tarski's high school algebra problem \cite{wilkie1980exponentiation}. \item[1992] \cite{burris1992small} (and its summary \cite{burris1993tarski}) give what we call \demph{the Burris-Lee theorem} \item[2000] Schanuel publishes papers on objective number theory \cite{schanuel2000objective}\cite{schanuel2000transcendencein} \item[2005] The survey paper \cite{burris2005saga} was published. \item[2006] Fiore, Cosmo, and Balat give a type-theoretic view on this structure, with $0$ \cite{fiore2006remarks}. \end{itemize} \begin{notation}\label{not:notationsOfNaturalNumberRelatedSystems} We adopt the following notations: \begin{itemize} \item $\N$ denotes the set of all non-negative integers. Sometimes, we regard it as a poset with the natural ordering. \item $\Np$ denotes the set of all positive integers. We may regard it as a poset with the divisibility order. \item $\RigfCh$ denotes the product poset of $\N$ and $\Np$. \end{itemize} \end{notation} \section{Riegs}\label{sec:riegs} \subsection{Preliminaries: rigs}\label{ssec:rigs} Since our theory of riegs is based on the theory of rigs ($=$ semirings), we start by recalling the notion of rigs. (The word `rig' means `ring without negatives.' \cite{schanuel1990negative}) \begin{definition}[Rig]\label{def:rigs} A (possibly non-commutative) \demph{rig} is a set $R$ equipped with \begin{itemize} \item two constants ($=$ nullary operations) $0,1 \in R$ and \item two binary operations, $+, \ti \colon R \times R \to R$ \end{itemize} that satisfies % \footnote{some of which might be redundant.} \begin{enumerate} \item $0+x=x$, % \item $x+0=x$, \item $(x+y)+z=x+(y+z)$, \item $x+y=y+x$, \item $1\ti x =x$, \item $x\ti 1 =x$, \item $(x\ti y)\ti z=x\ti (y\ti z)$, % \item $x\ti y=y\ti x$, \item $x\ti 0=0$, \item $x\ti (y+z)=(x\ti y) + (x\ti z)$, \item $0\ti x=0$, and \item $(x+y)\ti z=(x\ti z)+(y\ti z)$. \end{enumerate} If $R$ satisfies an additional equation \begin{enumerate}[resume] \item $x\ti y = y\ti x$, \end{enumerate} we call it a \demph{commutative rig}. A \demph{rig homomorphism} is a function that preserves the four operations $0,1,+,\ti$. The category of rigs and rig homomorphisms is denoted by $\Rig$. \end{definition} For the sake of simplicity, we may write $xy$ for $x\ti y$. % Of course, every ring is a rig. \begin{example}[Rig of natural numbers]\label{exmp:RigOfNaturalNumbers} The rig of natural numbers (with the usual addition and multiplication) $\N$ is the initial object of the category $\Rig$. \end{example} % \begin{example}[Rings]\label{exmp:RingsAreRigs} % Of course, every ring is a rig. However, we will see that % \end{example} \begin{example}[Rig of endohomomorphisms on a commutative monoid]\label{exmp:EndRig} For a commutative monoid $(A, e, \ast)$, the set of monoid endohomorphisms $\End{(A, e, \ast)}$ admits a (typically non-commutative) rig structure as follows: \begin{itemize} \item The element $0 \in \End{(A, e, \ast)}$ is the constant function to the neutral element $A \to A\colon a \mapsto e$. \item The element $1 \in \End{(A, e, \ast)}$ is the identity function $\id_A\colon A \to A$. \item The sum $f+g$ of two elements $f,g\in \End{(A, e, \ast)}$ is given by $(f+g)(a) \coloneqq f(a) + g(a)$. \item The product $f\ti g$ of two elements $f,g\in \End{(A, e, \ast)}$ is given by the composite $f\circ g$. \end{itemize} % This rig is typically non-commutative. \end{example} % \begin{example} % The free rig generated by one element $x$ is the rig of polynomials with natural number coefficients $\N[x]$. % \end{example} % In what follows, we will write $xy$ for $$ \subsection{Definition}\label{ssec:definitionOfRiegs} This subsection aims to introduce the notion of riegs. Although it is possible to define riegs by numerous equations (\Cref{prop:EquationalDefinition}), we adopt another definition, which is much more memorable. Note that $\End{(R, 1,\ti)}$ in the definition below is the rig explained in \Cref{exmp:EndRig} obtained from the multiplicative commutative monoid $(R, 1,\ti)$. % We define the notion of `rieg', which is intended to be a rig with \textbf{e}xponentials, to be a commutative rig with a module structure on itself. \begin{definition}[Rieg]\label{def:rieg} A \demph{rieg} is a commutative rig $(R, 0, 1, +, \ti )$ equipped with a rig homomorphism $R \to \End{(R, 1,\ti)}$. \end{definition} Let us unpack the definition of a rieg. The rig homomorphism $R \to \End(R, 1, \ti)$ sends an element $x\in R$ to a (commutative) monoid homomorphism, for which we will write \[ {-}^x \colon (R, 1, \ti) \to (R, 1, \ti). \] The condition that this is a monoid homomorphism is equivalent to the usual equations \begin{itemize} \item $1^x=1$, and \item $(yz)^x = y^x z^x$. \end{itemize} For $R \to \End(R, 1, \ti)$ to be a rig homomorphism, it must preserve $0$, $1$, $+$, and $\ti$, each of which corresponds to an equation listed in \Cref{table:riegequations}. \begin{table}[ht] \centering \begin{tabular}{c|c} \hline Rig structure& Corresponding equation\\ \hline $0$& $x^0 = 1$ \\ \hline $1$&$x^1 = x$ \\ \hline $+$& $x^{y+z} = x^y x^z$\\ \hline $\ti$&$x^{yz} = (x^z)^y$ \\ \hline \end{tabular} \caption{Four of rieg equations} \label{table:riegequations} \end{table} % \begin{description} % \item[$0$] $x^0 = 1$ % \item [$1$] $x^1 = x$ % \item [$+$] $x^{y+z} = x^y x^z$ % \item [$\ti$] $x^{yz} = (x^z)^y$ % \end{description} Summarising the above observations, we obtain an equational definition of the notion of riegs. While it is longer than \Cref{def:rieg}, it consists only of familiar conditions. \begin{proposition}[Equational definition of riegs]\label{prop:EquationalDefinition} The definition of riegs can be rephrased by the five operations: \begin{itemize} \item two constants ($=$ nullary operations), $0,1 \in R$, and \item three binary operations, $+, \ti, \ex\colon R\times R \to R$, \end{itemize} and fourteen equations: \begin{enumerate} \item $0+x=x$ \item $(x+y)+z=x+(y+z)$ \item $x+y=y+x$ \item $1 x =x$ \item $(x y) z=x (y z)$ \item $x y=y x$ \item $x 0 =0$ \item $x (y+z)=x y + x z$ \item $1 ^ x = 1$ \item $(yz)^x = y^x z^x$. \item $x ^ 0 = 1$ \item $x^ 1 = x$ \item $x^ {y+z} =x^ y x^ z$ \item $x^{y z} = (x^ z)^ y$, \end{enumerate} where $x^y$ denotes $x\ex y$ and $xy$ denotes $x\ti y$, as usual. \end{proposition} \begin{remark} \label{rmk:zerotozeroisone} As a special case of the equation $x ^ 0 = 1$, we have $0^0=1$. % In any rieg, we have % $0^0=1$. \memo{I can write its logical, categorical, ... interpretation.} \end{remark} % \memo{If $0^x=1$, then is $x$ zero? No, Heyting algebras} From this equational definition, we obtain the notion of rieg homomorphisms, as usual. \begin{definition} A \demph{rieg homomorphism} is a function that preserves all (five) operations $0,1,+,\ti,\ex$. We write $\Rieg$ for the category of riegs. \end{definition} Before we later turn to the sections on examples, we introduce here two trivial (but important!) examples of riegs: namely, the initial and terminal objects in the category of riegs. % The basic example is, of course, the rieg of natural numbers: \begin{example}[The initial rieg: natural numbers] \label{exmp:TheInitialRiegOfNaturalNumbers} The set of natural numbers $\N = \{0,1, 2, \dots\}$ equipped with the usual zero $0$, one $1$, addition $+$, multiplication $\ti$, and exponentiation $\ex$, form the rieg of natural numbers $\N$. Here are a few remarks about this example: \begin{itemize} \item This rieg $\N$ is an initial object in the category $\Rieg$. \item This is the unique rieg structure on the rig of natural numbers, since $\N$ is the initial rig (\Cref{exmp:RigOfNaturalNumbers}) and a rieg structure is given by a rig homomorphism $\N \to \End(\N, 1, \ti)$. \item We adopt the convention that $0^0 = 1$ (see \Cref{rmk:zerotozeroisone}). \end{itemize} \end{example} \begin{example}[The degenerate rieg] \label{exmp:ThedegenerateRieg} Every singleton admits the only one rieg structure, which we call a \demph{degenerate rieg} $\1$. A degenerate rieg is a terminal object of the category $\Rieg$. \end{example} \memo{I would write the summary of the following contents, picking a central example from each section.} \memo{remark:as a module of itself} \subsection{Digression: Why rigs, not rings?} The reader may wonder: why develop a theory using rigs, even though rings are so famous and successful? There are several possible answers, but perhaps the simplest is that subtraction and exponentiation are fundamentally incompatible—indeed, there is $0^{-1}$! \begin{proposition}\label{prop:riegIsNotRing} If a rieg $R$ is a ring, then it is degenerate $R\cong \1$. % No rieg is a ring unless it is the degenerate rieg $\1$. \end{proposition} \begin{proof} % Let $R$ be a rieg that is also a ring. % % If (the underlying rig of) the rieg $R$ is a ring, % Then % w We have $-1\in R$, which yields the equation $ 1=0^0=0^{1+(-1)}=0^{1}\ti 0^{-1}=0 \ti 0^{-1}=0. $ This implies that every element $r\in R$ is equal to $0$, since $r= r\ti 1 = r\ti 0 =0$. \end{proof} For example, exponentiation can be defined on the rig $\N$ (which is the decategorification of finite sets), but not on the ring $\Z$. To the best of the author’s understanding, one reason why exponential structures—despite being present in many mathematical objects—have not received the attention they perhaps deserve is that the process of decategorification often involves introducing formal subtraction. This subtraction does help clarify theories (sometimes by reducing the amount of information), but at the same time, it forces us to entirely forget the exponential structure. \section{Example 1: Riegs in finite and profinite arithmetic}\label{sec:RiegsInFiniteAndProfiniteArithmetic} \subsection{Introduction} Before delving into the technical details, let us first take a look at a few phenomena that will be studied in \Cref{sec:RiegsInFiniteAndProfiniteArithmetic}. % % {Modular arithmetic with exponentials} \subsubsection{Phenomenon 1: modular arithmetic with exponentials}\label{sssec:FiniteArithmetic} Let us consider the following typical problem from elementary number theory, which involves exponentiation. % can be solved by modular arithmetic: \begin{puzzle} Find all pairs of natural numbers $(n,m)$ such that \[2^n +5 =m^2.\] \end{puzzle} \begin{answer} Consider the equation modulo $8$. If $n \geq 3$, then $2^n \equiv 0 \pmod{8}$, so the left-hand side is congruent to $5 \pmod{8}$. However, the quadratic residues modulo $8$ are $0$, $1$, and $4$, so $m^2 \equiv 5 \pmod{8}$ is impossible. Therefore, we only need to check $n = 0$, $1$, and $2$. We find that the only solution is $(n,m) = (2,3)$. \end{answer} In this example, when considering exponentiation modulo $8$, we should divide \dq{first exceptions}, namely three numbers $n=0,1,2$. \memo{I will write more} % Rieg theory is involved here. The modular arithmetic of modulo $b$ requires first exceptions and that the number of them, $a$ must (not surprisingly) be greater than or equal to any number that appears as an exponent in the prime factorization of $b$. The rieg of modulo $b$ with first exceptions less than $a$ is denoted by $\Mr{a}{b}$. For example, in the above equation, we utilized the modulo rieg $\Mr{3}{8}$. In this section, we classify what $a,b$ is possible. \memo{Write a picture} \subsubsection{Phenomenon 2: Profinite dynamical systems with exponentials}\label{sssec:ProiniteArithmeticDynamicalSystems} Let us consider the following puzzle. \begin{puzzle}[A puzzle provided by J.Koizumi] Find a four-digit natural number $n$ such that the last four digits of $3^n$ are equal to $n$. \end{puzzle} There is a surprisingly simple way to find an answer; iteration.F irst, take an arbitrary natural number $n$, like $n=2024$. Then, repeatedly replace $n$ by the last $4$-digits of $3^n$\footnote{Thanks to the repeated squaring algorithm, a computer can conduct this calculation in a short time. \memo{say, by Wolfram alpha}}. \begin{itemize} \item \begin{itemize} \item $3^{2024} \equiv 6481$ \item $3^{6481} \equiv 6803$ \item $3^{6803} \equiv 2027$ \item $3^{2027} \equiv 4987$ \item $3^{4987} \equiv 9387$ \item $3^{9387} \equiv 5387$ \item $3^{5387} \equiv 5387$ \end{itemize} \item We obtain an answer $n=5387$. \end{itemize} \begin{answer} $n=5387$ is the only answer. \end{answer} Then, it is natural to ask whether we can go farther: \begin{question} Is there an infinite sequence of decimal digits \[\dots a_4 a_3 a_2 a_1\] such that, for every integer $k \geq 1$, the number $n = a_k \dots a_1$ (interpreted in decimal) satisfies the congruence \[ 3^n \equiv n \pmod{10^k}? \] \end{question} The answer is Yes! (See \Cref{fig:PictureListOfthreetotheN}) \begin{figure}[ht] \centering \begin{shaded} \begin{align*} 3^{87} &\equiv 87 \mod{100}\\ 3^{387} &\equiv 387 \mod{1000}\\ 3^{5387} &\equiv 5387 \mod{10000}\\ 3^{95387} &\equiv 95387 \mod{100000}\\ 3^{195387} &\equiv 195387 \mod{1000000}\\ 3^{4195387} &\equiv 4195387 \mod{10000000}\\ 3^{64195387} &\equiv 64195387 \mod{100000000}\\ 3^{464195387} &\equiv 464195387 \mod{1000000000}\\ &\vdots \end{align*} \caption{The unique solution of $3^n=n \mod{10^k}$ for each $k\geq 2$} \label{fig:PictureListOfthreetotheN} \end{shaded} \end{figure} \memo{Explain how this is an instance of Banach fixed point theorem. Explain why it works for $\Z_{10}$ but not for $\Z_5$. } % For any $k>1$ \memo{$k=1$ is also fine}, there is a unique $k$-digits natural number $n$ such that the last $k$-digits of $3^n$ are equal to $n$. This phenomenon is a reminiscent of $p$-adic integers. \memo{write something} However, in this case, the exponential operation is involved. In this section, we will construct profinite systems of numbers, which can be regarded as a $p$-adic number system with exponentials. Using that structure, we will be able to answer the above question easily. \memo{How to find it. } Rough sketch of our proof is as follows: \begin{answer}[Rough sketch] % In a topological rieg $\Mr{\infty}{10^\infty}$, the sequence % \[(3 \powow 1) =3, (3 \powow 2) =3^3, (3 \powow 3) =3^{3^3}, (3 \powow 4) =3^{3^{3^3}}, \dots\] % converges to an element $(3 \powow \infty) \in \Mr{\infty}{10^\infty}$. In a topological rieg $\Mr{\infty}{10^\infty}$, we can take the limit $\alpha$ of the sequence \[3, 3^3, 3^{3^3}, 3^{3^{3^3}}, 3^{3^{3^{3^3}}} \dots \to \alpha.\] % converges to an element $\alpha \in \Mr{\infty}{10^\infty}$. By the continuity of $3^x \colon \Mr{\infty}{10^\infty} \to \Mr{\infty}{10^\infty}$, we have $3^ \alpha = \alpha$. \end{answer} \memo{This should be unique. If $3^{\beta} = \beta$, then $\beta \equiv 87 \mod 100$. Since $\alpha \equiv \beta \mod{100}$, $\alpha = 3^{\alpha} \equiv 3^{\beta} = \beta \mod{1000}$} \subsubsection{Phenomenon 3: Well-defined modulo exponentials}\label{sssec:Well-definedModuloExponentials} $1,2,6,42,1806$ \subsection{The Burris-Lee theorem: Classification of quotient riegs of \texorpdfstring{$\N$}{N}} Modular arithmetic is based on considering quotient rings of the (initial) ring $\Z$. Similarly, by considering quotient riegs of the (initial) rieg $\N$, we aim to obtain tools for a modular arithmetic involving exponentiation. The goal of this subsection is to introduce the Burris–Lee theorem \cite{burris1992small,burris1993tarski}, which provides a classification of all quotient riegs of $\N$. Although the definitions are slightly different, all of the crucial arguments in this subsection are due to \cite{burris1992small,burris1993tarski}. For the reader's convenience, the full details of the proof will be given in this subsection. % \memo{On the terminology \dq{modulo riegs}} Let us start by clarifying what `quotient rieg' means. \begin{definition}[Quotient rieg]\label{def:quotientRieg} A \demph{quotient rieg} of a rieg $R$ is a rieg $R'$ equipped with a surjective rieg homomorphism $R\twoheadrightarrow R'$. \end{definition} Since $\N$ is the initial rieg, there exists a unique rieg homomorphism $\N \to R$ for any rieg $R$. Therefore, it makes sense to ask whether a given rieg $R$ is a quotient rieg of $\N$ without explicitly referring to the homomorphism $\N \to R$. \subsubsection{Examples of quotient riegs of \texorpdfstring{$\N$}{N}} Before we get into the theoretical considerations, let us list some examples of quotient riegs of $\N$. The reader does not need to check that they are actually riegs, since \Cref{thm:BurrisLeeTheorem} will verify everything. \begin{example}[Two trivial examples] The degenerate rieg $\1$ (\Cref{exmp:ThedegenerateRieg}) and $\N$ itself are trivially quotient riegs of $\N$. \end{example} \begin{example}[The rieg of truth values]\label{exmp:RiegOfTruthValues} As we will see later, \memo{cite the section} the set of truth values $\2 = \{\bot, \top\}$ has a natural rieg structure $(\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 function $\text{IsPositive}\colon \N \twoheadrightarrow \2$ defined by \[ \text{IsPositive}(n) \coloneqq \begin{cases} \top &(n>0)\\ \bot &(n=0) \end{cases} \] is the unique rieg homomorphism $\N \to \2$, which witnesses that $\2$ is a quotient rieg of $\N$. \end{example} \begin{example}[Parity rieg]\label{exmp:ParityRieg} As a slightly more nontrivial example, the natural surjection \[ \mathbb{N} \twoheadrightarrow \{0,\ \text{positive odd},\ \text{positive even}\} \] induces a quotient rieg structure on the $3$-element set $\{0,\ \text{positive odd},\ \text{positive even}\}$, which we refer to as the \demph{parity rieg}. Notice that the surjection \[ \mathbb{N} \twoheadrightarrow \{\text{odd}, \text{even}\} =\Z/2\Z \] does not induce a rieg structure on the set $\{\text{odd}, \text{even}\}=\Z/2\Z$, since $2^0=1$ is odd and $2^2=4$ is even. (This also follows from \Cref{prop:riegIsNotRing}.) \end{example} \begin{example}[Overflow riegs]\label{exmp:OverflowRiegs} For any natural number $n \geq 0$, we define the \demph{overflow rieg with threshold $n$} on the $(n+1)$-element set \[ \{0, 1, 2, \dots, n-1, \TB\}. \] It will be denoted by $\OF_n$. The rieg structure is induced by the natural surjection \[ \mathbb{N} \twoheadrightarrow \{0, 1, 2, \dots, n-1, \TB\}. \] Intuitively, the symbol $\TB$ stands for “too big to remember”: any number greater than or equal to $n$ is said to \emph{overflow} and is mapped to $\TB$. For example, in the overflow rieg with threshold $5$, we have $2^3=\TB$, $0^{\TB}=0$, and \begin{align*} 0^\TB \cdot 2^3+1^{4+2} +2^{1^{3+2}} &=0\cdot \TB+1^{\TB} +2^{1^{\TB}} \\ &=0+1+2^{1} \\ &=3. \end{align*} The overflow rieg with threshold $n=0$ (respectively, $n=1$) is the degenerate rieg in \Cref{exmp:ThedegenerateRieg} (respectively, the rieg of truth values in \Cref{exmp:RiegOfTruthValues}). \end{example} \subsubsection{Quotient rigs of \texorpdfstring{$\N$}{N}} Every quotient rieg $\N \twoheadrightarrow R$ is obviously a quotient rig of $\N$. So we first classify all quotient rigs of $\N$. Since $\N$ is initial also in the category of rigs $\Rig$, it makes sense to ask whether a given rig $R$ is a quotient rig of $\N$ without mentioning the rig homomorphism $\N \to R$. \begin{definition}[$\Mr{a}{b}$]\label{def:QuotientRigMrab} For a natural number $a\geq 0$ and a positive integer $b>0$, we define a surjection $\N \twoheadrightarrow\Mr{a}{b}$ onto the $(a+b)$-element set $\Mr{a}{b}\coloneqq \N/{\sim_{a,b}}$, where $\sim_{a,b}$ denotes the equivalence relation defined by \[n \sim_{a,b} m \iff (n=m)\lor ((n,m\geq a) \land (n\equiv m \mod{b})). \] \end{definition} \Cref{fig:ModuleRieg} is a visualization of $\Mr{3}{4}$. \begin{figure}[ht] \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{$\Mr{3}{4}$} \label{fig:ModuleRieg} \end{shaded} \end{figure} \begin{proposition}[Quotient rigs of $\N$]\label{prop:quotientrigs} % Let $a\geq 0$ be a natural number and $b>0$ be a positive integer. For a natural number $a\geq 0$ and a positive integer $b>0$, the surjection $\N \twoheadrightarrow\Mr{a}{b}$ induces a rig structure on $\Mr{a}{b}$. Conversely, every quotient rig of $\N$ is either the identity $\id_\N \colon \N \to \N$ or is of this form. % \begin{itemize} % \item The surjection $\N \twoheadrightarrow\Mr{a}{b}$ induces a rig structure on $\Mr{a}{b}$. % \item The rig $\Mr{a}{b}$ is % \end{itemize} \end{proposition} \begin{proof} \memo{easy...} \end{proof} % For example, (the underlying rig of) the degenerate 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. % A 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..} If the rig $\Mr{a}{b}$ admits a rieg structure, the unique rig homomorphism $\N \twoheadrightarrow \Mr{a}{b}$ should be a rieg homomorphism. Therefore, a rieg structure on the rig $\Mr{a}{b}$ is unique if it exists. So it makes sense to ask whether $\Mr{a}{b}$ is a rieg. Not every $\Mr{a}{b}$ is a rieg. For example, $\Mr{0}{b} \cong \Z/b\Z$ is a rieg if and only if $b=1$ (see \Cref{exmp:ThedegenerateRieg} and \Cref{prop:riegIsNotRing}). In the rest of the present subsection, we will study a sufficient and necessary condition for $(a,b)$ to make $\Mr{a}{b}$ a rieg in terms of elementary number theory. (\Cref{fig:PlotsOfQuotientRiegsOfN} shows the small pairs of $(a,b)$ that makes $\Mr{a}{b}$ a rieg.) \subsubsection{shifted-Carmichael numbers} As a preparation of \Cref{thm:BurrisLeeTheorem} (and the following contents), we introduce the notion of shifted-Carmichael numbers. % Before stating the classification theorem, we introduce two terminologies. \begin{definition}[Shifted-Carmichael number] A positive integer $n$ is said to be \demph{shifted-Carmichael} if \[ p \mid n \implies (p-1) \mid n \] for any prime number $p$. \end{definition} The list of shifted-Carmichael numbers begins with: \[1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 32, 36, 40, 42, 48, 54, 60, 64, 72, 80, 84, 96, 100, 108, 120, 126, \dots.\] Notice that there are infinitely many shifted-Carmichael numbers since $k!$ is shifted-Carmichael for any $k\geq 0$. \begin{remark}[Comparison with Carmichael numbers] Recall that a positive integer $n$ is said to be a \demph{Carmichael number} if % \begin{description} % \item[Carmichael] for any $x \in (\Z/n\Z)^{\times}$, $x^{n-1} \equiv 1 \mod{n}$ % \end{description} \begin{center} for any $x \in (\Z/n\Z)^{\times}$, $x^{n-1} \equiv 1 \mod{n}$. \end{center} On the other hand, \Cref{lem:AlgebraicCharacterizationOfShifted_CarmichaelNumbers} will show that a positive integer $n$ is shifted-Carmichael if and only if % \begin{description} % \item[shifted-Carmichael] for any $x \in (\Z/n\Z)^{\times}$, $x^{n} \equiv 1 \mod{n}$. % \end{description} \begin{center} for any $x \in (\Z/n\Z)^{\times}$, $x^{n} \equiv 1 \mod{n}$. \end{center} % Compared with the algebraic characterization of shifted-Carmichael numbers (\Cref{lem:AlgebraicCharacterizationOfShifted_CarmichaelNumbers}), The only difference is that the exponent $n$ is shifted by one. This is a reason for our terminology, shifted-Carmichael\footnote{Another passive reason is that many other names, including \demph{anti-Carmichael numbers}, are already used.}. A natural number $n$ cannot be simultaneously Carmichael and shifted-Carmichael, unless $n$ is $1$ or $2$. \end{remark} \subsubsection{The Burris-Lee theorem} To state \Cref{thm:BurrisLeeTheorem}, we need one more (very elementary) notion: \begin{definition}($H(n)$)\label{def:Hn} For a positive integer $n>0$, we write $H(n)$ for the maximum exponent in the prime factorization. \end{definition} More concretely, for a positive integer $n>0$ with the prime factorization $n={p_1}^{k_1}\dots {p_l}^{k_l}$, the value of $H(n)$ is given by $H(n) \coloneqq \max(k_1 , \dots, k_n)$. The notation $H(n)$ is borrowed from \cite{niven1969averages}\footnote{In \cite{niven1969averages}, $H(1)$ is defined to be $1$, while we adopt another convension $H(1) =0$.}. The first $9$ values of $H(n)$ are listed in \Cref{tab:Hn}. \begin{table}[ht] \centering \begin{tabular}{|c|c|c|c|c|c|c|l|l|l} \hline $n$& 1& 2& 3& 4& 5& 6 & 7&8 &9\\ \hline $H(n)$& 0& 1& 1& 2& 1& 1& 1&3 &2\\ \hline \end{tabular} \caption{First values of $H(n)$} \label{tab:Hn} \end{table} % For example, the values of $\H(n)$ for small $n$ are $\H(1)=0, \H(2)=1, \H(3)=1, \H(4)=2, \H(5) = 1, \H(6)=1, \H(7)=1, \H(8)=3$. \begin{theorem}[The Burris-Lee theorem \cite{burris1992small, burris1993tarski}]\label{thm:BurrisLeeTheorem} For $a\geq 0$ and $b>0$, the rig $\Mr{a}{b}$ admits a rieg structure if and only if % $b$ is a shifted-Carmichael number whose dimension is at most $a$. \begin{enumerate} \item $a\geq \H(b)$ and \item $b$ is shifted-Carmichael. \end{enumerate} \end{theorem} As a result, we obtain the complete (infinite) list of modulo riegs (\Cref{PictureListOfModuloRiegs}). \begin{figure} \centering \begin{shaded} \begin{tikzpicture} \begin{axis}[ width=14cm, height=18cm, xlabel={$a$}, ylabel={$b$}, ymin=1, ymax=130, xmin=0, xmax=10, xtick={0,...,10}, ytick={1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 32, 36, 40, 42, 48, 54, 60, 64, 72, 80, 84, 96, 100, 108, 120, 126, 128}, axis on top, enlargelimits=false, grid=major, % title={Shifted-Carmichael}, tick label style={font=\small}, label style={font=\small} ] % points \addplot[ only marks, mark=square*, mark size=1pt, color=black ] coordinates { (0,1) (1,1) (1,2) (1,6) (1,42) (2,1) (2,2) (2,4) (2,6) (2,12) (2,18) (2,20) (2,36) (2,42) (2,60) (2,84) (2,100) (2,126) (3,1) (3,2) (3,4) (3,6) (3,8) (3,12) (3,18) (3,20) (3,24) (3,36) (3,40) (3,42) (3,54) (3,60) (3,72) (3,84) (3,100) (3,108) (3,120) (3,126) (4,1) (4,2) (4,4) (4,6) (4,8) (4,12) (4,16) (4,18) (4,20) (4,24) (4,36) (4,40) (4,42) (4,48) (4,54) (4,60) (4,72) (4,80) (4,84) (4,100) (4,108) (4,120) (4,126) (5,1) (5,2) (5,4) (5,6) (5,8) (5,12) (5,16) (5,18) (5,20) (5,24) (5,32) (5,36) (5,40) (5,42) (5,48) (5,54) (5,60) (5,72) (5,80) (5,84) (5,96) (5,100) (5,108) (5,120) (5,126) (6,1) (6,2) (6,4) (6,6) (6,8) (6,12) (6,16) (6,18) (6,20) (6,24) (6,32) (6,36) (6,40) (6,42) (6,48) (6,54) (6,60) (6,64) (6,72) (6,80) (6,84) (6,96) (6,100) (6,108) (6,120) (6,126) (7,1) (7,2) (7,4) (7,6) (7,8) (7,12) (7,16) (7,18) (7,20) (7,24) (7,32) (7,36) (7,40) (7,42) (7,48) (7,54) (7,60) (7,64) (7,72) (7,80) (7,84) (7,96) (7,100) (7,108) (7,120) (7,126) (7,128) (8,1) (8,2) (8,4) (8,6) (8,8) (8,12) (8,16) (8,18) (8,20) (8,24) (8,32) (8,36) (8,40) (8,42) (8,48) (8,54) (8,60) (8,64) (8,72) (8,80) (8,84) (8,96) (8,100) (8,108) (8,120) (8,126) (8,128) (9,1) (9,2) (9,4) (9,6) (9,8) (9,12) (9,16) (9,18) (9,20) (9,24) (9,32) (9,36) (9,40) (9,42) (9,48) (9,54) (9,60) (9,64) (9,72) (9,80) (9,84) (9,96) (9,100) (9,108) (9,120) (9,126) (9,128) (10,1) (10,2) (10,4) (10,6) (10,8) (10,12) (10,16) (10,18) (10,20) (10,24) (10,32) (10,36) (10,40) (10,42) (10,48) (10,54) (10,60) (10,64) (10,72) (10,80) (10,84) (10,96) (10,100) (10,108) (10,120) (10,126) (10,128) }; \end{axis} \end{tikzpicture} \caption{The list of quotient riegs of $\N$} \label{fig:PlotsOfQuotientRiegsOfN} \end{shaded} \end{figure} \begin{figure}[ht] \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} \subsubsection{Examples and corollaries} 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{burris1992small, 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 $n= 1,2,6,42,1806$ are the only shifted-Carmichael numbers with $1\geq H(n)$. If $n$ is a $1$-dimensional shifted-Carmichael number and $p$ is the maximum prime factor, then $n/p$ is also a ($0$ or $1$-dimensional) shifted-Carmichael number and $p-1$ is a divisor of $n/p$. Therefore, we can inductively generate all $1$-dimensional shifted-Carmichael 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 shifted-Carmichael numbers. \end{conjecture} \cite{OEISsyl}\cite{burris1992small, burris1993tarski}, By a computer calculation, we know there is a $2$-dimensional shifted-Carmichael number bigger than $10^{10000}$. \memo{In the case of $1$-dimensional shifted-Carmichael 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 shifted-Carmichael numbers.} \begin{example} For any non-negative integer $n$, $1$ is a shifted-Carmichael number whose dimension is $0$. 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 shifted-Carmichael 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 shifted-Carmichael 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 shifted-Carmichael 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} % 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 \demph{characteristic} of a rieg is \memo{write} % \end{definition} % \memo{Solve some Diophantus equation utilizing those riegs} % \begin{definition}\label{DefinitionOrderCharacteristics} % \end{definition} % \subsection{Relation to other algebraic structures} \subsection{The complete lattice of characteristics} From this subsection, we will use the following notations: \begin{itemize} \item $\RigfCh$ denotes the product poset $\N \times \Np$. \item $\RigCh$ denotes the poset $\RigfCh$ with a formal maximum element $\chz$. \item $\RiegfCh$ denotes the full sub poset of $\RigfCh$ defined by \[ \RiegfCh\coloneqq \{(a,b \in \RigfCh\mid b \text{ is shifted-Carmichael and }a\geq H(b)\}. \] \item $\RiegCh$ denotes the poset $\RigfCh$ with a formal maximum element $\chz$. \end{itemize} These notations are based on a general theory of characteristics (See \Cref{sec:generaltheoryOfCharacteristics}). Notice that $\RigCh$ (respectively, $\RiegCh$) is isomorphic to the complete lattice of quotient rigs (respectively, quotient riegs) of $\N$. Even in those poset, we write $(a,b) \leq (a',b')$ for the associated order, which always means that $a\leq a'$ in the usual order, and $b\mid b'$. Of course, the formal maximum element $\chz$ is defined to be maximum. \subsubsection{Chracteristics of a rieg} Recall that the characteristic of a ring $R$ is the smallest positive integer $n$ such that $0 = \underbrace{1 + 1 + \dots + 1}_{n \text{ times}}$, if such an $n$ exists; otherwise, the characteristic is defined to be $0$. The most fundamental fact in field theory is that, if the ring $R$ is a field, its characteristic should be a prime number (or $0$). In other words, the existence of division imposes a number theoretic condition on its characteristic. We will define a similar notion for rigs and riegs. Recall that $\N$ denotes the usual poset of natural numbers, that $\Np$ denotes the poset of positive integers with the divisibility order, and that $\RigfCh$ denotes their product poset (\Cref{not:notationsOfNaturalNumberRelatedSystems}). \begin{definition}[Characteristic]\label{def:CharacteristicOfRigsAndRiegs} The \demph{characteristic} of a rig (or a rieg) $R$, which is denoted by $\ch R$, is the minimum pair % \memo{Clarify the meaning of \dq{minimum.} But I think there is no room for confusion...?} $(a,b) \in \RigfCh$ such that \[ \underbrace{1+\dots +1}_{a \text{ times}}= \underbrace{1+\dots +1}_{a \text{ times}}+ \underbrace{1+\dots +1}_{b \text{ times}}, \] if it exists. Otherwise, $\ch R$ is defined to be $\chz$. \end{definition} \begin{corollary}[Burris-Lee theorem in terms of rieg characteristics \cite{burris1992small, burris1993tarski}] A pair $(a, b)\in \RigCh$ is a characteristic of a rieg if and only if $(a,b)\in \RiegCh \subset \RigCh$. \end{corollary} This is analogous to the fact that the characteristics of fields should be prime, while those of rings can take all natural numbers. \begin{remark}[Is this definitin natural?] We slightly changed the definition of characteristic from the case of rings. In fact, the exact same definition does not work well. If there exists a positive integer $n$ such that $0 = n$, then $n - 1$ must be the additive inverse of $1$, and the rieg is isomorphic to the degenerate rieg (\Cref{prop:riegIsNotRing}). Our definition follows a general theory of characteristics of algebraic theory \Cref{sec:generaltheoryOfCharacteristics}. \end{remark} This order relation can be rephrased in terms of rigs and riegs: \begin{proposition} For $(a,b), (a',b') \in \RigCh$, $(a,b) \geq (a',b')$ if and only if there is a rig homomorphism $\Mr{a}{b} \to \Mr{a'}{b'}$. Furthermore, in the case where $(a,b), (a',b') \in \RiegCh$, $(a,b) \geq (a',b')$ if and only if there is a rieg homomorphism $\Mr{a}{b} \to \Mr{a'}{b'}$. \end{proposition} In other words, $\RigCh$ is isomorphic to the complete lattice of the quotient rigs of $\N$, and $\RiegCh$ is isomorphic to the complete lattice of the quotient riegs of $\N$. \begin{lemma}\label{lem:Shifted_Carmichaelapprox} For any positive integer $b$, there is the minimum shifted-Carmichael number $b'$ such that $b$ divides $b'$. \end{lemma} \begin{proof} Here is a concrete algorithm: If $b$ is shifted-Carmichael, then return $b$. If $b$ is not shifted-Carmichael, then take the maximum prime number $p_b$ such that $p_b$ divides $b$ but $p_b -1$ does not divide $b$. And (recursively) return the minimum shifted-Carmichael number $b'$ such that $\lcm (b, p_b-1)$ divides $b'$. This algorithm halts, since the prime number $p_b$ becomes smaller and smaller. It is easy to prove the minimality. \end{proof} \begin{example}[The minimum shifted-Carmichael number that is divided by $11$] First, start with $b=11$, we replace it with $\lcm (11, 11-1)=110$. Next, we replace $b=110$ with $\lcm (110,5-1)= 220$ and conclude $220$ is the least shifted-Carmichael number that is divided by $11$. \end{example} \begin{proposition}[Shifted-Carmichael approximation]\label{prop:riegCharacteristicApprox} For any $(a,b)\in \RigCh$, there is the minimum $(a',b')\in \RiegCh$ such that $(a,b)\leq (a',b')$. Furthermore, if $(a,b)\in \RigfCh$, then $(a',b')\in \RiegfCh$. \end{proposition} \begin{proof} If $(a,b)= \chz$, then $(a',b')=\chz$. We may assume $(a,b)\in \RigfCh$. Due to \Cref{lem:Shifted_Carmichaelapprox}, we can take the minimum shifted-Carmichael number $b'$ that is divided by $b$. Then, define $a'$ by $a\coloneqq \max(a,\H{(b)})$. \end{proof} In categorical terms, \Cref{prop:riegCharacteristicApprox} states that the two embedding (order-preserving) functions \[\RiegCh \hookrightarrow \RigCh \] \[\RiegfCh \hookrightarrow \RigfCh \] have a left adjoint. % . \memo{This data defines a \dq{closure operator} on $\RigCh$. but not preserving meets.} As an immediate corollary, we obtain the following propositions. \begin{proposition} $\RiegfCh$ is unbounded in $\N\times \N_{>}$. \end{proposition} \begin{proposition}[] For any $n\in \N$, the canonical rig homomorphism \[\N \twoheadrightarrow \Z/n\Z\] can be factored as \[\N \twoheadrightarrow \Mr{a}{b}\twoheadrightarrow \Z/n\Z,\] where $\N \twoheadrightarrow \Mr{a}{b}$ is a rieg homomorphism and $\Mr{a}{b}\twoheadrightarrow \Z/n\Z$ is a rig homomorphism. \end{proposition} \begin{proof} We can take $(a,b)$ by applying \Cref{prop:riegCharacteristicApprox} to $(0,n)\in \N\times \N_{>}$. \end{proof} \memo{mention: The part of phenomena: $(0,8) \mapsto (3,8)$, and $(0,10) \mapsto (2, 20)$} \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}}$?} \memo{Write on the unique solution of $3^x =x$ in $\Mr{\infty}{10^{\infty}}$.} \subsection{The topological rieg of profinite natural numbers} Recall that the profinite completion of an algebraic structure $A$ is defined as the limit of its finite quotient algebras (in the category of algebras or in the category of topological algebras) (\Cref{ssec:GeneralTheoryOfProfiniteAlgebras}). Our aim in this subsection is to analyze the algebraic and topological structures of $\proN$. \begin{definition} \demph{The rieg of profinite integers} $\proN$ is defined as the profinite completion of the initial rieg $\N$. \end{definition} In other words, the rieg $\proN$ is defined as the limit \[ \proN \coloneqq \lim \left (\RiegfCh^{\op} \to \Rieg \right ). \] Although it is possible to calculate it by definition, the shape of the above diagram $\RiegfCh^{\op}$ is a little tricky to calculate. So we will make it simpler by the next lemma. \begin{lemma}\label{lem:SimplifyingWithFactorial} For any $n\in \N$, we have $(n, n!)\in \RiegfCh$. Furthermore, for any $(a,b)\in \RiegfCh$, there exists an $n\in \N$ such that $(a,b ) \leq (n, n!)$. \end{lemma} \begin{proof} For any $n\in \N$, the factorial $n!$ is shifted-Carmichael since if $p\mid n!$ then $p\leq n$, which implies $p-1 \leq n$ and $(p-1)\mid n!$. Furthermore, $n\geq H(n!)$ holds since the exponent of $p$ in the prime factorization of $n!$, which is denoted by $v_p(n!)$ is given by Legendre's formula % \[ % \sum_{k=1}^{\infty} \left\lfloor {\frac{n}{p^k}}\right\rfloor % \] and is bounded above by $n$ as follows: \[ v_p(n!) = \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 $(n, n!)\in \RiegfCh$. The latter part follows since we can define $n$ by $n\coloneqq \max(a,b)$. \end{proof} \begin{proposition}\label{prop:profiniteInteger} The profinite rieg $\proN$ is the limit of the following diagram. \[ \begin{tikzcd} % \proN \cdots \ar[r, twoheadrightarrow , "\pi_4"]& \Mr{3}{3!}\ar[r, twoheadrightarrow, "\pi_3"] & \Mr{2}{2!}\ar[r, twoheadrightarrow, "\pi_2"] & \Mr{1}{1!}\ar[r, twoheadrightarrow, "\pi_1"] & \Mr{0}{0!} \end{tikzcd} \] \end{proposition} \begin{proof} \Cref{lem:SimplifyingWithFactorial} proves that the order preserving function \[ \N \to \RiegfCh: n\mapsto (n,n!) \] is well-defined and is a final functor. Therefore, the limit of the shape of $\RiegfCh^{\op}$ is reduced to the limit of the shape of $\N^{\op}$. \end{proof} \begin{theorem} The underlying set of the rieg of profinite integers $\proN$ is given by \[\textstyle \proN = \N \sqcup \proZ,\] where $\proZ$ denotes the usual set of profinite integers. The canonical projection map $\pi_{a,b}\colon \proN \to \Mr{a}{b}$ is given by the canonical functions % \[ % \pi_{a,b} (x) = % \begin{cases} % &(x=n \in \N)\\ % \end{cases} \[ \N \twoheadrightarrow \Mr{a}{b} \] and \[ \proZ \twoheadrightarrow \Z/b\Z \rightarrowtail \Mr{a}{b}. \] \end{theorem} \begin{proof} Due to \Cref{lem:SimplifyingWithFactorial} (and \Cref{lem:LimitsofTopologicalAlgebras}), the elements of $\proN$ are in bijevtive correspondence with the element of \[ \{(x_n \in \Mr{n}{n!})_{n\geq 0}\mid \forall n\geq 0,\; \pi_{n+1} (x_{n+1}) = x_{n}\}. \] Let $(x_n \in \Mr{n}{n!})_{n\geq 0}$ % be a sequence in the right hand side set. $(x_n \in \Mr{n}{n!})_{n\geq 0}$, If at least one term $x_n \in \Mr{n}{n!}$ is in the \dq{first exceptions,} in other words written as $x_n=k \in \Mr{n}{n!}$ for some $0\leq k k)\\ [k] & (n\leq k). \end{cases} \] Otherwise, every term $x_n$ belongs to the subset $x_n \in \Z/n!\Z \subset \Mr{n}{n!}$. Therefore, $x_n$ can be naturally regarded as an element of $\proZ = \lim_{n\to \infty}(\Z/n! \Z)$. % Since the forgetful functor $U \colon \Rieg \to \Set$ creates all small limits, the element of $\proN$ corresponds to a family of elements $\{x_{a,b} \in \Mr{a}{b}\}_{(a,b) \in \RiegfCh}$ such that if $(a,b) \leq (a',b')$ then $x_{a,b}= \mathrm{pr} (x_{a',b'})$, where $\mathrm{pr}$ denotes the canonical comparison homomorphism $\Mr{a'}{b'}\twoheadrightarrow \Mr{a}{b}$. \end{proof} \begin{figure}[htbp] \centering \begin{tikzpicture}[x=12cm, y=-0.8cm] \fill[black!60] (0.0000,0) rectangle (1.0000,0.3); \fill[black!60] (0.0000,1) rectangle (0.4000,1.3); \fill[black!60] (0.6000,1) rectangle (1.0000,1.3); \fill[black!60] (0.0000,2) rectangle (0.1067,2.3); \fill[black!60] (0.1467,2) rectangle (0.2533,2.3); \fill[black!60] (0.2933,2) rectangle (0.4000,2.3); \fill[black!60] (0.6000,2) rectangle (0.7067,2.3); \fill[black!60] (0.7467,2) rectangle (0.8533,2.3); \fill[black!60] (0.8933,2) rectangle (1.0000,2.3); \fill[black!60] (0.0000,3) rectangle (0.0213,3.3); \fill[black!60] (0.0284,3) rectangle (0.0498,3.3); \fill[black!60] (0.0569,3) rectangle (0.0782,3.3); \fill[black!60] (0.0853,3) rectangle (0.1067,3.3); \fill[black!60] (0.1467,3) rectangle (0.1680,3.3); \fill[black!60] (0.1751,3) rectangle (0.1964,3.3); \fill[black!60] (0.2036,3) rectangle (0.2249,3.3); \fill[black!60] (0.2320,3) rectangle (0.2533,3.3); \fill[black!60] (0.2933,3) rectangle (0.3147,3.3); \fill[black!60] (0.3218,3) rectangle (0.3431,3.3); \fill[black!60] (0.3502,3) rectangle (0.3716,3.3); \fill[black!60] (0.3787,3) rectangle (0.4000,3.3); \fill[black!60] (0.6000,3) rectangle (0.6213,3.3); \fill[black!60] (0.6284,3) rectangle (0.6498,3.3); \fill[black!60] (0.6569,3) rectangle (0.6782,3.3); \fill[black!60] (0.6853,3) rectangle (0.7067,3.3); \fill[black!60] (0.7467,3) rectangle (0.7680,3.3); \fill[black!60] (0.7751,3) rectangle (0.7964,3.3); \fill[black!60] (0.8036,3) rectangle (0.8249,3.3); \fill[black!60] (0.8320,3) rectangle (0.8533,3.3); \fill[black!60] (0.8933,3) rectangle (0.9147,3.3); \fill[black!60] (0.9218,3) rectangle (0.9431,3.3); \fill[black!60] (0.9502,3) rectangle (0.9716,3.3); \fill[black!60] (0.9787,3) rectangle (1.0000,3.3); \fill[black!60] (0.0000,4) rectangle (0.0034,4.3); \fill[black!60] (0.0045,4) rectangle (0.0079,4.3); \fill[black!60] (0.0090,4) rectangle (0.0124,4.3); \fill[black!60] (0.0134,4) rectangle (0.0169,4.3); \fill[black!60] (0.0179,4) rectangle (0.0213,4.3); \fill[black!60] (0.0284,4) rectangle (0.0319,4.3); \fill[black!60] (0.0329,4) rectangle (0.0363,4.3); \fill[black!60] (0.0374,4) rectangle (0.0408,4.3); \fill[black!60] (0.0419,4) rectangle (0.0453,4.3); \fill[black!60] (0.0464,4) rectangle (0.0498,4.3); \fill[black!60] (0.0569,4) rectangle (0.0603,4.3); \fill[black!60] (0.0614,4) rectangle (0.0648,4.3); \fill[black!60] (0.0658,4) rectangle (0.0693,4.3); \fill[black!60] (0.0703,4) rectangle (0.0737,4.3); \fill[black!60] (0.0748,4) rectangle (0.0782,4.3); \fill[black!60] (0.0853,4) rectangle (0.0887,4.3); \fill[black!60] (0.0898,4) rectangle (0.0932,4.3); \fill[black!60] (0.0943,4) rectangle (0.0977,4.3); \fill[black!60] (0.0988,4) rectangle (0.1022,4.3); \fill[black!60] (0.1033,4) rectangle (0.1067,4.3); \fill[black!60] (0.1467,4) rectangle (0.1501,4.3); \fill[black!60] (0.1511,4) rectangle (0.1546,4.3); \fill[black!60] (0.1556,4) rectangle (0.1590,4.3); \fill[black!60] (0.1601,4) rectangle (0.1635,4.3); \fill[black!60] (0.1646,4) rectangle (0.1680,4.3); \fill[black!60] (0.1751,4) rectangle (0.1785,4.3); \fill[black!60] (0.1796,4) rectangle (0.1830,4.3); \fill[black!60] (0.1841,4) rectangle (0.1875,4.3); \fill[black!60] (0.1886,4) rectangle (0.1920,4.3); \fill[black!60] (0.1930,4) rectangle (0.1964,4.3); \fill[black!60] (0.2036,4) rectangle (0.2070,4.3); \fill[black!60] (0.2080,4) rectangle (0.2114,4.3); \fill[black!60] (0.2125,4) rectangle (0.2159,4.3); \fill[black!60] (0.2170,4) rectangle (0.2204,4.3); \fill[black!60] (0.2215,4) rectangle (0.2249,4.3); \fill[black!60] (0.2320,4) rectangle (0.2354,4.3); \fill[black!60] (0.2365,4) rectangle (0.2399,4.3); \fill[black!60] (0.2410,4) rectangle (0.2444,4.3); \fill[black!60] (0.2454,4) rectangle (0.2489,4.3); \fill[black!60] (0.2499,4) rectangle (0.2533,4.3); \fill[black!60] (0.2933,4) rectangle (0.2967,4.3); \fill[black!60] (0.2978,4) rectangle (0.3012,4.3); \fill[black!60] (0.3023,4) rectangle (0.3057,4.3); \fill[black!60] (0.3068,4) rectangle (0.3102,4.3); \fill[black!60] (0.3113,4) rectangle (0.3147,4.3); \fill[black!60] (0.3218,4) rectangle (0.3252,4.3); \fill[black!60] (0.3263,4) rectangle (0.3297,4.3); \fill[black!60] (0.3307,4) rectangle (0.3342,4.3); \fill[black!60] (0.3352,4) rectangle (0.3386,4.3); \fill[black!60] (0.3397,4) rectangle (0.3431,4.3); \fill[black!60] (0.3502,4) rectangle (0.3536,4.3); \fill[black!60] (0.3547,4) rectangle (0.3581,4.3); \fill[black!60] (0.3592,4) rectangle (0.3626,4.3); \fill[black!60] (0.3637,4) rectangle (0.3671,4.3); \fill[black!60] (0.3681,4) rectangle (0.3716,4.3); \fill[black!60] (0.3787,4) rectangle (0.3821,4.3); \fill[black!60] (0.3831,4) rectangle (0.3866,4.3); \fill[black!60] (0.3876,4) rectangle (0.3910,4.3); \fill[black!60] (0.3921,4) rectangle (0.3955,4.3); \fill[black!60] (0.3966,4) rectangle (0.4000,4.3); \fill[black!60] (0.6000,4) rectangle (0.6034,4.3); \fill[black!60] (0.6045,4) rectangle (0.6079,4.3); \fill[black!60] (0.6090,4) rectangle (0.6124,4.3); \fill[black!60] (0.6134,4) rectangle (0.6169,4.3); \fill[black!60] (0.6179,4) rectangle (0.6213,4.3); \fill[black!60] (0.6284,4) rectangle (0.6319,4.3); \fill[black!60] (0.6329,4) rectangle (0.6363,4.3); \fill[black!60] (0.6374,4) rectangle (0.6408,4.3); \fill[black!60] (0.6419,4) rectangle (0.6453,4.3); \fill[black!60] (0.6464,4) rectangle (0.6498,4.3); \fill[black!60] (0.6569,4) rectangle (0.6603,4.3); \fill[black!60] (0.6614,4) rectangle (0.6648,4.3); \fill[black!60] (0.6658,4) rectangle (0.6693,4.3); \fill[black!60] (0.6703,4) rectangle (0.6737,4.3); \fill[black!60] (0.6748,4) rectangle (0.6782,4.3); \fill[black!60] (0.6853,4) rectangle (0.6887,4.3); \fill[black!60] (0.6898,4) rectangle (0.6932,4.3); \fill[black!60] (0.6943,4) rectangle (0.6977,4.3); \fill[black!60] (0.6988,4) rectangle (0.7022,4.3); \fill[black!60] (0.7033,4) rectangle (0.7067,4.3); \fill[black!60] (0.7467,4) rectangle (0.7501,4.3); \fill[black!60] (0.7511,4) rectangle (0.7546,4.3); \fill[black!60] (0.7556,4) rectangle (0.7590,4.3); \fill[black!60] (0.7601,4) rectangle (0.7635,4.3); \fill[black!60] (0.7646,4) rectangle (0.7680,4.3); \fill[black!60] (0.7751,4) rectangle (0.7785,4.3); \fill[black!60] (0.7796,4) rectangle (0.7830,4.3); \fill[black!60] (0.7841,4) rectangle (0.7875,4.3); \fill[black!60] (0.7886,4) rectangle (0.7920,4.3); \fill[black!60] (0.7930,4) rectangle (0.7964,4.3); \fill[black!60] (0.8036,4) rectangle (0.8070,4.3); \fill[black!60] (0.8080,4) rectangle (0.8114,4.3); \fill[black!60] (0.8125,4) rectangle (0.8159,4.3); \fill[black!60] (0.8170,4) rectangle (0.8204,4.3); \fill[black!60] (0.8215,4) rectangle (0.8249,4.3); \fill[black!60] (0.8320,4) rectangle (0.8354,4.3); \fill[black!60] (0.8365,4) rectangle (0.8399,4.3); \fill[black!60] (0.8410,4) rectangle (0.8444,4.3); \fill[black!60] (0.8454,4) rectangle (0.8489,4.3); \fill[black!60] (0.8499,4) rectangle (0.8533,4.3); \fill[black!60] (0.8933,4) rectangle (0.8967,4.3); \fill[black!60] (0.8978,4) rectangle (0.9012,4.3); \fill[black!60] (0.9023,4) rectangle (0.9057,4.3); \fill[black!60] (0.9068,4) rectangle (0.9102,4.3); \fill[black!60] (0.9113,4) rectangle (0.9147,4.3); \fill[black!60] (0.9218,4) rectangle (0.9252,4.3); \fill[black!60] (0.9263,4) rectangle (0.9297,4.3); \fill[black!60] (0.9307,4) rectangle (0.9342,4.3); \fill[black!60] (0.9352,4) rectangle (0.9386,4.3); \fill[black!60] (0.9397,4) rectangle (0.9431,4.3); \fill[black!60] (0.9502,4) rectangle (0.9536,4.3); \fill[black!60] (0.9547,4) rectangle (0.9581,4.3); \fill[black!60] (0.9592,4) rectangle (0.9626,4.3); \fill[black!60] (0.9637,4) rectangle (0.9671,4.3); \fill[black!60] (0.9681,4) rectangle (0.9716,4.3); \fill[black!60] (0.9787,4) rectangle (0.9821,4.3); \fill[black!60] (0.9831,4) rectangle (0.9866,4.3); \fill[black!60] (0.9876,4) rectangle (0.9910,4.3); \fill[black!60] (0.9921,4) rectangle (0.9955,4.3); \fill[black!60] (0.9966,4) rectangle (1.0000,4.3); \end{tikzpicture} \caption{$\proZ$ as limits of $\Z/n!\Z$} \end{figure} \begin{remark} $\Mr{\infty}{10^{\infty}}$. \end{remark} % \subsection{Discrete Dynamical System on Profinite Integers} \subsection{Metrics} \begin{definition}[Period function $\p$] The \demph{period function} $\p \colon \Np \to \Np$ sends a positive integer $n\in \Np$ to the minimum positive integer $\p(n)\in \Np$ such that \[ \forall x\in (\Z/n\Z)^{\times},\; x^{\p(n)} \equiv 1 \mod n. \] \end{definition} \begin{lemma}\label{lem:ExplicitDescriptionOfPeriodFunction} For a positive integer $n=2^e\times p_1^{e_1} \times \dots \times p_k^{e_k}$, $\p(n)$ is the least common multiple of \begin{itemize} \item $\begin{cases} 1 & (e=0,1)\\ 2 & (e=2)\\ 2^{e-2} & (e\geq 3)\\ \end{cases}$, and \item $(p_i -1)p_i^{e_i -1}$ for each $1\leq i \leq k$. \end{itemize} \end{lemma} \begin{proof} This follows from the following fact \[ (\Z/p^e\Z)^{\times} \cong \begin{cases} \Z/1\Z &(p=2, e=1)\\ \Z/2\Z \times \Z/2^{e-2}\Z &(p=2, e\geq 2)\\ \Z/(p-1)p^{e-1} \Z &(p>2, e\geq 1), \end{cases} \] and the group isomorphism \[ (\Z/n\Z)^{\times} \cong (\Z/2^e\Z)^{\times} \times (\Z/p_1^{e_1})^{\times}\times \dots \times (\Z/p_k^{e_k})^{\times}. \] \end{proof} \begin{definition}[Jump function]\label{def:JumpFunction} The \demph{jump function} $\j \colon \Np \to \Np$ is the right adjoint of $\p \colon \Np \to \Np$. \end{definition} \begin{para}{Explicit construction of $\j$.} % \begin{proof}[Explicit construction of $\j$.] Let $n\in \Np$ be a positive integer, and % Let $1=d_0< \dots 1$, then we have $\p(n)0\text{ and }f\text{: constant}\}\\ \mathrm{PI}&=\{f(x)\in \N[x]\mid f(0)>0\text{ and }f\text{: increasing}\}, \end{align*} % By considering an equivalence relation $\simeq$ as we obtain a $4$-elements riegs $\{\mathrm{ZC},\mathrm{ZI},\mathrm{PC},\mathrm{PI}\}$ as a quotient rieg. \memo{There are several things to check here. But all of them are straightforward.} \memo{The underlying rig is the freely generated rig with a generator $x$ and two equations $1+1=1$ and $x^2=x$.} This rieg satisfies $1+1 = 1$, but the underlying rig is not a lattice since $1+x\neq 1$. % \begin{itemize} % \item $\mathrm{ZC}=\{f(x)\in \N[x]\mid f(0)=0\text{ and }f\text{: constant}\}$ % \item $\mathrm{ZI}=\{f(x)\in \N[x]\mid f(0)=0\text{ and }f\text{: increasing}\}$ % \item $\mathrm{PC}=\{f(x)\in \N[x]\mid f(0)>0\text{ and }f\text{: constant}\}$ % \item $\mathrm{PI}=\{f(x)\in \N[x]\mid f(0)>0\text{ and }f\text{: increasing}\}$ % \end{itemize} \end{example} \memo{reference for lattice theory} \begin{proposition}[Rieg and Lattice]\label{prop:WhenIsARiegALattice} For a rieg $R$, the following conditions are equivalent: \begin{enumerate} \item The underlying rig is a (bounded) lattice. \label{ConditionLattice1} \item For any $x\in R$, $1+x=1$. \label{ConditionLattice2} \end{enumerate} \end{proposition} \begin{proof} The implication $\text{\ref{ConditionLattice1}}\implies \text{\ref{ConditionLattice2}}$ follows from the fact that $1$ is the maximum element in a lattice. We prove \ref{ConditionLattice1} from \ref{ConditionLattice2}. Substituting $x$ with $1$, we obtain $1+1=1$, i.e., this rieg is idempotent (\Cref{def:idempotentRieg}). Now it is enough to prove the absorption laws \begin{align*} x+xy&=x\\ x(x+y)&=x. \end{align*} It is proven as $x(x+y) = x^2 +xy = x+xy = x(1+y)=x1=x$. \end{proof} \memo{The condition \ref{ConditionLattice2} is called \demph{absorbing} (with respect to addition).} \subsection{Heyting algebras are riegs} A Heyting algebra is not just related but is a rieg satisfying additional equations. \begin{proposition} Every Heyting algebra $(H,0,1,\lor,\land, \leftarrow)$ is a rieg. \end{proposition} \begin{proof} We can directly prove this. Alternatively, this is also an immediate corollary of \Cref{PropositionbiCCC}, since a Heyting algebra is a bicartesian closed category whose underlying category is a poset. \end{proof} \begin{example}[A rieg that is a lattice but not a Heyting algebra] Let $\Po{X}$ be the power set of a non-empty set $X$, equipped with a rig structure given by $\emptyset, X, \cup$ and $\cap$. We consider a rieg structure on $\Po{X}$ that is different from \Cref{ExamplePowerset}. First, fix an arbitrary element $x\in X$ and define the exponential as \[ A^B\coloneqq \begin{cases} A & (x\in B)\\ X & (x \notin B). \end{cases} \] This rieg structure is given by the composition of two rig homomorphisms. The first one is a rig homomorphism to the rig of truth value $\2 = \{\bot, \top\}$ defined as \[\Po{X} \to \2\colon A \mapsto \dq{x\in X}.\] The other is the unique rig homomorphism \[\2 \to \End{(\Po{X}, X, \cap)},\] which sends $0\in \2$ to the constant funciton $\mathrm{const}_{X}\colon \Po{X} \to \Po{X}$ and $1\in \2$ to the identity function $\mathrm{id}_{X}\colon \Po{X} \to \Po{X}$. \memo{Since rig homomorphisms $\Po{X} \to \2$ correspond to ultrafilters on $X$, we can construct similar rieg structure for each ultrafilter $\mathcal{F}$ on $X$. The above example is the special case where $\mathcal{F}$ is a principal filter generated by $x\in X$.} % where $\2$ denotes the rieg of truth values. % \begin{itemize} % \item $\Po{X}\to \2= \{\bot, \top\}$ % \item $\2 \to \End{(\Po{X}, X, \cap)}$ % \end{itemize} If $X$ has at least two elements, this rieg is not a Heyting algebra, because \[\{x\}^{\{x\}}=\{x\}\neq X.\] \end{example} \begin{proposition} A rieg $R$ is a Heyting algebra, if and only if it satisfies the following additional equations: \begin{itemize} \item $1+x=1$ % \item $x\ti x=x$ % \item $1+1=1$ %$x+x = x$ \item $x^x =1$ % \item $x(y+1)=x$ %$$xy+y=y$ % \item $x^{y+1}=x$ %$y y^x = y$ % \item $(x+y)y=y$ \item $x y^x = xy$ \end{itemize} \end{proposition} \memo{Are all of them necessary?} \begin{corollary} The category of Heyting algebras $\HeyAlg$ is a reflective full subcategory of the category of riegs $\Rieg$. \[ \begin{tikzcd} \HeyAlg \ar[r, shift right, hookrightarrow]&\Rieg \ar[l, shift right] \end{tikzcd} \] \end{corollary} The construction of the left adjoint is the usual one: quotient by new equations. For example, the associated Heyting algebra of $\N$ is the Heyting algebra of truth values $\{\bot, \top\}.$\footnote{This particular example is a trivial case, since a left adjoint preserves colimits.} The relation between Heyting algebras and riegs is not an addition of structures, but an addition of properties. In this respect, it is closer to the relationship between abelian groups and groups rather than to the relationship between rings and groups. \memo{Full sub. Birkhoff's theorem} \memo{Is it Malcev?} \appendix \section{Preliminaries on equational theory and profinite topology} In this section, let $\T$ be a (finite arity single-sorted) algebraic theory. We are especially interested in the case $T= \text{(the theory of riegs)}$. The category of $\T$-algebras is denoted by $\TAlg$. \subsection{Characteristic of \texorpdfstring{$\T$}{T}-algebras}\label{ssec:generaltheoryOfCharacteristics} From an abstract point of view, this definition 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} 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.} \subsection{Categorical properties of riegs (and general \texorpdfstring{$\T$}{T}-algebras)} \begin{remark}[Categorical properties of riegs] Several category-theoretic properties of $\Rieg$ immediately follow from the mere existence of an equational definition by the theory of categorical universal algebra. Some of them are noted below. % However, if you are not familiar with category theory, you can ignore them, since most of the content of this paper is understandable without them. \begin{itemize} \item The category of riegs $\Rieg$ has all small limits and colimits. \item Furthermore, the forgetful functor $U\colon \Rieg \to \Set$ (preserves and) creates all limits. \item The forgetful functor $U\colon \Rieg \to \Set$ has a left adjoint $F\colon \Set \to \Rieg$ \item Every rieg homomorphism $f\colon R \to S$ is uniquely (up to the canonical isomorphism) decomposed into the composition of a surjective homomorphism followed by an injective homomorphism $R \twoheadrightarrow \Image(f) \rightarrowtail S$. \end{itemize} This means we can construct arbitrary small limits using limits in $\Set$. For a given family of riegs $\{R_{\lambda}\}_{\lambda\in \Lambda}$, its categorical product is given by the product set $\prod_{\lambda\in \lambda} R_{\lambda}$ with the index-wise operations. \begin{proposition}[Free forgetful adjunction] \end{proposition} Furthermore, we have a variation of the homomorphism theorem: \begin{proposition}[Surj-inj factorization system] \end{proposition} \end{remark} An element of the free rieg $F(\{x\})$ looks like \[(3^{x}+x^{x^{x}})^{x^{2^{x}}+5^{x+0^{x}}+1}+0^{x} x.\] \subsection{Topological \texorpdfstring{$\T$}{T}-algebras and their profinite completion}\label{ssec:GeneralTheoryOfProfiniteAlgebras} A \demph{topological $\T$-algebra} is a model of $\T$ in the category $\Top$, that is, a $\T$-algebra equipped with a topology such that all operations of $\T$ are continuous. Morphisms of topological $\T$-algebras are continuous $\T$-algebra homomorphisms. The category of topological $\T$-algebras is denoted by $\TTAlg$. It is straightforward to verify the next lemma. \begin{lemma}[Limits in the topological $\T$-algebras]\label{lem:LimitsofTopologicalAlgebras} $\TTAlg$ admits all small limits, which are preserved by the two forgetful functors $\TTAlg\to \TAlg$ and $\TTAlg\to \Top$. \end{lemma} In otherwords, a small limit in $\TTAlg$ is just the limit at the underlying set level equipped with the canonical $\T$-algebra structure and the initial topology. % For a \begin{notation} % For a $\T$-algebra $R$, % \end{notation} For a given $\T$-algebra $R$, a \demph{quotient} $\T$-algebra is a surjective $\T$-algebra homomorphism $R\twoheadrightarrow Q$ (up to the canonical isomorphisms). The quotients of $R$ form a complete lattice $\Quo(R)$, in which $Q\geq Q'$ if and only if there exists a $\T$-algebra homomorphism $Q\twoheadrightarrow Q'$ that commutes with the associated surjection from $R$. By the definition of order, there is the canonical functor $\Quo(R)^{\op} \to \TAlg$. Let $\fQuo(R)$ denote the subposet of $\Quo(R)$ that consists of all finite quotient $\T$-algebras. \begin{definition}[Profinite completion of a $\T$-algebra] For a $\T$-algebra $R$, its \demph{profinite completion} $\pro{R}$ is the limit of all finite quotients of $R$. In other words, $\pro{R}$ is the limit of the following diagram: \[ {\fQuo(R)}^{\op} \to \TAlg \xrightarrow{\text{discrete}} \TTAlg. \] \end{definition} \begin{remark}[As a codensity monad] It is much more natural to define the profinite completion as an endofunctor on the category $\TTAlg$ although we will not need it in the present paper. The category of finite (and discrete) $\T$-algebras $\finTAlg$ is a full subcategory of the category $\TTAlg$, and the codensity monad of the embedding $\finTAlg \hookrightarrow \TTAlg$ is the profinite completion. \end{remark} The profinite completion admits a metric structure defined by \dq{distinguishing distance.} \begin{definition} For a $\T$-algebra \end{definition} \begin{proposition}[] \end{proposition} \begin{remark} Pro(finite $\T$-algebra) and $\T$-algerba on a profintie space. Jonsson-Tarski algebras... ? \end{remark} \subsection{Profinite topology and ultrametric on a profinite set} In this subsection, let $J$ be a small category, $F\colon J \to \FinSet$ be a functor, and $\{\alpha_j\colon P \to Fj\}_{j\in \ob(J)}$ be a limit cone over the functor \[ J \xrightarrow{F} \FinSet \xrightarrow{\text{discrete}} \Top. \] As a topological space, $P$ is profinite, i.e. compact Hausdorff and totally disconnected. (This is a well known fact, for example, see \memo{Cite} for a proof.) \begin{definition}[distinguishing value] For two elements $p,q \in P$, we define its \demph{distinguishing value} $r(p,q)\in \N\sqcup\{\infty\}$ by \[ v(p,q) \coloneqq \inf\{|Fj| \in \N\mid j\in \ob(J), \;\alpha_j(p) \neq \alpha_j(q)\}. \] \end{definition} \begin{lemma}\label{lem:LemmaForUltrametric} With the above settings, we have the following: \begin{enumerate} \item For any $p, q\in P$, we have $v(p,q) = \infty \iff p=q$. \item For any $p,q \in P$, we have $v(p,q) = v(q,p)$. \item For any $p,q,r$, we have $\min (v(p,q), v(q,r)) \leq v(p,r)$. \end{enumerate} \end{lemma} \begin{proof} To prove $(1)$, we observe that $p=q$ if and only if $\alpha_j(p) = \alpha_j(q)$ for any $j\in \ob(J)$ if and only if $v(p,q) = \infty$. $(2)$ is trivial by definition. We prove $(3)$. If $p=r$, then $(1)$ implies $v(p,r)=\infty$, and the inequality. If $p\neq r$, let $j\in \ob(J)$ be an object such that $\alpha_j(p)\neq \alpha_j(r)$ and $v(p,r) = |F_j|$. Then, either $\alpha_j(p) \neq \alpha_j(q)$ or $\alpha_j(q) \neq \alpha_j(r)$ holds. Therefore, either $v(p,q) \leq |Fj| = v(p,r)$ or $v(q,r) \leq |Fj| = v(p,r)$ holds. This implies the inequality. \end{proof} \begin{proposition}\label{prop:UltrametricOfProfiniteDiagram} The function $d(p,q)\coloneqq 2^{-v(p,q)}$ is an ultrametric over the set $P$, that is, $(P, d)$ satisfies the following conditions. \begin{enumerate} \item For any $p, q\in P$, we have $d(p,q) = 0 \iff p=q$. \item For any $p, q\in P$, we have $d(p,q) = d(q,p)$. \item For any $p, q, r\in P$, we have $\max(d(p,q),d(q,r)) \geq d(q,r)$. \end{enumerate} \end{proposition} \begin{proof} This follows from \Cref{lem:LemmaForUltrametric}. \end{proof} In this metric space, the inequality $d(p,q) \leq \frac{1}{2^N}$ holds if and only if $|Fj|0$. Then let $N$ be the minimum natural number such that $\frac{1}{2^N}< \epsilon$. By the assumption, we take an object $t_N\in \ob(J)$ with the required conditions. We prove that the open subset $p\in \alpha_{t_N}^{-1}\alpha_{t_N}(p) \in \mathcal{O}_{\text{initial}}$ is subsumed by the $\epsilon$-ball of the point $p$. Take an arbitrary element $q\in \alpha_{t_N}^{-1}\alpha_{t_N}(p)$. Then, for any $j\in \ob(J)$ with $|F_j|0$, the \demph{radical} of $n$, which is denoted by $\rad(n)$, is the maximum sqare-free devisor of $n$. \end{definition} In other words, the radical of $n={p_1}^{k_1}\dots {p_l}^{k_l}$ is defined by \[\rad(n)\coloneqq p_1 \cdots p_k.\] For example, $\rad(2025)=\rad(3^4 \cdot 5^2)=3\cdot 5 = 15$. $H(n)$ and $\rad(n)$ are mutually strongly related. $\H(n)$ is the minimum natural number $h\geq 0$ such that $n$ divides $\rad(n)^{h}$. Conversely, $\rad(n)$ is the maximum divisor $r\mid n$ such that $H(r)=1$. \begin{proof}[Proof of \Cref{thm:BurrisLeeTheorem}] Assuming $\Mr{a}{b}$ has a rieg structure, we will prove $b$ is a shifted-Carmichael 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 \Cref{lem:AlgebraicCharacterizationOfShifted_CarmichaelNumbers}, $b$ is shifted-Carmichael. 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 \H(b)$, we obtain \[\rad(b) ^a\equiv 0 \mod{b},\] equivalently, $a\geq \H(b)$. Conversely, assuming that $b$ is a shifted-Carmichael 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 $00). \end{array} \right. \] The rieg of natural numbers is a subrieg of this rieg. However, the subset of all non-negative rational numbers is not subrieg, since it is not closed under exponentials. \memo{The rieg $[0,\infty)$ is not a $\Top$-internal rieg, since $\ex$ is not continuous. Then, the rig of non-negative continuous functions is not closed under element-wise exponentials. How about non-negative $L^1$ functions?} \memo{(J. Koizumi) exp-preserving function $(0,\infty)\to (0,\infty)$ is either the constant function to $1$ or the identity function.} \end{example} \begin{remark}[The rig ${[0,\infty]}$ is not a rieg]\label{RemarkExtendedReals} It is natural to ask whether this rieg structure can be extended to the rig $[0,\infty]$. The answer is no. The rig ${[0,\infty]}$ cannot have a rieg structure. Suppose that there is an extension to a rieg structure. First, since $2^{\infty}=2^{\infty+1}= 2^{\infty} \ti 2$, we have $2^{\infty}\in \{0,\infty\}$. And, since $2^{\infty}(0.5)^{\infty} = 1^{\infty} =1$, we have $2^{\infty}\in (0,\infty)$, contradiction. \end{remark} \subsubsection{Finite system of numbers} % The overflow rieg with threshold $1$ will appear soon (\Cref{ExampleRiegOfTruthValues}) as the rieg of truth values. \memo{threshold $2$ is also theoretically important: $\{0,1, \mathrm{plural}\}$. $2^{\infty}\neq 1^{\infty}$} Is it possible to perform modular arithmetic in rieg theory? In fact, this question is of great importance in the development of general rieg theory, especially the theory of characteristics, and will be discussed in detail. \memo{Rieg of functions with first-order differential coefficients} \memo{What's called the exponential ring of complex numbers} \memo{Some example from Heyting, e.g. max-min of [0,1]} \memo{max-plus algebra} \subsubsection{Numbers with Infinites} There are some riegs, wth \dq{infinites}. This cannot happen for a (non-trivial) ring, because $0+\infty = 1+ \infty$ implies $0=1$. \begin{example}[Cardinal numbers] The cardinal arithmetic also has the structure of a rieg. However, one must be careful about the size problem, since the class of all cardinal numbers is a proper class, not a set. The familiar solution is to assume the existence of a Grothendieck universe, but there is no need to go to such great lengths. We can simply take a strong limit cardinal $\kappa$ (for example, $\beth_{\omega}$) and consider the set of all cardinal numbers less than $\kappa$. Then this set has a rieg structure by cardinal arithmetic. When $\kappa = \aleph_0$, this is the rieg of natural numbers. \memo{The regularity of $\kappa$ is not needed here, but in some situations, it may be useful to take a strong limit cardinal with cofinality greater than $\omega$, such as $\beth_{\omega_1}$).} \memo{Relation to topos} \end{example} \memo{Under the GCH (generalized continuum hypothesis), the rieg induced from $\beth_{\omega}$($=\aleph_{\omega}$ by the GCH) is worth mentioning.} \memo{And, forcing can access this rieg structure.} % The next example cannot be realized with substitution operations. In this sense, it is $$ \begin{example}[Complemented natural numbers] $\N\cup\{\infty\}$ has a canonical rieg structure, which is obtained as the limit of the overflow riegs \[ \begin{tikzcd} \dots\ar[r]&\OF_{2}\ar[r]&\OF_{1}\ar[r]&\OF_{0}. \end{tikzcd} \] In this sense, this rieg is the overflow rieg with threshold $\infty$. \memo{$[0,\infty]$ does not have a rieg structure} Notice that this construction is similar to the construction of $p$-adic integers. % In \Cref{SubsectionProfinite}, we will see the profinite completion of $\N$, which is a refinement of $\N\cup\{\infty\}$ \end{example} \subsubsection{Lists of numbers} \subsubsection{Rig with many rieg structures} \label{sssection:rigwithmany} \begin{example}[Rieg of dual numbers \memo{Constructed by Yuhi Kamio}] \label{exmp:RiegofDualNumbers} Recall that a dual number is a number plus an \dq{infinitesimal number} \[a+b\ep \ (a,b \in \R)\] The ring of infinitesimal numbers is denoted by $\R[\ep]$ and algebraically defined as $\R[\ep]=\R[x]/(x^2).$ There is a similar rieg, which we call the \demph{dual number rieg.} \begin{definition}[Dual numbers, concrete definition]\label{SubsubsectionDualNumbers} The dual number rieg $\N[\ep]$ has $\N \times \Z$ as the underlying set and its element $(n,m)$ is denoted by $n+m\epsilon$. Three operations are defined as follows: \begin{enumerate} \item $(n+m\ep)+ (n'+m'\ep)=(n+n')+(m+m')\ep$ \item $(n+m\ep)\ti (n'+m'\ep)=(nn')+(nm'+n'm)\ep$ \item $(n+m\ep)\ex (n'+m'\ep)=\underbrace{(n+m\ep)\ti \dots \ti (n+m\ep)}_{n' \text{times}} = (n^{n'}, n^{n'-1}n'm\ep).$ \end{enumerate} \end{definition} \end{example} This definition has a more conceptual paraphrase, with which we can easily prove that it's actually a rieg. First notice that the projection \[\N[\ep]\to \N\colon n+m\ep \mapsto n\] is a rig homomorphism to the initial rig $\N$. Thus we have the composite rig homomorphism \[\N[\ep]\to \N\to \End(\N[\ep],\ti,1),\] and this gives the exponential structure of the dual number rieg. More generally, we have the following proposition. \begin{proposition}[Rieg structure by a natural number evaluation]\label{PropositionNNevaluation} For a rig $R$ and a rig homomorphism (or say, \dq{natural number evaluation}) \[v\colon R \to \N,\] $R$ admits an induced rieg structure \[R \to \N \to \End(R,\ti,1).\] \end{proposition} In other words, the exponential is given by \[x^y = \underbrace{x\ti\dots \ti x}_{v(y)\text{ times}}.\] For example, we can replace the additive group $\Z\ep$ in the definition of the dual number rieg with an arbitrary commutative monoid. \begin{example}\label{ExamplePolynomialexp} In \Cref{PropositionNNevaluation}, letting $v\colon R \to \N$ be the evaluation function \[\mathrm{ev}_0 \colon \N[x]\to \N \colon x\mapsto 0,\] we have a rieg structure on $\N[x]$ with \[f(x)^{g(x)} = f(x)^{g(0)}= \underbrace{f(x)\ti\dots \ti f(x)}_{g(0)\text{ times}}.\] \end{example} \begin{example}[Rieg of polynomials] \label{exmp:PolynomialRieg} Is it possible to have more than one rieg structure on a single rig? The answer is (not at all surprisingly) yes. A typical example is the rig of polynomials $\N[x]$. Since $\N[x]$ is the free rig with a generator $x$, rieg structures on $\N[x]$ \[\N[x] \to \End(\N[x],\ti,1)\] bijectively correspond to the elements of $\End(\N[x],\ti,1).$ \end{example} \begin{example}[Shift operator] \end{example} \subsection{Riegs of three elements} The degenerate rieg $\1$ is the unique $1$-element rieg. The rieg of truth values $\2$ is the unique $2$-element rieg. This subsection aims to provide all $3$-element riegs. \begin{proposition}[$3$-element riegs] There are $8$ isomorphism classes of $3$-element riegs. \end{proposition} Let $R$ be a $3$-element rieg. There are three possible characteristics $\ch(R) = (1,1), (1,2), (2,1)$. \para{Case 1: $\ch(R) = (1,2), (2,1)$} If $\ch(R) = (1,2), (2,1)$, then $R$ is the parity rieg (\Cref{exmp:ParityRieg}) or the overflow rieg with the threshold $2$ (\Cref{exmp:OverflowRiegs}). \para{Case 2: $\ch(R) = (1,1)$} So we need to classify all $3$-element riegs with characteristics $\ch(R) = (1,1)$. Let $R= \{0,1,a\}$. We distinguish cases based on the value of $1 + a$. \para{- Case 2.1: $\ch(R) = (1,1)$ and $1+a=1$} If $1+a=1$, then the rieg $R$ satisfies the equation $1+x=1$, which means that the underlying rig of $R$ is the lattice $(\{0=Latex, scale=1, every node/.style={scale=1}] \coordinate (O1) at (0,0); \coordinate (A1) at (0,2); \coordinate (B1) at (0,4); \coordinate (O2) at (1,0); \coordinate (A2) at (1,2); \coordinate (B2) at (1,4); \filldraw (O1) circle (2pt) node[left] {$0$}; \filldraw (A1) circle (2pt) node[left] {$a$}; \filldraw (B1) circle (2pt) node[left] {$1$}; \filldraw (O2) circle (2pt) node[right] {$0$}; \filldraw (A2) circle (2pt) node[right] {$a$}; \filldraw (B2) circle (2pt) node[right] {$1$}; \draw[dashed] (O1) -- (A1) -- (B1); \draw[dashed] (O2) -- (A2) -- (B2); \draw[->, line width=0.6pt] (O1) -- (O2); \draw[->, line width=0.6pt] (A1) -- (A2); \draw[->, line width=0.6pt] (B1) -- (B2); \coordinate (O3) at (2.5,0); \coordinate (A3) at (2.5,2); \coordinate (B3) at (2.5,4); \coordinate (O4) at (3.5,0); \coordinate (A4) at (3.5,2); \coordinate (B4) at (3.5,4); \filldraw (O3) circle (2pt) node[left] {$0$}; \filldraw (A3) circle (2pt) node[left] {$a$}; \filldraw (B3) circle (2pt) node[left] {$1$}; \filldraw (O4) circle (2pt) node[right] {$0$}; \filldraw (A4) circle (2pt) node[right] {$a$}; \filldraw (B4) circle (2pt) node[right] {$1$}; \draw[dashed] (O3) -- (A3) -- (B3); \draw[dashed] (O4) -- (A4) -- (B4); \draw[->, line width=0.6pt] (O3) -- (A4); \draw[->, line width=0.6pt] (A3) -- (A4); \draw[->, line width=0.6pt] (B3) -- (B4); \coordinate (O5) at (5,0); \coordinate (A5) at (5,2); \coordinate (B5) at (5,4); \coordinate (O6) at (6,0); \coordinate (A6) at (6,2); \coordinate (B6) at (6,4); \filldraw (O5) circle (2pt) node[left] {$0$}; \filldraw (A5) circle (2pt) node[left] {$a$}; \filldraw (B5) circle (2pt) node[left] {$1$}; \filldraw (O6) circle (2pt) node[right] {$0$}; \filldraw (A6) circle (2pt) node[right] {$a$}; \filldraw (B6) circle (2pt) node[right] {$1$}; \draw[dashed] (O5) -- (A5) -- (B5); \draw[dashed] (O6) -- (A6) -- (B6); \draw[->, line width=0.6pt] (O5) -- (O6); \draw[->, line width=0.6pt] (A5) -- (B6); \draw[->, line width=0.6pt] (B5) -- (B6); \coordinate (O7) at (7.5,0); \coordinate (A7) at (7.5,2); \coordinate (B7) at (7.5,4); \coordinate (O8) at (8.5,0); \coordinate (A8) at (8.5,2); \coordinate (B8) at (8.5,4); \filldraw (O7) circle (2pt) node[left] {$0$}; \filldraw (A7) circle (2pt) node[left] {$a$}; \filldraw (B7) circle (2pt) node[left] {$1$}; \filldraw (O8) circle (2pt) node[right] {$0$}; \filldraw (A8) circle (2pt) node[right] {$a$}; \filldraw (B8) circle (2pt) node[right] {$1$}; \draw[dashed] (O7) -- (A7) -- (B7); \draw[dashed] (O8) -- (A8) -- (B8); \draw[->, line width=0.6pt] (O7) -- (B8); \draw[->, line width=0.6pt] (A7) -- (B8); \draw[->, line width=0.6pt] (B7) -- (B8); \end{tikzpicture} \caption{The four possible exponentiations $x \mapsto x^a$} \label{fig:FourExponentials} \end{figure} \para{- Case 2.2: $\ch(R) = (1,1)$ and $1+a=a$} The only remaining case is $1+a=a$, since $1+a=0$ is impossible (\Cref{prop:riegIsNotRing}). Since $R$ is idempotent (\Cref{def:idempotentRieg}), the underlying rig structure is determined: \[ R \cong \langle a \mid 1+1=1, 1+a=a, a^2=a\rangle \text{ in } \Rig \] Therefore, the rieg structures on $R$ are in bijective correspondence with monoid homomorphisms $\phi \colon (R, 1, \ti) \to (R,1,\ti)$ with \begin{itemize} \item $x \ti x = x$, which always holds \item $x\ti\phi(x) = \phi(x)$, and \item $\phi^2(x) = \phi(x)$. \end{itemize} There are two such morphisms visualized in \Cref{fig:TwoExponentials}. \begin{figure}[htbp] \centering \begin{tikzpicture}[>=Latex, scale=1, every node/.style={scale=1}] \coordinate (O1) at (0,0); \coordinate (A1) at (0,2); \coordinate (B1) at (0,4); \coordinate (O2) at (1,0); \coordinate (A2) at (1,2); \coordinate (B2) at (1,4); \filldraw (O1) circle (2pt) node[left] {$0$}; \filldraw (A1) circle (2pt) node[left] {$a$}; \filldraw (B1) circle (2pt) node[left] {$1$}; \filldraw (O2) circle (2pt) node[right] {$0$}; \filldraw (A2) circle (2pt) node[right] {$a$}; \filldraw (B2) circle (2pt) node[right] {$1$}; \draw[->, line width=0.6pt] (O1) -- (O2); \draw[->, line width=0.6pt] (A1) -- (A2); \draw[->, line width=0.6pt] (B1) -- (B2); \coordinate (O3) at (3.5,0); \coordinate (A3) at (3.5,2); \coordinate (B3) at (3.5,4); \coordinate (O4) at (4.5,0); \coordinate (A4) at (4.5,2); \coordinate (B4) at (4.5,4); \filldraw (O3) circle (2pt) node[left] {$0$}; \filldraw (A3) circle (2pt) node[left] {$a$}; \filldraw (B3) circle (2pt) node[left] {$1$}; \filldraw (O4) circle (2pt) node[right] {$0$}; \filldraw (A4) circle (2pt) node[right] {$a$}; \filldraw (B4) circle (2pt) node[right] {$1$}; \draw[->, line width=0.6pt] (O3) -- (O4); \draw[->, line width=0.6pt] (A3) -- (O4); \draw[->, line width=0.6pt] (B3) -- (B4); \end{tikzpicture} \caption{The two possible exponentiations $x \mapsto x^a$} \label{fig:TwoExponentials} \end{figure} % \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!} % % % % \input{2023_07_23Ver/riegsOfPropositions0729} \printbibliography \end{document}