We wish to study integer recurrence systems of the form:

$$\left\{\begin{align} f_1(n) & = P_1\big(f_1(n-1), f_2(n-1), \ldots, f_k(n-1)\big)\\ f_2(n) & = P_2\big(f_1(n-1), f_2(n-1), \ldots, f_k(n-1)\big)\\ \vdots\\ f_k(n) & = P_k\big(f_1(n-1), f_2(n-1), \ldots, f_k(n-1)\big) \end{align}\right.$$

where the $P_i$'s are polynomials in $\mathbb{N}[x_1, x_2, \ldots, x_k]$, and given initial values for $f_i(0) \in \mathbb{N}$.

**Question:** Does there exist a characterization of the functions $f_1$ that can be obtained this way? Tools to show that some functions are not expressible?

**Examples:** The factorial function $n \mapsto n!$ is the function $f_1$ in:

$$\left\{\begin{align} f_1(n) & = f_2(n - 1) \times f_1(n - 1) & \text{ and } f_1(0) = 1\\ f_2(n) & = f_2(n-1) + 1 & \text{ and } f_2(0) = 1 \end{align}\right.$$

The square function is easy too, taking $f_1(n) = (f_2(n-1))^2$, but we believe that the function $n \mapsto (n^2)!$ is not doable.

We can have (double) exponential behaviors, for instance $n \mapsto 2^{2^n}$:

$$f_1(n+1) = f_1(n)^2 \text{ and } f_1(0) = 2\enspace,$$

or $n \mapsto 2^{n^2}$.