Consider the set of all discrete functions from $\mathbb F\_q^2$ to $\mathbb F\_q$ (denote it by $\mathcal F(\mathbb F\_q^2, \mathbb F\_q)$, the cardinality $|\mathcal F(\mathbb F\_q^2, \mathbb F\_q)| = q^{q^2}$). Some of the functions can be computed just from the *value* of others, i.e.
$$
f(x,y) = \phi\_{f,g} (g(x,y)),
$$
where $\phi\_{f,g} : \mathbb F\_q \to \mathbb F\_q$ in general depends on $f$ and $g$.


Some particular examples:


* shift by a constant ($a \in \mathbb F\_q$): $f(x,y) = g(x,y) + a$
* multiplication by a constant: $f(x,y) = a \cdot g(x,y)$
* raising to a power $t < q$: $f(x,y) = (g(x,y))^t$. If $t \geq q$ we can reduce it, as $a^q = a$ for any $a \in \mathbb F\_q$ and therefore $(g(x,y))^{t} = (g(x,y))^{t-q+1}$ for all $x,y \in \mathbb F\_q$.
* and others.


I want to build the minimum subset $\mathcal G \subset \mathcal F(\mathbb F\_q^2, \mathbb F\_q)$ such that every function in $\mathcal F(\mathbb F\_q^2, \mathbb F\_q)$ can be calculated from one function from $\mathcal G$. In other words, for each $f \in \mathcal F(\mathbb F\_q^2,\, \mathbb F\_q)$ there exist $g = g\_f \in \mathcal G$ and $\phi = \phi\_{f,g\_f} : \mathbb F\_q \to \mathbb F\_q$ such that
$$
f(x, y) = \phi (g(x,y)), \quad \forall x,y \in \mathbb F\_q.
$$


What could such subset $\mathcal G$ be? Or, at least, what could its cardinality be?


P.S. What are possible generalisations to the case of $k$-ary functions, i.e. $f : \mathbb F\_q^k \to \mathbb F\_q$?



Discrete functions as functions of value of another function
This is essentially counting the number of partitions of a set of $q^2$ labelled elements into $q$ unlabelled groups. (This generalizes to counting surjective maps from one labelled set onto a smaller set.) This is because you only ask for a "rewriting of the output" by a unary function on the range set. I believe the Twelvefold Way (in the context of Enumerative Combinatorics) includes this case as a way of enumerating such maps.


A more general situation than the one described is where one is allowed to permute the inputs, either by individual functions on each variable or by switching the variables, or both. The exact enumeration of this is more challenging, but usually dividing by the size of the suggested automorphism group generated by the input transformations leads to a correct or at least target asymptotic for the number of representatives of the class you seek.


Gerhard "This Is Candidate For Migration" Paseman, 2019.03.26.


