演習問題ぶらぶら解く - 整数値しか取らない多項式

\[ %%% 黒板太字 %%% \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\F}{\mathbb{F}} \newcommand{\N}{\mathbb{N}} %%% カリグラフィー %%% \newcommand{\calf}{\mathcal{F} } \newcommand{\calg}{\mathcal{G} } %%% 引数を取るもの %%% \newcommand{\f}[2]{ \frac{#1}{#2} } \newcommand{\im}{\operatorname{im} } \]

こんにちは．

今回も演習問題を駄弁りながら解いていきます．

「解いて」いくと言いましたが，必ずしも解けるとは限りません．

というか解けませんでした．

悲しいね．

でも，実はゲーム実況の真似をわざわざしているのは，解けなかった時のためだったりします．

数学にあまり興味がない方は，「数学をしているひとは，問題が解けて楽しいんだろうなあ」というイメージを持たれていることがあります．

でも実際には全然違います．問題なんか解けないことの方が多いのです．

数学をするということは，解けない問題，問題が解けない自分，そして自分が悩まされてる問題をサクサク解いていく奴らと向き合うということです．そうしたものと，いかに折り合いをつけるかという負けられない闘いなんです．

まあ自分より賢いひとがいるのは当たり前なんですけど，問題が一向に解けない自分が許せなくなることはありますね．

でも解けない問題も，こうやって記事にして供養すればなんか立ち直れる気がします．これはそのための記事でもあります．

なお，私としてはやっぱり自分で考えたいので，答えがわかっていても黙っていていただけると嬉しいです．

問題文

以下はCox, Little, O’Shea『Ideals, Varieties, and Algorithms』からの引用です．9章2節の演習問題11より．

Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (Undergraduate Texts in Mathematics)

Suppose we want to construct a polynomial $p(s)$ that satisfies

\begin{align} p(0) &= c_0 \\ p(1) &= c_1, \\ &\vdots \\ p(d) &= c_d \\ \end{align}

where the $c_i$ are given values in $\mathbb{Z}$. Show that if we set

\begin{align} Δ_0 &= c_0, \\ Δ_1 &= c_1 − c_0, \\ Δ_2 &= c_2 − 2c_1 + c_0, \\ &\vdots \\ \Delta_d &= \sum_{n=0}^d (-1)^n \dbinom{d}{n} c_{d-n}, \end{align}

then the polynomial $$ p(s) = Δ_0 \dbinom{s}{0} + \Delta_1 \dbinom{s}{1} + \cdots + \Delta_d \dbinom{s}{d} $$ satisfies $p(i) = c_i$ for $i = 0, . . . , d$.

何を言っているのかというと……2項係数 $$ \dbinom{s}{d} $$ というのは $s$ の多項式としてみると次数が $d$ になっていて，かつすべての整数 $s \geq 0$ に対して整数を返します．

ここまでは高校で習ったことなんですが，実は，2項係数はその中でも特別な関数です．つまり整数値しかとらない $d$ 次以下の多項式 $q$ があったら，それは2項係数を使って $$ q(s) = a_0 \dbinom{s}{0} + a_1 \dbinom{s}{1} + \cdots + a_d \dbinom{s}{d} $$ と書き表すことができて，しかも係数 $a_i$ は一意的です．

この問題は，この2項係数についての事実のうち「2項係数の組が整数値関数全体を張る」ところに相当する結果を述べています．

すなわち，整数 $c_i$ が与えられたときに，$p(i) = c_i$ となるような多項式 $p$ を具体的に2項係数の張る自由Abel群の元として構成できると述べています．

アプローチ

まあ解けなかったんですけど，何をしたかだけ説明しておきます．

TeX で書くと大変なのでもうノートをそのまま貼ってしまいます．

取り敢えず，通るべき整数点の個数 $d$ に関する帰納法を使うことにしました．ヒントにもそう書いてあったので，これは間違いのないアプローチです．

$Δ_k$ の定義の式がちょっと気持ち悪かったので修正しています．この修正要らないのかもしれないですね．本文でそう与えられてるわけですからね．

なおノートでは $\Delta_d$ と書いていますが，添え字を $d $ にしてしまったのはおろかでした．まあ修正するほどでもないですが．

これはね，いちばん最初に考え付く愚直なアプローチを試しているところです．

「とりあえず定義を書き下してしまう」というやつです．

やさしい問題ならこれで解けてしまうものなんですが，この問題はそううまくいきませんでした．

「……と言い換えられる」のところ，$c_i$ が任意にとれることを使っていて，ちょっと飛躍がある気がしますが，まあ直観的には正しいからいいかなー．

愚直なアプローチが頓挫したところです．

まあそりゃそういうときもあるわな．

計算や論理のミスでないことを確かめるために，少し具体例を計算してみましたが，計算ミスとかではなく単純に壁にぶちあたってるだけでした．

問題文で与えられた仮定のうち，まだあんまり使ってないやつがあるので，それをうまく使えないか試行錯誤しているところです．途中で手がすごく痛くなってきて，ぶん投げてしまいました．

ノートの右下にある茶色いのは，布団に頭をつっこんでうめいているオオサンショウウオのイラストです．

感想

この問題が示そうとしていること自体は，結構おもしろいと思いました．

2項係数という「とても特殊な」関数だと思っていたものが，実は整数値多項式のなすAbel群の基底という，普遍的な性質を持っていたとは……ちょっと驚きですね．

この手の驚きは，経験があります．

Fourier解析のときにもそういう発見がありました．「三角関数，おまえ直交基底だったのか…」っていう発見です．

三角関数の定義を知った時には「こんな特殊な関数定義してどないするん？」と思ったものですが，実は $L^ 2$ 空間の直交基底さまだったという，アレ．

小説でいうと「おさななじみで，いっしょにバカやってた友達が実は有名企業の社長のこどもだった」的なアレです．

まあアーベル群の基底くらい自由度あるじゃん？と言われたらそれまでですが．

実はこの演習問題は有名な結果だそうです．Newton–Gregory の補完多項式とかいうそうです．