熊本大学 教育学部数学科 応用数学研究室

Contents

研究紹介

研究テーマ

「組合せ論」は, 純粋数学の中でも特に, 数学の実際の応用分野(例えば量子情報理論や情報通信など)と最も深く関連している分野であるといえます. 組合せ論は, 数え上げ, グラフ理論, 符号・暗号の理論, 離散幾何, 有限幾何, 組合せ最適化といった様々な分野からなり, またそれらが互いに深く関連しながら成り立っています. 私は特に, 組合せデザインや代数的グラフ理論, 符号理論と呼ばれる群論や整数論といった代数学を基礎にする分野とそれらの実際の応用について興味を持っています.

組合せデザイン

図1
クリックすると拡大されます。

「1ゲーム3人で対戦するゲームを7人で行いたい. 皆が公平に対戦できる(どの2人も同じ回数対戦する)ようにしたい. 最小何ゲームでこの条件を達成できるか?」という問題を考えてみましょう. 図1を見てください. 頂点をプレイヤーに, 直線(真ん中の円)を対戦する3人に対応させます. どの2頂点もちょうど一つの直線(真ん中の円)に含まれていることが見て取れるでしょう. これは先ほどの問題の解(7ゲーム, またこれ以下はあり得ないことも証明できる)になっています. この組合せ構造は, 有限幾何の分野において「射影平面」(Fano plane)とよばれているものです. このような構造が, 何頂点のときに存在する(存在しない)のかという問題は, 組合せデザインにおける最も有名な未解決問題の一つです.

また, このような構造は, 次のような代数的手法を用いても構成できます. {0,1,2,3,4,5,6}をプレイヤーの集合とし, B1={0,1,3}, B2={1,2,4}, B3={2,3,5}, B4={3,4,6}, B5={4,5,0}, B6={5,6,1}, B7={6,0,2}を各ゲームで対戦するプレイヤーの集合とすると, これは問題の解になっていますが, B1に1ずつ加える(7を超えたときは7で割った余りを取る)ことで, その他の試合が巡回的に構成されていることがわかります. これには, B1の任意の2つの要素の差を考えてみると, 7を法として1から6までのすべての数がちょうど1回出現するという性質を利用しています. このような組合せ構造は「差集合」と呼ばれています.

私は特に, 有限体やその拡張であるガロア環上の差集合の構成問題や, アソシエーションスキームの存在性について興味を持っています.

代数的グラフ理論

図2
クリックすると拡大されます。

図2のグラフはPetersenグラフと呼ばれ, とても興味深い性質を持っています. 各点から出ている辺の数はすべて3で, 隣接している任意の2点に同時に接続している点の数は0つ, 隣接していない任意の2点に同時に接続している点の数は1つという性質を持っています. このような性質をもつグラフは強正則グラフと呼ばれ, グラフの隣接行列(グラフの接続関係を表す0,1行列)の固有値を用いて特徴付けすることができます. 実際, 正則グラフが強正則であるための必要十分条件は隣接行列の異なる固有値の数が3つ(うち一つは点の次数)であることが知られています. 同様に, 固有値を使って特徴付け可能なグラフの一つに、ラマヌジャングラフというものがあります.

私は, それらのグラフの中でもケーリーグラフと呼ばれる固有値が群の指標和を用いて表せるクラスについて, 組合せ論的手法と環や体の指標和の計算を組み合せて構成する手法の開発を試みています.

誤り訂正符号

図3
クリックすると拡大されます。

情報通信においては, 我々が普段利用している言葉をそのまま送受信することは一般にはなく, 文字を0,1から成る列に変換して, 送受信を行います. 例えば, 0から15までの16個の文字については, 長さ4の16個の01列に対応させるのは自然な考え方でしょう. しかし, 情報通信においては通信路上の「雑音」がつきもので, 送信した01列のある位置の0と1が反転しまうことがしばしば起きます. そうなると, 送信者が送りたい情報が異なる情報として送信者に届いてしまいます. 例えば, 3=0000, 7=0001に対応させていたとし, 送信者は3を送ったとします. このとき, 雑音によって, 最後のビットの0に誤りが生じ1に反転してしまったとします. このとき, 受信者には7として届いてしまいます. この原因は, 4桁から成る16個の01列に16個の文字をまるまる対応させていたことにあります. よって, 多少の余裕を持たせて, 誤りを発見・訂正をしましょうというのが「誤り訂正符号」です.

図3のように7ビットの01列に16個の文字を対応させれば, 高々1つのどんな誤りが生じても発見・訂正できます. 例えば, 高々一つの誤りしか起きないという仮定のもとで, 受信者が1101101を受け取ったとします. この01列に対応する文字は表にはないので, まず誤りが起きたという事実がわかります. また, 1101101と1=1101001は1ビットの違いしかなく, そのほかの文字とは2ビット以上で異なっています. よって, 送信した文字は1と判定できます. このような誤り訂正符号の構成や存在問題には, 線形代数, 有限体, 整数論といった数学が深く関連しています.

組合せ論の応用

図4
クリックすると拡大されます。

図5
クリックすると拡大されます。

複数のユーザが同時に通信を行う通信方式のことを多重アクセス通信と呼びます. 複数のユーザが同時に通信可能であるというメリットがある一方で, ユーザの電波が混信してしまうという問題点も生じます.このような問題点を解決する(混信した情報から自分の情報だけを抽出する)のに組合せ構造が非常に役に立ちます.

-1,1を成分に持つ正方行列で任意の2行が直交するものを「アダマール行列」と呼びます(図4). まず, あらかじめ、アダマール行列の各行ベクトルrを各ユーザに一つずつ割り当てておき, 各送信者は情報1を送るときr を,情報0を送るとき-rを使って図5のように送ることとします. ここで, 受信者は, どのベクトルがどの送信者に割り当てられているか, また, 送信者が誰かは知っているものとします. 図5において, 受信者A’は, 送信者Aが送った情報が1か0かを判定できるでしょうか?

答え: 受信者A’は混信して受信したベクトルtとAに割り振られたベクトルr4の内積<t,r4>を計算します. この値が正ならば, 送信者Aが情報1を送った. この値が負ならば, 送信者Aが情報0を送ったと判断できます. 実際, ベクトルtはベクトルr1からr8の線形結合として表現されます. 一方, アダマール行列の性質から, 任意の異なるriとrjの内積<ri,rj>は0です. よって, <t,r4>=<±r4,r4>=±8となります. ここで, +は送信情報が1のとき, -は0のときです.よって, 上の方法で判定できるというわけです.

自然な問題として, アダマール行列の存在問題は?AとBの送信開始時刻が同期していないときは?光通信の場合は?といった疑問が生じます. 私は, このような問題に対し, 組合せ論的立場から研究をしています.