2
$\begingroup$

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.

$\endgroup$

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.