2018-05-14

アックス−グロタンディークの定理

定理解説

体 $k$ と正整数 $n$ に対して、写像 $P\colon k^n \to k^n$ が多項式写像であるとは、 $P_1, \dots, P_n \in k[x_1, \dots, x_n]$ が存在して

$P(x_1, \dots, x_n)=(P_1(x_1, \dots, x_n), \dots, P_n(x_1, \dots, x_n) ) \quad (x_1, \dots, x_n) \in k^n$

が成り立つときにいいます。この記事ではTaoの記事とそのコメント欄を参考に次の定理のSerreの議論に基づいた証明を解説します。

定理(Ax, Grothendieck) 多項式写像 $P\colon \mathbb{C}^n \to \mathbb{C}^n$ が単射であれば全射である。

Hilbertの零点定理を使って、無限体の話を有限体の話へ移します。この記事では可換環論の幾つかの命題を既知と仮定します。

可換環論からの準備

Hilbertの零点定理

$k$ を体とし、 $k[x_1, \dots, x_n]$ のイデアル $I$ に対して、 $V(I)$ を

$V(I):=\{(a_1, \dots, a_n) \in k^n \mid f(a_1, \dots, a_n)=0 \ ({}^{\forall}f \in I)\}$

と定義し、集合 $S \subset k^n$ に対してイデアル $I(S) \subset k[x_1, \dots, x_n]$ を

$I(S) := \{f \in k[x_1, \dots, x_n] \mid f(a_1, \dots, a_n)= 0 \ ({}^{\forall}a_1, \dots, a_n) \in S\}$

と定義する。また、イデアル $I$ の根基 $\sqrt{I}$ は

$\displaystyle \sqrt{I}:=\{f \in k[x_1, \dots, x_n] \mid f^r \in I \ ({}^{\exists}r \in \mathbb{N})\}$

で定義されるイデアルである。

Hilbertの零点定理 $k$ を代数閉体とする。このとき、イデアル $I \subset k[x_1, \dots, x_n]$ に対して、 $I(V(I) )=\sqrt{I}$ が成り立つ。

Jacobson環

可換環 $R$ がJacobson環であるとは、 $R$ の任意の素イデアルが極大イデアルの共通部分として表されるときにいう。体や $\mathbb{Z}$ はJacobson環である。

定理１ 可換環 $R$ がJacobson環であれば、多項式環 $R[x_1, \dots, x_n]$ もJacobson環である。

この定理はHilbertの零点定理の一般化と考えることができる。実際、体 $k$ がJacobson環であることから $k[x_1, \dots, x_n]$ のイデアル $I$ に対して $\sqrt{I}=\bigcap_{I \subset \mathfrak{p}}\mathfrak{p}=\bigcap_{I \subset \mathfrak{m}}\mathfrak{m}$ *1が成立し、これがkeyとなって $k$ が代数閉体の場合に零点定理の主張が証明される。

この定理１を利用して次の重要な定理が示される：

定理２ 可換環 $R$ がJacobson環で体 $k$ は $R$ 上有限生成な環とする。このとき、 $k$ は $R$ 上有限生成加群である。

$R$ を体とすればZariskiの補題となる(Zariski版零点定理と呼ばれることもある)。

Zariskiの補題 体 $k$ 上有限生成な体は $k$ の有限次拡大体である。

有限性に関する補題

補題 $\mathbb{Z}$ 上有限生成な可換環の極大イデアルによる剰余体は有限体である。

証明. $R$ を $\mathbb{Z}$ 上有限生成な可換環とし、 $R$ の極大イデアル $\mathfrak{m}$ をとって剰余体を $k:=R/\mathfrak{m}$ とすると、 $k$ は $\mathbb{Z}$ 上有限生成なので $\mathbb{Z}$ がJacobson環であることと定理２から $k$ は $\mathbb{Z}$ 上有限生成加群である。もし $k$ の標数が $0$ であれば $\mathbb{Q}$ が $k$ の部分 $\mathbb{Z}$ 加群となるが、 $\mathbb{Z}$ はNoether環なので $\mathbb{Q}$ も $\mathbb{Z}$ 上有限生成となってしまう。これはあり得ない(有理数の分母の素因数が有限通りしかあり得なくなってしまうため)。よって、 $k$ の標数は $p > 0$ である。すると、 $k$ は $\mathbb{F}_p$ 上有限生成な環なのでZariskiの補題より $k$ は $\mathbb{F}_p$ の有限次拡大となり、それは有限体である。 Q.E.D.

Ax-Grothendieckの定理の証明

