# Properties of smallest expressions for polynomials, and potential proof.

See here for an intro. Smallest expressions for polynomials is analogous to smallest grammars for strings.

Let $R = \Bbb{Z}_p[x_1, \dots, x_k]$.

My goal is to prove that for any $\ \ h(k,p) = \max \{\Phi(f): f \text{ is a minimal expression for a polynomial in } \Bbb{Z}_p[x_1, \dots, x_k]\}$, grows polynomially in $k, p$.

Notice then that algorithms exist that make the problem solvable in $O(h(k,p))$. The problem being computing the value of a polynomial at any given input in $\Bbb{Z}_p^k$.

That would prove that there exists a fast algorithm for integer factorization, as there is a set of polynomial functions $\{P_i: i = 1\dots k\}$ for any function $g : \Bbb{Z}_p^k \to$ itself such that $g(\bar{x}) = (P_1(\bar{x}), \dots, P_k(\bar{x}))$.

Notice that we can construct some minimal expressions:

$\{x_1^{e_1} + \dots + x_k^{e_k} : e_i = 0 \dots p-2, \ \forall i\} \subset {\rm Min}(R)$

is known to be true, where '$\dots$' means the actual expression can be much longer and is not part of the expression.

Proof. Any expression sum of polynomial, constant & variable-disjoint, smallest expressions $E_1 + \dots + E_n$ is also a smallest expression as there's no way to form a product and any sum re-expression using grouping results in the same number of operations. Interestingly the same cannot be said about any product. Since $E_1^{100} E_2^{80}$, so far as $\Phi$ is defined, is more optimal written another way: $(E_1 E_2)^{80} E_1^{20}$, for instance.

Thus we may want to try to build the biggest possible smallest expressions of the finite set of polynomial maps $R$, by adding together disjoint smallest expressions.

Conjecture. There are no optimality gains for having less coefficients with $0$ in the sum-expansion (standard form) of a polynomial. Proof. Suppose that $E_1$ = $E_2$ with coefficient $c_i$ set to zero in its standard form. There's an optimality gain for $E_2$ iff $\Phi(E_2) \lt \Phi(\min(E_1))$. But $\Phi(E_2) \geq \Phi(E2(\dots, 0, \dots)) = \Phi(E_1) \geq \Phi(\min(E_1))$.

I will attempt now to construct a maximal smallest expression: (no proof yet)

It basically goes: use up the constants and the variables one by one until you're out (finiteness) and keep things as disjoint as possible for as long as possible. Also try to keep max height of nested expressions to a minimum. So,

\begin{align*} f(\bar{x}) &:= 1 + 2 x_1 + 3 x_2 + \dots + (k+1) x_k + \dots \\ &= 1 + x_1 (2 + (k+2)x_1) + x_2(3 + (k+3)x_3) + \dots + x_k((k+1) +(2k + 1)x_k) +\dots \\ &= 1 + x_1 (2 + x_1((k+2) + x_1(2k + 2))) + \dots \\ &= 1 + f_1(x_1) + f_2(x_2) + \dots f_k(x_k) + \dots \end{align*}

Here we still have an obvious sum of disjoint $f_i$. Where the $f_i$ are each of degree $p-2$ as $x_i^{p-1} = 1$ and can be evaluated in $O(p)$ time.

Now we have to introduce mixtures of variables. If we added $c_i x_1 x_2$ to the last expression above and combine $f_1(x_1) + c_i x_1 x_2 + f_2(x_2) := E_1$

Lemma. If $E_1, E_2$ are disjoint smallest expressions and $E_i \neq D^{\ell}$ for some $\ell \gt 1, \ i \in \{1,2\}$, then $E_1\cdot E_2$ is a smallest expression. Proof. If $E_1 \cdot E_2$ were not smallest, then there exists $E \equiv E_1 \cdot E_2$ such that $\Phi(E) \lt 1 + \Phi(E_1) + \Phi(E_2)$

If you're not aware of it, you should look into arithmetic circuit complexity [1]; in this framework, your function $\Phi(f)$ is (essentially) the minimum size of an arithmetic formula computing $f$.
In particular, let's call each of the operands $\cdot$, $+$, and $-$, a 'gate', and let's look at expressions with at most $S$ gates. Note that by your definition of 'expression', we can write any expression as a tree, where the leaf nodes are constants or variables, and where each non-leaf node is a gate that accepts two inputs (so in particular, if there are $S$ gates, there are $S+1$ leaves). Now, the number of rooted binary trees on $S+1$ labeled leaves is given by $(2S+1)!!$ [2]; since we need to choose one of 3 possibilities for each gate ($+$, $-$, or $\cdot$), this means there are $3^{S}(2S+1)!!$ different expressions. Asymptotically, this is at most something like $2^{O(S\lg S)}$.
On the other hand, the number of functions from $\mathbb{Z}_{p}^{k}$ to $\mathbb{Z}_{p}$ is given by $p^{p^{k}} = 2^{p^{k}\lg p}$. It follows that, by the pigeonhole principle, for all $S = o(p^k)$, there exists a function that cannot be computed by an expression $f$ with at most $S$ gates (or in your notation, $\Phi(f) \leq S$). Therefore $h(k, p)$ is at least $\Omega(p^{k})$, which unfortunately is exponential in $k$.
• Here's an overview of the argument: We start by estimating the number of expressions of size $S$; let's say there are at most $X$ of them. If $X$ is less than the total number of functions, then this means that some function cannot be represented by an expression of size at most $S$ (so in particular, its smallest representation has size at least $S$). Since this is true for all $S=o(p^k)$, there is some function whose smallest expression has size at least $p^k$. – jschnei Apr 19 '14 at 7:09
• (We could, of course, count the number of smallest expressions instead of expressions of any size, but this would just give a smaller value of $X$ and make the proof even stronger). – jschnei Apr 19 '14 at 7:11