用户: Cybcat/多项式复合

前一段时间在某群里流传着一个神秘的高代期中考题:

定理 0.1. 如果 $f\in \mathbb{Q}[x]$ 满足 $f(f(x))\in \mathbb{Z}[x]$ 以及 $f(0)\in \mathbb{Z}$, 则有 $f\in \mathbb{Z}[x]$ 成立.

而我们将展示一个神奇的解决方案, 不过一个刚学高代的大一同学大概不会这么思考这个问题...

1一个引理

首先我们可以在素数局部观察这个问题, 也就是说可以把 $\mathbb{Q},\mathbb{Z}$ 放到 ${\mathbb{Q}}_p,{\mathbb{Z}}_p$ 中. 于是我们就提出了下面的引理:

引理 1.1. 若 $f\in {\mathbb{Q}}_p[x]\backslash {\mathbb{Z}}_p[x]$, 且 $f(0)\in {\mathbb{Z}}_p$, 那么 $f(f(x))\notin {\mathbb{Z}}_p[x]$.

证明. 记 $f=f_0+\cdots +f_d{x}^d$, 那么 $f\circ f=f_0+\cdots +f_d^{d+1}{x}^{d^2}$, 如果 $f_d\notin {\mathbb{Z}}_p$ 那么首项 $f_d^{d+1}\notin {\mathbb{Z}}_p$, 因此我们可以假设 $f_d\in {\mathbb{Z}}_p$. 为便利, 记 $N_k:=v_p(f_k)$.

现在我们能对 $f$ 的 Newton 折线说什么呢? 由于已知 $f_0,f_d\in {\mathbb{Z}}_p$, 但是有在 ${\mathbb{Q}}_p\backslash {\mathbb{Z}}_p$ 中的系数, 因此折线两端在 $v\ge 0$, 但是中间某个 $v(f_j)<0$. 说明折线必然下凸低于了 $v=0$. 于是假设共 $d$ 段的斜率从负到正为$$s_1\le s_2\le \cdots \le s_k\le 0<s_{k+1}\le \cdots \le s_d.$$于是 $(k,N_k)$ 是折线最低点 (其中最右边的那个), 其中 $N_k<0$. 由于 Newton 折线斜率的相反数对应根的赋值, 于是在代数闭包 $\overline{{\mathbb{Q}}_p}$ 中 $f(x)=f_d{\prod }_{j=1}^d(x-{\theta }_j)$, 其中 $v({\theta }_j)=-s_j$. 于是 $f(f(x))=f_d{\prod }_{j=1}^d(f(x)-{\theta }_j)$, 这便是我们研究复合函数的基本出发点.

那么 $f(f(x))$ 的 Newton 折线的诸段斜率由诸 $f(x)-{\theta }_j$ 贡献, 要证明它不在 ${\mathbb{Z}}_p$, 就需要检查折线某时刻低于 $0$.

•	首先对于 $1\le j\le k$, 由于 $v({\theta }_j)=-s_j\ge 0$, 由于 $f-{\theta }_j$ 的常数项 $f_0-{\theta }_j$ 赋值正, 而首项 $f_d$ 赋值也正. 因此 $f-{\theta }_j$ 的折线中保有 $s_{k+1},\cdots ,s_d$ 的部分不变, 它们的抬升和为 $s_{k+1}+\cdots +s_d=N_d-N_k$.
•	其次对于 $k+1\le j\le d$, 由于 $v({\theta }_j)=-s_j<0$, 尽管 $f-{\theta }_j$ 的常数项 $f_0-{\theta }_j$ 赋值负, 但是首项 $f_d$ 仍不变. 也就是说折线的低点纵坐标不会大于 $v({\theta }_j)$, 因此 $f-{\theta }_j$ 的折线中斜率正部分的抬升和至少为 $N_d-(-s_j)=N_d+s_j$.

根据这些内容, 我们来计算 $f(f(x))$ 的最低点的纵坐标 $M$ 的上界, 一个控制就是 $f(f(x))$ 的首项赋值 $(d+1)N_d$ 减掉 $f(f(x))$ 折线斜率中全体正的抬升和. 于是$$\begin{array}{rl}M& \le (d+1)N_d-k(N_d-N_k)-\sum _{j=k+1}^d(N_d+s_j)\\ & =N_d+k{N}_k-(s_{k+1}+\cdots +s_d)=(k+1)N_k.\end{array}$$由于 $N_k<0$ 故 $M<0$, 引理得证.

