2
$\begingroup$

This is a question written by my instructor Z. Loria .

Consider the following problem: Given a polynomial $p(x) = \sum_{i=0}^n a_ix^i$, where $a_i$ are integers, is there a natural number $n \in \mathbb{N}$ such that $p(n) = 0$?

Show that this problem is decidable by presenting an algorithm in pseudocode that always either outputs such an $n$, or stops in finite time and declares that no such $n$ exists.

I've to present the above algorithm.

The naïve approach will be to iterate through all the possibilities, but the problem is that it never terminates when the polynomial has no integer roots.

I was thinking about finding some upper bound on the value of $x$ and only then iterate through all the possibilities (accept if found, decline if not).

I vaguely remember that for polynomials in that form we can find some $x$ such that $|p(x)|$ only grows, but I'm not sure how to do it.

$\endgroup$
6
  • 1
    $\begingroup$ Hint, $p(x)$ is basically $a_nx^n$ when $|x|$ is large enough. $\endgroup$
    – John L.
    Mar 22 at 13:26
  • $\begingroup$ You are in the right track. Try to (algebraically) find a value for $x$ large enough so that $|P(x)|$ only increases after it $\endgroup$
    – nir shahar
    Mar 22 at 13:46
  • $\begingroup$ Maybe start with doing a few examples and plotting them out (on Desmos for example) $\endgroup$
    – nir shahar
    Mar 22 at 13:47
  • $\begingroup$ We require you to credit the original source of all copied/quoted material: cs.stackexchange.com/help/referencing. I have given you this feedback before: cs.stackexchange.com/questions/140887/… $\endgroup$
    – D.W.
    Mar 23 at 6:28
  • 3
    $\begingroup$ Credit the author -- which means the instructor of that course. If there is a publicly available copy of the assignment, link to it. $\endgroup$
    – D.W.
    Mar 24 at 17:11

3 Answers 3

5
$\begingroup$

(Let's call the root $\xi$, because $n$ here means the degree of the polynomial. That's seriously bugging me about the question.)

The secret is in noticing that it's easy to test if $\xi$ is a root, since you just evaluate the polynomial, but you only need to test a finite number of candidates.

As a first observation, if $\xi$ is an integer root of the polynomial, then $\left| \xi \right| \le \left| a_0 \right|$, so you only need to test $2\left| a_0 \right|+1$ candidates. In fact, you can do better than this because $\left| \xi \right|$ must be a factor of $\left| a_0 \right|$ by the rational root theorem. So you need only test the factors (both positive and negative) of $a_0$. Either way, a finite number of candidates.

As a second observation, if

$$\sum_{i=0}^{n} a_i\,\xi^i = 0$$

Then for any positive integer $m$

$$\sum_{i=0}^{n} a_i\,\xi^i \cong 0\mod m$$

So, for example, if

$$\sum_{i=0}^{n} a_i\,2^i \not\cong 0\mod 3$$

then there cannot be a root of the polynomial $\xi$ such that $\xi \cong 2 \mod 3$.

Conversely, suppose that for two different coprime moduli $m_1$ and $m_2$, you find all integers $0 \le \xi_j < m_1$ and $0 \le \upsilon_k < m_2$ such that

$$\sum_{i=0}^{n} a_i\,\xi_j^i \cong 0\mod m_1$$

and

$$\sum_{i=0}^{n} a_i\,\upsilon_k^i \cong 0\mod m_2$$

then you can use the Chinese remainder theorem to find all $0 \le \psi_l < m_1 m_2$ such that

$$\sum_{i=0}^{n} a_i\,\psi_l^i \cong 0\mod m_1 m_2$$

This is an important optimisation in practice (i.e. in real computer algebra systems) because evaluating the polynomial might require large integer arithmetic since intermediate values may be larger than a machine word. Using this technique, you can use word-sized integer operations to eliminate a lot of candidates.

$\endgroup$
2
$\begingroup$

$$|ax^3+bx^2+cx+d|>0$$ is equivalent to

$$\left|1+\frac bax^{-1}+\frac cax^{-2}+\frac dax^{-3}\right|>0.$$

Clearly, the limit of the LHS is $1$, and by continuity, there will be a finite $X$ such that $x>X$ implies the above inequality. This generalizes to any degree.


You can take

$$X>\max\left(\left|\frac{3b}a\right|,\sqrt{\left|\frac{3c}a\right|},\sqrt[3]{\left|\frac{3d}a\right|}\right).$$

$\endgroup$
1
$\begingroup$

If $a_n = 1$, then all integer roots are divisors of $a_0$, either positive or negative, and all other roots are irrational or complex. The integer roots can often be found quite quickly.

It's only slightly more difficult if $a_n ≠ ± 1$: Multiply each coefficient by $a_n^{n-1}$, then let $y = x \cdot a_n$ or $x = y / a_n$. You get an equation for y with the highest coefficient $a_n = 1$. You find all the integer solutions for y. The rational solutions for x are $y / a_n$, and you pick those that are integers.

$\endgroup$
1
  • $\begingroup$ $a_0 = -x\sum_{i=1}^n a_ix^{i-1}$. If $x$ is an integer root, $x$ divides $a_0$. $\endgroup$
    – John L.
    Mar 23 at 10:14

Your Answer

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

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