Return to Question

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$

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?

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\}$.

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$

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$

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\}$.

Conjectured properties, which could maybe be proven:

• $\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$

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\}$.

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$