Can primitive recursive functions be simulated in the smallest reasonable primitive recursive group?

Question

Second Edition, completely rewritten with unchanged questions.

The said questions are motivated by the bizarre wording of the concluding § in A Class of Reversible Primitive Recursive Functions by L. Paolini, M. Piccolo & L. Roversi (Electronic Notes in Theoretical Computer Science 322 (2016) 227–242, doi:10.1016/j.entcs.2016.03.016, author pdf).
Kudos to the 2 upvoters for making sense of the 1st Ed.: 2 days after posting it, I couldn't & came up with this. Apologies and thanks to the 100+ viewers for your efforts & special thanks to Andrej Bauer for your sharp questioning.

The paper itself is not problematic. It purports to simulate the usual set of primitive recursive functions (PRF) by means of carefully chosen bijections from $\mathbb{Z}_∗$, the free monoid over the signed integers, to itself. Then, they proceed the other way around, to simulate those bijections using PRF's; which, it turns out, amounts to simulate all the members of the group they generate.

I attempt here to make sense of their concluding remark by rephrasing it in group-theoretic terms. Sorry if it is old moons to you, and any comments to that effect are welcome: all this is way beyond the fields I know.
So, I shall explain my terminology at some tedious length, before I can restate the results of the Paolini-Piccolo-Roversi paper and only then, ask my questions. Meaning you might find the post more entertaining by reading it from the bottom up; you're welcome to try.

---

The locus dramatis is the group $U_p$ of bijective functions from $\mathbb{Z}^p$ to itself, with group law the composition of functions and unit the identity $I_p$; and the disjoint union thereof $U_*=\bigsqcup_{p \in N} U_p$.

In my ignorance of established terminology, I chose the following; again, your comments are welcome if you know any better.

• Identifying tuples from $\mathbb{Z}^p$ with words from the free monoid $\mathbb{Z}_*$, we let $|w|$ denote the size of the tuple $w$ & $(w_1, w_2)$ denote $w_1$ concatenated with, i. e. followed by, $w_2$, and identify $\mathbb{Z}$ with $\mathbb{Z}^1$;

• a denizen of $U_p$ has arity at most $q$ if, up to conjugation by some reordering of its $p$ arguments, it is equal to the Cartesian product $f_q \times I_{p-q}$ for some $f_q \in U_q$;

• lifting concatenation to an operation over $U_*$, we rewrite $f_q \times I_{p-q}$ as $(f_q, I_{p-q})$ and extend every bijection $ f \in U^p$ to a bijection $ (f, I_\infty) : \mathbb{Z}[X] \to \mathbb{Z}[X]$.

• This switch, from the free monoid $\mathbb{Z}_*$ to polynomials $\mathbb{Z}[X]$, disposes of technicalities about how to feed a function with a word too short for its taste: just zero-pad it the way you pad a polynomial with null terms to match degree requirements;

• this promotes $U_*$ to the status of a group acting on $\mathbb{Z}[X]$: the group of (bijections of) fixed arity with values in $\mathbb{Z}$;

• From now on, the subscript $q$ in $f_q \in U_p$ will systematically denote the arity of $f$: the smallest $q$ such that $f$ has arity at most $q$. By exception, all the $I_q$'s remain available for tuple juggling, as aliases of the identity function: $I_0$, the unit element of $U_*$ and the only one of arity $0$.

So much for the preliminaries! Finally,

• groups acting on $\mathbb{Z}_*$ have a unique feature: an exponentiation defined over the whole group. As usual, $f^k$ in $U_p$ denotes $f$ composed $k$ times with itself for all $k \in \mathbb{Z}$ : $f^0 = I_0$, $f^{-z} = (f^{-1})^z$. Then, the exponentiated $f_q$ is the bijection $f_q^* : (z, w_q) \to (z, f_q^z(w_q))$ for all $(z, w_q) \in \mathbb{Z}^1 \times \mathbb{Z}^q$; it has arity $q+1$.
• With $U_*$ closed under exponentiation, a minimally recursive group is any subgroup of $U_*$ that is closed under exponentiation and under permutations of (finite subsets of) function arguments; and,
• for any subset $S$ of $U_*$, the primitive recursive group generated by $S$, denoted $R_*(S)$, is the smallest subgroup of $U_*$ containing $S$ that is minimally recursive. $R_p(S)$ is $R_*(S) \cap U_p$.

