今年の冬は Gröbner 基底でスーパー大学受験ガール！ konn-san.com

今年の受験は Gröbner 基底で乗り切れ！

どうもみなさん今日は！突然ですが僕は受験数学が苦手です。しかし、代数幾何のGröbner（グレブナー）基底の理論を学んでから、受験数学が全く苦にならなくなりました！今回は、まだ受験数学と格闘しなくてはならないみなさんの為に、受験に役立つGröbner基底の紹介を、しちゃうゾ☆

直線と平面の問題

さてさて、まずは次の空間図形の問題を考えてみまっしょー。

問題．$x,y,z$-空間に直線 $$\ell:(x, y, z) = (0, -3, -2) + t(1,3,2)\quad (t \in \mathbb{R})$$ と点 $P(1,2,1)$ がある。$\ell$ を含み $P$ を通る平面 $\alpha$ と、$z$ 軸との交点 $R$ の座標を求めよ。

うひゃあ、典型的な空間図形の問題ですね……！コワイ！

えっと、まず平面の式が必要で……直線 $\ell$ は $A(0, -3, 2)$ を通って $(1,3,2)$ と並行な線で……$\alpha$ はこれと $P(1,2,1)$ を通る平面だから……適当な実数 $t, s \in \R$ があって……ムニャムニャ……

$$\begin{aligned} \vec{AX} &= t \vec{AP} + s\vec{AQ} \\ \therefore \vec{OX} &= \vec{OA} + \vec{AX}\\ &= \vec{OX} + t \vec{AP} + s\vec{AQ} \\ &= ... = (s+t, -3 + 5s + 3t, -2 + 3s + 2t) \end{aligned}$$

だからええとこれが $z$ 軸上の点だから第一・第二成分 $=0$ と置いて……$s + t = 0, -3 + 5s + 3t = 0$ だから……ウーン……

$$R(0, 0, -\frac{1}{2})$$

だ！！！とかやっちゃ、ダメですよ！？こういう時こそGröbner基底を使うんです！！

Gröbner基底っていうのは、多項式環のイデアルの都合のよい生成元のことです。ってどういうこと？？？
むずかしい話になるので詳細は略しますが、イデアルって云うのは、「多項式の零点で表される図形」、イデアルの都合のよい生成元っていうのは「図形の性質が全て詰まっていてしかも扱い易い多項式」のことだと思えばいいです。

では、さっそくやってみましょー。まずは、上の図形をイデアルに直すところからです。$\ell$ を表すイデアルを $\mathfrak{I}$ ¹ とすると、 $$\mathfrak{I} = \left\langle x-t, y - (3t - 3),z - (2t - 2) \right\rangle$$ のようになります。なんか変なカッコで囲まれてますけど、これは「イデアルだよ！」という意味だと思えばいいです。この式はどっから来たんでしょう？まず $\ell$ の式を眺めてみましょー。

$$\ell:(x, y, z) = (0, -3, -2) + t(1,3,2) = (t, 3t - 3, 2t - 2)$$

つまり、$x = t, y = 3t - 3, z = 2t -2$ が、直線 $\ell$ の定義式ですね。この式と上の $\mathfrak{I}$ の式を良く見比べてみると……？そうですね！右辺を左辺に全部移項して、$=0$ の形にしたものがイデアルの各要素になっていることがわかります！標語的に書けば、

図形を表すイデアル ＝ 定義式を $=0$ の形に変形してカンマで並べて鉤括弧で囲め！

ということになります。同様に点 $P$ に対応するイデアルを $\mathfrak{J}$ ²とすると、これはどうなるでしょうか？点の定義式って……？と思うかもしれませんが、$x = 1, y = 2, z = 1$ ということなので、移項して $=0$ とすれば、 $$\mathfrak{J} = \langle x - 1, y - 2, z - 1 \rangle$$ が $\mathfrak{J}$ ということになります。まずは、平面の式を求めたいので、図形 $\mathfrak{I}$ と $\mathfrak{J}$ の両方を含むような図形を探したい、ということになります。そうした計算は、次のようにして定義されるイデアル積 $\mathfrak{I} \mathfrak{J}$ の正体を知ることに外なりません。

