整数係数多項式 $P$ であって, $P(0)\neq 0$ かつ任意の非負整数 $n,m$ に対して $P^n(m)P^m(n)$ が平方数となるものをすべて求めよ. ここで, $P^k$ で $P$ の $k$ 回合成を表すものとする.
平山：解は？$n+1$ くらい？
宿田：たぶん？
平山：$mP^{m}(0)$ が平方数くらいから始めるかな
馬杉：$0$ いいんだ
平山：割と本質っぽい、$P^{m}(0)=c_{m}$ とおきますか
馬杉：$c_{\text{平方数}}$ は平方数
平山：定数項は平方数か
兒玉：$P^{m}(n+1)P^{P(m)}(n)$ は平方数
(※編注：実際には $P(m)$ 非負を要請する必要あり)
馬杉：$P^{m}(n)$ の素因数ってどんな感じ？オーダーとか知りたい
平山：思ったより情報が得られんなあ
兒玉：定数項が $1$ なの言えそう
平石：兒玉さんのやつ $m=0$ 入れたら $(n+1)P^{P(0)}(n)$ が平方数
兒玉：これめっちゃ重要じゃね？
馬杉：頑張ったらなんかすでに出来そう
平山：定数項が非負だとちょっと微妙じゃない？
兒玉：平方数なのでOK
平山：は？自分で言ったのに忘れてた
馬杉：$P^{P(0)}$ を $Q$ とおくと $Q(p-1)$ は $p$ の倍数
馬杉：よって $Q(-1)$ は任意の素数の倍数で、$0$
平石：$-1$ 入れちゃっていいの
平山：多項式一般の性質として
馬杉：というか $Q(n)=n+1$ 言えばいいわけじゃん
平山：あー多項式だとそんなこともできるのか
馬杉：っていうか $1$ ずらすとか？
平山：$Q$ だけじゃ情報減ってて全然無理なんだよね
兒玉：方針的に微妙な気がする
平山：定数項とりあえず決めないとダメかな..
宿田：$(c_{m}+n)(c_{n}+m)$ が平方数
馬杉：有用そう、どうやるの
宿田：$(m,n)=(c_{m},c_{n})$ を代表
馬杉：なるほどね
馬杉：$n$ の素数 $p$ でのオーダーがべらぼうに大きければ
馬杉：$P(n)$ と 定数項のオーダーが一致するねっていう
平山：でも合成とオーダーって相性微妙じゃない？
兒玉：宿田の式で定数項を $a^{2}$ とすると、$c_{n}$ は $a^{2}$ の倍数で
兒玉：$m$ に $a$ の素因数、$n$ に $1$ 代入して $a=1$
馬杉：おっ
宿田：おっ
平山：上の $Q$ が $P$ 自身になったのか
馬杉：$mc_{m}$ 平方数なんだっけ
平山：$(m+1)(c_{m}+1)$ も平方数で、だいぶヤバそう
平石：その二つだけなら $(1,49)$ とか反例あるけど
平山：ダメじゃん！
宿田：$(n+1)P(n)$ が平方数なんだよな
(※※※ここから本質的に変わらない式変形が続く※※※)
兒玉：宿田の式が本質だと思ってる
馬杉：$(c_{m}+n)(c_{n}+m)$ は平方数です、$\{c_{n}\}$ は？
馬杉：なんかいけそうじゃーん
兒玉：これIMOで出なかった？
宿田：あっwwww
平石：3番級とかだったような
平山：あったわwwww
兒玉：2010年の3番ですね
平山：$0$ 入る可能性あるけど流石にごまかせるやろ
宿田：絶対オーバーキルで草
平山：本質的な作業、宿田の代入一つだけ…
馬杉：多項式すらいらんねやん、草
平山：流石にオーバーキルせず解き切るか…
宿田：もし ${\rm mod}\ p$ で $c_{n}\equiv c_{n+1}$ ならずっと一定
宿田：これ $P(x)-x$ とか見てみると良さそうじゃないですか
馬杉：確かに？
平山：$c_{p}$ が $p$ の倍数だから ${\rm mod}\ p$ の観察は本質っぽいけど
馬杉：たしかに
平山：というか $c_{0},\cdots,c_{p-1}$ って ${\rm mod}\ p$ で重複ないのか
平石：それいつの間に言った
平山：周期を考えればそれはそう
平山：ということは $n,P(n),\cdots,P^{p-1}(n)$ も完全剰余系か
平山：$P(n)-n$ が定数じゃなければ適当に素因数取って終わりじゃん
兒玉：ああなるほど
平石：あーそうか
平山：答案にしたら短くて虚無感の募るタイプですな～
- 解答を書くと元の条件はほとんど使っておらず, 多項式の性質で多くの議論ができることがわかる.
$c_i = P^{i}(0)$ とおく. $p$ を素数とすると, $m=p, n=0$ とした代入より $pc_p$ は平方数であり, $c_p$ は $p$ の倍数である. また, $l$ を正の整数とすると $ c_i \equiv c_j \pmod p$ ならば $c_{i+l} =P^l(c_i) \equiv P^l(c_j)=c_{j+l} \pmod p$ である. 次の補題を示す.
任意の整数 $ n$ について, $P(n)-n$ の任意の素因数は $P(0)$ の素因数である.
$q$ を $P(0)$ を割り切らない素数とする. 以下合同式は $\bmod q$ で考える. $c_i $ が $q$ の倍数になる最小の正の整数 $i$ を $k$ とすると, 帰納的に考えて, $c_i$ が $q$ の倍数であることは $i$ が $k$ の倍数であることと同値であり, $c_q$ は $q$ の倍数であることとあわせて $k$ は $q$ の約数である. $P(0)=c_1$ は $q$ の倍数でないことから, $k\neq 1$ であり, $k=q$ である. よって $c_1, c_2, \ldots, c_{q-1}$ はすべて $q$ の倍数でない. また, $1 \leq i < j \leq q-1$ かつ $c_i \equiv c_j$ をみたす整数の組 $(i,j)$ が存在すると仮定すると, 帰納的に $n \geq i$ ならば $c_n \not \equiv 0$ が成り立ち, $c_q$ が $q$ の倍数であることに矛盾する. 以上より $c_0, c_1, \ldots, c_{q-1}$ を $q$ で割った余りはすべて異なり, $0,1, \ldots, q-1$ のすべてが現れる. よって $n \equiv c_i$ をみたす非負整数 $0 \leq i \leq q-1$ が存在し, $P(n)-n \equiv P(c_i)-c_i=c_{i+1}-c_i \not \equiv 0$ である. 以上より示された.
整数係数多項式 $R$ を用いて $P(n)-n=P(0)+nR(n)$ とおくと, 補題より, 任意の $3$ 以上の整数 $a$ について, $P(0)+aP(0)^2 R(aP(0)^2)=P(0)(1+aP(0)R(aP(0)^2)$ の任意の素因数は $P(0)$ の素因数である. $1+aP(0)R(aP(0)^2)$ は $P(0)$ と互いに素であることから, $|1+aP(0)R(aP(0)^2)|=1$ であり, $|aP(0)|>2$ とあわせて $R(aP(0)^2)=0$ が必要である. ここで, $P(0) \neq 0$ より, $R$ は無限個の零点をもち, $R=0$ である.
よって$P(n)=n+P(0)$ が必要である. $b = P(0)$ とおくと, 与式で $n=1, m=0$ とすることで $b$ は平方数である. また, $n=4, m=1$とすることで $4b^2+17b+4$ は平方数であり, $(2b+2)^2 < 4b^2+17b+4 < (2b+5)^2$ より, $4b^2+17b+4=(2b+3)^2$ または $4b^2+17b+4=(2b+4)^2$ が成り立ち, $b=1$ または $b=12$ である. $b$ は平方数であったから $b=1$ が必要である. 逆に $P(n)=n+1$ が条件をみたすことは容易にわかるため, 求める $P$ は $P(n)=n+1$ のみである.