Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

About some time I am struggling with the following interesting problem:

There is a well-known theorem of Mignotte which says that for a polynomial $f\in\mathbb{Z}[x]$ of degree $n$ and height (coefficient size) $2^\tau$, the height of its divisors is bounded by:

$2^n\mathcal{M}(f)=\mathcal{O}(2^{n+\tau})$,

see, e.g., http://arxiv.org/abs/0904.3057

In other words, the height of polynomial's divisors can be larger than the height of a polynomial itself. Example could be:

$x^5+3x^4+2x^3-2x^2-3x-1=(x^4+4x^3+6x^2+4x+1)(x-1)$.

My conjecture is that this cannot happen for polynomial's square-free part. To be precise, for a polynomial $f\in\mathbb{Z}[x]$ of height $2^\tau$, its square-free part $f^*=f / \gcd(f,f')$ cannot have height larger than $2^\tau$.

Simple example: $f=(x-1)^3=x^3-3x^2+3x-1$ and $f^*=x-1$.

I appreciate if someone has ideas how to prove that or find a counterexample.

Why it's an interesting problem is because theoretical complexity of many algorithms from algebraic geometry use such bounds. On a similar note, modular approaches use these bounds to estimate the number of primes needed for computation.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

The squarefree part of $$(x^4+7x^3+8x^2+7x+1)(x-1)^2=x^6+5x^5-5x^4-2x^3-5x^2+5x+1$$ is $$(x^4+7x^3+8x^2+7x+1)(x-1)=x^5+6x^4+x^3-x^2-6x-1$$ which has greater height. It's clear the coefficients and the degree can be varied greatly to get as many counterexamples as desired.

share|improve this answer
    
awful thanks.. so I don't have to spend time on that. May I ask how you found that counterexample ? was that just a wild guess or you have some algorithmic approach ? –  asm Aug 9 '12 at 7:18
    
Neither. I just thought about it and tried some stuff and eventually saw a way to do it. By the way, if my post does answer your question, the standard way to acknowledge that around here is to "accept" the answer by clicking the check mark next to it. –  Gerry Myerson Aug 9 '12 at 13:13

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.