$$\mathfrak{I} \mathfrak{J} = \left\langle fg\ \middle|\ f \in \mathfrak{I}, g \in \mathfrak{J} \right\rangle$$

ちょっと見なれないかもしれませんが、右辺の意味は、

それぞれのイデアル（図形）の要素を取ってきて、掛け合わせて得られる式全体のイデアル

ということです。どういうことか？上で見た $\mathfrak{I}, \mathfrak{J}$ の式を代入すれば、

$$\mathfrak{I}\mathfrak{J} = \langle (x - 1)(x - t), (x - 1)(y -(3t -3)), (x - 1)(z - (2t - 2)), (y - 2)(x - t), (y - 2)(y-(3t -3)), \dots \rangle$$

ね、一つずつ取ってきて掛け合わせた感じになってるでしょ？どうしてこうなるのか？そこはそれ、受験数学だからなるものはなります！

……と云ってしまってもいいですけど、いちおうちゃんと説明出来ます。そもそもイデアルというのは、「各要素がゼロになるような点全体の集合」なのでした。ところで、

$$(x - 1)(y -(3t -3))=0$$

という方程式の意味は、直観的には「$x - 1 = 0$ または $y - (3t - 3) = 0$ のどちらか一方が成り立つ」という意味でした。つまり、イデアル積の「両方から一つずつ取ってきて掛け合わせる」という事の意味は、「それぞれの定義式のどちらか一方でゼロを取るならゼロにしちゃうよ！」というくらいの意味で、だから両方の図形の和集合みたいな感じになる訳です。式を並べて書くのが「かつ」で、積を取るのが「または」なんだとすれば、なるほどそんなもんかな、という気分になってくれるでしょう。……なってくれるよね？なってください。

なって貰ったところで、もういちど虚心坦懐にイデアル $\mathfrak{I}\mathfrak{J}$ の式を眺めてみましょう。きっと平面の情報が隠れているハズ……

$$\mathfrak{I}\mathfrak{J} = \langle (x - 1)(x - t), (x - 1)(y -(3t -3)), (x - 1)(z - (2t - 2)), (y - 2)(x - t), (y - 2)(y-(3t -3)), \dots \rangle$$

ウゲエ、こんなのの何処に平面の情報が隠れているんダッι(｀ロ´)ノ！

……とまあ、怒らないでください。これだけ見せられたら確かにウゲエっとなってしまうのもわかります。そこで、登場するのが Gröbner基底です！
Gröbner基底とは何か。都合のよい生成元だと云いましたね。「図形の性質が全て詰まっていてしかも扱い易い多項式」のことなのでした。では、Gröbner基底を早速計算してみましょう！

……ハイ、と云うことで、その計算結果がこちらになります。

$$\mathfrak{I}\mathfrak{J} = \langle x + y - 2z - 1,y z - 3/2 z^2 - y + 3/2 z,t z - 1/2 z^2 - t - 1/2 z + 1,y^2 - 9/4 z^2 - 7/2 y + 21/4 z,t y - 3/4 z^2 - 2t - 3/2 y + 7/4 z + 2 \rangle$$

ウゲエ、何やら式がイッパイ……。しかし、良く見ると、$x, y, z$ だけしか含まない式が幾つかあるようで、しかも一番最初の式 $x + y - 2z - 1$ は 一次式になっていますね。これを $=0$ と置いた図形は確かに平面を定めます。これに、最初の直線 $\ell$ や点 $P$ の式を代入してみると……

$$x + y - 2z -1 = t + (3t - 3) - 2(2t - 2) - 1 = 0$$ $$x + y - 2z - 1 = 1 + 2 - 2 \dot 1 - 1 = 0$$

おお！見事に点 $P$ と直線 $\ell$ を通っていることがわかりました！やりましたね！実際、グラフで図示するとこんな感じになっています。

あとは、これで $x = y = 0$ と置いてやれば、交点が求まります。

あるいは代入する代わりに、上で求めた平面 $\alpha$ と $z$ 軸の交点だと見てやって、Gröbner基底を求めても大丈夫です。$z$ 軸というのは $x = y = 0$ を満たす直線のことなので、図形 $\langle x, y, x + y - 2z - 1 \rangle$ のGröbner基底を求めてやればいい訳です。その結果は、

$$\langle z + 1/2 ,y,x \rangle$$

