多面体内の格子点の個数と体積について ： エルハート多項式と相互法則

平成

25年

度

学 位 論 文

多面体 内の格子点の個数 と体積 について

一エルハー ト多項式 と相互法則 一

兵 庫 教 育 大 学 大 学 院 教 育 内容・ 方 法 開 発 専 攻

M12150A

学 校 教 育 研 究 科 認 識 形 成 系 教 育 コ ー ス 菅 生

智 文

目 次

1.4

単体 第

1章

凸 多面体 の基礎

1.1

ア フ ィン空 間 6 6 11 17 24

26

26 32

45

45 51 61

71

71 73 83 85

90

1.2

凸集 合

1.3

凸多面体 第

2章

2.1 2.2 第

3章

3.1 3.2 3.3 第

4章

4.1 4.2 4.3 4.4 参考文献 錐 の 中の格 子 点 エル ハ ー ト多項式 単 体 内の格 子点 単体 の エルハー ト多項式 形 式 的幕 級数 錐 の 中の格子 点 の母 関数 に よる数 え上 げ 単体 のエル ハ ー ト多項式 と相互法則 多面体 の エルハー ト多項 式 単 体 的複 体 凸多面体 のエルハー ト多項式 と相 互法則 多面体のエルハー 格子′点の数 と体積 卜多項式 と多面 体 の体積

は じめ に

研 究 の 動 機 この論文 の 中心 となつてい るエルハー ト多項式 を考 えた ウジェー ヌ・エ ルハー ト(Eugene Ehrhart、 1906∼

2000)は

、フランスの高校 (リ セ )の 教 員 で あつた。 フラ ンスの高校 教員 を しなが ら、エル ハー ト多項 式 の相互 法則 を見つ けた。筆者 は、大学院修 了後 に高校教員 にな る。 そ の よ うな ところに興 味 を もつた こ とか ら、 この研 究 を進 め よ うと思 つた。 また、筆 者 は、数 学 の内容 の なか で、ベ ク トル が苦手 で あつた。 高校 の数 学 の 中で 、ベ ク トル は大 きな比重 を 占めてい る。 そ こで、高校 教員 にな つた際 に、ベ ク トル の必 要性 や 便利 性 を生徒 に説 くこ とがで き るよ うに、ベ ク トル に関 わ る理解 を深 め、大 学 院在 学 中に探 究 してお きたい とい うのが、研 究 の動機 の背景 とな ってい る。

研 究 の 内 容

t

よく知 られた定理 として、平面内の格子点を頂点 とする多角形に対 し

て、その内部の格子点の個数から面積を求める定理、ピックの定理があ

る。 ピックの定理 とは、境界をのぞいた多角形の内部にある格子点の個

数をを個、辺上にある格子点の個数を

b個

とすると、その多角形の面積

S

は

'

S=づ

+:b-1

と表す ことがで きる とい う定理 である。 この論文 では、 ピ ックの定理 を 拡張 して、

3次

元空間内の凸多面体 の格子点の情報 か ら、その凸多面体の 体積 を求 める定理 の存在 について述べ る。 その定理 を、本論文では、エルハー ト多項式 づ(民 η)、 グ(民η

)を

用いて 証明 してい く。エルハー ト多項式 とは、格子点を頂 点 とす る Ⅳ 次元空間 内の凸多面体

Pに

対 して、

Pを

η倍 に拡大 した図形 の内部 の格子点の数 をηで表 した式の ことで、これが ηに関す る多項式 となることをエルハー

3 卜が発 見 したので あ る。づ_(民η_)は

Pの

境界 を含 めた

Pの

内部 の格 子 ′点の 数 を数 えた多項式 で、づ*(民 η_)は

Pの

境界 をのぞい た部分 の格子点 の数 を 数 えた多項式 で あ る。 エル ハー ト多項式 では、

2次

元 、

3次

元 だ けではな く、Ⅳ 次元 で 凸多面 体 内の格 子 点 の数 を扱 う。ただ し、Ⅳ 次元 の図形 を扱 うた めには、2,3次 元 内で は、直観 的 に明 らかで あ る凸多 面体 の面や 辺 とい つた概 念 を線形 代数 の理論 を用 いて Ⅳ 次元 で も うま く定義 してお く必要が あ る。Ⅳ 次元 で は、直観 的 な定義 は使 えないので 、超 平 面 。支 持超平 面 といつた概念 を用 いて高次 元多面体 の 「面」 を定義 し、点

"が

RN内

の 凸多面 体

Pの

頂 ′点で あ る とは、点 “ が

Pの

0次

元 の面 とな る こ ととす る。 また 、線分 υ

zが

RⅣ 内 の凸多 面体

Pの

辺 で あ る とは、線 分 ν

zが

Pの

1次

元 の面 と な る こ と とす る。 この よ うに、ベ ク トル を扱 う理論 で あ る線形代 数 を使 うこ とに よ り、

2,3次

元 で は直観 的 に扱 っていた こ とを次 元 に よ らず に 定義す るこ とがで き る。

また、エルハート多項式を考えていくうえで、形式的幕級数が重要な

手法となる。形式的幕級数oい

]]と

は、Qを 係数とする人に関する級数

の集合のことである。つまり、

apllの

元は、有理数列

{α

じ

}を

用いて、

Σ

Qメ

t=0

=α

O+α

lλ +α2λ

2+…

.+απλπ

+.…

(1)

と表されるものである。このとき、この級数の収束については考慮せず形

式的な式として扱う。つまり、式

(1)は

係数に現れる数列

{αO,α l,α2,…

・

}

の

1つ

の表し方にすぎない。数列

_{αO,α l,α2,…

.}が

与えられたとき、数

列の各項を係数にもつ、

α

_O+α

l人 +α2λ

2+…

.+απλη十.… とい う形式 的幕級数 の ことを数列{αれ

}の

母 関数 とい う。形式的幕級数の 演算 として、加 法 と乗法 を行 うことがで きる。そ して、和 についての単 位元 。逆元 、積 についての単位元 も存在 し、場合 に よつては積 につ いて の逆元 も存在す る。形式的幕級数 とは、数 列 に対 して、それが満 たす漸 化式 を求 めた り、組み合 わせ論 にお ける数 え上げ問題 を考 えた りす る時 の手法 として特 に威 力 を発揮す る。 この論文 の主た るテーマの一つ として、エルハー ト多項式の相 互法則 があ る。エルハー ト多項式の相互法則 とは、

Pを

RⅣ 内の格子点 を頂点

4 に もつ 凸多面体 とす る と、

Pの

エルハー ト多項式,(民 η_)、 ダ_(二η_)には、 ダ_(民 η

_)=(-1)amP」

_(鳥

-2)

とい う関係 が成 り立つ こ とであ る。上の式 か ら、J(P,η_)と が_(民η)の 最高 次係 数 は等 しくな る こ とが分 か る。 また、各項 の係 数 の絶 対値 は等 しく な り、

1つ

お きに符 号 が入 れ替 わ つてい る。 最後 にエルハ ー ト多項 式 と体積 の関係 につ いて述 べ る。

Pを

R3内

の格 子点 を頂 点 に もつ 凸多面体 とす る と、

dim P=3の

ときは、

Pの

エルハー ト多項 式 の最 高 次係 数 は

Pの

体積 とな るので、

3次

元 内の格 子 点 を頂 点 とす る凸多面体 で も、 凸多 面体 の格子 点 に関す る情報 を用 い て体積 を求 め るこ とがで き るこ とが期待 で きる。 しか し、

3次

元 内の直方体 に内接す る図

1の

よ うな 四面体

Pで

は、直方体 の高 さが大 き くな るにつれ 、体積 も大 き くな らな けれ ばな らないが、

Pの

内点 で あ る格 子 点 の数 、

Pの

境 界上 にあ る格子 点 の数 は、それ ぞれ 常 に

0個

、

4個

とな り、体積 が変 わっ て も格子 点 の数 は不変 なので、格子 点 の数 の情報 で は

Pの

体積 を求 め る こ とがで きない こ とが分 か る。 そ こで、

_:格

子 点 の情報 も用 い る。

_:格

子 点 とは、座標 が

_:の

整数倍 とな るソ点で あ る。実際、RⅣ 内の凸多面体

Pに

対 して、境 界 をのぞ いた

Pの

内部 にあ る格子 ′点の数 を,、

Pの

境 界 上の格 子 点 の数 をb、 境 界 をのぞいた

Pの

内部 にあ る

:格

子点 の数 を グ、

Pの

境 界上 の

_:格

子 点 の数 を が と して、

3次

元 内の整 な凸多面体

