一元丢番图方程解的边界

在假期无聊翻阅一本计算理论教科书[1]的时候看到了这个问题,于是尝试证明一下:


问题:令$c_1x^n+c_2x^{n-1}+\cdots+c_nx+c_{n+1} $为有根$x=x_0$的多项式,$c_{max}$为$c_i$的绝对值的最大值,试证明$\mid x_0 \mid \lt (n+1)\frac{c_{max}}{\mid c_1\mid}$。

由根为$x=x_0$可得

$c_1x_0^n+c_2x_0^{n-1}+\cdots+c_nx_0+c_{n+1} = 0 $

移向得

$c_1x_0^n = - (c_2x_0^{n-1}+\cdots+c_nx_0+c_{n+1})$

取绝对值得

$\mid c_1x_0^n\mid = \mid c_2x_0^{n-1}+\cdots+c_nx_0+c_{n+1}\mid$

由triangle inequality得

$\mid c_1x_0^n\mid \le \mid c_2x_0^{n-1} \mid + \cdots + \mid c_nx_0 \mid + \mid c_{n+1} \mid$

将等式右边的$c_i$替换成$c_{max}$,不等式依然成立

$\mid c_1x_0^n\mid \le c_{max} (\mid x_0^{n-1}\mid + \cdots + 1)$

若$\mid x_0\mid \lt 1$ ,因$n+1 \ge 1$,$\frac{c_{max}}{\mid c_1\mid} \ge 1$,$\mid x_0 \mid \lt (n+1)\frac{c_{max}}{\mid c_1\mid}$恒成立

若$\mid x_0\mid \ge 1$ ,将$\mid x_0^{n-1}\mid + \cdots + 1$替换为$n\mid x_0^{n-1}\mid$并移项消去

$\mid x_0 \mid \le n\frac{c_{max}}{\mid c_1\mid}$

可得$\mid x_0 \mid \lt (n+1)\frac{c_{max}}{\mid c_1\mid}$

Q.E.D.


Q: 这个证明是用来干什么的?

A: 这个问题和希尔伯特第十问题[2]有弱相关,这个边界也可以证明一元丢番图方程的整数根是一个Turing Decidable[3]的语言。证明的过程只用到了初中级别的代数知识,不过(对咱这种数学很差的笨蛋来说)构造证明的过程存在一些技巧性。


傻孩子们这里是注释而不是引用:

[1] Sipser, Michael. Introduction to the Theory of Computation. 2nd ed. P. 156

[2] 见这里

[3] A language is Turing Decidable iff there is a Turing Machine which will accept strings in the language and reject strings not in the language.