整值多项式与二项式基

形式陈述

有理系数多项式 $p\in\mathbb Q[x]$ 称为整值多项式，若 $p(m)\in\mathbb Z$ 对每个 $m\in\mathbb Z$ 成立。全体这样的多项式记为 $\operatorname{Int}(\mathbb Z)$ 。它包含 $\mathbb Z[x]$ ，但一般不等于 $\mathbb Z[x]$ 。

对给定次数界 $\deg p\le d$ ，以下三条等价：

$p$ 是整值多项式
$p(0),p(1),\ldots,p(d)$ 全是整数
唯一的Newton 展开 $p(x)=\sum_{k=0}^da_k\binom{x}{k}$ 的所有 $a_k$ 都是整数

而且 $a_k=\Delta^kp(0)$ 。所以 $\operatorname{Int}(\mathbb Z)$ 中次数至多 $d$ 的多项式，作为加法阿贝尔群，有基 $\binom x0,\ldots,\binom xd$ 。这里说的是整数线性组合，不是普通幂基中的系数为整数。

直觉

$\binom{x}{2}=x(x-1)/2$ 有一个分母二，但连续两个整数总有一个偶数，所以它对整数输入仍取整数。把“系数含分母”当作“值一定出现分数”，忽略了因子之间的整除关系。

二项式多项式恰好把这些整除关系预先打包。非负整数 $m$ 下， $\binom mk$ 是子集数；负整数 $m=-a$ 、 $a\ge1$ 下，

\binom{-a}{k}=(-1)^k\binom{a+k-1}{k},

从 $k$ 个连续负因子逐个提出负号即可证明，右边也为整数。因此二项式基在全部整数上整值。

主定理现在有很短但完整的证明。第一条显然推出第二条。第二条使每个 $\Delta^kp(0)$ 成为整数值的有限整数线性组合，故推出第三条。第三条与上段“每个基函数在正、负整数都整值”结合，推出第一条。唯一性来自基的不同次数，不需要另作整除算法。

例子与边界

给定次数至多三的多项式，已知 $p(0),p(1),p(2),p(3)=(1,2,5,11)$ 。差分各行是

(1,2,5,11),\quad(1,3,6),\quad(2,3),\quad(1).

因此

p(x)=1+\binom x1+2\binom x2+\binom x3 =\frac{x^3+3x^2+2x+6}{6}.

它不是整系数多项式，却整值。计算 $p(4)=1+4+12+4=21$ ；计算 $p(-2)=1-2+2\cdot3-4=1$ 。负输入检查说明主张不只针对组合计数里的非负大小。

连续节点与次数界都不能丢

$p(x)=x/2$ 在 $0,2$ 上取整数，但 $p(1)=1/2$ 。即使已经知道次数至多一，两个不连续整数节点也不能替代规定的连续节点。任意连续的 $a,a+1,\ldots,a+d$ 则可以：平移 $q(x)=p(x+a)$ 后套同一定理。

若没给次数界，检查 $0,1,\ldots,d$ 也不够。例如

q(x)=\frac{x(x-1)\cdots(x-d)}{(d+2)!}

在所有已检查点都为零，但 $q(d+1)=1/(d+2)$ 。多看几个整数并不能变成对未知次数的证明。

推论与应用

两个整值多项式的和与积仍整值，因为每个整数输入处的和与积仍为整数。更具体地，二项式基乘法有非负整数结构常数：

\binom xi\binom xj =\sum_{k=\max(i,j)}^{i+j} \frac{k!}{(k-i)!(k-j)!(i+j-k)!}\binom xk.

先让 $x=m\ge0$ 。左边数一个 $i$ 元子集 $A$ 和一个 $j$ 元子集 $B$ 。按并集大小 $k$ 分类，先选 $A\cup B$ ，再将它分为 $A\setminus B$ 、 $B\setminus A$ 、 $A\cap B$ ，三块大小分别为 $k-j,k-i,i+j-k$ 。这给系数；在无限多个 $m$ 上相等后就是多项式恒等式。

例如

\binom x2^2=\binom x2+6\binom x3+6\binom x4.

$x=4$ 时为 $36=6+24+6$ 。由此可在整值坐标里直接乘多项式，不必先扩成分数系数再猜整除性。

差分与离散原函数也保持整值： $\Delta\binom xk=\binom{x}{k-1}$ ，原函数取 $\binom{x}{k+1}$ 即可。这给组合幂和的整数性一份结构证书。它不意味着普通导数保持整值，例如 $\frac d{dx}\binom x2=x-1/2$ 已在每个整数处取半整数。

参考资料

Richard P. Stanley，Enumerative Combinatorics, Vol. 1，作者第二版书稿，§1.9，Corollary 1.9.3，书稿印页87：整值当且仅当差分系数为整数；前一命题提供Newton展开。本页将其写成有限连续采样判据并完整证明。
同书§1.2的广义二项式系数与子集计数，支撑负整数恒等式及本页的并集分类乘法证明。

形式陈述 ​

连续节点与次数界都不能丢 ​

反向链接

形式陈述

连续节点与次数界都不能丢