**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 azero-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 azero-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})$, forsomeconstant $a_{p-3}$ andany$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".

ad lib"? $\endgroup$ – Andrej Bauer Sep 3 '20 at 6:38one particular choice, and then say later that the choice did not matter. I am immediately suspicious about "arbitrary". How arbnitrary? Can I make it a non-bijection? Perhap I can start choosing things so that I sneak in some non-computability somewhere? I should not be worrying about these things before I understand the definitions. $\endgroup$ – Andrej Bauer Sep 3 '20 at 6:58understandyour question. $\endgroup$ – Andrej Bauer Sep 3 '20 at 9:03yourpatience. Yes, let's move to chat. $\endgroup$ – Andrej Bauer Sep 3 '20 at 9:173more comments