1
$\begingroup$

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.

1 Answers 1

1

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.

  • 0
    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.2012-08-09