$P\colon \mathbb{C}^n \to \mathbb{C}^n$ を多項式写像とし( $P=(P_1, \dots, P_n)$ )、単射であると仮定する。 $2n$ 変数多項式環 $\mathbb{C}[x_1, \dots, x_n, y_1, \dots, y_n]$ のイデアル $I$ を $P_1(\boldsymbol{x})-P_1(\boldsymbol{y}), \dots, P_n(\boldsymbol{x})-P_n(\boldsymbol{y})$ の生成するイデアルとする( $\boldsymbol{x}=(x_1, \dots, x_n), \boldsymbol{y}=(y_1, \dots, y_n)$ )。 $P$ の単射性から各 $j=1, \dots, n$ に対して $x_j-y_j \in I(V(I) )$ なので、Hilbertの零点定理によって $Q_{i, j} \in \mathbb{C}[\boldsymbol{x}, \boldsymbol{y}]$ ( $1 \leq i, j \leq n$ )および $r_i \in \mathbb{N}$ が存在して

$\displaystyle \sum_{i=1}^n(P_i(\boldsymbol{x})-P_i(\boldsymbol{y}) )Q_{i, j}(\boldsymbol{x}, \boldsymbol{y}) = (x_j-y_j)^{r_j}$ –①

が成り立つ。ここで、背理法で定理を証明するために $P$ は全射ではないと仮定する。すると、或る $\boldsymbol{a}=(a_1, \dots, a_n) \in \mathbb{C}^n$ が存在して、任意の $\boldsymbol{x} \in \mathbb{C}^n$ に対して $P(\boldsymbol{x})-\boldsymbol{a} \neq 0$ が成り立つ。これより、 $I$ を $P_1(\boldsymbol{x})-a_1, \dots, P_n(\boldsymbol{x})-a_n$ の生成する $\mathbb{C}[\boldsymbol{x}]$ のイデアルとすると $1 \in I(V(I) )$ であり、Hilbertの零点定理によって $R_i \in \mathbb{C}[\boldsymbol{x}]$ が存在して

$\displaystyle \sum_{i=1}^n(P_i(\boldsymbol{x})-a_i)R_i(\boldsymbol{x})=1$ –②

が成り立つ。

今、可換環 $R \subset \mathbb{C}$ を $P_i, Q_{i, j}, R_i$ ( $1 \leq i, j \leq n$ )の係数達および $a_1, \dots, a_n$ が生成する $\mathbb{Z}$ 上の環とする。 $R$ の極大イデアルの一つを $\mathfrak{m}$ とすると、有限性に関する補題から $k:=R/\mathfrak{m}$ は有限体である。 $R$ の定義から、①、②は $k$ 係数の等式と思って成立することがわかる。これは $P$ を $k$ 係数に還元した多項式写像 $\widetilde{P}\colon k^n \to k^n$ が単射でありかつ全射でないことを示している。つまり、或る有限集合から自分自身への全射でない単射が存在するといっているのである。そんな馬鹿な。 Q.E.D.

*1: $\mathfrak{p}$ は素イデアルで $\mathfrak{m}$ は極大イデアル。一つ目の等号は標準的に成立し、定理から二つ目の等号が得られる

2018-05-12

自然数の複雑度

整数整数-683 整数-1438

自然数 $n$ の複雑度とは、足し算と掛け算と括弧の使用のみを許して $n$ を $1$ だけで表示するのに必要な $1$ の個数の最小値のことを言います。

例えば、 $7$ と $9$ の複雑度は $6$ です。

$7=(1+1)\times (1+1+1)+1,\quad 9=(1+1+1)\times (1+1+1)$

$n$ の複雑度を $c(n)$ と表すことにしましょう。

$\begin{align}&c(1)=1, c(2)=2, c(3)=3, c(4)=4, c(5)=5, c(6)=5, c(7)=6, c(8)=6, c(9)=6, \\ &c(10)=7, c(11)=8, c(12)=7, c(13)=8, c(14)=8, c(15)=8, c(16)=8, c(17)=9, \\ &c(18)=8, c(19)=9, c(20)=9, c(21)=9, c(22)=10, c(23)=11, c(24)=9, c(25)=10, \\ &c(26)=10, c(27)=9, c(28)=10, c(29)=11, c(30)=10, c(31)=11, c(32)=10\end{align}$

Question１ $2^n=\prod_{i=1}^n(1+1)$ という表示があるが、 $c(2^n)=2n$ は一般に成り立つだろうか？

複雑度が $n\geq 1$ となるような最小の自然数を $e_n$ とすると、 $e_1$ から $e_{89}$ は次のようになることが知られています*1：

