Let g(x),p(x) $\in$ $\mathbb Z[x]$ and deg(p) < deg(g).

Suppose that we are given a complex root g($\alpha$) = 0, and that $\alpha$' is the truncation of $\alpha$ to its to its first $\it{d}$ decimal digits (also assume that we also only take the real part after exponentiating each $\alpha$). Is there any theorem that we can use to tell us for which $\it{d}$, $\epsilon$ the implication

p(x)|g(x) $\implies$ -$\epsilon$ < p($\alpha$') < $\epsilon$

I am also interested whether there are any theorems about the converse implication.

My application is that I'm trying to find divisors of a sparse high degree polynomial where we have knowledge about the coefficients of the divisor. I'm aware that the typical method here would be to try using LLL, and I tried looking over the paper Factoring Polynomials with Rational Coefficients. However, I can't say that I understand the paper well enough to tell whether my question was answered in that paper or if my question fundamentally misunderstands the problem.

  • $\begingroup$ You need also a bound on the coefficients of $p$ otherwise it is not true as $\mathbb{Q}[i]$ is dense in $\mathbb{C}$. If you have such a bound $B$ then the set of polynomials $\sum_{n=0}^{\deg(g)} b_n x^n \in \mathbb{Z}[x], |b_n| < C$ is finite so yes there exists such a $d,\epsilon$. $\endgroup$ – reuns Sep 3 '17 at 1:06
  • $\begingroup$ Thanks. I should have mentioned that there is a bound on the coefficients, and that each coefficient is bounded above by 1. Is there any good text/source for this problem that you know of? Maybe it is pretty straightforward to show directly and I am just overthinking it? $\endgroup$ – Kevin Sep 3 '17 at 1:39
  • $\begingroup$ You can try something like this : in some sense (which one ?) the polynomial $f$ of degree $d$ such that $|f(a)-f(a+\epsilon)|$ is minimal is $f(x) = (x-a)^d$ $\endgroup$ – reuns Sep 3 '17 at 1:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.