Start with the $\mathbb{Q}$-vector subspace $V_0$ of the polynomial ring $Q[x_1,\ldots,x_n]$ spanned by $\{1,x_1,\ldots,x_n\}$. In each step, we can choose an element of the form $v_iv_i'$ for $v_i,v_i'\in V_i$, adjoin it to $V_{i}$ to obtain $V_{i+1}$.

Is there an algorithm that computes for a given finite subset $S$ the minimal number $n$ of steps needed such that there is a choice of $V_1,\ldots,V_n$ with $S\subset V_n$?

For example $S=\{x^2+x+1\}$ can be obtained in one step, use the trick $x^2+x+1 = x(x+1)+1$.

Another interesting example is Strassen's algorithm, which says in this language that the entries of a 2x2 matrix multiplication can be obtained in 7 steps, instead of the obvious 8 steps.

After reading this question, I would be surprised if such an algorithm is known in the generality I was asking for.


Your Answer

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

Browse other questions tagged or ask your own question.