9
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Is this question related? math.stackexchange.com/questions/700477 $\endgroup$
    – MphLee
    Jun 16 '21 at 14:59
  • 1
    $\begingroup$ @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. $\endgroup$
    – pregunton
    Jun 17 '21 at 12:37
  • $\begingroup$ 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. (...) $\endgroup$
    – MphLee
    Jun 17 '21 at 13:15
  • 2
    $\begingroup$ (...) 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$. $\endgroup$
    – MphLee
    Jun 17 '21 at 13:22
  • 1
    $\begingroup$ @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. $\endgroup$
    – pregunton
    Jun 21 '21 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.