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)$ ?

Improve this question
$\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
    Commented Feb 28, 2013 at 9:26
  • 1
    $\begingroup$ @Lierre: I'm just asking if there exists anything more efficient in this special case. $\endgroup$
    – Max Alekseyev
    Commented 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$
    – Federico Poloni
    Commented 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$
    – Federico Poloni
    Commented Jul 30, 2013 at 8:06

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I'm confused by $p$ being a modulus and an irreducible factor at the same time. $\endgroup$
    – Max Alekseyev
    Commented 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
    Commented 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
    Commented 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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .