フィボナッチ・フリーク

数学の小ネタ集。

Fibonacci Freak

整数全体の等差数列への分割に関するMirsky–Newmanの定理

 

しばらくブログの更新が止まっていてすいません.2018年に入ってから自分の数学の勉強が忙しく,なかなか小ネタを書く時間がありませんでした….ただ書きたいネタ自体はいろいろあるので,ブログは続けていこうと思います.

 

今回は次の有名な定理を示します.

定理(Mirsky-Newman).整数全体の集合\mathbb{Z}が,次のようにn(\geq 2)個の互いに交わらない等差数列に分割されたとする:

\mathbb{Z}=\displaystyle\coprod_{i=1}^n a_i+b_i\mathbb{Z}~~(b_1\geq b_2\geq\dots\geq b_n).

このときb_1=b_2である.

特にこの定理から,整数全体を公差の相異なる2つ以上の等差数列に分割することは不可能であることがわかります.

よく知られた証明としてはSteinとShakarchiの複素解析の本に載っているものがありますが,最近私は簡単な別証明をひとつ思いついたので,それを以下に紹介します.

 

まず整数全体をどの等差数列に属するかによってn色に塗り分けます.Nb_1,b_2,\dots,b_nの十分大きい公倍数とすれば,色のパターンは\{0,1,\dots,N-1\}を周期として繰り返し,また各色はこの周期に3つ以上含まれます.そこでこれらN個の色と同じ順に正N角形の頂点を塗り分けることで,定理の証明は次の命題に帰着できます.

命題.N角形の頂点をn(\geq 2)色に塗り分けたとき,色iの点全体が正c_i角形をなしていたとする.このときc_1\leq \dots\leq c_nとするとc_1=c_2である.

問題のN角形の頂点を複素数平面上のz^N-1=0の解全体と同一視します.このとき色iの点全体は正c_i角形をなしているので,ちょうどz^{c_i}-\alpha_i=0\alpha_i|\alpha_i|=1なる複素数)の解全体に対応しています.よって次の式が成り立ちます:

z^N-1=\displaystyle\prod_{i=1}^n(z^{c_i}-\alpha_i).

ここでc_1\leq \dots\leq c_nかつc_1\neq c_2と仮定すると,上式右辺を展開した式のz^{c_1}の係数は(-1)^{n-1}\alpha_2\alpha_3\dots\alpha_n\neq 0ですが,左辺のz^{c_1}の係数は0なので矛盾しており,これで命題が示されました.

【講演ノート】12点定理

数物セミナー2017冬の談話会@慶應義塾大学にて,「12点定理」について講演しました.以前からずっとブログで紹介したい!と思っていた内容なのですが,ブログに書く時間がないことに気づいたので(最近数学が忙しいのです),講演用に準備した原稿をそのまま置いておきます.

わざわざホモトピーを定義しているのに線積分ホモトピー不変性は説明していなかったり,単連結という用語を無定義で使っていたりと,ツッコミどころ満載ですが,どうか大目に見てください. 

内容のざっくりした説明

12点定理は平面上の格子点を結んでできるある種の多角形Pとその「双対」P^\veeを考えたとき,それぞれの周上にある格子点の数を足すと必ず12になる,という不思議な定理です.この定理にはたくさんの証明が知られていますが,今回は\mathrm{SL}_2(\mathbb{Z})の考察,普遍被覆への持ち上げ,そしてモジュラー形式を用いてこれを証明します.

 

リンク

12points.pdf - Google ドライブ

 

誤植

P.8 \Delta(z)の定義式は,正しくは \displaystyle\Delta(z)=e^{2\pi iz}\prod_{n=1}^\infty(1-e^{2\pi inz})^{24} です.

 

参考文献

実は以下の記事を和訳しただけという説があります.

B. Poonen and F. Rodriguez-Villegas, Lattice polygons and the number 12, Amer. Math. Monthly 107 (2000), 238–250.

【解決編】平面上の凸図形に含まれる多角形の面積

前回の記事で,次のような問題の解答を募集しました.

問題.平面上の凸図形Xに対し,「Xに含まれるn角形の面積の最大値をXの面積で割ったもの」をM_n(X)と書く.Xを動かしたとき,M_n(X)のとりうる値の最小値は何か?

 

fibonacci-freak.hatenablog.com

 

これについてある方からTwitterでリプライをいただき,なんとこの問題は

E. Sasという数学者により1939年に解かれていた

ことが判明しました!(昔の人,すごい!)

 

そこで,今回はその証明を紹介したいと思います.簡潔な証明なのですぐに終わります.

 

定理 (E.Sas, 1939).任意の凸図形Xに対しM_n(X)\geq \dfrac{n}{2\pi}\sin\dfrac{2\pi}{n}であり,Xが円のときに等号が成立する.

 

証明.Xに含まれる線分のうち距離が最大のものを1つとりABとする.問題の内容は相似で不変なのでABの長さが2であると仮定してよい.A=(-1,0), B=(1,0)となるように座標をとる.ABの最大性から,X-1\leq x\leq 1の範囲に入ることに注意する.

 

f:id:fibonacci_freak:20171206232657p:plain

 

\theta\in[0,\pi]に対し\{(x,y)\in X\mid x=\cos\theta\}におけるyの最大値をh(\theta)と定める.同様に\theta\in[\pi,2\pi]に対してはyの最小値をh(\theta)と定める.するとXの境界は

f(\theta):=(\cos\theta,h(\theta))

によりパラメータづけできる.このときXの面積は

\displaystyle X=\int_{\theta=0}^{2\pi}-h(\theta) dx(\theta)=\int_0^{2\pi}h(\theta)\sin\theta d\theta

となる.

ここでt\in[0,2\pi]を1つとり,t_k=t+\dfrac{2k\pi}{n}と定める.f(t), f(t_1), f(t_2),\dots,f(t_{n-1})を頂点とするn角形の面積をS(t)とすると,和積の公式より

\displaystyle \begin{align*}S(t)=\sum_{k=0}^{n-1} \dfrac{\cos t_k h(t_{k+1})-\cos t_{k+1}h(t_k)}{2}\end{align*}\\ \displaystyle =\sum_{k=0}^{n-1} \dfrac{(\cos t_{k-1} -\cos t_{k+1})h(t_k)}{2}\\ \displaystyle=\sum_{k=0}^{n-1} \sin t_k\sin\dfrac{2\pi}{n} h(t_k)

 

と表すことができる.よってtを無作為にとったときのS(t)の期待値は

\displaystyle \dfrac{1}{2\pi}\int_0^{2\pi}S(t)dt=\dfrac{n}{2\pi}\sin\dfrac{2\pi}{n}\int_0^{2\pi}h(\theta)\sin\theta d\theta=\dfrac{n}{2\pi}\sin\dfrac{2\pi}{n}\cdot X.

 

これはあるtが存在してS(t)\geq \dfrac{n}{2\pi}\sin\dfrac{2\pi}{n}\cdot Xとなることを示しており,主張は示された.\square

 

見事な証明とはこのことです.まるで芸術作品のような美しさを感じませんか?

【解答募集】平面上の凸図形に含まれる多角形の面積

追記:解決したので「解決編」を書きました.

fibonacci-freak.hatenablog.com

 

 

 

 

私は今(2017年12月5日現在),こんな問題を考えています.

問題.平面上の凸図形Xに対し,「Xに含まれるn角形の面積の最大値をXの面積で割ったもの」をM_n(X)と書く.Xを動かしたとき,M_n(X)のとりうる値の最小値は何か?

 

たとえばXが正六角形の場合,M_3(X)=\dfrac{1}{2}, M_4(X)=\dfrac{2}{3}等となります.nを大きくしていくとM_n(X)は1に近づくことも推測されます.

 

f:id:fibonacci_freak:20171205214206p:plain

 

今のところ自分で導けた結果は次の2つです.

命題.M_3(X)\gt\dfrac{1}{3}.

証明.凸図形Xに含まれる三角形のうち面積が最大のものを1つ取り,その頂点をA, B, Cとする.これらはXの周上にあるとしてよい.ABC180^\circ回転させた図形(以下「耳」と呼ぶ)を各辺に貼り付けると,下図のような大きな三角形が得られる.面積の最大性から,Xはこの三角形に含まれることがわかり,M_3(X)\gt\dfrac{1}{4}が従う.

 

f:id:fibonacci_freak:20171205221610p:plain

 

さらにXのうち3つの耳に含まれる部分の面積を評価する.3つの耳を平行移動して全て重ねた時,Xと交わっていた部分(図の赤い部分)全てに含まれる点があったとすると,もとの図形の中でそれらはABCと等しい面積を持つ三角形をなす.ゆえに赤い部分は境界以外では高々2つまでしか交わらないので,赤い部分の面積はABCの高々2倍であり,Xの面積はABCの高々3倍であることがわかる.よってM_3(X)\gt\dfrac{1}{3}\square

 

命題.M_4(X)\gt\dfrac{1}{2}.

証明.凸図形Xに含まれる四角形のうち面積が最大のものを1つ取り,その頂点をA, B, C, Dとする.これらはXの周上にあるとしてよい.A,Cそれぞれを通り対角線BDに平行な直線と,B,Dそれぞれを通り対角線ACに平行な直線を描くと,ABCDの2倍の面積を持つ平行四辺形が得られる.面積の最大性からXはこの平行四辺形に含まれることがわかり,M_4(X)\gt\dfrac{1}{2}が従う.\square

 

(それから一応,M_3(X)\gt\dfrac{3}{8}という評価も得られたような気になっていますが,証明が複雑なので間違っている気もしています.確証が得られたら追記します.)

 

しかし正直なことを言うと,さすがにもっと良い評価が得たい!という気持ちでいっぱいです.

そこで,ぜひ優秀な読者の皆さんにも一緒に考えてもらいたい,というわけです.

もし何か新しい結果が得られたら,Twitter(@Asuka_Tsukimi)までご連絡ください!

twitter.com

ご協力をお願いします(*^^*)(*^^*)(*^^*)(*^^*)

格子立方体の一辺の長さとWittの消去定理

格子点(座標が整数の点)を結んでできる図形は面白い問題の源泉です.今回は格子点を結んでできる立方体について考えてみましょう.まずn次元の格子立方体を厳密に定義します.

定義.n次元空間の格子点を頂点とするn次元立方体を格子立方体という.ただし立方体とは,単位区間n個の直積の直交変換による像である.

この定義はたとえば2次元なら正方形,3次元なら通常の立方体と一致します. さて,ここで次のような問題を考えます.

問題.n次元の格子立方体の一辺の長さとしてあり得る実数の集合をL(n)で表す.L(n)はどのような集合になるか?

まずは2次元の場合を考えてみましょう.三平方の定理より一辺の長さは0以上の整数a,bを用いて\sqrt{a^2+b^2}と表すことができます.逆にこのように表せる実数Dに対して一辺がDの格子正方形が存在することも自明です.よって

L(2)=\{\sqrt{a^2+b^2}\mid a,b\in \mathbb{Z}_{\geq 0}\}\setminus \{0\}

であることがわかりました.

3次元の場合は少し難しいですが,体積を考えるとうまくいきます.先ほどと同じように,三平方の定理から辺の長さDは正整数の平方根であることがわかります.一方,格子立方体の体積は辺のベクトルを並べた行列の行列式に等しく,辺のベクトルは成分が全て整数なので,体積も当然整数になります.よってD^3は整数であり,Dが正整数であることがわかりました.逆に任意の整数Dに対して一辺の長さがDの立方体が存在することは自明なので,結局

L(3)=\mathbb{Z}_{\gt 0}

であることがわかりました. 全く同じ議論から

L(2k+1)=\mathbb{Z}_{\gt 0}

もわかります.

4次元の場合はさらに面白いことが起こります.そう,4次元にはあの定理があるのです!

Lagrangeの四平方和定理.任意の正整数Dは4つの非負整数a,b,c,dによってD=a^2+b^2+c^2+d^2と表せる.

4次元立方体の一辺の長さは先ほどと同様に整数の平方根になりますが,逆に任意の正整数Dに対して一辺の長さが\sqrt{D}の立方体を構成することができます.実際,上の定理を使ってD=a^2+b^2+c^2+d^2と表すと,

v_1=\begin{pmatrix}a\\b\\c\\d \end{pmatrix}, v_2=\begin{pmatrix}b\\-a\\d\\-c \end{pmatrix}, v_3=\begin{pmatrix}c\\-d\\-a\\b \end{pmatrix}, v_4=\begin{pmatrix}d\\c\\-b\\-a \end{pmatrix}

で張られる格子立方体の一辺の長さは\sqrt{D}になります.よって

L(4)=\{\sqrt{D}\mid D\in \mathbb{Z}_{\gt 0}\}

がわかりました.上で構成した立方体の直積を考えれば,より一般に

L(4k)=\{\sqrt{D}\mid D\in \mathbb{Z}_{\gt 0}\}

であることもわかります.

 

これで残ったのはn=4k+2の場合のみとなりました.n=2の場合の正方形の直積を考えれば

L(4k+2)\supset \{\sqrt{a^2+b^2}\mid a,b\in \mathbb{Z}_{\geq 0}\}\setminus \{0\}

となります.

実はこの包含は等号になります!

証明には対称双線型形式に関するWittの消去定理を使います.

Wittの消去定理.標数0の体上の有限次元ベクトル空間V_1,V_2,V'_1,V'_2に,それぞれ対称双線型形式B_1, B_2, B'_1, B'_2が与えられているとする.V_1\oplus V_2には対称双線型形式B_1\oplus B_2が誘導され,V'_1\oplus V'_2にはB'_1\oplus B'_2が誘導される.このとき,V_1\oplus V_2\cong V'_1\oplus V'_2かつV_1\cong V'_1ならばV_2\cong V'_2である.ただし\congは等長同型,すなわち対称双線型形式を保つ線形同型が存在することを表す.

これを使うために,格子立方体を対称双線型形式の言葉に言い換えます.

定義.有理点を頂点とする立方体を有理立方体という.

実は一辺の長さがDの有理立方体を与えることは(\mathbb{Q}^n,DB)から(\mathbb{Q}^n,B)への等長同型を与えることと対応します.ここでB\mathbb{Q}^nの標準内積です.この対応はv_1,\dots,v_nで張られる有理立方体に対し,標準基底をv_1,\dots,v_nに送る線型写像を対応させることで得られます.

さて,DL(4k+2)の元とすると,格子立方体は有理立方体なので,先ほどの対応から(\mathbb{Q}^{4k+2},DB)\cong (\mathbb{Q}^{4k+2}, B)となります.一方でD\in L(4k)でもあるので,(\mathbb{Q}^{4k},DB)\cong (\mathbb{Q}^{4k}, B)となります.よってWittの消去定理より(\mathbb{Q}^2,DB)\cong (\mathbb{Q}^2, B)がわかり,これはDが有理正方形の一辺の長さであることを意味しています!

よって正整数p,q,r,sを用いてD=\sqrt{\dfrac{p^2}{q^2}+\dfrac{r^2}{s^2}}と表すことができます.両辺を二乗し分母を払うと

(qs)^2D^2=p^2+r^2

となります.ここで次の定理を使います.

Eulerの定理.正整数nが二つの平方数の和として表せるための必要十分条件は,4で割ったあまりが3である素因数の指数が全て偶数であることである.

とくにこの条件はnを平方数で割っても(もちろん割った後が整数なら)変わらないことに注意します.いまD^2三平方の定理から正整数であることがわかっているので,前の式とEulerの定理よりD^2も平方数の和として表せます.よってD\in\{\sqrt{a^2+b^2}\mid a,b\in \mathbb{Z}_{\geq 0}\}\setminus \{0\} がわかりました.

 

n=4k+2の場合に関する以上の解法は楕円曲線に関する業績で知られるN.Elkiesによるもの(MathOverflowの回答)です.こんな素朴な問題に深い整数論的現象が潜んでいるなんて,とても面白いと思いませんか!

USAMO2008第6問と有限体上の線形代数

USAMO(アメリカ数学オリンピック)の2008年大会では,第6問として次のような問題が出題されました.

ある数学の会議において,どの2人の数学者も友達かそうでないかのどちらかであるとする.参加した数学者全員は二つの大きな部屋のいずれかで夕食を食べる.数学者たちはみな,自分の友達のうち偶数人が含まれる部屋で食事をしたいとする.全員の希望を満たすように数学者を分ける方法の総数は2の冪(つまりある正整数kに対し2^k)であることを示せ.

 