Pの

体積 を

y

とす る と、

y=:ゲ

十

_伊―

_静―

:b

とな ることが、エルハー ト多項式の理論 か ら導 ける。 図

1:直

方体 の頂 点 か らな る四面体

5 論 文 の 構 成 第

1章

は、 この論文での基礎 とな る用語 ・概念 を定義す る。ベ ク トル 空間に関す る基本的な事項、例 えば、線形部分空間、

1次

独 立、

1次

従属 等 につ いては、既矢口として議論 を進 めてい る。ア フィン空 間に関 して定 義 して、 この論文で登場す る凸集合 、凸多面体、単体 を定義 してい く。 第

2章

は、 この論文 のテーマ となつてい るエルハー ト多項式 につ いて 具体的な例 を挙 げなが ら考 えてい く。エルハー ト多項式 について考 える ために錐 θ の中の格子点 を数 える。実際、エルハー ト多項 式に関す る理 論 は任意 の整 な凸多面体 に対 して成 り立っていることが分かってい るが、 まず、 この章 の後 半では単体 につ いてのエルハー ト多項式 を考 え ること とす る。 第

3章

では、第

2章

で行 つていた格子点の数 え方 を工夫す るこ とによ り、エルハー ト多項式 を考 えてい きたい。 まず、エルハー ト多項 式 を考 えてい く うえで、重要 な手法 となってい る形式的幕級数 について基礎的 な ことを述べ る。 この第

3章

で も、第

2章

の後半か らひきつづ き、単体に ついて考 える。 第

4章

では、一般 の多面体のエルハー ト多項式 について考 えてい く。そ こでまず、多面体 を単体 に分割す ることについて考 えてい く。次 に、凸 多面体 のエルハー ト多項式 とその相互法則 について考 え、その結果 を用 いて、多面体 の体積 を格子点の個数 か ら求 める関係 式 について述 べ る。

第

1章

凸 多面体 の基礎

以下、ベ ク トル空間に関す る基本的な事項 、例 えば、線形部分空 間

,1

次独 立

,1次

従属等 については、既知 として議論 を進 める。

1.1

ア フ ィン空 間

定義

1.1.17を

RⅣ か ら RⅣ へ の写像 とす る。 この とき、

Tが

ア フィン 変換 で あ る とは、実数 を成分 とす るある Ⅳ 次正則行 列 σ お よび 、ベ ク ト ル α ∈RⅣ が あって 、任意 の “ ∈RⅣ に対 して、