となり、一つ目の式から $z = -1/2$ がわかります。

Gröbner基底の計算方法

では、具体的にGröbner基底はどのように計算すればいいんでしょうか？幾つか方法を解説しますが、簡単な方法からやってみましょう。

皆さんは、受験生ですから、1変数の多項式の割り算は出来ますね？出来るとしましょう。それを多変数に拡張してやったような方法でやります。
まず、割り算するときの約束です。多項式 $z^4 + 2x + 3x^2y + z^3 y^2$ のようなものがあったとき、各項の文字部分 $x, x^2y, z^3 y^2$ をそれぞれ単項式と呼んだことを思い出しましょう。次のように単項式の間の順序を定めます。

1. まず、文字の間の大小関係を決めます。これは好きに決めて構いません。例えば $x > y > z$ としてみましょう。
2. 「大きな文字」をより沢山含んでいる方が大きい単項式とします。例えば $x^3 > x^2$ ですし、 $x^2 > y^{100}z^{500}$ です。外の小さな文字がどれだけ大きな指数を持っていても、大きな文字が小さければ意味ないです。

このようにして決めた単項式の順番に従って、文字式降冪の順に、つまり大きい方から順々に並べていってください。例えば、

$$z^4 + 2x + 3x^2y + z^3 y^2 \to 3x^2y + 2x + y^2 z^3 + z^4$$

のようになります。多項式 $f$ の各項を上の順序で並び換えて一番先頭にくるような項をの「先頭項」と呼び、$LT(f)$ と書きます。

そして、遂に多項式の割り算に入ります。単項式の割り算と違うところは、割られる式に対して、複数の割る式が取れることです。つまり、 「$x ^2 y + x + y$ を $x^2 - y$ と $x - y$ で割る」といったような事を考えたりします。割られる式は常に一つです。複数の式で割る場合は、どの順番で割っていくかは常に固定します。

具体的に割る方法は、

1. 割る式($g$)・割られる式($f_1, f_2, f_3 \dots$)を上の順序に関して降冪の順で書き直す
2. 割る式の順番を決めて $f_1, f_2, f_3, \dots$ とする。$f_i$ で割った商 $q_i$ と余り $r$ を求めたい。
3. $g$ の先頭項を降ろしてきて $s$ とする。
4. $s$ と 各 $f_i$ の先頭項を見比べていって、割れる項があったら普通の割り算をして、商と余りを $q, r$ とする。
5. もし割れる項がなければ、$s$ の先頭項を $r$ に加え、$s$ からは消す。
6. $q_i \leftarrow q_i + q$, $g$ の残っている先頭項を新たに $s$ に足して 4 を繰り返す。残っている項がなくなったら終わり！

こんな感じです。以下、式の集まり $G = \langle g_1, g_2, \dots, g_s\rangle$ で $f$ を割った余りを $\bar{f}^G$ と書く事にします。 また、多項式 $f, g$ の S-多項式 $S(f, g)$ を次のように定めます。

$$S(f, g) = \frac{LCM(LT(f), LT(g))}{LT(f)} f - \frac{LCM(LT(f))}{LT(g)} g$$

ここで、 $LCM(\alpha, \beta)$ は単項式 $\alpha, \beta$ の最小公倍式です。ようは、$f,g$ を適当に足し引きして先頭項を打消し合わせたものが $S(f, g)$ です。ナンノコッチャわからなければ、「各文字の指数の最大値を取ったもの」と思えばいいです。例えば、$LCM(x^2yz, xz^2) = x^2yz^2$ です。

これを踏まえると、イデアル $I$ のGröbner基底を求める手法は次のようになります。

1. $G = I$ とする。
2. $G$ の各元 $f, g$ に対して、次を繰り返す。
   3. $s = \overline{S(f, g)}^G \neq 0$ ならば $G$ に $s$ を加える。そうでなければ何もしない
3. もしどの二元に対しても $\overline{S(f, g)}^G = 0$ となったらそこでおわり

こうして得られた $G$ が、イデアル $I$ のGröbner基底になっています。まあ詳しくはWikipedia とかの計算法を見ればいいんじゃないですか。手計算が面倒なら、SINGULAR という非常に優れたソフトウェアを使ってパソコンに計算を肩代わりさせることも出来ますし、Haskell が使える人はぼくの作ったcomputational-algebra ライブラリを使うといいかもしれません。

