Factorization of polynomials into "shortest possible" factors

Question

A while ago I asked a question at Mathematica.SE about how to factorize a polynomial into terms with as few monomials as possible each. I now realized that I actually do not know what is rigorous mathematics behind this.

In fact that one was about univariate polynomials, and the same can be asked about several variables.

The question is whether there is some rigorous mathematics (algebra/geometry) behind asking for simultaneously minimizing the number of factors, and the number of monomials in each factor.

For an illustration, here is an example from that question: factorization of $$1 - q^8 - q^{11} - q^{14} + q^{19} + q^{22} + q^{25} - q^{33}$$into $\mathbb Q$-irreducibles is \begin{multline*}(1 - q)^3 (1 + q)^2 (1 + q^2) (1 + q^4) (1 - q + q^2 - q^3 + q^4 - q^5 + q^6)\\ (1 + q + q^2 + q^3 + q^4 + q^5 + q^6)\\ (1 + q + q^2 + q^3 + q^4 + q^5 + q^6 + q^7 + q^8 + q^9 + q^{10})\end{multline*} while "my" optimal expression would be$$(1 - q^8) (1 - q^{11}) (1 - q^{14}).$$

For many variables, and also allowing rational expressions, I would like to recognize in\begin{multline*}\left(x+y^3\right)^2 \left(x^2+y^6\right)^2 \left(x^2-x y^3+y^6\right) \left(x^2+x y^3+y^6\right) \left(x^4+y^{12}\right)\\ \left(x^4-x^2 y^6+y^{12}\right) \left(x^8+y^{24}\right)\end{multline*}that it is equal to$$\frac{\left(x^{12}-y^{36}\right) \left(x^{16}-y^{48}\right)}{\left(x-y^3\right)^2}$$

Answer 1

This is essentially a question about algebraic circuit complexity. Namely, we can consider formulas which are products of sums of powers of variables (which, using standard notation from circuit complexity, would be called "$\Pi\Sigma\wedge$ formulas"), and you are asking for the smallest expression which evaluates to your given polynomial.

Although I don't know about this particular class of formulas, typically questions of the form "Given a polynomial, what is the smallest formula or circuit in a given class $\mathcal{C}$ that computes it" are at least $\mathsf{NP}$-hard, which means there's unlikely to be an algorithm significantly better than a simple "brute-force" exponential algorithm. (And, even if you think maybe $\mathsf{P}=\mathsf{NP}$, I still wouldn't be holding my breath for a better algorithm any time soon.)

Geometrically, you can view all polynomials that have formulas of the form $\prod_{i=1}^d \sum_{j=1}^{d_i} (\text{powers of variables})$ as the image of a $d$-th Segre re-embedding of $d_i$-th secant varieties of Veronese embeddings. For examples of how this works with other circuit classes (which are better studied, both in complexity theory and in algebraic geometry), e.g. for $\Sigma\Pi\Sigma$ circuits, see Landsberg's article "Geometric complexity theory - an introduction for geometers" or his recent book "Geometry & Complexity Theory".