Finite algebraic structures where all hyperoperations (addition, multiplication, exponentiation, tetration, etc.) are well-defined

Let $$\langle R, +, \times, \uparrow, \uparrow\uparrow, \uparrow\uparrow\uparrow, \ldots; 0, 1\rangle$$ be an algebraic structure with two constants $$0, 1$$ and where an infinite sequence of binary hyperoperations is defined, such that that the following holds ($$x\uparrow y$$ will equivalently be denoted as $$x^y$$):

1. The substructure $$\langle R, +, \times, \uparrow, 0, 1\rangle$$ satisfies all of Tarski's identities plus $$x+0=x$$, $$x\times 0=0$$, $$x^0=1$$. In particular, $$\langle R, +, \times, 0, 1\rangle$$ is a commutative semiring.

2. All higher-order hyperoperations satisfy the identities $$x\uparrow^n 0 = 1$$, $$x\uparrow^n (y+1) = x\uparrow^{n-1} (x\uparrow^n y)$$ for all $$n\ge 2$$.

The paradigmatic example of such a structure is of course the infinite set of natural numbers $$\mathbb{N}$$. However, I'm interested in exploring examples of finite structures of this sort. To simplify the problem, I am for the moment focusing on structures which are "like $$\mathbb{N}$$" in the sense that all their elements can be obtained from $$0$$ by repeated incrementation. That is, we assume the following:

1. $$R$$ is additively generated by $$1$$ (all its elements can be put as a finite sum of the form $$1+1+\ldots+1$$, where the empty sum is taken to be $$0$$).

2. $$R$$ has finite cardinality as a set.

Alternatively, $$R$$ can be thought of as a finite model of Peano arithmetic, excluding the two axioms $$\forall m,n, (S(m)=S(n)) \implies (m=n)$$ and $$\forall n, S(n)\neq 0$$, and including the corresponding inductive definitions for all the hyperoperations.

Conditions 3 and 4 together imply that there must be an identity of the form

$$\underbrace{1+1+\ldots+1}_{b\: \text{times}} = \underbrace{1+1+\ldots+1}_{b+a\: \text{times}}$$

where $$a$$ is a positive integer and $$b$$ a nonnegative integer. Since this identity must be invariant under the sucessor function $$x \mapsto x+1$$ and equality is transitive, this means that any such structure must be a finite quotient of $$\mathbb{N}$$ of the form $$\mathbb{N}/(a\mathbb{N}+b)$$, where $$a\mathbb{N}+b$$ is the congruence relation where two distinct numbers are identified iff they are both greater than $$b$$ and they differ by a multiple of $$a$$ (which we will denote by $$x \equiv y \mod_{\ge b} a$$).

Thanks to the distributive property, it's straightforward to check that multiplication can be uniquely defined in any quotient of this form, turning it into a semiring. I'm fairly sure this part of my reasoning is correct, as for example this answer from MathOverflow reaches the same conclusion.

However, exponentiation cannot always be consistently defined for arbitrary $$a$$ and $$b$$. For example, we have $$2\equiv 5 \mod_{\ge 0} 3$$ but $$2^2 \not\equiv 2^5 \mod_{\ge 0} 3$$, so the ring $$\mathbb{N}/(3\mathbb{N}+0) \cong \mathbb{Z}/\mathbb{3Z}$$ is not compatible with exponentiation (in fact no nontrivial ring can be compatible with exponentiation, since if $$1$$ has an additive inverse we must have $$1 = 0^0 = 0^{-1 + 1} = 0^{-1} \times 0 = 0$$).

Ordinary modular exponentiation has the property

$$k^{\nu(n)} \equiv k^{\nu(n)+\lambda(n)} \mod_{\ge 0} n,$$

for any integer $$k$$, where $$\lambda(n)$$ is the Carmichael function of $$n$$ and $$\nu(n) = \max_{p\mid n} \nu_p (n)$$ is the maximum exponent appearing in the prime factorization of $$n$$ (with $$\nu(1) = 0$$). Since $$k^b \ge b$$ for any $$k \ge 2$$ and nonnegative $$b$$, we have that the congruence

$$k^b \equiv k^{a+b} \mod_{\ge b} a$$

will hold for any $$k$$ if $$\lambda(a) \mid a$$ and $$\nu(a) \le b$$. Call $$\Lambda$$ the set of pairs $$(a,b)$$ satisfying these two conditions (the set of possible $$a$$ form the sequence A124240 in OEIS). The property $$m \mid n \implies (\lambda(m) \mid \lambda(n)) \land (\nu(m) \le \nu(n))$$ implies that $$(\lambda(a), \nu(a)) \in \Lambda$$ whenever $$(a, b) \in \Lambda$$, so that power towers of arbitrary height can be consistently defined in $$\mathbb{N}/(a\mathbb{N}+b)$$. The corresponding congruence relation satisfies $$\forall k\in R, \quad (s\equiv t) \implies (s+k\equiv t+k) \land (s\times k\equiv t\times k) \land (s^k\equiv t^k) \land (k^s\equiv k^t)$$ (the first three congruences on the right side come from basic modular arithmetic), so all of Tarski's identities, which hold in $$\mathbb{N}$$, will be preserved when taking the quotient.