空間図形の問題2

次はこんな問題を考えてみましょー。

$O$ を原点とする座標平面上において、 $$\vec{OP} = s\vec{OA} + t\vec{OB}\quad (s, t \in \mathbb{R}, \text{ で } O,A,B \text{は同一直線上にない})$$ とする。$s, t$ が $3s + 4t = 2$ を満たしながら変化するとき、 $P$ の軌跡を求めよ。

えーっと、$3s + 4t = 2 \iff 3/2 s + 2t = 1$ だから……$s' = 3/2s, t' = 2t$ と置いて……

$$\vec{OP} = s\vec{OA} + t\vec{OB} = s' (2/3 \vec{OA}) + t' (\vec{OB}/2)$$

だから……$\vec{OA'} = 2/3 \vec{OA}, \vec{OB'} = \vec{OB}/2$ とすれば、$s' + t' = 1$ だから……$P$ の軌跡は……えーと……「線分 $OA$ を $2:1$ に内分する点と $OB$ の中点を通る直線」……？

あーダサいダサいダサい！ダサ過ぎます！何で両辺 $2$ で割るの！っていうか何がイケてないって、そりゃあんた、ナニが

線分 $OA$ を $2:1$ に内分する点と $OB$ の中点を通る直線

ですか！具体的に式を答えろってんですよ、ええ。なんなら変数を消去して定義式を答えろってんです！だいいち、こんなのはGröbner基底をつかえば一発なんです！

明日もう一度ここに来て下さい。本物の変数消去を見せてあげますよ。³

いや、明日じゃなくて今でいいんですけど。おきまりのようにイデアル $I$ ⁴を定義しましょう。$\vec{OA} = (a, c), \vec{OB} = (b, d)$ などと置けば、先の式を変形して次のようなイデアルになります。

$$I = \langle x - (sa + tb), y - (sc + td), 3s + 4t - 2 \rangle$$

これのGröbner基底を求めてやると……

$$I = \langle s + 4/3 t - 2/3 ,c t - 3/4 d t - 1/2 c + 3/4 y,a t - 3/4 b t - 1/2 a + 3/4 x,-b c + a d + 2c x - 3/2 d x - 2a y + 3/2 b y \rangle$$

……お！最後の式$-b c + a d + 2c x - 3/2 d x - 2a y + 3/2 b y$がお誂え向きに $s, t$ も含まない、$\vec{OA}$ と $\vec{OB}$ の値だけで決まる直線の式になってますね！これにさっきの内分点だの中点だのを代入すれば、ちゃんと同じものになってることもわかります！

　 |l､{　 　j}　/,,ｨ//｜　　　　　／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
　 i|:!ヾ､ﾉ／ u {:}//ﾍ　　　　　|　あ…ありのまま 今　起こった事を話すぜ！
　 |ﾘ u’ }　 ,ﾉ　,!V,ﾊ |　　 　 ＜　『おれはGröbner基底を計算していたと
　 fト､_{ﾙ{,ィ’ｅﾗ　, ﾀ人.　　　　|　　思ったらいつのまにか変数 $s, t$ を消去していた』
　ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ　　　|　連立方程式だとか媒介変数表示だとか
　　ヽ iLﾚ 　u’ |　| ヾｌﾄﾊ〉. 　　|　そんなチャチなもんじゃあ　断じてねえ
　　 ﾊ !ニ⊇　‘／:} 　V:::::ヽ.　│　もっと恐ろしいものの片鱗を味わったぜ…
　 /:::丶’T’’ ／u’　__ /:::::::/｀ヽ ＼＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿⁵

実は、「上手く順序の選んでGröbner基底を計算すると、その変数を消去出来る」という事実があります。ヒューッ！スゴイ！

つまり、パラメータを消去したいような式が与えられたら、

1. 与えられた式から成るイデアルを作って、
2. 消したい文字が大きくなるような順序で、
3. Gröbner基底を計算して、
4. その文字の出て来ない式をその基底の中から選ぶ。

というような手続を踏めば、一瞬で⁶パラメータを消去出来るという寸法です。なんってこったい／(^o^)＼。

勿論、数式が足りなかったり多すぎたりすると上手くいかないことがあって、そういう場合は $0 = 0$ とか一点に潰れた意味のない図形になってしまったり、 $1 = 0$ みたいにそもそも存在しない図形になってしまったりします。
また、パラメータの選び方によっては、その後に得られた方程式が定義する図形の一部分にしかならなかったりします。この辺りは普通に変数消去をした際に値域をチェックしなきゃいけないのと同じですね。

もっと変数消去

$t$ が任意の実数を動くとき、 $$\begin{cases} x &= 1 + t^2\\ y &= 2 - t - t^2 \end{cases}$$ は一つの曲線を描く。この曲線と $x$ 軸とで囲まれた部分の面積を求めよ。

面積はどうでもいいですけど、この曲線ってどんな曲線なんですかね？わたし、気になります⁷！

という訳で、上で紹介した変数消去法を試してみましょー。$I = \langle x - (1 + t^2), y - (2 - t - t^2) \rangle$ のグレブナー基底を求めて、$t$ を消去してやると……

$$x^2 + 2x y + y^2 - 7x - 6y + 10$$

が唯一の基底として得られます！これが定義方程式のようですね！グラフに描いてみると、

……？え？面積？パラメータ積分すればいいんと違う。

連立方程式の解

Gröbner基底が威力を発揮するのは、他にもあります！例えば、次のような連立方程式は受験でよく出て来ますね。

$$\begin{cases} x^2+y^2 &= 16\\ x^3+y^3 &= 44 \end{cases}$$ のとき、 $x + y$ の値求めよ。

これも、Gröbner基底を使えば一瞬です！今、知りたいのは $x + y$ の値なので、これを $s$ と置いて、方程式から $x, y$ を消去することを考えてみましょう。つまり、次のGröbner基底を考える訳です。

$$I = \langle x^2 + y^2 - 16,x^3 + y^3 - 44,s - (x + y) \rangle$$

これのGröbner基底を計算して、 $s$ だけを含む式を見てみると……？

$$s^3 - 48s + 88$$

という式が得られました！この式 $=0$ と置くと、 $$s^3 - 48s + 88 = (s - 2)(s^2 + 2s -44) = 0$$ となって、今 $x, y \in \R$ より $s \in R$ とならなくてはなりませんから、$s = 2$ が答えだと判ります！やったね！⁸

連立方程式の解ふたたび未遂

これと同様にして、

$x = \sqrt[3]{7+ 5\sqrt{2}}, y = \sqrt[3]{7 - 5\sqrt{2}}$ のとき、$x^4 + y^4, x^5 + y^5$ を根号を用いずに表せ。

というような問題も一瞬で解けます！というようなことを書こうと思ったんですが、自前のライブラリだと二十分経っても計算が終わらず、Singular に計算させたところ、

$$I = \langle t^{21}-140t^{18}+3098t^{15}+4788t^{12}-702391t^{9}+3996104t^6+2190656t^3-175616, 555268627200s-164581t^{20}+22955732t^{17}- \dots \rangle$$

というホンにホンに懼ろしいイデアルが出来したので、諦めました。

極値問題ナンノソノ

なんかー、多項式のー、領域とかー、そんなんばっかんでー、飽きたんスけどー。

そんな声が聴こえてきました。よろしい、ならば極値問題だ⁹。

正の数 $x, y, z$ が $\frac{1}{x} + \frac{1}{y} + \frac{1}{z} = 6$ を満たすとき、$x+ 2y +3z$ の最小値を求めよ。

アーなんかこういうのよくありますよねハイ。求まったからといってナンナンジャイという感じですが、まあそれいったら御仕舞いなので。
実は Lagrange の未定乗数法 という大学に入ると習う秘技がありまして、それは、

制約 $f(x, y, z) = 0$ の下で函数 $g(x, y, z)$ の極値を求めよ。

という形式の問題を解く時には、連立方程式

$$\begin{cases} \partial_\lambda \left\{ \lambda f(x, y, z) + g(x, y, z) \right\} &= 0\\ \partial_x \left\{ \lambda f(x, y, z) + g(x, y, z) \right\} &= 0\\ \partial_y \left\{ \lambda f(x, y, z) + g(x, y, z) \right\} &= 0\\ \partial_z \left\{ \lambda f(x, y, z) + g(x, y, z) \right\} &= 0 \end{cases}$$

の解を求めればよいというモノです。これを解いて、$\lambda$ を無視してやって、後はそこが極値かな〜〜〜？んん〜〜〜？と見ていけばいい訳ですナ。
これはまあ、高校の範囲に出て来ないので、あんまり使っちゃいけないタイプの解法ですね。良い子はマネしないように¹⁰。で、左辺の式に出て来る $\partial_x, \dots$ というのはそれぞれ「$x$ 以外の文字は唯の定数だと思って $x$ の函数として微分する」と云う意味の記号で、$x$ による偏微分などといったりします。$\partial_y$ とか $\partial_\lambda$ とかも同じ意味。まあ「これは偏微分って云うんだよ〜」とか云って教えちゃう悪徳予備校教師とかもいるし、未定乗数法くらい知ったところで問題ネエ！というような気もする。

これと Gröbner基底の合わせ技で、なな、なんと！この問題解けちゃいます！まず、制約式から $x, y, z \neq 0$ としていいので、条件に $xyz$ を掛けて分母を払って、$f(x,y,z) = yz + 2zx + 3xy - 6xyz$ とおいて、 $g(x,y,z) = x+2y+3z$ の極値候補を求めていきまっしょー。これを上の連立方程式に代入（して整理）すると……。

$$\begin{cases} yz + 2xz + 3 xy - 6xyz &= 0\\ 2 \lambda z + 3 \lambda y + 1 &= 0\\ \lambda z + 3 \lambda x + 2 &= 0\\ \lambda y + 2 \lambda x + 3 &= 0 \end{cases}$$

となります。そこで、このイデアルを考えて、更にグレブナー基底を計算してやると¹¹、次のようになります。

$$I = \langle 9z^3-18z^2+11z-2, y+9z^3-15z^2+5z, x + 2y - 6z^2+3z, 4\lambda-27xz^2+54xz-33x-54yz^2+108yz-66y+81z^3-180z^2+135z-22\rangle$$

これをよく見ると……おっ！最初の式は $z$ に関する簡単な三次式になってますね〜。受験数学の訓練を受けている皆さんなら、因数定理を使って適当に $9z^3 - 18z^2 + 11z - 2 = (z-1)(3 z - 2) (3 z - 1)$ とか因数分解できることと思います。こうして得た解 $z = 1, 2/3, 1/3$ を上のイデアルに残っている $y+9z^3-15z^2+5z = 0, x + 2y - 6z^2+3z = 0$ に順次代入して計算すると……

$$(x,y,z) = (1,1,1), (-2/3, 2/3, 2/3), (1/3, -1/3, 1/3)$$

と云う三つの解の候補があります。条件から求めるべき $x, y, z$ はいずれも正の数でしたし、まあ受験数学になれているみなさんは、Cauchy-Schwartz の不等式とかを使って $x + 2y + 3z$ のこの制約下での最小値が $6$ となることもわかるでしょうから、答えのとき、$x = y = z = 1$ で最小値 $6$ を取る、とめでたく結論出来る訳です。

ちなみに、上のイデアルが表す図形は以下のような感じになっています（不要なので $\lambda$ は無視しています）。

ちょうど三種類の曲面があって、それらの交点が上で求めた三つの解になっている訳です。つまり、条件付きの極値問題というのは、

これこれこういう図形の交点を求めてください！

という問題のことだったんだよ！な、なんだってー（AA略¹²

極値その2

もっと簡単な、

$x^2+y^2=1$ を満たす実数 $x, y$ について、$(x+y)(2x - y)$ の最大・最小を求めよ。

といった問題についても、同様に計算すれば¹³、

$$I = \langle 20/3 y^3 + x - 19/3 y,-10/3 y^2 + \lambda + 13/6 ,y^4 - y^2 + 1/40 \rangle$$

となって、最後の多項式はみなさんもお馴染の複二次式ですから、$y^2$ を一つの変数と思って解いて、もう一度解いてやれば、解の候補が四つ見付かって、あとは絞り込むだけになります¹⁴。

三角関数の計算問題

たしかに Gröbner基底すごそうだけど、多項式だけじゃーん。

という声が聴こえてきました。では、ちょっと毛並みを変えて、今度は三角関数の絡んだ問題を解いてみましょう……！

$\sin x + \cos y = 1/2, \cos x + \sin y = 1/3$ のとき、$\sin(x + y)$ の値を求めよ。

$t = \sin x, u = \cos y, s = \cos x, v = \sin y$ とおきます。このとき、三角関数の有名な関係式 $\sin^2 + \cos^2 = 1$ を組み合わせて $t^2 + s^2 = 1, u^2 + v^2 = 1$ が得られます。また、加法定理から $\sin(x+y) = \sin x \cos y + \cos x \sin y = tu + sv$ となるので、これを上の制約式で割ってやった余りを求めれば、答えが出ます。 $$\mathcal{I} = \left\{t + u - \frac{1}{2}, s + v - \frac{1}{3}, t^2 + s^2 - 1, u^2 + v^2 - 1\right\}$$ これでそのまま割ってもいいですが、せっかくなので Gröbner 基底を（次数付き逆辞書式順序について）求めてやると、 $$G = \langle g_1, g_2, g_3, g_4 \rangle = \langle u + \frac{2}{3} v - \frac{13}{36} ,t - \frac{2}{3} v - \frac{5}{36} ,s + v - \frac{1}{3} ,v^2 - \frac{1}{3} v - \frac{1127}{1872} \rangle$$ となります。実は、グレブナー基底による割り算の余りは一意に決まってくれるという嬉しい性質があります！さっそくこいつらで割ってみましょう！

$$tu + sv = g_1 t - g_2 2/3 v + 13/36 + g_3 v - g_4 (13/9) + (-59/72)$$

いいかんじに有理数の余り $-59/22$ が求まりましたね！これが答えです！

カージオイド

最後に、今までの手法を幾つか組み合わせて受験数学の有名問題を解いてみましょう。

$r = a(1 + \cos \theta)$ で表される曲線がある。

曲線があるらしいです。カージオイド（心臓形）と呼ばれる曲線ですね。「曲線がある」で終わっているのは、まあ、どういう問題が出たか忘れたからです。もう四年前だから覚えてる訳なんてないですね！

問題を忘れてしまったので、じゃあとりあえず、「この極座標表示を $x, y$ によるデカルト座標表示に直せ」という問題だったということにして解いてみましょう。そもそも極座標とは、

$$\begin{cases} x &= r \cos\theta\\ y &= r \sin\theta\\ r^2 &= x^2 + y^2\\ \theta &= \arctan(y/x) \end{cases}$$

で表される座標系でした。この関係式を使って、上の曲線の方程式から $r, \theta$ を消去してしまえばよさそうです！しかし、$\sin \theta, \cos \theta$ は多項式ではないので直接 $\theta$ を消去することは出来ません。なので、前の例と同じように $s = \sin \theta, c = \cos \theta$ とおいて、$r, s, c$ を消去することを考えましょう。

座標変換や $\sin, \cos$ の関係式を一緒にしたイデアルが次です。

$$I = \langle r - a(1 + \cos \theta), x - rc, y - rs, r^2-(x^2+y^2) \rangle$$

$s^2+c^2=1$ とかを入れないといけない気がしますが、$x = rc, y = rc, r^2 -(x^2+y^2)$ から出て来るので、これで十分なわけです。
では、先程のようにGröbner基底を計算して、$a, x, y$ のみを含む式を探してみると…… $$2a x^3 - x^4 + a^2 y^2 + 2a x y^2 - 2x^2 y^2 - y^4$$

が該当しそうです！グラフを描いてみると、この多項式の零点の図形は、確かにカージオイドを描くことが判りました！

なんか原点周りの曲線がちょっと粗いように見えますが、これはグラフ計算機の近似計算のせいで描画がおいついていないだけです。拡大してみると、ちゃんとなってるのがわかります。

おわりに

Gröbner基底すごいぞ〜受験数学とけるぞ〜という話でした。ベクトルの幾何の問題や連立方程式の問題は、コンピュータでGröbner基底を計算すればアッという間に解けるので、この冬はGröbner基底を覚えて他の受験生と差を付けよう！

参考文献

• Cox, Little, and O’Shea “Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra”.