$\begin{align}e_{1}&=1\\ e_{2}&=2\\ e_{3}&=3\\ e_{4}&=4\\ e_{5}&=5\\ e_{6}&=7\\ e_{7}&=10\\ e_{8}&=11\\ e_{9}&=17\\ e_{10}&=22\\ e_{11}&=23\\ e_{12}&=41\\ e_{13}&=47\\ e_{14}&=59\\ e_{15}&=89\\ e_{16}&=107\\ e_{17}&=167\\ e_{18}&=179\\ e_{19}&=263\\ e_{20}&=347\\ e_{21}&=467\\ e_{22}&=683\\ e_{23}&=719\\ e_{24}&=1223\\ e_{25}&=1438\\ e_{26}&=1439\\ e_{27}&=2879\\ e_{28}&=3767\\ e_{29}&=4283\\ e_{30}&=6299\\ e_{31}&=10079\\ e_{32}&=11807\\ e_{33}&=15287\\ e_{34}&=21599\\ e_{35}&=33599\\ e_{36}&=45197\\ e_{37}&=56039\\ e_{38}&=81647\\ e_{39}&=98999\\ e_{40}&=163259\\ e_{41}&=203999\\ e_{42}&=241883\\ e_{43}&=371447\\ e_{44}&=540539\\ e_{45}&=590399\\ e_{46}&=907199\\ e_{47}&=1081079\\ e_{48}&=1851119\\ e_{49}&=2041199\\ e_{50}&=3243239\\ e_{51}&=3840479\\ e_{52}&=6562079\\ e_{53}&=8206559\\ e_{54}&=11696759\\ e_{55}&=14648759\\ e_{56}&=22312799\\ e_{57}&=27494879\\ e_{58}&=41746319\\ e_{59}&=52252199\\ e_{60}&=78331679\\ e_{61}&=108606959\\ e_{62}&=142990559\\ e_{63}&=203098319\\ e_{64}&=273985919\\ e_{65}&=382021919\\ e_{66}&=495437039\\ e_{67}&=681327359\\ e_{68}&=1006290359\\ e_{69}&=1406394359\\ e_{70}&=1857794399\\ e_{71}&=2728424159\\ e_{72}&=3743197919\\ e_{73}&=5008227839\\ e_{74}&=6872690159\\ e_{75}&=9839491199\\ e_{76}&=13485479039\\ e_{77}&=16724776319\\ e_{78}&=24679458719\\ e_{79}&=35524698479\\ e_{80}&=44211625919\\ e_{81}&=62391692159\\ e_{82}&=93753213119\\ e_{83}&=121551917759\\ e_{84}&=163539961199\\ e_{85}&=250585241759\\ e_{86}&=320429329919\\ e_{87}&=424847520719\\ e_{88}&=630371064959\\ e_{89}&=872573642639 \end{align}$

数値観察としては、 $e_1=1, e_4 = 4, e_7 = 10, e_{10} = 22, e_{25} = 1438$ を除くと全て素数です。また、 $e_4, e_7, e_{10}, e_{25}$ については素数の $2$ 倍です。

Question２ $e_n$ は $n=1, 5, 7, 10, 25$ を除いて全て素数だろうか？

更に、 $\frac{e_n-1}{2}$ も素数が多い傾向がみられます。例えば $37 \leq n \leq 89$ では $n=75$ を除いて素数です。つまり、 $e_n$ はSophie Germain素数を量産している可能性があります*2。

$e_n$ のことがよくわかっていないのに対して、複雑度が $n\geq 1$ となるような最大の自然数 $M(n)$ は決定されています。

定理(Selfridge) $\epsilon \in \{0, \pm 1\}, \ k \geq 1$ とする。このとき、 $M(3k+\epsilon)=3^k+\epsilon 3^{k-1}$ である。

略証. 複雑度の定義から

$\displaystyle M(m)=\max_{a+b=m}\{M(a)+M(b), M(a)M(b)\}$ –①

が成り立つことがわかる。明らかに $M(1)=1$ であり、①を使えば $M(2)=2, M(3)=3$ がわかる。あとは①を利用して $m$ に関する数学的帰納法によって証明できる*3。 Q.E.D.

一般に $c(n) \leq n$ なので、 $c(n), c(c(n) ), c(c(c(n) ) ), \dots$ と複雑度を取る操作を反復すると、有限回で $c(m)=m$ なる不動点 $m$ に到達します。不動点に到達するまでの回数が $h$ であるような最小の $n$ が $h=1$ から $h=5$ までは知られています。それはすなわち次の六つの数です。