$\square$

从这个引理出发证明定理非常简单, 只需注意到在每个 $p$ 赋值都非负的有理数是整数, 即 $\mathbb{Q}\cap {\bigcap }_p{\mathbb{Z}}_p=\mathbb{Z}$.

不过好像又有这样一个更加简单的证明.

引理的另证. 沿用前面 $N_k=v_p(f_k)$ 的记号. 现在我们来观察 $f\circ f$, 其实则是诸 $F_r:=f_r\cdot f(x{)}^r$, $r$ 从 $0$ 到 $d$ 的求和. 其中的系数 $x^{rt}$ 具有系数 $f_r{f}_t^r$ 加上一堆乱七八糟的. 这里 $v_p(f_r{f}_t^r)=N_r+r{N}_t$ 就是证明的突破口.

让我们考虑 $M(r,t)=N_r+r{N}_t$. 我们希望研究它的最小值, 显然 $r\ne 0$, 它的最小值首先肯定比 $0$ 小, 且条件告诉我们存在某 $N_t<0$ 对 $t\ne 0$. 于是我们观察 $M(r,t)=M_{\text{min}}<0$ 时, 怎么让 $r,t$ 尽可能大. 显然 $t$ 可以直接取使得 $N_t=N_{\text{min}}$ 的最大 $t$, 这不依赖于 $r$ 的选取. 这时固定 $t$, 再变动 $r$ 使得 $r$ 也最大即可. 此时的 $r,t$ 是唯一的.

此时我们实际上最小最大化了这样一个结果, 考虑 $N_r+N_{t_1}+N_{t_2}+\cdots +N_{t_r}$ 最小, 注意这里 $t_1,\cdots ,t_r$ 取任意 $r$ 个自然数, 然后 $r+t_1+\cdots +t_r$ 尽可能大. 换言之, $f\circ f$ 的展开中, 对于我们上面得到的 $r,t$, 项 $x^{tr}$ 的系数中有且仅有唯一的 $v_p$ 赋值最小者 $f_r{f}_t^r$, 其赋值是一个负数 $M<0$. 因此 $f\circ f$ 的 $x^{tr}$ 系数不在 ${\mathbb{Z}}_p$ 中, 结论得证.

$\square$

更好的是, 这个证明似乎稍作修改就能推广到 $f$ 多重迭代的情景.

2推论

有一个日本竞赛题就和这个引理有密切关系.

定理 2.1. 假设 $g\in \mathbb{Q}[x]$ 满足 $g^{(2)}=g\circ g$ 和 $g^{(3)}=g\circ g\circ g$ 都在 $\mathbb{Z}[x]$, 则 $g\in \mathbb{Z}[x]$.

证明. 我们仍然只需在局部观察, 只需将 $\mathbb{Z},\mathbb{Q}$ 替换为 ${\mathbb{Z}}_p,{\mathbb{Q}}_p$. 那么奇技淫巧在于定义如下的多项式$$f(x):=g(x+g^{(2)}(0))-g^{(2)}(0).$$首先 $g^{(2)}(0),f(0)=g^{(3)}(0)-g^{(2)}(0)\in {\mathbb{Z}}_p$. 其次$$f(f(x))=g^{(2)}(x+g^{(2)}(0))-g^{(2)}(0)\in {\mathbb{Z}}_p[x].$$由此推出 $f\in {\mathbb{Z}}_p[x]$, 进而 $g(x)=f(x-g^{(2)}(0))+g^{(2)}(0)\in {\mathbb{Z}}_p[x]$ 得证.

$\square$

这个结论可以推广为, 如果得知对于某个正整数集合 $S$ 中的元素 $s$, 都有 $g^{(s)}\in {\mathbb{Z}}_p[x]$, 且全体 $S$ 中元素互素, 那么 $g\in {\mathbb{Z}}_p[x]$. 实际上互素的条件是必须的, 不互素的反例很容易发现, 例如 $g(x)=x+1/2$ 则 $g(g(x))=x+1$, 那么此时 $g^{(2)},g^{(4)}\in \mathbb{Z}[x]$ 然而 $g\notin \mathbb{Z}[x]$. 细节就留给读者.