← Notes on Rieg Theory

Older Versions__2023_07_23Ver__ProfiniteIntegers.tex

\section{Finite and Profinite arithmetics}\label{SectionProfiniteConstruction}
% \label{SubsectionProfinite}
\subsection{Introduction}

% % {Modular arithmetic with exponentials}
\subsubsection*{Finite arithmetic}
In this section, we treat modular arithmetic with exponentials. As an introduction, let us consider the following typical elementary number theory problem, which can be solved by modular arithmetic:

\begin{problem}
Find all pairs of natural numbers $(n,m)$ such that
    \[2^n +5 =m^2.\]
\end{problem}
\begin{answer}
Consider the remainder by $8$. If $n$ is greater than or equal to $3$, the left-hand side is congruent with $5$, and the right-hand side is one of the square remainders of $8$, which are $0,1,4$, and it's absurd. Therefore, it suffices to check all the cases where $n=0,1,2$,  and we find that $(n,m)=(2,3)$ is the only solution.
\end{answer}

In this example, when considering exponentiation modulo $8$, we should divide \dq{first exceptions}, namely three numbers $n=0,1,2.$ 

 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.

 \subsubsection*{Profinite arithmetic}

 \cite[][Chapter 7, section 1/ Chapter 10, section 1]{khrennikov2004p}
 \memo{J.Koizumi}

 Consider the next question
 \begin{problem}
     Find a two-digit natural number $n$ such that the last two digits of $3^n$ are equal to $n$.
 \end{problem}
 \begin{answer}
     $n=87$ is the only answer.
 \end{answer}

  \begin{problem}
     Find a three-digit natural number $n$ such that the last three digits of $3^n$ are equal to $n$.
 \end{problem}
 \begin{answer}
     $n=387$ is the only answer.
 \end{answer}
 \begin{problem}
     Find a four-digit natural number $n$ such that the last four digits of $3^n$ are equal to $n$.
 \end{problem}
 \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 a infinite sequence \[\dots a_4 a_3 a_2 a_1\] of dicimal digits
     % $\a_i \in \{0,1,2,3,4,5,6,7,8,9\}$
     such that, for any $k\geq 1$, the number $n=a_k \dots a_1 $ (regarded as decimal notation) satisfies $3^n \equiv n \mod{10^k}$?
 \end{question}
 The answer is Yes! (See Figure \ref{PictureListOfthreetotheN}) 
 % 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}$}
 

 \begin{figure}[h]
    \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
    % \\
    % 3^{2464195387} &\equiv 2464195387 \mod{10000000000}\\
    % 3^{62464195387} &\equiv 62464195387 \mod{100000000000}\\
    % 3^{262464195387} &\equiv 262464195387 \mod{1000000000000}\\
    % 3^{7262464195387} &\equiv 7262464195387 \mod{10000000000000}\\
    % 3^{27262464195387} &\equiv 27262464195387 \mod{100000000000000}
    \end{align*}
    \caption{Solutions of $3^n=n \mod{10^k}$}
    \label{PictureListOfthreetotheN}
    \end{shaded}
\end{figure}

%  \begin{figure}
%     \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}\\
%     3^{2464195387} \equiv 2464195387 &\mod{10000000000}\\
%     3^{62464195387} \equiv 62464195387 &\mod{100000000000}\\
%     3^{262464195387} \equiv 262464195387 &\mod{1000000000000}\\
%     3^{7262464195387} \equiv 7262464195387 &\mod{10000000000000}\\
%     3^{27262464195387} \equiv 27262464195387 &\mod{100000000000000}\\
%     \end{align*}
%     \caption{$3^x=x$}
%     \label{PictureListOfthreetotheN}
%     \end{shaded}
% \end{figure}

% \subsubsection*{Theoretical motivation}

% There is another more theoretical motivation to classify all modulo riegs.
% For rings, the quotient rings of the initial ring $\Z$ are easily classified and described as $\Z/n\Z$ using natural numbers $n$. This classification is important even if you are not interested in integer ring $\Z$ itself. It is because it can be used to define the \emph{characteristic} of a ring $R$ (or usually, fields), considering the unique ring homomorphism
% \[\Z \to R \text{ in }\Ring\]
% and its surjection-injection factorization.

% We can establish similar characteristics theory for riegs, utilizing quotient algebras of the initial rieg $\N$ (i.e. modulo riegs) and
% % We call them \emph{modulo riegs}. 
% % As in the ring case, we can discuss the theory of rieg's \dq{characteristic}, 
% considering the unique rieg homomorphism
% \[\N \to R\text{ in }\Rieg\]
% and its surjection-injection factorization.

% Just as examining the prime ideals of an integer ring $\Z$ reveals that the characteristics of any fields are either zero or prime, examining the modulo rieg (of $\N$) leads to properties about arbitrary riegs.
% For example, see Corollary \ref{CorollaryClassificationOfCharacteristics}. 



\subsection{The complete lattice of characteristics}
The characteristic of a rieg, a priori, takes value in the complete lattice
\[
    \qTame \coloneqq \N \times \N_{>} \cup \{\chz\},
\]
equipped with the component-wise (usual, divisibility) order relation.
In Theorem \ref{TheoremPossibleChar}, we specified the realizable values, which are the elements of
\[\Tame = \{(a,b)\in \qTame\mid \text{$b$ is a tame number whose dimension is at most $a$}\},\]
which contains $\chz$ as well.

This order reration can be rephrased in terms of rigs and riegs:
\begin{proposition}
    For $(a,b), (a',b') \in \qTame$, $(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 \Tame$, $(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, $\qTame$ is isomorphic to the complete lattice of the quotient rigs of $\N$, and $\Tame$ is isomorphic to the complete lattice of the quotient riegs of $\N$.

\begin{lemma}\label{LemmaTameapprox}
    For any positive integer $b$, there is the minimum tame number $b'$ such that $b$ divides $b'$.
\end{lemma}
\begin{proof}
Here is a comcrete algorithm:
If $b$ is tame, then return $b$.
    If $b$ is not tame, then take the maximum prime number $p$ such that $p$ divides $b$ but $p-1$ does not divide $b$.
    And (recursively) return the minimum tame number $b'$ such that $\lcm (b, p-1)$ divides $b'$.

    This algorithm halts, since the taken prime number $p$ becomes smaller and smaller. It is easy to prove the minimality.
\end{proof}

\begin{example}[The minimum tame 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 tame number that is divided by $11$.
\end{example}

\begin{proposition}[Tame approximation]\label{PropositionTameapprox}
    For any $(a,b)\in \N\times \N_{>}$, there is the minimum $(a',b')\in \Tame$ such that 
    \[(a,b)\leq (a',b')< \chz.\]
\end{proposition}
\begin{proof}
    First, by Lemma \ref{LemmaTameapprox}, we can take the minimum tame number $b'$ that is divided by $b$. Then, $a'$ is defined to be $\max(a,\dim{(b)})$.
\end{proof}
This implies that the embedding (order-preserving) function
\[\Tame \hookrightarrow \qTame \]
has the left adjoint. \memo{This data defines a \dq{closure operator} on $\qTame$. but not preserving meets.}

As an immediate corollary, we obtain the following propositions.
\begin{proposition}
    $\Tame \setminus \{\chz\}$ 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 Proposition \ref{PropositionTameapprox} to $(0,n)\in \N\times \N_{>}$.
\end{proof}

\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{Discrete Dynamical System}
\subsection{Metrics}
% (related question: how about in $\Mr{\infty}{p^{\infty}}$)? This does not even exist!}
% \newpage
% \input{2023_07_23Ver/riegsOfPropositions0729}