これは純粋に組み合わせ論の問題ですが,実は線形代数の知識を使うと見通しよく解くことができます.

 

解答.数学者に1,2,\dots,nと番号をつける.以下,行列やベクトルは全て\mathbb{F}_2=\mathbb{Z}/2\mathbb{Z}上で考える.ijが友達であるときa_{ij}=1,そうでないときa_{ij}=0と定め,a_{ii}iの友達の総数を2で割った余りとする.これによりn\times n行列(a_{ij})が定まる.また,iを部屋Aに割り当てるときv_i=0,部屋Bに割り当てるときv_i=1とするとn次元ベクトル(v_i)が定まる.このとき,割り当て方vが数学者全員の希望を満たすことは

\[\begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n}\\ a_{21} & a_{22} & \dots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\a_{n1} & a_{n2} & \dots & a_{nn}\end{pmatrix}\begin{pmatrix}v_1\\ v_2\\\vdots\\v_n\end{pmatrix}=\begin{pmatrix}a_{11}\\ a_{22}\\ \vdots\\a_{nn}\end{pmatrix}\]

と同値である.実際左辺の第i成分は,iが部屋Aにいるときは

(部屋Bにいるiの友達の総数) \mathrm{mod}~2

であり,iが部屋Bにいるときは

iの友達の総数)+(部屋Bにいるiの友達の総数) \mathrm{mod}~2

なので,これがa_{ii}になることはiの希望が満たされることと同値である.よって全員の希望を満たす割り当て方は存在すれば2冪であることがわかった.解の存在を示すには,拡大係数行列

\[\left(\begin{array}{cccc|c}a_{11} & a_{12} & \dots & a_{1n} & a_{11}\\a_{12} & a_{22} & \dots & a_{2n} & a_{22} \\ \vdots & \vdots & \ddots & \vdots & \vdots\\ a_{n1} & a_{n2} & \dots & a_{nn} & a_{nn}\end{array}\right)\]

のランクがもとの行列のランクに等しいことを示せば良い.行変形により第i_0行の第1列からn列までを0にできたとすると,実は同じ行のn+1列も0になる.実際,行変形としては第i_1,i_2,\dots,i_k行を第i_0行に足すという操作だけ考えればよい.このとき

\displaystyle \sum_{p=0}^ka_{i_pi_q}\equiv 0~(\mathrm{mod}~ 2)

より

\displaystyle \sum_{p,q}a_{i_pi_q}\equiv \sum_{p=0}^k a_{i_pi_p}\equiv 0~(\mathrm{mod}~ 2)

なので第n+1列も0になっている.ゆえに拡大係数行列のランクはもとの行列と等しく,解の存在が示された.\square

定規だけで円に接線を引く

平面上に円が描かれており,その周上の一点Pが指定されているとします.Pでこの円に接する直線を,定規だけを用いて作図することはできるでしょうか?

この問題には面白い解答があります.

まず円周上にP以外に4つの点をとります.これは好きなようにとって構いません.次にこれら5点を星型に結び,下図のように2本の直線を引いて,交点をQとします.すると実は直線PQが接線になっているのです!

f:id:fibonacci_freak:20171027224350p:plain

証明はパスカルの定理を用いると簡単にできます.

パスカルの定理.二次曲線上の一般の位置にに6点A,B,C,D,E,Fをとると,ABDEの交点,BCEFの交点,CDFAの交点は一直線上に並ぶ.
f:id:fibonacci_freak:20171027222909p:plain

今回の場合,接点Pを非常に近い2点P',P''に置き換えることで円周上に6点が並び,ちょうどP',P'',Qが一直線上に並ぶことが帰結されます.P',P''Pに近づく極限を考えることで,これが接線になることがわかります.

またパスカルの定理は円だけでなく一般の二次曲線に対して成り立つので,この方法は他の二次曲線にも使えることがわかります!

実際にこの方法で双曲線に接線をひいてみたものが下図です.

f:id:fibonacci_freak:20171027224429p:plain

イェイ!(*^^*)