2
$\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?

$\endgroup$

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.