As for higher order hyperoperations, this is where I have the most doubts. I could only think of two further restrictions:

• First, base-zero tetration $$0 \uparrow \uparrow k$$ for $$k\in \mathbb{N}$$ defines a periodic sequence of period 2 alternating between $$1$$ and $$0$$. If we are to have $$0 \uparrow \uparrow b = 0 \uparrow \uparrow (b+a)$$, either $$a$$ is even or we get the trivial case $$0=1$$.

• In this answer it is shown that modular tetration $$x \uparrow \uparrow k \mod_{\ge 0} a$$ for any nonzero $$x$$ is eventually constant as $$k \to \infty$$; call the limiting value $$\hat{x}$$ and $$L(a)$$ the least number such that $$x \uparrow \uparrow L(a) \equiv \hat{x}$$ for all $$x$$. A sufficient condition for $$x\uparrow \uparrow b \equiv x\uparrow \uparrow (b+a) \mod_{\ge b} a$$ to hold, then, is to simply choose $$b \ge L(a)$$ such that both numbers are congruent to $$\hat{x}$$. I believe this condition is also necessary, since if we choose $$b \le L(a) - 1$$ then there is some $$y$$ for which $$y\uparrow\uparrow (L(a)-1)$$ is not congruent to $$y\uparrow\uparrow (L(a)-1+a) \equiv \hat{y}$$.

These two restrictions also apply for higher-order hyperoperations, as they eventually reduce to repeated tetration. Call $$\Lambda^*$$ the set of pairs $$(a,b) \in \Lambda$$ satisfying the two extra conditions $$2 \mid a$$ and $$L(a) \le b$$.

If I haven't made any mistake so far, the quotients $$\mathbb{N}/(a\mathbb{N}+b)$$ with $$(a,b) \in \Lambda^*$$ are then examples of finite structures compatible with the whole sequence of hyperoperations. The only other finite structure of this sort which is a quotient of $$\mathbb{N}$$ would be the trivial ring with $$0=1$$.

My question is:

Is my whole reasoning so far essentially correct? Are there any other restrictions that I missed?

EDIT (23-06-2021): I found some literature regarding finite semirings with exponentiation. They seem to be known as HSI-algebras in this context, since Tarski's identities are sometimes referred to as the High School Identities. In particular, Theorem 1.1 of this article confirms that the only finite quotients $$\mathbb{N}/(a\mathbb{N}+b)$$ admitting exponentiation are the ones such that for any prime $$p$$ and $$e \in \mathbb{N}$$ we have $$p^e|a \implies e \le b \qquad \text{and} \qquad p|a \implies (p-1)|a,$$ which is equivalent to $$(a,b) \in \Lambda$$ (the theorem actually considers quotients of $$\mathbb{N}-\{0\}$$, but it can be easily extended to the case with $$0$$). I consider this part of the question settled.

• Is this question related? math.stackexchange.com/questions/700477 Jun 16 '21 at 14:59
• @MphLee I guess it is kind of related, but I don't really see how it might help in finding an answer, as I'm interested only in finite structures. Jun 17 '21 at 12:37
• Atm I have not time to work on this so take this as a possible hint. But in my opinion there is a point to mind when talking about having all the higher hyperoperations. Define $h_k(n):=a\uparrow^{k-1} n$ for a fixed $a$. As you notice in some $\mathbb Z_m$ not even exponentiation can be always defined consistently. Ideally we would lik to have, for a t least one $a$ a family of endofunctions $h_k:\mathbb Z_m\to \mathbb Z_m$ where $h_0(n)=n+1$, $h_0(n)=a+n$, $h_2$ is an endomorphism of $\mathbb Z_m$ and $h_{k+1}h_0=h_kh_{k+1}$ in general. (...) Jun 17 '21 at 13:15
• (...) The first thing to notice is that even if it is possible to obtain your structure for some $m$, and just a fixed $a\in\mathbb Z_m$, all the $h_k$ are elements of a finite monoid $\mathbb Z_m^{ \mathbb Z_m}$ that has $m^m$ functions. So there must exists a $k_0\leq m^m$ such that $h_{k_0}=h_k$ for $k<k_0$. Jun 17 '21 at 13:22
• @MphLee Yes, that's essentially what I would like to know. Of course, any answerer is welcome to expand on anything else they deem interesting (e.g. any explicit formula for $L(x)$, or asymptotics for the number of different hyperoperations as a function of $a$ and $b$, following your previous comments), but it's not strictly required. Jun 21 '21 at 16:01