10
$\begingroup$

In relation to my question 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)$ ?

$\endgroup$
4
  • $\begingroup$ Why don't you want to factor $f(x^2)$? Factorization algorithms are good and quite efficient. Not enough for you ? $\endgroup$
    – Lierre
    Feb 28, 2013 at 9:26
  • 1
    $\begingroup$ @Lierre: I'm just asking if there exists anything more efficient in this special case. $\endgroup$ Feb 28, 2013 at 14:00
  • $\begingroup$ Just an observation: a necessary condition is that $f(x^2)$ can be factored as $g(x)g(-x)$ over the reals; this should be possible iff $g(\omega) \geq 0$ for each $\omega \in i \mathbb{R}$. I don't know if there is a simpler way to check that; similar versions of this criterion are used when dealing with structured matrix equations. $\endgroup$ Jul 30, 2013 at 7:57
  • $\begingroup$ Oops, I meant to write, iff $f(\omega)\geq 0$ for each $\omega \in i\mathbb{R}$. This in turn maybe means something when combined with other results on polynomials which are positive on the whole real line? Or on polynomials that are sums of two squares? $\endgroup$ Jul 30, 2013 at 8:06

2 Answers 2

2
$\begingroup$

(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.

$\endgroup$
3
  • $\begingroup$ I'm confused by $p$ being a modulus and an irreducible factor at the same time. $\endgroup$ Feb 27, 2013 at 20:56
  • $\begingroup$ p is a prime number, p(x) is an irreducible polynomial (named so as to emphasize that it's a prime in F_q[t].) Feel free to call them by whatever letter you like! $\endgroup$
    – JSE
    Feb 27, 2013 at 21:55
  • $\begingroup$ Over a general field, this is the same as asking whether for each irreducible factor of appearing an odd number of times, the field extension produced by adjoining a root $\alpha$ of that factor, contains a square root of that root, $\sqrt{\alpha}$. $\endgroup$
    – Will Sawin
    Jul 30, 2013 at 3:29
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ So what you are proposing is not better than just factoring $f(x^2)$, is it? $\endgroup$ Feb 27, 2013 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.