Question

In relation to my question http://mathoverflow.net/questions/123058/expression-for-the-sum-of-square-roots-of-zeros-of-a-polynomial

How to characterize polynomials $f(x)$ with rational coefficients such that $f(x^2)=g(x)\cdot g(-x)$ where $g(x)$ is also a polynomial with rational coefficients?

Is there a computationally efficient way to identify if given polynomial $f(x)$ is such without factoring $f(x^2)$ ?

Answer 1

Letting $g(x) = \sum_0^n a_jx^j$, the coefficient of the $x^{2k}$ term in the product $g(x)g(-x)$ is precisely equal to $$ \alpha_k = \sum_{i+j = 2k} (-1)^j a_i a_j $$ So, if you are given some $f(y) = \sum_{k=0}^n \beta_k y^{k}$, you know that testing whether $f(x^2) = g(x)g(-x)$ reduces to solving the system of multivariate quadratic equations $\alpha_k = \beta_k$ where the $\beta_k$ are specified by your $f$ coefficients and the $\alpha_k$ are as above.

I think no matter which way you cut it, solving a multivariate quadratic system in general is NP hard and unless you get lucky with Buchberger's algorithm, I would not expect an efficient solution.

Update In response to the comment regarding factoring below, yes it is equivalent to testing if $f$ factors. The important thing is: we are testing for factorization rather than computing the factorization. I think the present formulation might offer certain advantages in the case when $f$ does not factor. A certificate of non-existence might be furnished by effective versions of Hilbert's Nullstellensatz.

For instance, if we define the $n+1$ shifted polynomials $$\gamma_k(a_0,\ldots,a_n) = \alpha_k(a_0,\ldots,a_n) - \beta_k,$$ and if there is no set of $a_0,\ldots,a_n$ which simultaneously makes the $\gamma_k$-s vanish, then there must exist polynomials $\delta_k$ so that $$\sum_{k=0}^n \gamma_k\delta_k = 1.$$ More importantly from a computational perspective, the total degree of each $\delta_k$ is bounded by $(n+1)^2 2^{n+1} + 2(n+1)$. For details, see the main theorem of:

Sharp Effective Nullstellensatz. Janos Kollar. Journal of the American Mathematical Society, Vol. 1, No. 4. (Oct., 1988), pp. 963-975

Answer 2

(Caveat: nothing in this response has been checked or even really thought through.)

If it's true with integral coefficients, it's true mod p for all p. Now the question of whether f(x^2) splits as g(x)g(-x) for f in F_p[x] is the question of whether f is a norm in the quadratic extension obtained by adjoining a square root of x, which should just be a question about whether each irreducible factor p(x) appearing an odd number of times in f splits in that quadratic extension. By quadratic reciprocity (I think) this comes down to whether each of these irreducible factors p(x) has p(0) a quadratic residue. This is easy enough to check for lots of p.

Of course, to have any hope, you need f(0) to be a square (as an integer) so I think in practice what I'd do would be to take a long list of primes p, reduce f mod p for each p, and if f factors into p_1(x) ... p_k(x) mod p, check that each p_i(0) is a residue. And if this keeps on happening you should gain confidence that your f(x^2) actually factors in this way.