I am trying to prove the properties below, and by doing this, I hope to find a way to speed up the computation of the below defined addition and multiplication. I am also interested if these finite semirings are known (If the algebraic structure can be proven to be a semiring).
Context: I am interpreting the factorization trees, such as $T_{19}$ shown here, which knows the factorization of every number $1 \le m \le 19$, as decision trees for numbers which might be larger then $19$. For this interpretation I take every node of the tree as asking recursively the number $N$ a question concerning its smallest prime divisor.
Each number $N$ then is classified / projected on one of the numbers $1,\cdots,19$, which I denote as $\pi_n(N)$.
Idea: First we define $\pi_n(N):= \max_{ x \le N, x \in D(N) \cap [n]} x $, where $D(N)$ denotes the set of divisors of $N$ which are sorted with the lexicographic prime factorization ordering, which is denoted as $\le$ and the $\max$ is being taken with respect to this ordering and $[n]:=\{1,2,\cdots,n\}$.
Here are some values calculated for $\pi_n(N)$:
Properties of $\pi_n(N)$:
- $\forall m \leq n \in \mathbb{N}: \pi_n(m) = m$
- $\forall N \in \mathbb{N}: 1 \leq \pi_n(N) \leq n$
- $\forall N \in \mathbb{N}: \pi_n(N) \, | \, N$
- $\forall N \in \mathbb{N}: \pi_n(\pi_n(N)) = \pi_n(N)$
- (?) $\forall a,b \in \mathbb{N}: \pi_n(a \cdot b) \le \pi_n(a) \cdot \pi_n(b)$
We define the "successor" function on $[n]:=\{1,2,\ldots,n\}$:
$$ \psi: [n] \rightarrow [n] $$
$$ m \mapsto \pi_n(m+1) $$
We define addition on $[n]$ as $\oplus$:
$$ \oplus: [n] \times [n] \rightarrow [n] $$
$$(a , b) \mapsto \psi^{(b)}(a) = \psi(\psi(...(\psi(a))...))$$
where the successor function $\psi$ is iterated $b$ times.
We define the multiplication on $[n]$ as $\otimes$:
$$\otimes: [n] \times [n] \rightarrow [n]$$
$$ (a , b) \mapsto a \oplus a \oplus \ldots \oplus a $$
where the addition will be iterated $b$ times.
Conjectured properties of the operations
- $([n], \oplus,\otimes)$ is an abelian semiring (without neccessarily having a $0$ and a $1$).
Idea for notation
Idea for notation: $a \equiv b \operatorname{proj}(n)$ if and only if $\pi_n(a) = \pi_n(b)$.
Therefore,
- $a \operatorname{proj}(n) := \pi_n(a)$
- $a + b \operatorname{proj}(n) := \pi_n(a) \oplus \pi_n(b)$
- $a \cdot b \operatorname{proj}(n) := \pi_n(a) \otimes \pi_n(b)$ (Definition consisent on equivalence classes?)
Conjectured properties (semiring definition)
- $a + b \operatorname{proj}(n) \equiv b + a \operatorname{proj}(n)$
- $a \cdot b \operatorname{proj} \equiv b \cdot a \operatorname{proj}(n)$
- $a \cdot (b + c) \operatorname{proj}(n) \equiv a \cdot b + a \cdot c \operatorname{proj}(n)$
- $a + (b+c) \operatorname{proj}(n) \equiv (a+b) + c \operatorname{proj}(n)$
- $a \cdot (b \cdot c) \operatorname{proj}(n) \equiv (a \cdot b) \cdot c \operatorname{proj}(n)$
We get:
$$ a = b \iff \forall n \in \mathbb{N}: a \operatorname{proj}(n) \equiv b \operatorname{proj}(n) $$
If, $a = b \implies \forall n \in \mathbb{N}: \pi_n(a) = \pi_n(b)$, thus $a \equiv b \operatorname{proj}(n)$. On the other hand, if we let $n = \max(a,b)$, then $1 \leq a, b \leq n \implies a = \pi_n(a) = \pi_n(b) = b$.
Examples of addition and multiplication tables $\oplus$ for $n=1$ $$ \left(\begin{array}{r}1\end{array}\right) $$
$\otimes$ for $n=1$ $$ \left(\begin{array}{r}1\end{array}\right) $$
$\oplus$ for $n=2$ $$ \left(\begin{array}{rr}2 & 1 \\ 1 & 2 \end{array}\right) $$
$\otimes$ for $n=2$ $$ \left(\begin{array}{rr}1 & 2 \\ 2 & 2 \end{array}\right) $$
$\oplus$ for $n=3$ $$ \left(\begin{array}{rrr}2 & 3 & 2 \\ 3 & 2 & 3 \\ 2 & 3 & 2\end{array}\right) $$
$\otimes$ for $n=3$ $$ \left(\begin{array}{rrr} 1 & 2 & 3 \\ 2 & 2 & 2 \\ 3 & 2 & 3\end{array}\right) $$
$\oplus$ for $n=4$ $$ \left(\begin{array}{rrrr}2 & 3 & 4 & 1 \\ 3 & 4 & 1 & 2 \\ 4 & 1 & 2 & 3 \\ 1 & 2 & 3 & 4\end{array}\right) $$
$\otimes$ for $n=4$ $$ \left(\begin{array}{rrrr}1 & 2 & 3 & 4 \\ 2 & 4 & 2 & 4 \\ 3 & 2 & 1 & 4 \\ 4 & 4 & 4 & 4\end{array}\right) $$
$\oplus$ for $n=5$ $$ \left(\begin{array}{rrrrr} 2 & 3 & 4 & 5 & 2 \\ 3 & 4 & 5 & 2 & 3 \\ 4 & 5 & 2 & 3 & 4 \\ 5 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 2 \end{array}\right) $$
$\otimes$ for $n=5$ $$ \left(\begin{array}{rrrrr} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 2 & 4 & 2 \\ 3 & 2 & 5 & 4 & 3 \\ 4 & 4 & 4 & 4 & 4 \\ 5 & 2 & 3 & 4 & 5 \end{array}\right) $$
Visualization of addition and multiplication tables for $n=100$
Successor Graphs Let $G_n = ([n],E_n)$ be the directed graph defined on the vertices $[n]$ and between the vertices $a,b$ is an edge $a \rightarrow b \iff b = \pi_n(a+1)$.
Some graphs are shown in the following two tables.
We can see from this graphs a certain modularity and make the conjecture, that we have:
\begin{equation} a \oplus b = \begin{cases} a+b & \text{if } a+b \le n, \\ (a+b-\pi_n(n+1)) (\mod n-\pi_n(n+1)+1) + \pi_n(n+1), \text{ otherwise} \end{cases} \end{equation}
\begin{equation} a \otimes b = \begin{cases} a \cdot b & \text{if } a \cdot b \le n, \\ (a \cdot b-\pi_n(n+1)) (\mod n-\pi_n(n+1)+1) + \pi_n(n+1), \text{ otherwise} \end{cases} \end{equation}
These two equations could be used to speed up the computation of $\oplus, \otimes$ and would prove that the structure above is an abelian semiring.
Question: Can these two equation above about $\oplus,\otimes$ be proven?
