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?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.