Beware, gentle reader!!! My choice of terms is far from ideal. It suggests $R_*(S)$ is the natural representative of the usual PRF's in reversible computing; however, it is only true if the set of generators is neither too small, nor too rich. More on this in a moment.

---

In the above setting, the primitive recursive group chosen by Paolini–Piccolo–Roversi has 4 generators: the unit translation I denote $++ : \mathbb{Z}^1 \to \mathbb{Z}^1$; a zero-testing bijection: $\mathbb{Z}^2 \to \mathbb{Z}^2$ that maps $(0, 0)$ to $(0, 1)$ and $(z, 0)$ to itself, $z \ne 0$; a pairing bijection $\mathbb{Z}^3 \to \mathbb{Z}^3$ that maps $\mathbb{Z}^2 \times \{0\}$, bijectively, to $\mathbb{Z}^1 \times \{0\}^2$; an unpairing bijection that provides the inverse mapping, $\mathbb{Z}^1 \times \{0\}^2 \to \mathbb{Z}^2 \times \{0\}$.
That this $R_*(S)$ contains simulations of all the PRF's and conversely, can be simulated by PRF's, is not in question; I take it for granted.

The bizarre conclusion is, they regard an "open issue" whether the pairing function is "independent from the remaining functions" (sic); said functions being, I surmise, the other generators of their group.
At first glance, the issue seems to me closed and tightly barred with a negative answer: there are PRF's that map bijectively $\mathbb{N}^2$ to $\mathbb{N}$, and it looks like an easy programming exercice to extend one to a pairing fucntion in $R_*(S)$, as soon as it features a zero-testing bijection.
In other words: if $S$ is restricted to the fist 2 generators, $R_*(S)$ still contains the other 2; it just makes it all the easier to simulate $R_*(S)$ with PRF's.

In view of this, let me suggest a tougher issue: what if we also remove the zero-testing capability? In other, hopefully unambiguous, words:

Q1: if $S$ contains only translations over $\mathbb{Z}^1$, does the resulting group, $R_*(\{++\})$, contain a zero-testing bijection ? Such a function is any bijection from $\mathbb{Z}^p$ to itself that maps $(z, 0, 0_{p-2})$ to some $(z, b, w_{p-2}(z))$, with $b=1$ if $z=0$, else $0$.

As soon as one such bijection is found, it is a straightforward matter to build a cleaner one upon it, one of arity $p+1$ that maps $(z, 0, 0_{p-1})$ to $(z, b, 0_{p-1})$.

Given that concatenation & exponentiation behave well with respect to the Euclidean norm over $\mathbb{Z}^p$ and that, for $S$ as above, $R_p(S)$ contains the linear group over $\mathbb{Z}^p$, the next question cries out to be asked:

Q2: if $S$ is the orthogonal group over $\mathbb{Z}^{p-1}$, does $R_p(S)$ contain a zero-testing isometry? This one is a bijection from $\mathbb{Z}^p$ to itself, tweaked to preserve Euclidean norms: it maps $(z, 1, 0, a_{p-3})$, for some constant $a_{p-3}$ and any $z \in \mathbb{Z}$, to $(0, 1, 0, w_{p-3}(0))$ if $z=0$, else to $(z, 0, 1, w_{p-3}(z))$; with $w_{p-3}$ of size $p-3$, having the same norm as $a_{p-3}$ and otherwise unspecified.

The answer to Q1 is likely negative, which turns the group over 1 generator $R_*(\{++\})$ into a fairly exotic fellow: the smallest group with reasonable claims to be closed under some sort of recursion, yet too small to simulate the PRF"s.
It offers addition and iteration, hence a sizeable bit of linear algebra, even of polynomial algebra with substitution... only equality testing is wanting. Hence the title of this post, and my choice of the term "minimally recursive" .

I added Q2 out of curiosity and a personal distaste for undecidable questions: if my life depended on it, I would bet the answer to Q1 is "no or maybe undecidable" and the answer to Q2 "decidably no".

Answer 1

