2

Take $f\in\mathbb Z[x]$. Denote $(f)_i$ the $x^i$ coefficient in polynomial $f$. Define $f\ne 0$ to be bounded by some $C\in\mathbb Z$ iff $\max_{i=0,\dots,\deg(f)}\{\lvert (f)_i\rvert\}\leq C$ (i.e.$\lvert (f)_i\rvert\leq C$ for all $i=0,\dots,\deg(f)$).

Given two nonzero polynomials $g,h\in\mathbb Z[x]$ and $C\in\mathbb Z$ s.t. $gh$ is bounded by $C$, my conjecture is that $g$ is bounded by $C$ or $h$ is bounded by $C$.

Any ideas whether this could be true and/or how to (dis)prove it?

My thoughts:

First I thought this would be false, so I started looking for counterexamples. However, after running some searches, I found none.

The conjecture does not hold in $\mathbb Q[x]$: take $g=x^2 - 2x + 1,h=x^2 + \frac 32 x + 1$ and then $gh=x^4 - \frac 12x^3 - x^2 - \frac 12x + 1$ is bounded by $C=1$ but neither $g$ nor $h$ is.

I can prove the conjecture for when one of the factors has at most two nonzero terms: $g=a_ix^i+a_nx^n,i<n$ then denote $b_m$ the leading coefficient of $h$ and $b_{\mathrm{l}}$ the last nonzero coefficient of $h$ and so for the leading coefficient of the product $\lvert a_nb_m\rvert\leq C\implies \lvert a_n\rvert\leq C\land\lvert b_m\rvert\leq C$ and for the last nonzero coefficient $\lvert a_ib_{\mathrm{l}}\rvert\leq C\implies\lvert a_i\rvert\leq C\land\lvert b_{\mathrm{l}}\rvert\leq C$. So $g$ is bounded by $C$.

One could try to prove the conjecture this way: if there are coefficients $(g)_i, (h)_j>C$, then show there is a coefficient $(gh)_k>C$. However, $k=i+j$ does not work as this example illustrates:

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

in which the $x^3$ coefficient in the product is smaller than the $x$ and $x^2$ coefficients in the first and the second factor, but it still is not a counterexample either, since some other coefficients in the product are at least as large as the $2$ in the factors.

Why is this important for me?

I was working on an exercise regarding the Berlekamp-Zassenhaus algorithm (Berlekamp-Zassenhaus on Wikipedia). I was supposed to find all irreducible divisors of some $f\in\mathbb Z[x]$ that are bounded by 10 (using the terminology from the beginning of this question). The point is that I can find all the divisors bounded by 10 and my conjecture would show that the minimal such divisors are irreducible since every reducible divisor bounded by 10 would have a factor also bounded by 10.

mimo31
  • 123

1 Answers1

0

The conjecture is FALSE.

One possible counterexample is $C=1, g=x^3-2x^2+2x-1=(x-1)(x^2-x+1), h=x^3+2x^2+2x+1=(x+1)(x^2+x+1)$, which gives $gh=x^6-1$.

However, for the use in the mentioned algorithm, a weaker statement would suffice:

Any reducible $f\in\mathbb Z[x]$ which is bounded by $C\in\mathbb Z$ has at least one non-trivial divisor ($\in\mathbb Z[x]$) which is also bounded by $C$.

It remains unknown to me whether this statement holds as it is not disproved by the presented counterexample to the original one.

note: Many thanks to my friend Samuel for finding the counterexample.

mimo31
  • 123