Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Why don't you want to factor $f(x^2)$? Factorization algorithms are good and quite efficient. Not enough for you ? –  Lierre Feb 28 '13 at 9:26
1  
@Lierre: I'm just asking if there exists anything more efficient in this special case. –  Max Alekseyev Feb 28 '13 at 14:00
    
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. –  Federico Poloni Jul 30 '13 at 7:57
    
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? –  Federico Poloni Jul 30 '13 at 8:06

2 Answers 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.

share|improve this answer
    
I'm confused by $p$ being a modulus and an irreducible factor at the same time. –  Max Alekseyev Feb 27 '13 at 20:56
    
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! –  JSE Feb 27 '13 at 21:55
    
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}$. –  Will Sawin Jul 30 '13 at 3:29

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

share|improve this answer
    
So what you are proposing is not better than just factoring $f(x^2)$, is it? –  Max Alekseyev Feb 27 '13 at 20:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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