Why, shiver mey timbers! Q1 has a positive answer. I cannot believe I am the 1st to notice it, although I do not recall even hearing of it, as a classroom exercise or otherwise; if you know it in published form, kindly provide a link & I will be glad to credit the inventor.

So, we are looking for an algorithm that compares the integer $z$ with zero, using only incrementation and exponentiation. First, note those are enough to square integers, which reduces the problem to comparing the unsigned $z^2$ with $0$.

The key observation is, they are also enough to compute the quotient and remainder of the division of $n \ge 0$ by $2$: defining $Add_{1/2} : (n, b, c) \to (n+b, c, b)$, the exponential ${Add_{1/2}}^*$ maps $(2 \cdot n+b, 0, 0, 1)$ to $(2 \cdot n+b, n, b, 1-b)$.

Then, replace $2 \cdot n + b$ with $n$ and reiterate at least $\log_2 (n + 1)$ times, adding the successive remainders. This computes $L_2(n_0)$, the sum of the digits in the base 2 expansion of $n_0$, in ${} \le n_0$ iterations: $L_2(\sum_{k \ge 0} {b_k \cdot 2^k}) := \sum_{k \ge 0} b_k$. The function $L_2(n_0)$ only takes on the value 0 when $n_0 = 0$, otherwise it is ${} \ge 1$: almost the one we were looking for.

(Edited §, found a simplification). So, define the sequence $n_{k+1} := L_2(n_k)$; from any $n_0 \ge 1$ it falls in a few steps to $1$, where it remains stationary. This is because $L_2$ is strictly decreasing when $n_k \ge 2$. Whereas it is 0 whenever $k \ge n_0 = 0$.

Et voilà, your zero-testing function: $n_{n_0 + 1}$. It is a not-so-easy exercise, then, to make the computation reversible; however it is pure programming, not math. (Edited on second thoughts); not so pure. The usual programming trick to reversibly replace $2 \cdot n + b$ with $n$ by means of a pairing function is not available yet, and we must do with an arithmetic ersatz; it may help answer Q2 to expose it.

So: we have bijections $ Swap: (m, n) \to (n, m)$, $ Add(z): (n) \to (n + z)$ and $Halve(2 \cdot n + b): (z, 0, 1) \to (z+n, b, 1-b)$; we work with a 9-tuple $((2 \cdot n + b)_0, 0_1, 0_2, 1_3, l2_4, c_5, 0_6, 0_7, 1_8)$ where $c$ acts as a bit bucket, or rather a bit dump to throw used binary digits after reclaiming their component in the tuple.
Now, compose the following in sequence:

• compute quotient & remainder: $Halve((2 \cdot n + b)_0): (0_1, 0_2, 1_3) \to (n_1, b_2, (1-b)_3)$;
• add the remainder: $Add(b_2): (l2_4) \to ((l2+b)_4)$;
• reclaim component 0: $Add^{-2}(n_1): ((2 \cdot n + b)_0) \to (b_0)$; $Add^{-1}(b_2): (b_0) \to (0_0)$;
• lay $b$ on top of the dumped bits: $Add^2(c_5): (0_6) \to ((2 \cdot c)_6)$; $Halve^{-1}((2 \cdot c)_6): (c_5, 0_7, 1_8) \to (0_5, 0_7, 1_8)$; $Add(b_2): ((2 \cdot c)_6) \to ((2 \cdot c + b)_6)$;
• reclaim components 2 and 3: $Swap^{(2 \cdot c + b)_6}: (b_2, (1-b)_3) \to (0_2, 1_3)$.

The final tuple is $(0_0, n_1, 0_2, 1_3, (l2+b)_4, 0_5, (2 \cdot c + b)_6, 0_7, 1_8)$: swap components 0-1 and 5-6, and you are ready to iterate. In the end, component 4 will have grown from $0$ to $L_2(2 \cdot n + b)$ and component 0 dwindled from $(2 \cdot n + b)$ to $0$, swap them and you are ready to go for $n_{k+2}$.

I do not claim authorship for separating fixed from changing function arguments and for the notation $value_{index}$ and in the preceding §§: they are so natural, I probably reinvented the wheel as is my wont. Again, just provide a link to published material & I will gladly credit the inventor.

This leave Q2 open, although without computability-theoretical added value. Still, if you care to provide an answer, I will rather accept it than this one.