T(")=θ

“

+α

が な りたつ こ とで あ る。 ア フ ィン変換

T(")=σ

_"+α

の特別 な場 合 と して 1.α

=0の

とき、ア フ ィン変換

Tは

1次

変換。

2.θ

=E(Eは

単位 行 列_)の とき、ア フ ィン変換

Tは

平行移動。 とな る。 逆 にい えば、ア フィン変換 とは、

1次

変換 と平行 移 動 の合成 で あ る とい うこ ともで き る。 定義

1.1.2 RNの

空 でない部分集 合 ″ が ア フィン部分空 間 で あ る とは、

RNの

線 形部 分空 間 び とベ ク トル α が あって、 フア

=び

+α

が成 り立つ こ とで あ る。 ここで び

+α

とは

{"∈

RArレ

=%+α

,∃

%∈

び

} で表 され る集 合 の こ とで あ る。

第

1章

凸多 面体 の基礎

7

命題

1.1.3Tを

RⅣ 上 のア フ ィン変換 、″ を RⅣ 内のア フ ィン部 分空 間 とす る と、

T(7)も

ア フ ィン部分空 間 とな る。

証明

ノを一次変換 として、

T(″

_)=∫

_(″

_{)+β とお く。びを線形部分空間}

として、レ

/=び

十αとお く。 このとき、

T(レ

7)={T(ω

_)ル

7Dω

_}

={T(し

+α

)￨び

∋鶴

}

={バ

し

_+α)+β

_lび

∋鶴

_}

={∫

(し

)+ノ

(α)十

β

lび

∋し

}

=ノ

(び)十 (∫(α)十

β

)

となるが、∫

(び)は

ベクトル空間、

(∫(α)十

β

)は

ベクトルなので

T(p1/)は ア フ ィン部 分空 間 とな る。

□ よ く知 られ てい るよ うに,RⅣ の線形部分空 間 υ の次元

dimび

とは、次 のいずれ か の値 で あ り、

1.び

を生成 す るベ ク トル の個数 の最小値

2.び

を生成 し、

1次

独 立 なベ ク トル の個 数

3.び

内の

1次

独 立 なベ ク トル の個数 の最 大値

これ らは、すべて等 しい値になる。

(I司

参照。

)

ベ ク トル空間の次元を用いて、アフィン空間にも次元の概念を導入し

たい。

定理

1.1.4T/T/=び

+α を

RⅣ

_{内のアフィン部分空間として、βを}

T/1/の

元 とすると、

7=び

+β となる。

証明

アフィン部分空間の定義より、

PT/=び +α

={"+α

_l"∈

び

_}と

な

るので、ある

"0∈

びがあって、β

=“

0+α

である。したがつて、

び

+β

=び

十

“

0+α

=(び

十

"0)+α

=υ

+α

=T/1/ とな る の で 、題 意 は示 され た。

□

ゆ  

   

  颯

が               と れ                                     ス υ ” ，             れ さ “     ヽ 、 １ １ ノ １ て       〓 し       ち 敵     れ   ヽ Σ 一

碑

︱

_た

_だ

_し

 

ψ

﹄

れ

フ       β

凸  

。・・５ 

ヽ    

］ ”

︲，４ょり、

二 早   １ き       る     １ ． １   理 と     な   明 理 第   定 ︵ ︶       と   証 定 は び の元 とな る。 また、

υ=Σ れ

τ=二1 なので、 ν ― “1=(ι lωl+ι2“

2+…

・+tπ “π)一 κl

となる。Σ〕

ち

=1よ

り

、ι

l=1-(ι

2+…

°

十ι

π

)と

なるので、

づ=1 ι

l"1+ι

2"2+…

°十 ιπ “π―"1

=(1 (ι2+…

°十 ι_2))"1+ι

2"2+…

・+ιη "れ 一_“1

="1 (ι 2+…

・+ιれ)πl+ι2“

2+…

・+ιπ "π ― "1 =ι

2("2 π l)+…

・+ιぼ “π一"1) とな る。 したがつて、ν― “1は びの元であ り、νは

7=び

十“

1の

元 と なる。

□ 補題

1.1.6空

間

RNの

線形部分空間 び,ア と点 α,α′があって、び

+α

=

♂

+α

′な らば、び

=び

′となる。(α とα′は等 しい とは限 らない。) 証明 空間

RNの

線形部分空間 硫 び と点 α,α′が び

+α

=び

′

+α

′をみ たす とす ると、び

=び

+(α

′―α

_)で

ある。 また、 α ∈び

+α

=び

′

+α

′ となるので、(α ―α′)が び′に含まれ る。 したがつて、 び

=び

′

+(α

′―α

_)=び

′ とな る。

□

第

1章

凸多 面体 の基礎

9

上 の補題 1.1.6に よ り、次 の よ うにア フィン空間 に も次元 を定義 す るこ とがで きる。 定義 1。

1.7ア

フ ィン部分空 間p1/∈

RNに

対 して、T/1/がベ ク トル 空 間 び とベ ク トル α を用 い て

7=び

+α

で表 され る とき、線形 部 分空 間 び の 次元 をア フ ィ ン空 間

7の

次 元 とい い、dim p1/で 表 す。 ア フ ィン空 間 の次元 を、次 の よ うに直接 とらえ る こ ともで きる。 定理 1.1.8 RⅣ の ア フィン部 分空 間

7に

対 し、″ に含 まれ る有 限集 合 {ωo,ωl,…

・

,ω

d}の

うち、

(ωl― ωo),(ω2 ω O),… ,,(ωd一 ωo) が

R上

線形独 立 とな るものの個数 の最大値 を考 える と、 これが(pr/の次 元

_)+1に

一致す る。(つま り上記の よ うな αの最大値 がT//の次元 となる) 証明 アフィン部分空間について、

T/7=び

+α

となる線形部分空間 びおよ び α ∈RⅣ を とる。p1/⊃ {ω O,…・,ωα}の うち(ωl―ωo),…・,(ωα一ωo)で1

次独立 となるものの個数の最大値 を

D+1と

す る。 この とき、

D=dimび

を示す。

び∋

{υl,・

…

,υ

d}が

1次

独立であるとする。このとき

ω_O=α ω

l=υ l+α

ω

a=υ d+α

は

7の

元 で 喝 ―ω

O=υ

メゴか ら (ωl― ωo),(ω2 ω O),… .,(ωご ― ωo)

は

1次

独立である。よつて

#{ω

o,…

・

,ω

分

=α

+1≦

D+1と

なり、

dimび

_≦

pを

得る。

一方で、

{ωl,・

…

,ωd}⊂

7で

(ωl― ωo),(ω2 ω O),…・,(ωd― ω_o)

第

1章

凸多 面体 の基礎

が

1次

独 立 とす る。 この とき、ωα

=%J+α

(i=0,… 。,d)す る と、

ωづ

ω

O=鶴

j し

0∈ び

で 喝 一ωO(づ

=1,…

・,α)は

1次

独 立 な び の 元 で あ る。 よつ て 、

#{ω

l―

ω

o,…

・

,ωd―

ωO}=α ≦

dimび

となる。 したがつて

D=dimび

である。

□

定理

1.1.9 RN内

のア フィン部分空 間 7、 及 び、ア フィン変換

Tに

対 し て、

dim″ =dim T(″

)と な る。 証 明 まずT(″

_)=ス

_(π)十

buは

正則

)と

お く。 定理 1.1.8よ りT(T/1/) の次元 は dim T(T/7) =maX{α ∈NIT(7)∋ _{∃υ も,…} ,υi S・t.01-島 ,… ,り,一 り3が独 立 }

=maX{α ∈_Np1/∋ ∃υo,… .,りαS.t.T(υl)一 T(Oo),… ,,T(りα)一 T(Oo)が 独 立 _}

=maX{α

∈

Nlp1/∋

∃

υ

O,.… ,υ

α

S・t.ス_(υl―

υ

o),… _{,ス (υ}

α一υ

o)が

独立

_}

とな るが、ス は正則 なので、行列 ス をベ ク トル にか けて も

1次

独 立性 は 変 わ らないか ら、最後 の値 は次 に等 しい。

maX{α ∈ NI″ ∋ ∃Oo,・ .・ ,υ_αS.t.り 1-り 0,...,り_{α ― υ}Oが独 立 _}

=dilnフア □ 定 義 1.1。

10空

間 RⅣ の空 で な い部 分集 合 χ に対 して 、

X内

の点 α を一

つ固定し、部分集合

{"一

α

l"∈

X}が

張る

RⅣ

の線形部分空間をびとす

る。 この とき、び

+α

を

AFF(χ

_{)と 表 し、}

Xが

張 る

RNの

ア フィ ン部分 空間 とい う。 定理 1。1.1l RⅣ の部 分集合 χ に対 し、定 義 1.1.10で 定義 した ス

FF(χ

₎ は α に依存 しない。

証明

χ⊂

RⅣ

、X∋ α

,α

′

をとる。

{"―

引

"∈

X}で 生成される線形部

分空間をびとして、

AFF(χ

_)=び

+α

とする。

{“

一♂

￨"∈

X}で

生成

10

第

1章

凸多 面体 の基礎 され る線形部 分空 間 を び とす る。まず、び ⊂ び′を示すために、各 “∈χ につ いて

"一

α が び に含 まれ るこ とを示 す。 実 際 、 "― α =("― α ′ )― (α ― α ′ ) とな り、("一 α′)、 (α―α′)が 共に線形部分空 間 び′に含まれ るので、(“一α) は び の元 とな る。 よつて び ⊂ び′となる。 同様 に、び′⊂ び も示 され るか ら び

=び

で あ る。 最後 に α′一α ∈び よ り び′

+α

′

=び

―_(α′― α

_)+α

′

=び

+α

とな る。

□ 定義 1.1.10か ら容 易 にわか るよ うにア フ ィン部 分空 間 ″ が

RN内

の部 分集合

Xを

含 む な らば、

7は Xの

張 るア フィン部 分空 間 を必然 的 に含 む。 つ ま り、χ の張 るア フ ィン部 分空 間 とは

Xを

含 む最小 のア フ ィン部 分空 間 とい うこ ともで きる。

1.2

凸集合

定義

1.2.l RNの

空 でない部分集合 スが凸集合であ るとは、ス 内の任意 の点 ",ν に対 して、点",υ を結ぶ

RN内

の線分 {ι

_"+(1-ι

)υ10≦

ι≦

1,オ

∈

R}

が ス に含 まれ る こ とで あ る。 凸集合 の例 と して、三角形・ 円板 。球体 。四面体・立方 体 な どが あげ ら れ る。

定理

1。2.2 RⅣ

の凸集合からなる空でない族

_{ス

づ

_}(づ

∈」

_)力

｀

あつたとき、

∩に」

Aづ

が空集合でないならば、∩た

_.ス

づも凸集合である。

証明

_∩に

_fス

じ

内の任意の点

",υ

をとる。このとき、任意のづ

crに

つい

て、点

“

,υ

はスメこ含まれる。ん は凸だから、定義

1.2.1よ

り、

0≦

ι≦

1 １ ■

第 1章

凸多面体の基礎

12

となるι∈

Rに

ついて、ι

"十(1-t)ν

がスメこ含まれる。りは任意だつたか

らι

“

十

(1-ι)ν

は ∩ スをに含まれる。 したがつて、

tcI {ι

“

十

(1-t)υ 10≦

ι

≦

1,ι

∈

R}⊂

∩五

j づcI となる。

これより

_{、∩んは凸集合である。}

□

づcr 定義

1.2.3 RNの

空 でない部分集合 χ が あった とき、

ス

={ス

⊂

RⅣ

_{降は凸集合,X⊂ ス}

_}

とすると、■。=∩

A∈

ススは

Xを

含む凸集合の中で最小となる。このよう

な ス

0を

CONV(X)と

表 し、

Xの

凸閉包 とよぶ。 補題 1.2.4 RⅣ の凸集合 スが、 "1,.… ,“υを含むな らば、 0≦

ち∈

R,Σ

ち

=1

を=1

となるι

t(づ

=1,…

・

,υ)に

ついてΣ〕ち

_"tは

スに含まれる。

づ=1 証明 υについての数学的帰納法 を用いる。 1.υ

=1の

とき、ι

l=1よ

りιl“

1=“

1∈ スであ る。 2.υ

_=た

の とき成 り立つ と仮定す る。 υ

=た

+1の

とき、

jl=1な

らι

2=…

・_=ιた

_+1=0で

Σれ

=“

lCA

づ₌₁

である。また、ι

l≠

1な

ら

彗れ

=れ

+に

-0基

_(島

→

第

1章

凸多 面体 の基礎

13

と

な

る

。

こ

の

と

き

、

_ち

ち

=1-ι

lよ

り

、

Σ

」

(丁

芸

百

)=1な

の

で

、

帰糸内法 の仮定 よ り、

:(∴

a)は

スの元 となる。 したがつて、 スが凸であることか ら、

れ十

に

一

→

_:(T壬

_≒

_T→

□ は ヽ ｔ ｒ リ

胞

 

脚

湖

よ

り

_、

・

_・

２

_．

５

上   題 以   補

ι

α十

(1-→

β

=Σ

←

銑

+に

一→→吻

`=1 とな る。 この とき右辺 の係数 の和 を考 え る と

Σ←

け に一の

→

=ι

Σ

_E銑

十は一のΣ島

づ=1 じ₌₁ づ=1 =ι

+(1-ι

) =1

第

1章

凸多面体 の基礎

14

である。また、包ば,sを が

0以

上であることか らιzづ

+(1-ι

)St≧ 0と なるの で、ι_{α十 (1-ι})β はX′ の元である。つま り、χ′が凸 となる。

□ 補題

1.2.6Xを

RⅣ 内の部分集合 とす る と

θ

OⅣ

1/(χ

)=し

_l

θ

οⅣ

1/(S) S⊂X S:有 限 とな る。 証 明

Sを Xの

有 限部分集合 とす る と、

θ

OⅣ

1/(S)⊂ θ

OⅣ

y(χ

)

なの で、

∪θ

ο

Ⅳ

y(S)⊂

θ

OⅣ

y(χ

) S⊂X

S:有 限

となるのは明 らか。

一方、θ

OⅣ

y(X)は

Xを

含む最小の凸集合だか ら、_{∪ θ}

OⅣ

y(S)が

S⊂X

S:有 限

Xを

含 み、凸集合 であることを示せ ば

し

l

θ

ο

/Vy(S)⊃

σ

OⅣ

y(χ

) S⊂X

S:有 限

とな り証 明 は終 了す る。

Xの

任意 の元

_"に

対 して 、

"∈

θ

OⅣ

y({π})⊂

∪θ

OAry(S)

S⊂ χ S:有 限

より

_{、χ⊂∪θοⅣ}

T/(S)は

正しい。また、

S⊂X

S:有限

α∈θ

OⅣ

y(■

_),

_ス⊂

X, A={α

_l,…

_・

_,a7れ

}

b∈

θ

OⅣ

y(3), 3⊂ χ

_{, 3={bl,・}

…

,bm}

に対 して 、

第

1章

凸多面体 の基礎 とす る とき、補題 1.2.5よ り、

α

_=Σ

λ

_づ

_Q⑩

夕を

∈

R,Σ

ん

を

=⇒

づ=l t=1

b=Σ

_ち

_{り ⑩≦ら∈}

R,Σ

_ら

=⇒

′=1 」=1 と表 せ るので 、

C=Σ

ι

ん

じ

Q+Σ

(1-つ

り

場

づ

=1

′=1 とな り、

Σ

Eι

た

ら

十Σ

E(1-→

り

=ι

Σ

Eた

づ

+に

一→Σ

Eら

づ

₌₁

」=1 づ_{=l J=1} 1 かつ ι_{れ ≧}

0,(1-ι

_{)J′ ≧}0 となる。よつて、ネ甫題1.2.5よ り、c∈ θ

OⅣ y(A∪

3)で

ある。したがつて、

∪θ

ο

Ary(S)

S⊂ χ S:有 限 は凸集 合 とな る。

□ 以下、RⅣ 内の部分集合

Xに

対 して、

Xの

生成す る

RNの

ベ ク トル空間 を

_(X)と

表 す。

X={α

l,・ …,απ

}な

らば、(χ)を 〈αl,.… ,απ)と もか く。 定理

1.2.7Xを

RⅣ 内の部分集合 とす ると、

AFF(χ

_)=AFF(θ

OⅣ

1/(χ₎₎

とな る。 証 明 θ

ONy(χ

_{)の元 υに対 して、} ν∈θ

OⅣ

y(5)(S⊂

X,Sは

有 限)

となる。よつて、S={“

1,・

…

,“

れ

}と

すれば、

ν

=Σ

れ しち…メπ∈χ

,Σ

ち

=⇒

じ₌₁ じ=1 15

第

1章

凸多面体 の基礎 と表せ るので、

とな る。

一方 、χ ⊂ θ

OⅣ

y(x)で

あるので、

〈

θ

OAry(χ )_π

o)⊃ (χ

―

_"o)

で あ る こ とは、明 らかで ある。 よつて、

(θ

OⅣ

y(χ

)一_・

o)=(χ

―_"o)

とな る。 した が つて、

ス

FF(θ OⅣ

y(χ

_))=(θOⅣ

y(χ

_)一

“o)十

"0

=(χ

―π

_o)+"o

=4FF(χ

) とな る。

□ 定義 1.2.8 RⅣ 内の 凸集 合 ス の次 元 とは、ス が張 る RⅣ の ア フィ ン空 間 五

FF(■

_)の次元 とす る。

RNの

部 分集 合 ス で あつて も

dimス

が rVと は限 らない。 例 えば、

3次

元空 間 に、三 角形 △ が浮 かんでい る状態 もあ りえ る。 この とき、△ の次 元 は

2で

あ る。 定理 1.2.7よ り、ス

=θ

OⅣ

y(x)と

表 せ る凸集 合 ス につ いて、ス の次 元 は、

AFF(χ

_)の次元 に一致す る。 16 κ                               ０ ” ヽ 、 ︲ ︲ ′ ノ ち                 一

越

Ⅸ

Ⅷ

 

司

 

 

 

申

一     一 ２         ０ ＞ 観       鮨 ︶           ” ち     ち           一

π

Σ

７

Σ

Ｈ

て

_、

詢

咋 

  

_一一

  

 

よっ



Ｍ、

０   ０ 一             る   σ ν           な   く と 一 九 の π 一 Ｘ ま

第

1章

凸多面体 の基礎

1.3

凸 多面体

定義

1.3.1空

間RⅣ 内の部分集合

Pが

RNの

凸多面体であ るとは、

P=

θ

OⅣ

y(χ

)と なる

RN内

の有限集合

Xが

存在す ることである。また、凸 多面体

Pの

次元

dim Pを

Pの

凸集合 としての次元 とす る。 一般 にRⅣ 内の集合

Xに

対 して、次の よ うに

Xの

内点や境界点 とい う 概念 があ り、 これ らの概念 は、開集合 、閉集合 の定義 に密接 に関わつて い る。 まず、空間

RNの

元 α、α

>0に

対 して、 3d(α

_)={"∈

RⅣ_II"―

α

_l<α

_} とお く。 つ ま り、3d(α

)は

α を中心 として半径 αの開球 体 で あ る。 定義

1.3.2空

間 RⅣ 内の部 分集合 χ、及 び 、RⅣ 内の元 α

,bに

つ いて、 ● αが

Xの

内点で あ る とは、

3a(a)⊂

Xと

な る よ うな正 の数 αが存 在す る こ とで あ る。

●

bが

Xの

境界点であるとは、任意の正の数αに対して

Bd(b)∩

X≠

0

かつ、

Bd(b)￠

Xと

なることである。

内点 とい う概念 に よつて、開集合、閉集合 は次 の よ うに定義 され る。 定義

1.3.3空

間

RNの

部分集合

Xに

対 して、 ・

Xが

開集合であるとは、

X内

の任意 の元

_"が

Xの

内点 とな ること であ る。 ・

Xが

閉集合であるとは、χ の補集合 が、開集合 とな ることで ある。 17

○

第

1章

凸多面体の基礎

18

例 えば、前頁で述べた よ うに、

3次

元空間内で、

2次

元の三角形 が浮か んでいた場合 、定義1.3.2か らす る と、三角形上の全ての点が、境界点 と して扱 われて しま うことになる。 しか しなが ら、ここでは三角形 の辺以外 の点 を

"内

点 "と して扱 いたい。 したがって、次の よ うな定義 を考 える。 定義

1.3.4空

間RⅣ 内の凸多面体

Pを

考 え、

Pの

張 るアフィン部分空間 をT/7とす る。 この とき、

Pの

点 α

,bに

対 して、 ●αが凸 多面体

Pの

内点である とは、

3d(o)∩

l1/⊂

Pと

なる よ うな 正の数 αが存在す ることである。 ・

bが

凸多面体

Pの

境界点であるとは、任意の正の数 αに対 してBd(b)∩

P≠

0、

かつ、βα

_(b)∩

″ ￠

Pと

なることである。

RN内

の凸多面体

Pに

対 して、凸多面体 としての

Pの

境界点の全体を

∂

Pと

かく。

(定

義

1.3.4参

照

) 図 1.1:凸多面体の次元 凸多面体 の内点、境界点 を、定義1.3.4のよ うに してお くと、定義1.3.2 では、

"境

界点 "と なる図1,1の よ うな “が

"凸

_{多面体の内点}

"と

_して扱 われ るよ うになる。 特 に例外 的なのは、

Pが

1点 {P}の

ときである。 この とき、

Pの

張 る アフィン空 間p1/は

1点

とな る。正の数 αに対 して、3ご_{(P)∩ T/7は}

Pに

含 まれ るので、点

Pは

多面体

Pの

内点であ り、3d(P)∩

P≠

0で

あるが、

BdO)∩

レ

/⊂

Pと

な ることよ り、∂

P=0で

ある。 次に、

2次

元,3次元内では直観 的に明 らかである多面体の面・辺 とい う 概念 を Ⅳ 次元で うま く定義 したい。Ⅳ 次元 では、直観的な定義 は使 えな いので、以下 に順 に述べ るよ うに厳密 かつ論理的な定義 を与 える必要が ある。

第

1章

凸多面 体 の基礎

定義

1.3.5 RⅣ

内の部分集合∬が超平面であるとは、

(α l,・

…

,α

N)≠

(0,… ,0)

であるような実数 α

`,ろ

が存在 して、

言 い換 えれ ば、空 間 RⅣ 内の超 平 面 とは次 元 Ⅳ

-1の

ア フ ィン部 分空 間で あ る。

RNの

超 平面 ∬ が定 め る

RNの

2つ

の閉半空 間 を

●

∬

(■

l={(■

_1,″ 2,・

・

・

,″

Ⅳ

)∈ RⅣ_IΣ

胆

1%銑

≦

b}

●

∬

( )={(″

_1,″ 2,・

・

・

,″

Ⅳ

)∈ RⅣ_IΣ

胆

l

α

j均

≧

b} の よ うに表す。(実際には、〃(+),∬←)は ∬ を定める αl,.… ,αN,ら によつ て決 ま る。例 えば、αl,・ …,αⅣ,ら の全ての符号を入れかえて も∬ は不変 で、 この とき ∬(+)と _∬( )が_{入れかわる。}

_)〃

(+)∩ _∬

()=〃

_{でぁ る。} 定義

1.3.6空

間RⅣ 内の凸多面体

Pが

あつた とき、空間RⅣ 内の超平面 Jfが

Pの

支持超平面である とは、

1.P⊂

〃(+)ま_たは、

_P⊂

_∬( )

2.0≠ P∩

∬災

P

を満 たす ことをい う。 定義 1.3.7 RⅣ 内の凸多面体

Pが

あ り、

Pの

部分集合

Fが Pの

面である とは、

P∩

〃

=Fで

あるよ うな、

Pの

支持超平面 ∬ が存在す る ことで ある。 図1.2の よ うに、〃 が凸多面体

Pの

支持超平面であるとは、

Pが

〃 の 片側 だけに入 つていて、

Pの

一部が 〃 に含 まれてい ることを示 している。 また、 この とき

Pと

∬ の共通部分である線 分 ″νが

Pの

面 になる。例外 的な場合 として、

Pが

1点

_{P}の

とき、

Pは

面 を

1つ

も持 たない。 以 下 、RⅣ 内のベ ク トル αl、 α

2に

対 して 、そのベ ク トル αl、 α2の内 積 を[αl,α

Jと

表 す。 定理 1.3.8 RⅣ 内の凸多面体

Pは

高々有 限個 の面 を持 ち、各 々の面 は

RN

の凸多面体 で あ る。 19 ヽ ︱ ＞ Ｉ ノ ■ υ 〓 ″ α

Ｎ

〒

ん

同

Ⅳ Ｒ ∈ Ⅳ ″ ″ ｆ 伸 Ｆ ヽ る 。

卜 

 椰

こ る れ さ 表 と

20 第

1章

凸多 面体 の基礎 と表 され るので、

訓

降 

る。

_協

 

 

 

臓

ｋ

＆

︲

，

α

_Ｊ

︲

司

υ

Σ

朝

城

レ

υ

_獅

Ｈ

υ

_≫

Ｈ

υ

嘱

引

[υ,α

]=

一 一       一 一     〓

第

1章

凸多 面体 の基礎 となる。 よつて、 (1.1)の点 ν∈

Pが

∬ に含 まれ る ⇔ [ν,α

]=b

⇔ ι_′

_+1=…

・_=ιυ

₌₀

⇔ν

=Σ

れ

づ=1

⇔ν∈θ

OⅣ

y({ν l,・

…

,鋳}) であるか ら、面

F=P∩

Jfは υl,.… ,鋳 の凸閉包 とな る。したがつて 、面は

υ

l,…

・

,鋳

の選び方で決まるので有限個となる。また、

F=θ

OⅣ

y({υl,・

…

,ν

」

}) よ り面 も凸多面体である。

□ 上記 の証明か ら直 ちに次の系 を得 る。 系 1.3.9 RⅣ 内の凸多面体

Pは

RN内

の有 限集合 χ の凸閉包であると仮 定 し、∬ を

Pの

支持超平面 とす る と、

P∩

Ff=σ

OⅣy(〃

∩

X)で

ある。 定義

1.3.10 RN内

の凸多面体

Pの

面

Fが

i‐面であるとは、

Fの

次元がJ であるときにい う。

定義

1.3.11点

"が

RⅣ

内の凸多面体Pの 頂点であるとは、

{π

}が

Pの

0-面

となることである。凸多面体

Pの

頂点全体の集合を頂点集合という。

また、

Pの

1-面

を

Pの

辺という。さらに、

dim P=α

のとき、

Pの

(α

-1)

面を

Pの

facetと

い う。

定理

1.3.12 RⅣ

内の凸多面体

Pが

部分集合 χ の凸閉包であるとき、

P

の頂点は、

Xに

含まれる。

証明

αを

Pの

頂点 とすると、P∩ ∬

={α

}と

なる支持超平面 ∬ があ

る。

このとき、系

1.3.9よ

り

P∩

″

=θ

OⅣ

y(If∩

_χ

_)={α

_}と

_なる。

_し

たがつて、〃∩

X={α

}と

なるので、Pの 頂点は、χに含まれる。

□

P=θ

OⅣ

7(X)の

とき、頂 点集 合

yは xに

含 まれ て い る こ とは分 か った が、 この とき、頂 ′点集合

yだ

けで十 分 で あ ろ うか 、つ ま り、

P=

θ

OⅣ

y(y)と

な るだ ろ うか。

3次

元 で凸多 面体 を想 像すれ ば直観 的 に正 しい と感 じ られ るが、実 際 に これ は Ⅳ 次元 で正 しい。 つ ま り、次 が成 り 立つ。 １ ■ ０ ４

第

1章

凸多 面体 の基礎 定理 1.3.13 RⅣ 内 の凸多 面体

Pに

対 し、

Pの

頂 ′点集 合 を

yと

す る と、

P=θ

O/VT/(y)と

な る。 また、凸多面体

Pの

境 界部分 は

Pの

面 の和集合 で あ る こ とは

3次

元 で 凸多面体 を想 像 すれ ば正 しい と感 じられ るが 、実 際 に これ も Ⅳ 次 元 で正 しい。 つ ま り、次 が成 り立つ。 定理

1.3.14凸

多面体

Pに

つ いて、∂

Pは Pの

面 の和集合 に等 しい。 定理 1.3.13と 定理 1.3.14は 、

2次

元や

3次

元では直観 的 に正 しい と感 じ られ るが、一般 の次元 では証 明 を要す るこ とであ る し、

2,3次

元 で も厳密 な証 明 はや や 工夫 を要す る。 しか し、 こ こでは これ らを正 しい と認 めて 議 論 をすす め る。詳 しい証 明 につ いて は

2]を

参 照 され た い。 定理 き、 (1.動 証 明 .,“

υ

_}と

すると

分 条件 は

一糾

 ＼

・・︲

_﹁／

。３．．５

_¨

   

 雄

ｌ Ｐ             一 不 と表

哺

可

卿

_卸

ち     ま 、 ば

の

 

 

一

一

 

 

分

で

Ｐ     “     十 Ｆ 凸多面体

であるとする。

に対 して、

"グ

超平面

″={Z∈

RⅣ_I[α

_,Zl=b},α

∈

RA7,b∈

R

が

Pの

支持 超 平面 で 、

P⊂

〃

(),P∩

∬

=Fで

あ る と し、

〃∩

_{"1,“2,・

…

,"υ

}={"1,・

…

,"s}(1≦

S<υ

)

とおく。

_(S=υ

とすると、定理

1.3.13よ

り

P=θ

OⅣ

1/({"1,・

…

,“

π

})⊂

〃

となつてしまうから

s<υ

となる。

)こ

のとき、

し

,al=b(1≦

j≦

Sの とき

)

レ

,“

′

]>b(S<J≦

υのとき

)

Pの

任意 の面

F

り、空 間

RNの

第

1章

凸多面体 の基礎 であるか ら、

し

,d=Σ

ちレ

,亀

]>bΣ

ち

=b

23 づ==1

となるので、

“

は

Fに

属 さない。 したがって、

"グ

∂

Pで

ある。

次に、必要性を示すために点

“

が

Pの

内部 P― ∂

Pに

属すると仮定し、

とお く。上の結果 よ り、z∈

P―

∂

Pで

ある。 “∈

P―

∂

Pよ

り、T/7を

P

の張 るアフィン部分空間 として、Bd(“_)∩ p1/⊂

Pと

なる正 の数 αが存在 す る。 この とき、3α_(a)∩ p1/の_{内部 の点 νは、全 て}

Pの

_{点である。}

"=zの

ときは、(1.3)によって、示す こ とは何 もないので

_"≠

zと

す る。 この とき、線分z“ を

"の

側 にほんの少 し (長さα未満

)延

長 した′点 を νとす る と、ν

cPで

_"は

線分zυ _{を内分す る。} π ＋ ＋ ” ヽ １ ′ ノ ー エ 一 υ ／ ′ ︲ ヽ ＼ 〓 Ｚ ヽ ｌ ︲ ′ ノ 〓 Ｓ υ Σ Ｈ Ｒ ∈ Ｓ ＜ 一 ０ ／ ′ ︲ ︲ ヽ ヽ ” Ｓ

υ

い

≫

_″

Ｈ

〓 ν “ ヽ 、 ︲ ′ ／ ヽ 、 ︰ ′ ノ ー エ 一 υ ／ ｒ ｉ ｌ ヽ ■ ０ ヽ ︱ １ ／ ヽ １ ′ ノ ー エ 一 υ ／ ｒ ｉ ヽ ＼ 十 Ｓ 一 ／ ｆ ｌ ＼ ＜ ０ (1.3) (1.4) つ ま り、実数

0<ι

<

のとき、

P=θ

OⅣ

y({

とすれば、

となる。 この とき、

1で

“

=(1-ι

)ν

+;Zと

な るものが存在す る。

“

1,… .,"υ})よ

り、

＋     ↓ ＞   一 一     ， ＜ １       ０ ／ ＝ い ヽ   ＞ 一

υ

Σ

Ｈ

﹄

一 一       ＞ ”       １ 一 υ >0,ι

>0よ

り、 ∈R

第

1章

凸多面体の基礎 であ り。 また、 Σ

E((1-ι

)S,+ι

_(:))=Σ

ISt―

ι Σ」 St tt ι

=1-ι

+ι =1 とな るか ら、式 (1.4)は 式 (1,2)の 形 の表 示 となってい る。

1.4

単体

定理 1.4.l RⅣ 内の次元 αの凸多面体

Pの

頂 点の個数 は、少 な くとも α

+1

で あ る。 証 明

RⅣ

内 の 凸多 面体

Pに

対 して 、

Pの

次元

=ス

FF(P)の

次 元 とな

る。

Pの

頂点集合

1/={"1,,…

,"υ

}と

すると、定理

1.3.13よ

り、

P=

θθⅣ

1/(y)な

ので、定理 1.2.7も用 いて

AFF(P)=AFF(θ

OⅣy(y))

=AFF(1/)

=(“

2 "1,・ …,"υ 一 “

1)+"1 (1・

5) とな る。 よつて、

Pの

次元

=dim("2 "1,…

.,"υ ―

"1) (1・

6) で あ り、 した が つて 、α≦ υ

-1で

あ るので 、υ

>d+1と

な る。

□ 定義 1.4.2 RⅣ 内の次元 αの凸多 面体

Pの

頂 点 の個数 が α

+1で

あ る と き、

Pを

α単 体 とい う。

定理

1.4。

3P=θ

OⅣ

y({“0,… .,“d})が

α単体ならば、

(″1-“ o),…・,("α ― “ o) は

1次

独 立 とな る。 24 □

第

1章

凸多 面体 の基礎

証明 RⅣ 内のご次元単体

P=σ

OⅣ

T/({"o,・

…

,"α

})に

ついて、定理

1.3.12よ

り、頂′

点は、全て

_{{“ 0,.…}

,"d}に

含まれる。

Pは

α単体なので頂

点α

+1個

だから、

{"0,・

…

,"d}が

頂点全体の集合に一致する。式

(1.5)、

式

_(1.6)と

同様にして、

dim(・

1-π

o,.… ,"α

"0)=Pの

次元

=α

とな る。 よつて、 (“1-“ o),…・,(“α 一 “ o) は、

_("1-"o,…

.,“_d―

"0)の

基底 とな り、

1次

独 立 とな る。 25

26

第

2章

錐 の 中の格 子 点

第

1章

で は 、 この論 文 で の基礎 とな る用語 。概 念 を定義 して きた。 こ の第

2章

で は 、論 文 のテー マ とな ってい るエルハ ー ト多項 式 につ い て具 体 的 な例 を挙 げなが ら考 えてい く。 実 際 、エルハ ー ト多項 式 に関す る理 論 は任 意 の 凸多面体 に対 して成 り立つ こ とがわか ってい るが 、 まず、 こ の章 の後 半 で は単体 につ いてのエル ハー ト多項式 を考 え る こ ととす る。

2.1

エルハー ト多項式

まず、必要 な用語 を定義す る。 定義

2.1.1空

間RⅣ 内の点 α

=(α

l,α2,,… ,αⅣ

)に

対 して、 ・ αが整数点、または格子点である とは、αづ(1≦ j≦ Ⅳ)が 全 て整数 であること ・ αが有理点である とは、αづ(1≦ づ≦ Ⅳ)が全 て有理数 であること とす る。 定義

2.1.2空

間RⅣ 内の凸多面体

Pに

対 して、 ・

Pが

整で ある とは、

Pの

任意 の頂点が整数点 であること ・

Pが

有理的であるとは、

Pの

任意 の頂 点が有理点であること とす る。 定義 2.1.3 RⅣ 内の集合 χ、及び、 自然数 ηについて

η

χ

={η

α

lα

∈χ

} と定 める。つ ま り、ηχ とは原点 を中心 と して

Xを

η倍 に拡大 した図形 である。

第

2章

錐 の中の格子点

27

定義

2.1.4空

間RⅣ 内の

Pを

次元

dの

整 な凸多面体 とす る。 この とき、 各 自然数 η∈

Nに

対 して、整数 `(民 η)ヽ ダ(民η)を 、 ・ づ(P,η

)=‖ (2P∩

ZⅣ) ・ j*(民η

)=1(η (P―

∂

P)∩

ZⅣ) と定義す る。ただ し、集合

Xに

対 して

IXと

は、

Xの

要素の個数 を表す。 つま り、」_(民 η_)と はヽη

Pに

含まれ る整数 ′点の個数 であ り、づ*(P,η)とはヽ η

Pか

ら境界 をのぞいた部分 に含 まれ る整数点の個数 のこ とである。今、 各 自然数 ηに対 して、ηP,η

_(P―

∂

P)は

有界 であるので、 1(η

P∩

ZⅣ

),

‖(η

(P―

∂P)∩

ZN)

は無限大 とはな らず に 自然数 とな る。

Pを

拡大 した多面体の中の整数点 を数 えるかわ りに

Pの

中のあ る種の 有理点の個数 を数 えると考 えることもできる。 命題

2.1.5空

間RⅣ 内の整 な凸多面体P、 _{及び、整数 ηに対 して、} 1.づ_(P,η

)=#{α

C Plη

α∈ZN}

2.グ_(P,η

_)=#{α

C(P一 ∂

P)lη

α∈

ZN}

となる。

証 明

り

:{α

CP∩

_QⅣlη

α∈ZN}→ η

P∩

ZⅣ を原 点 中心 の η倍 の拡大写像 とすれ ば、 これ が全 単射 で あ る こ とは明 ら かで あ るか ら、

1が

成 り立つ。

Pを

P一

∂

Pに

置 き換 えれ ば、

2も

同様 に 示 され る。

□ J(P,η_)ヽ ダ_(民η

_)は

ヽ

Pの

整数ベ ク トル の平行移 動 で不変 で あ る。つ ま り、次 が成 り立つ。 命題 2.1.6 ZⅣ 内のベ ク トル tと して、RⅣ 内の整 な凸多面体

Pを

tだ

け 平行移動 した多面体 をP′ とす る と、 1.づ_(P,η

_)=を

_{(P′ ,η})

第

2章

錐 の 中の格子 点 2.づ*(P,η_)=j*(P′,η) とな る。 証 明 ηP′ は η

Pを

整 数ベ ク トル だ け平行移動 した ものにな ることを示せ ば よい。

ZN内

のベ ク トル

t及

び 、 自然数 η と して 、 ∫:RⅣ → RⅣ

,

ノ′:RⅣ →

RAr,

θ

:RN →

RAr,

を

∫

(")=“

十

t,

∫

′

_(")="+η

t,

θ

(“

)=η

“

と定めると、

η

P=g(P), P′

=∫

(P),

η

P′ =θ oノ(P)

となる。このとき、

RⅣ

内の任意の元

"に

対 して、

gO∫

_{(π)=g(∫(π ))} =g(・

+t)

=η(“ 十t) =η π tt ηt =∫

′

Og(“)

となるので、

η

P′

=goノ

(P)=ノ

′

Og(P)=∫

′

_(η

P)

となる。 したがつて、

j(P,η_)=づ (P′ ,η)と

なる。

Pを

P― ∂

Pに

おきかえ

れば、

2も

同様に示すことができる。

□

ここで、

2次

元の例で

,(民

η

_),づ

*ば

,η)の

定義を確認しておく。

例

2.1.7頂

′_{点 (5,0),(0,4),(7,6)を 持つ}

R2内

の三角形

F(図

_{2,1を 参 照)を} 考 える。この ときの、づ(F,1)、 づ(F,2)、 を(二 3)と づ*(F,1)、 j*(F,2)、 j*(二3) を求 め る。 実 際 、格 子 点 の数 を数 え る と、 づ_(二

1)=22

づ*(二

1)=18

り_(二

2)=81

づt(二

2)=73

づ_(民

3)=178

づ

*(F,3)=166

とな る。 28

第

2章

錐 の 中の格子 点 図

2.1:2次

元 の格 子 点数 これ らの数 列 づ_(二 1),を_(民 2),づ_(二 3),… . グ_{(F,1),ダ(F,2),づ}*(F,3),… . には何 か規 貝J性 が あ るのだ ろ うか。 そ こで 、一般 項 が計算 で き る よ うな 例 で考 えてみ る。 例

2.1.8頂

′_{点(0,0,0),(0,1,1),(1,0,1),(1,1,0)を 持つ}

R3内

の四面体

Fを

考 え る。 この

Fは

、単位 立方体 と

4頂

点 を共有す る正 四面 体 で あ る。 こ の ときの、づ_(二 η_)、 グ_(F,η)を求 め る。

nFは

図 2.2の よ うにな る。 これ を、″ν平面 に平行 な面 で切 つて 、その 断面 の格 子 点 の数 を考 えてい く。

1.z=η

の断面 の格子 ′点は η

+1個

で あ る。_(図 2.3参 照)

2.z=η

-1の

断面 の格 子点 は3η

-1個

で あ る。_(図 2.4参照₎

3.z=η

一づの断面 の格子 点 は η

+2η

j-2づ

2+1個

で あ る。 (図 2.5参照) 上記 の

3に

つ い て、計算 の詳細 を以下 に示 す。_(0,0),(η,η)を結 ぶ線 分 を対角線 とす る正方形 内の整数点 の数 は、(η

+1)2と

な る。 ここか ら、余 29

第

2章

錐 の 中の格 子点 図

2.2:Fを

η倍 した 図形 η

F

y 図

2.3:z=η

の 断 面

図

2.4:z=η

-1の

断 面 分 な整 数 ′点の 個 数 を取 り除 い て考 え る。 図 2.5の (1),(2)の 部 分 の 格 子 ′点 の数 は合 わせ て 、 2×

_(1+2+3+・

・・+づ

_)=づ

(を

+1)

とな る。 同様 に 、 図 2.5の (3),(4)の 部 分 の格 子 点 の数 は合 わせ て 、 2×

_(1+2+3+…

・十(η 一j))=(η 一 づ)(η―

j+1)

とな る。 よつ て 、求 めた い格 子 点 の数 は 、 (η

+1)2_(η

_j)(η 一

j+1)一

づ(を

+1)=η

+2η

を-2を

2+1

で あ る。 この式 は 、づ

=0,η

で も成 り立つ 。 30

第

2章

錐 の 中の格 子 点 31

6):

図

2.5:z=η

―りの断面 以 上 よ り、

づ

_に→

=Σ

_EC+2磁

-2′

十⇒

づ=0 η

3+3η 2+5η

+3

0.1) となる。 次 に、づ*(二η)を 考える。グ(二η

)は

、づ(二 η)の 境界上の格子点 を除い た ものなので、

Fの

境界上の格子′点を考 える。

1.z=η

も しくは、

z=0の

断面の境界上の格子点は η

+1個

で ある。

2.0<づ

<η

の とき、

z=η

―をの断面 の境界上 の格子点 は2η 個 であ る。(図 2.5参 照) とな る。 したがつて、

ダ

_(二

η

)=

づ

_(二

η

_{)一 {2(η}

+1)+2η

×

(η

-1)}

η

3+3η 2+5η

+3

= 3 {2(η

+1)+2η

×

(η

-1)}

η

3_3η2+5η

-3

●・

2)

第

2章

錐 の 中の格 子 点 とな る。 以上 の計 算結 果 か ら得 られ た式(2.1)と 式 (2.2)を 見比べ る と、奇妙 な 一致 が見 られ る。 まず、この とき が(二η)と づ(F,η)は、ηに関す る多項式 になってい る。 また、ダ(二η)と づ(二η)の次数 は等 しく、 さ らに、各 次数 の係 数 の絶 対値 が等 しくな り、最 高次数 の

1つ

下 の項 の係 数 か ら

1つ

お きに符号 が逆転 してい る。 これ は、偶然 の一致ではな く、 この単体 に限つ て見 られ る現象 ではない。 この よ うな、づ*(P,η)やり(P,η)の値 を示す ηに 関す る多項 式 を多面 体

Pの

エルハ ー ト多項 式 とい う。 そ して、 この

2つ

の式 の間 に は 、エル ハー ト多項式 の相互 法則 とよばれ るあ る関係 式 が成 り立 ってい る。 このエル ハ ー ト多項式 、及 び 、そ の相 互法 則 に関 わ る事 柄 が この論 文 で の主 た るテーマ で あ る。 これ らのエルハー ト多項式 、及び 、その相 互法則 はフランスの ウジェー ヌ・エルハー ト_{(Eugene Ehrhart)に} よ り

1960年

頃 に発見 され た。 ウジェー ヌ・エルハ ー トの研 究 のほ とん どは、エルハ ー トが ス トラスブール (フラ ンス_)で リセ の教 師 を してい る ときに行 われ た もので ある。 リセ とい うの は、フランス の後期 中等教育機 関で あ り、 日本 の高等学校 に相 当す る。 ウ ジェーヌ 。エルハー トは

22歳

の時 に、高校 教員 の資格 を得 て、い くつ かの 高校 で教員 を行 う。そ して、高校 の教員 を しなが ら、 自分 の時間 をつ かつ て数 学 の研 究 に打 ち込 んだので あ る。彼 は 、

40代

の頃か ら論文 をか きは じめ る。 そ の後 、 同僚 の求 めに応 じて

60歳

で博 士 号 を得 た。(卜]参 照) また、ウジェーヌ 。エルハー トはエルハー ト多項式 に関す る上述の相互法 則、エルハー トーマ ク ドナル ドの相互法則 を予想 して、様 々な特殊 な場合の 証 明 を行 つた。 そ の約

10年

後 の

1971年

にマ ク ドナル ド_{(I,G.Macdonald)} が一般 の場 合 の証 明 を発 見 した。本 当は、エルハ ー トーマ ク ドナル ドの相 互 法則 は凸多 面体 だ けで はな く、 も う少 し条件 を緩 めた多 面体 に対 して も成 立 し、実 際、多様 体 と同相 な多面体複 体 に対 して も成 り立つ こ とが 知 られ て い る。

2.2

単体 内の格子点

これ まで、凸多面体

Pに

ついて づ_(民η_)、 づ*(P,η_{)を 考えてきたが、この} 節ではまず、単体

Fに

関す るJ(二η)、 グ(二η)に ついて考 えていきたい。

定義

2.2.lFを

RⅣ

内の整α単体とし、Fの 頂′

点集合を

{υ O,υl,…

。

,υd} 32

第

2章

錐 の 中の格子点 とす る とき、

Fを

P={(α

,1)∈

RN+11α

∈

F⊂

R旬

と定義す る。 つ ま り、

1つ

次 元 が高 い RⅣ

+1内

の

/V+1番

目の座標 が

0の

超 平 面 に

F

をお き、 この

Fを

Ⅳ

+1番

目の座 標 の方 向へ

1だ

け平行移動 した ものを

Fと

する。

_(図 2.6を

参照

_)こ

のとき、

P⊂

RⅣ

+1も

整 α単体であり、その

頂点は

(υo,1),(υl,1),・ … ,(υd,1)

となる。以下、

(υt,1)を

うをと表記する。

図

2.6:Fを

平行移動 した

F

Fを

RⅣ 内の整 α―単体 とす る とき、

Fの

境界 ∂

Fは

∂

P={(α

,1)∈ RⅣ+11α

∈∂

F⊂

RN}

となる。

定義

2.2.2Fを

RⅣ 内の単体 とし、定義2.2.1で述べた記号 を用い る。 の とき、RⅣ

+1内

の部分集合 θ と∂θ を

・ θ

={γ

β

lβ

∈F, 0≦

r∈

R}

33 vi,1)

第

2章

錐 の 中の格子点

34

・ ∂θ

={rβ

lβ

∈∂

F, 0≦

r∈

R}

とする。

以 下、 この節 全 体 を通 じて、定義 2.2.1と 定義 2.2.2の 記 号 を用 い る。 補 題

2.2.3こ

の とき、

θ一∂θ={γβ

lβ

∈

(F―

∂

F), 0<γ

∈

R}

である。

証 明 まず は 、θ 一 ∂θ が {γβlβ ∈ 『 ― ∂⊃

, 0<γ

∈

R}に

含 まれ る こ とを示 す。

"を

σ 一 ∂θ の元 とす る と、“は θ の元 とな るので 、定義 2.2.2よ り、

"=γ

β

(β

∈F,0≦ γ∈R)

となる。このとき、β∈∂Fと すると、

“

∈∂θとなり、矛盾。また、γ

=0

とすると、

_"=0∈

∂θとなり矛盾。したがつて、

β∈

F一

∂

F,

γ

>0

となる。

次に逆の包含関係を調べるために、

γβ∈RN+1 (γ >0,β ∈F― ∂F)

とい う元を考える。このとき、γβ ∈θは θの定義から明らか。あと

は、γβ グ∂θを示せばよい。もしも、γβ ∈∂θ と仮定して、つまり、

γ

′≧

0,β

′∈∂

Fに

ついて

γβ=γ

′

β

′

(2.3)

とすると、γβ、γ

′

β

′

の

Ar+1番

目の座標はγ

,γ

′

だからγ=γ

′となる。し

たがって、γ≠

0よ

り、式

_(2.3)の

_{両辺をγで害}

Jる

と、β

=β

′∈∂

Fと

な

る。これは矛盾なので、γβ￠∂σとなる。よつて、γβ∈θ―∂θを得る。

□

次の補題

2.2.4に

より、θや

_c一

∂θ

_)の

格子点を調べることと、づ

_(二

η

)、 グ_(F,η)を求 め るこ とを関連 づ け る。 補題

2.2.4空

間 RⅣ 内の単体F、 及 び 、 自然数 ηに対 して 、

第

2章

錐 の 中の格 子 点 1.づ_(F,η

_)=‖

_{(Z,η)∈

θ

_lZ∈

ZN}

2.グ_(ft

η

_)=‖

{(Z,η

)C(θ

―∂θ

)IZ∈ ZⅣ} とな る。_(図 2.7参照) 図

2.7部

分集 合 θ 証 明 まず、

1に

つ いて考 える。 自然数 ηを

1つ

固定

‖

{(Z,η )∈

θ

lZ∈ ZⅣ

}=1(θ

∩

{(″1,…

・

,″N+1)￨″

Ⅳ

+1 35 した とき

=η

}∩

zN+1)(2.4)

∩Z/tr+1) (2.5)

づ

_(二

η

_)=‖

_(η

F∩

ZA7)=‖_({(“,η)￨"∈

η

F}

よ り、

σ∩

_{(″1,.… ,χ

Ⅳ

+1)￨″

N+1=η

}={(",η

)￨"∈

η

F}

(2.o を示せ ば よい。

まず、θ∩

{(・1,・

…

,χ

Ⅳ

+1)￨″

Ⅳ

+1=嗜

の元が、

{(“,η )lπ

∈η

F}に

含ま

れることを考える。θの任意の元は、定義

2.2.2よ

り、ある

Fの

元 β、

0

以上の実数 rを 用いて、

rβ

と表すことができる。このとき、

rβ

の座標を

rβ _=(″1,・

…

,″

Ⅳ

+1)

第

2章

錐 の 中の格子 点

とおくと、このとき、″

Ar+1=η

をみたすことは

r

βが

Fの

元よりβ

=(“

′

,1)(た

だし、

“

′

_は

_Fの

_元

) 36

=η

を意 味す る。 よつて、 とす る と、ηβ

=(η

“ ′ ,→ とな る。

逆に、

_{(“,η )￨“

∈η

F}の 元

(",2)に

対し、ある元α∈Fが あつて、

"=η

α とな るか ら (π ,η)=(η α,η)=η (α,1)

となり、

(α,1)∈

Fよ りθ∩

{(″1,・

…メ

N+1)￨″

N+1=η

}の

元となる。し

たが つて、

1が

成 り立つ。 次 に、

2に

つ いて考 える。 自然数 ηを

1つ

固定 した とき ‖{(Z,η )∈ (θ ― ∂θ)IZ∈ ZN}=1((θ 一 ∂θ)∩ {(・1,…・ ,″A7)￨″Ⅳ =η }∩ ZN+1) (2.7) グ(二 η

)=1(η

(F―

∂

F)∩

ZAr)=‖_{({(",η)￨"∈} η

_(F一

∂

F)}∩

ZIV+1) (2.8) よ り、 (θ 一∂θ)∩ {(・1,・ …,″Ⅳ)lπⅣ

=分

={(",η

)￨"∈ η

(F―

∂

F)}(2,9)

を示せ ば よい が、式 (2.9)は 式 (2.6)と 同様 に示 され る。

□ 補題 2.2.4に よつて、づ(二η)、 づ *(二_η )が θ や θ ―∂θ 内の格 子 点 を調 べ るこ とに帰着 され たが、次 の定理 に よって θ 内の点は一意的 な表示 を もち、そ の こ とが格 子 点 の個数 のカ ウン トに重要 な役割 を果 たす。 定理

2.2.5θ

内の任意 の′点α は、非負 の実数rO,.… _{,rdを 用 いて}

α

=Σ

甑

2=0 の形 に表 され る。また、この とき、rO,.… _{,raは αに よつて一意的に定 まる。} 証 明 島 とは、(υを,1)∈ RⅣ

+1の

こ とで あ るか ら、 まず、α が

α=Σ 亀

0ぉ

り

,①

≦ぼ 噂

づ₌₀ p.1の

第

2章

錐 の 中の格 子点

と表すことができるのかを考える。Fの 頂′

点は、

{(υo,1),… ,,(υ

ぁ

1)}で

あるから、定理

1.3.13に

より、

F=θ

OⅣ

y((υ_O,1),…

_・

,(υd,1))

なので、

Pの

任意の元 βは定理

1.2.5よ

り、

β=Σ ち

C,⇒

,0≦

ち∈

RΣ

ち

=1

を₌₀ づ₌₀

と表される。θの任意の元 α=rβ

(0≦ r∈ R,β

∈F)に ついて、

α

=rβ

=rΣ

ち

_鴎⇒

づ=0 d

=Σ

rち

鶴

1) 0・

1⇒ じ₌₀ と表 す こ とが で き る。 この とき、γ≧0、 ιづ≧

0で

あ るか ら、rtづ ≧

0で

あ り、式 (2.11)は 式 (2.10)の 形 の表示 の

1つ

で ある。 次 に、一意性 につ いて考 えてい く。そのた めには、(υO,1),… .,(υd,1)が

1次

独 立 に な る こ とを示せ ば よい。 そ こで 、い ま、実数 れ

_(j=0,一

,α) につ いて、

Σん

α

ωら

⇒

=0 0.1幼

づ₌₀

と仮定 したとき、れ

=0(づ

=0,… ・

,α)を

示す。式

(2,12)が

成 り立つ とき、

Σん

づ

Q=0か

つ Σた

じ

=0

を=0 づ=0 37

第

2章

錐 の 中の格 子点

となり

_、Σκ

j=0よ

りた

0=Σ

_E(一

れ

)と

なる。よつて、

」=0 を₌₁ d

Σンを

Q=た

oυo十

た

lυl十

た

2υ

2+…

十考

aυd

づ₌₀

=嵯

閉

_)中

山

動…伽

d =(一 た

1-ん

2 …

°たa)υO十 たlυ

l+た

2υ

2+…

°十 んdυd =た1(υl― υ

o)+た

2(υ

2 υO)+…

・十 たd(υd一 υo)

=0

である。

F=θ

OⅣ

y({υ o,・

…

,υ

ご

})が

α次元単体なので、定理

1.4.3よ

り

´

(υl― υo),… 。,(υd― υo) は

1次

独 立 で あ る。 したが つて、 た

_1=た

_2=…

・

_=た

d=0

とな り、た

0=Σ

(―たを

)=0で

あ るので、 j=o (υo,1),,… ,(υd,1) は

1次

独 立 で あ る。

□ 定理

2.2.6θ

―∂θ 内の任意 の点 α は正 の実数rO,.… _,raを用 い て

α=Σ 勉

2=0

の形に表される。また、このとき、

r。_{,.… ,γ}

αはαによって一意的に定まる。

証明

Fの

頂′

点集合は

(υO,1),… ,(υ

ぁ

1)で

ある。補題

2.2.3に

よりθ―∂θ

の元をα とすると、α =rβ (r<0,β ∈

F―

∂F)と 表す ことができる。

d

定理

1.3.15よ

り

、

j―

∂

クの元βはΣン

j=1を

みたす

0<ι

づ

∈

Rを

用い

う=0 38