整数値多項式の意味と2つの必要十分条件

すべての整数 nn に対して P(n)P(n) が整数になる多項式を整数値多項式と言います。

整数値多項式の例と,おもしろい2つの必要十分条件を紹介します。

整数値多項式の例

  • 係数がすべて整数なら整数値多項式です。例えば, P(x)=x2+2x+3P(x)=x^2+2x+3 などです。

  • 係数が整数でなくても整数値多項式になることがあります。例えば, P(x)=12x2+12x=12x(x+1)P(x)=\dfrac{1}{2}x^2+\dfrac{1}{2}x=\dfrac{1}{2}x(x+1) です。実際,xx が奇数でも偶数でも x(x+1)x(x+1)22 の倍数なので P(x)P(x) は整数になります。

整数値多項式の性質

定理1(整数値多項式の必要十分条件1)

P(x)P(x)kk 次多項式とする。

ある整数 nn が存在して P(n),P(n+1),...,P(n+k)P(n),P(n+1),...,P(n+k) が整数なら,P(x)P(x) は整数値多項式

つまり,すべての整数について調べなくとも連続する k+1k+1 個の整数に対して整数であることを確認すれば十分です。

定理1の証明を2通り紹介します。1つめは次数 kk に関する帰納法,2つめはラグランジュ補間を使う方法です。

証明1

k=0k=0 のときは P(x)P(x) は定数関数なので定理1が成立。

k=tk=t のときに定理が成立すると仮定する。t+1t+1 次多項式 P(x)P(x) に対して P(n)P(n) から P(n+t+2)P(n+t+2) までが整数とする。

このとき,階差 Q(x)=P(x+1)P(x)Q(x)=P(x+1)-P(x) を考えると,

  • Q(n)Q(n) から Q(n+t+1)Q(n+t+1) まで整数
  • Q(x)Q(x)tt 次多項式

よって帰納法の仮定より Q(x)Q(x) は整数値多項式。階差が整数なので P(x)P(x) も整数値多項式。

k+1k+1 点からすべてを決定する」公式であるラグランジュ補間も比較的思いつきやすいです。

証明2

補間点を xi=n+i(i=0,...,k)x_i=n+i\:(i=0,...,k) としてラグランジュ補間を使うと, P(x)=i=0kP(xi)fi(x)fi(xi)P(x)=\displaystyle\sum_{i=0}^{k}P(x_i)\dfrac{f_i(x)}{f_i(x_i)}

ただし,fi(x)=ki(xxk)f_i(x)=\displaystyle\prod_{k\neq i}(x-x_k)

P(xi)P(x_i) は整数なので fi(x)fi(xi)\dfrac{f_i(x)}{f_i(x_i)} が整数であることを示せば十分。これは以下のように計算すればわかる:

  • 分母の絶対値は fi(xi)=i!×(ki)!|f_i(x_i)|=i!\times (k-i)!
  • xx が整数のとき,分子の絶対値 fi(x)f_i(x) は「xnx-n から xni+1x-n-i+1 までの積」と「xni1x-n-i-1 から xnkx-n-k までの積」の積。つまり「連続する ii 個の整数の積」と「連続する kik-i 個の整数の積」の積。つまり i!×(ki)!i!\times (k-i)! の倍数である(※)。

※連続する ii 個の整数の積は i!i! の倍数です、→連続するn個の整数の積と二項係数

コンビネーションとの関係

さきほどの証明2でも述べましたが,連続する tt 個の整数の積は t!t! の倍数です。よって,ct(x)=x(x1)(x2)(xt+1)t!c_t(x)=\dfrac{x(x-1)(x-2)\cdots(x-t+1)}{t!} は整数値多項式です(コンビネーション xCt{}_x\mathrm{C}_t を関数にした感じです)。さらに,この重み付き和 t=0katct(x)\displaystyle\sum_{t=0}^ka_tc_t(x) も,各 ata_t が整数なら整数値多項式です。ただし c0(x)=1c_0(x)=1 とします。

実は,整数値多項式は上の形のものに限られます!

定理2(整数値多項式の必要十分条件2)

kk 次多項式 P(x)P(x) について,

P(x)P(x) が整数値多項式
    \iff ある整数 a0,...,aka_0,...,a_k が存在して P(x)=t=0katct(x)P(x)=\displaystyle\sum_{t=0}^k a_tc_t(x)

証明

\Leftarrow はさきほど述べたように各 ct(x)c_t(x) が整数値多項式であることから従う。

\Rightarrow を証明する。x=0,1,...,kx=0,1,...,k に対してP(x)=t=0katct(x)P(x)=\displaystyle\sum_{t=0}^k a_tc_t(x) を満たすような「実数」a0,...,aka_0,...,a_k は以下のように求められる:

  • 両辺に x=0x=0 を代入すると右辺は t=0t=0 の項以外が消えるので a0=P(0)a_0=P(0)
  • x=1x=1 を代入すると a1=P(1)a0a_1=P(1)-a_0
  • x=2x=2 を代入すると a2=P(2)2a1a0a_2=P(2)-2a_1-a_0
  • 以下同様に x=kx=k まで順々に代入していくと aka_k まで求まる。

kk 次多項式は,k+1k+1 点で値が決まったら一意に定まるので結局任意の xx に対して P(x)=t=0katct(x)P(x)=\displaystyle\sum_{t=0}^k a_tc_t(x) となる。

そして,上記の求め方の各式は at=P(t)整数a_t=P(t)-整数 という形なので,P(0),...,P(k)P(0),...,P(k) が整数なら a0,...,aka_0,...,a_k も整数である。

ラグランジュ補間を使った証明がおもしろいです!「帰納法は泥臭い,帰納法を使わないほうが大抵かっこいい」と言っていた知人を思い出します。