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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.