Are there known patterns among minimal expressions?

Question

Let $R = F[z_1, z_2, \dots]$ be the finite-degree polynomials in a countable number of variables. Let $\mathcal{E}(R)$ be the set of all expressions of polynomials. Note that there could be an infinite number of expressions involving the symbols $(, ), +, -, \cdot, z_1, z_2, \dots, a \in F$ that correspond to the same single polynomial.

Consider all minimal expressions of polynomimals in $R$. Let $E$ be an expression for polynomial $f$, then a minimal expression for $f$ is one in which $\Phi(E)$ is minimal where $\Phi : \mathcal{E}(R) \to \Bbb{R}$ is defined as a mapping from expressions that counts the number of operations to directly compute the expression, i.e. given $\Phi(+) := b, \ \Phi(-) := b, \ \Phi(\cdot) := c$ the unique map $\Phi$ such that, $\forall A, B \in \mathcal{E}(F)$,

1. $\Phi(A - B) = \Phi(-) + \Phi(A) + \Phi(B)$
2. $\Phi(A + B) = \Phi(+) + \Phi(A) + \Phi(B)$
3. $\Phi(AB) = \Phi(\cdot) + \Phi(A) + \Phi(B)$
4. $\Phi(z) = 0, \ \forall z \in F$
5. $\Phi(x_i) = 0, \ \forall i = 1 \dots k$

Then is there more we can say? Can we construct a sequence of minimal expressions $E_k$ each in $k$ variables such that $f(k) = \Phi(E_k)$ is not dominated by any polynomial function $f: \Bbb{N} \to \Bbb{R}$?

What about combining minimal expressions. If $E_1, E_2$ are minimal then is $E_1(z_1, \dots, E_2, \dots)$ minimal, or if not, then is it true if $E_1$ involves only variables disjoint from $E_2$'s variables? Stuff like that.

Thank you.

Answer 1

Define $\mathcal{E}(R)$ to be the set of all admissible expressions of polynomials in $R$, define it recursively by:

1. $r \in \mathcal{E}, \ \forall r \in F$.
2. $z_i \in \mathcal{E}, \ \forall i = 1, 2\dots$
3. $E_1, E_2 \in \mathcal{E} \implies (E_1) \cdot (E_2) \in \mathcal{E}$
4. $E_1, E_2 \in \mathcal{E} \implies E_1 + E_2, \ E_1 - E_2 \in \mathcal{E}$
5. $E \in \mathcal{E} \implies E' = {\rm Sym}(E) \in \mathcal{E}$, where $Sym(E)$ is a symbol referring to $E$

For simplicity and convenience let all atomic operations occur in time $1$. Then a run-time computing function $f$ for the algorithms specified in $\mathcal{E}(R)$ can be defined by applying the following rules in this order:

1. $f(r) = f(z_i) = 0, \ \forall r, i$
2. $f(+) = f(-) = f(\cdot) = 1$
3. $f((E)) = f(E)$
4. $f(E_1 \cdot E_2) = f(\cdot) + f(E_1) + f(E_2)$
5. $f(E_1 + E_2) = f(+) + f(E_1) + f(E_2)$
6. $f(E_1 - E_2) = f(-) + f(E_1) + f(E_2)$
7. $f({\rm Sym}(E)) = f(E)$ (the first time, and...) $0$ afteward.

There's a group that acts level sets of $f$. This is accomplished with a permutation of $+, -, \cdot$, followed by a permutation of $F \cup \{z_1, z_2, \dots \}$. Check the rules and see that $f$ is unchanged by such an operation. Then group acting on the level sets is $S_3 \times S_{\infty}$. If we consider only expressions in $k$ variables, $\mathcal{E}(F[z_1, \dots, z_k])$, then said group becomes finite when $F$ is a finite field.