位数 120 の 2 つの群の difference set について
梶浦大起（hikajiura@hiroshima-u.ac.jp）

2021/10/16

1

導入
G を位数 v の有限群とする。G の k 点部分集合 D が (v, k, λ)-difference set であるとは，任意の非単位元 a ∈ G に対して，a = x−1 y となる x, y ∈ D の数が a の取り方によらず λ 通りであるときを指す。difference set は，群軌道が対称 2(v, k, λ)-design になる部分集合の特徴づけとして [1] で示されて以来，様々な研究が行われている。良い性質を持つ群のクラスには非常にいろいろなことが知られており，特に巡回群の difference setなどではいくつかの無限系列が実際に構成されている [4]。しかし，具体的に群をひとつ与えたときに，その群の difference set の存在・非存在を決定する問題は非常に難しく，まだまだわかっていないことも多い。
本講演では，以下のふたつの群で difference set の存在・非存在を決定する問題を考えたい:

G1 := x, y, z | y 3 , x5 , z 8 , xy(yx)−1 , zx(xz)−1 , zyz −1 y
= (C3 o C8 ) × C5 ,G3 := x, y, z | y 3 , x5 , z 8 , zyz −1 y, zxz −1 x, yx(xy)−1= C3 o (C5 o C8 ).
ここで，Cn は n 次巡回群とする。
言い換えると，本講演における中心的な問題は以下のものになる:■問G1 と G3 に (120, 35, 10)-difference set が存在するか判定せよ。

上の問いについて，我々は以下のように存在しないことを示した:
定理 1 (主結果). G1 と G3 には (120, 35, 10)-difference set は存在しない。

1

■背景

研究の背景のひとつとして，我々はパラメータ v ，k ，λ を与えたときに，対称 2(v, k, λ)-design を分類したいという意識がある。前述の通り difference set は対称2-design の便利な構成法としてよく知られており，もし (v, k, λ)-difference set が存在することを示せれば対応する対称 2(v, k, λ)-デザインを構成することができる。
今回の話は以下の予想に興味がある:
予想 A 対称 2(120, 35, 10)-design は非存在である。
予想 A を解くことは非常に難しい。そこで，まずは部分的な問題として，difference setで非存在であることを示したい。つまり次の予想をときたい:
予想 B (120, 35, 10)-difference set は非存在である。
本講演はこの予想 B について部分的な解決ができたことを報告するものである。予想

B についての先行研究と本研究の結果の位置づけを簡単に述べる。位数 120 の有限群は同型を除いて 47 種類，可解群 44 種類，非可解群 3 種類がある。この内，可解群については3 つの群を除いて (120, 35, 10)-difference set が存在しないことが示されている [5]。本講
演の主結果は，この未解決であった位数 120 の可解群のうち 2 つについて非存在であることを示した。

2準備

2.1

等分布函数とその準同型

ここでは主定理の証明を理解するための用語と記号を準備する。最初に，difference setを一般化した等分布函数という概念を導入する:
定義 2 (relation parititon). X と I を有限集合とする。R : X × X −→ I が全射である
とき，(X, I, R) を relation partiton とおく。
特に，• I の元 i0 が存在して，R(i0 ) = {(x, x) ∈ X × X | x ∈ X} のとき，unital relation
parititon と呼び，
• 任意の i ∈ {0, . . . , d} に対して，ある ki ∈ Z が存在して以下が成り立つとき，regular relation parititon と呼ぶ:
ki = #{z ∈ X | R(x, z) = i} = #{z ∈ X | R(z, x) = i}ki を分岐指数と呼ぶ。
2for any x ∈ X.

■注意

分岐指数は簡単な計算で，任意の i で ki #X = #Ri であることがわかる。

■例

1. X を有限群，I := X ，R(x, y) := x−1 y とする。このとき，(X, I, R) は unital
regular relation parition となる。これを thin relation partition と呼ぶ。
2. 有限群 G が X に可移に作用しているとする。このとき，I を X × X の対角作用（i.e., X × X に g · (x, y) := (gx, gy)）による軌道分解とする。このとき，R(x, y)
を (x, y) ∈ X × X を含む I の元に対応させる写像とすると，(X, I, R) も regular

unital relation partition であり，特に Schurian relation parition と呼ぶ。本講演
では，簡単のために G の部分集合 H について，左剰余類 G/H のなす Schurianrelation partition も簡単のために G/H と書くことにする。
3. より一般に association scheme は regular unital relation parition である。
定義 3 (等分布函数). (X, I, R) を unital regular relation paritition とする。f ∈ ZX が(X, I, R) 上の (v, k, λ)-等分布函数であるとは，以下を満たすこと:• v = #X ，P• k = x∈X f (x)，• 任意の i ∈ I\{i0 } に対して，λ = (Ai f |f )X /ki が成り立つ。
ここで，f1 , f2 ∈ Z に対し (f1 |f2 )X :=（i.e., ZX の `2 -内積），Ai ∈ ZX×Xx∈X f (x)g(x)P

を i に対応する隣接行列（i.e., R(x, y) = i ならば Ai (x, y) = 1，それ以外で 0）とする。
等分布函数は以下の命題から difference set の一般化であることがわかる:
命題 4. 空でない有限群 G の部分集合 Y が (v, k, λ)-difference set であることと，Y の特性函数が G の thin relation partition 上の (v, k, λ)-等分布函数であることは同値である。
証明）thin relation partition の分岐指数は全て 1 であることと，Y の特性函数を δY とおけば，各 g ∈ G に対して(Ag δY , δY )G = #{(x, y) ∈ Y × Y | x−1 y = g}
(証明了)であることから言える。

この節の最後に，この講演で非常に重要になる relation paritition の準同型を以下で定める:

3

定義 5 (relation paritition の準同型). (X1 , I1 , R1 )，(X2 , I2 , R2 ) を relation parititionとする。このとき，(t, τ ) ∈ Map(X, Y ) × Map(I1 , I2 ) が relation paritition の準同型であるとは，任意の x, y ∈ X1 に対して以下を満たすこと:

R2 (t(x), t(y)) = τ (R1 (x, y)).
■例

1. 群準同型 ϕ の組 (ϕ, ϕ) は thin relation paritition の間の準同型となる。
2. G を有限群として，部分群の列 H < K < G とする。このとき，X1 := G/H ，I1 := H\G/H ，X2 := G/K ，I2 := K\G/K としてそれぞれの Schurian relation
paritition (X1 , I1 , R1 )，(X2 , I2 , R2 ) を考える。
写像 θ : X1 −→ X2 を G/H から G/K への標準射影，τ : I1 −→ I2 を以下のように定めたとき，組 (θ, τ ) は準同型となる:

τ (HaH) := KaKfor any a ∈ G.

命題 6. (t, τ ) を (X1 , I1 , R1 ) から (X2 , I2 , R2 ) の準同型とする。このとき，t が全射ならば τ も全射である。
証明）準同型の定義は，R1 ◦ (t × t) = τ ◦ R2 ともかける*1 。いま，relation paritition の定義から R1 と R2 は全射であり，更に仮定から t × t も全射なので，τ が全射になること(証明了)が直ちにわかる。
特に t が全射のとき (t, τ ) を全射準同型と呼ぶ。

*1 t × t : X1 × X1 −→ X2 × X2 ; (x, y) 7−→ (t(x), t(y)) で定める。

4

3

主結果の証明3.1

証明の概略

主結果の証明の概略を述べる。証明の中心は以下のアルゴリズムである:

Algorithm 1 Difference set の存在問題決定アルゴリズム
Input: v, k, λ ∈ Z>0 , 有限群 G（ただし #G = v ）;Output: True or False;
1: read(G の部分群列 G = H0 > H1 > H2 > . . . Hm = 1);
2: Let D0 := {k} ⊂ ZG/H0 = Z;
3: for i = 1 to m do
4:

Let θ: G/Hi から G/Hi−1 への標準射影;

5:

Di := {f ∈ θ∗−1 (Di−1 ) | (v/#Hi , k, λ#Hi )-等分布函数かつ 0 ≤ f ≤ #Hi };6:

if Di = ∅ then7:
8:

return False;end if

9: end for
10: return

True;

ここで各 i について θ∗ : ZG/Hi −→ ZG/Hi−1 は θ の押出し，i.e., 各 f ∈ ZG/Hi に対しXθ∗ (f )(y) :=f (x).

x∈θ −1 (y)と定める。上記のアルゴリズムについて，以下の定理が成り立つ:
定理 7. Dm は G の (v, k, λ)-difference set の特性函数の全体である。特に，アルゴリズ
ムの計算結果が True であれば G に (v, k, λ)-difference set は存在し，False であれば Gに (v, k, λ)-difference set は存在しない。
この定理は以下の補題から直ちに示される（証明は後述）:
補題 8. ふたつの unital regular relation paritition (X1 , I1 , R1 )，(X2 , I2 , R2 ) とその間の全射準同型 (θ, τ ) を考える。このとき，任意の (X1 , I1 , R1 ) 上の (#X1 , k, λ)-等分布函数 f ∈ ZX1 に対し，θ∗ (f ) は (X2 , I2 , R2 ) 上の (#X2 , k, λ#X1 /#X2 )-等分布函数と5なる。
■定理 7 の証明 上記の補題から任意の i に対して以下の命題が示される:

Di = {f ∈ ZG/Hi | (v/#Hi , k, λ#Hi )-等分布函数かつ 0 ≤ f ≤ #Hi }.
実際，右辺が左辺を含むのは明らかで，左辺が右辺を含む（i.e., 任意の (v/#Hi , k, λ#Hi )等分布函数 f が 0 ≤ f ≤ #Hi を満たせば θ∗ (f ) ∈ Di−1 となる）ことも，押し出しの定義から 0 ≤ θ∗ (f ) ≤ #Hi−1 となることからいえる。
特に，Hm = 1 で f ∈ ZG/Hm が 0 ≤ f ≤ 1 （i.e., f は G のある部分集合に関する特性函数）であるときは，(v, k, λ)-等分布函数であることと (v, k, λ)-difference set であることが同値であったので Dm は (v, k, λ)-difference set の特性函数の全体であることがわかる。

3.2

先行研究とアルゴリズムの関係

このアルゴリズムは [1, Lemma 4.1.] の一般化にあたる結果である。[1] は補題 8 の結果について，(X1 , I1 , R1 ) と (X2 , I2 , R2 ) が共に thin relation paritition（i.e., 有限群）で，かつ f は 0 ≤ f ≤ 1 （i.e., 特性函数）の場合に示した。この結果を用いて λ < 20 の場
合の difference set の分類などが行われている [6]。また，特性函数の条件を外した（i.e.,multi set の）場合にも同様に成り立つことが知られ，それらを利用したアルゴリズムがGAP[2] に「DifSets」というライブラリとして実装されている。実際ライブラリを活用して v ≤ 100 の場合の difference set の分類などが行われている [7]。
本講演で示すアルゴリズムはこれらの結果の一般化である。先行研究では有限群での範囲でしか等分布函数（先行研究では，difference sum や intersection number，differencelist などと呼ばれる）を計算できなかった。しかし，我々のこの一般化によって有限群よりも広い範囲で計算が可能になったことが主結果証明の決め手となっている。

3.3

所与の群による判定について

3.3.1

G1 の判定G1 := x, y, z | y 3 , x5 , z 8 , xy(yx)−1 , zx(xz)−1 , zyz −1 y について，以下の部分群列
H0 > H1 > . . . > H4 を取る:
H0 = G1 ,H1 := hx, zi ,H2 := hzi ,6

H3 := z 2 ,H4 := 1.

この中で，H1 と H2 は正規部分群ではない。また，#H1 := 40，#H2 := 8，#H3 := 4である。
このとき，前述のアルゴリズムを計算機を用いて計算すると，以下のことがわかる:
命題 9. アルゴリズムと同じ記号を使う。各 Di の濃度は以下のとおり:#D0 = 1,#D1 = 3,

#D2 = 45,

#D3 = 0,

#D4 = 0.

i.e., D3 = ∅ であり，アルゴリズムの実行結果は False になる。

3.3.2

G3 の判定G1 := x, y, z | y 3 , x5 , z 8 , zyz −1 y, zxz −1 x, yx(xy)−1 について，以下の部分群列 H0 >H1 > . . . > H4 を取る:
H0 = G1 ,H1 := hx, zi ,H2 := hzi ,H3 := z 2 ,H4 := 1.

この中で，H1 と H2 は正規部分群ではない。また，#H1 := 40，#H2 := 8，#H3 := 4である。
このとき，前述のアルゴリズムを計算機を用いて計算すると，以下のことがわかる:
命題 10. アルゴリズムと同じ記号を使う。各 Di の濃度は以下のとおり:#D0 = 1,#D1 = 3,

#D2 = 45,

#D3 = 0,

#D4 = 0.

i.e., D2 = ∅ であり，アルゴリズムの実行結果は False になる。

4

補題 8 の証明

4.1

証明の準備

(X1 , I1 , R1 )，(X2 , I2 , R2 ) を unital regular relation paritition として，k0 , . . . , kr を(X1 , I1 , R1 ) の分岐指数，l0 , . . . , ls を (X2 , I2 , R2 ) の分岐指数，(θ, τ ) を (X1 , I1 , R1 ) から (X2 , I2 , R2 ) への全射準同型とする。

t を CX1 から CX2 への線型写像としたときに，`2 -内積に関する随伴 t† : CX2 −→ CX1を以下で定義する:(fY |t(fX ))X2 = (t† (fY )|fX )X1
7for any f1 ∈ CX1 , f2 ∈ CX2 .

簡単な計算で任意の線型写像に対して随伴が存在することがわかる。
また，{Ai }i∈I1 を (X1 , I1 , R1 ) の隣接行列全体 {Bi }i0 ∈I2 を (X2 , I2 , R2 ) の隣接行列全体とする。このとき，以下が成り立つ:
命題 11. 任意の β ∈ I2 に対して，θ † Bβ θ =Pα∈τ −1 (β) Aα が成り立つ。

証明）x ∈ X の特性函数を δx ∈ ZX とする。任意の x1 , x2 ∈ X に対して一致することを示す。左辺を実際に計算すると，以下が成り立つ:((θ† Bβ θ)δx1 |δx2 )X1 = (Bβ θ(δx1 )|θ(δx2 ))X2 = (Bβ δt(x1 ) |δθ(x2 ) )X2X
X=(Bβ δθ(x1 ) )(y)δθ(x2 ) (y) =δθ(x1 ) (y1 )δθ(x2 ) (y2 )y∈X2=R2 (y1 ,y2 )=β1 R1 (θ(x1 ), θ(x2 )) ∈ τ0otherwise

−1(β)

.

また，(t, τ ) が準同型であることから右辺について以下がわかる:

XAi δx1 , δx2 i∈τ −1 (i0 )=1 R1 (θ(x1 ), θ(x2 )) ∈ τ −1 (β)
0otherwise

X1(証明了)よって両辺が等しいことが示された。
次に，以下の命題を用意する:
命題 12. 任意の y ∈ Y に対して，#t−1 (y) = #X/#Y 。

証明）(θ, τ ) が unital relation partition 間の準同型であることから以下が成り立つ:

θ(x1 ) = θ(x2 ) ⇐⇒ (θ(x1 ), θ(x2 )) ∈ S0 ⇐⇒ (x1 , x2 ) ∈ tα∈τ −1 (i20 ) R−1 (α)(x1 , x2 ∈ X1 ).

上から，任意の y ∈ X2 に対して x ∈ θ −1 (y) をひとつ固定すると，以下が成り立つ:

θ−1 (y) = {z ∈ X | θ(z) = y} = {z ∈ X | (x, z) ∈ tα∈τ −1 (i20 ) R1−1 (α)}
G={z ∈ X | (x, z) ∈ R1−1 (α)}α∈τ −1 (i20 )(X1 , I1 , R1 ) が regular であることから，右辺の濃度は x ∈ X1 の取り方によらない。
よって，任意の y ∈ X2 で t−1 (y) が定数であることが示される。

#t−1 (y) = #X/#Y は，ty∈X2 t−1 (y) = #X からすぐに確認できる。
上の命題から直ちに以下が示される:

8(証明了)

命題 13. 任意の β ∈ {0, . . . , s} に対して，lβ (#X/#Y ) =α∈τ −1 (β) kα 。

P証明）(θ, τ ) が準同型より以下が成り立つ:

G(t × t)−1 (R2−1 (β)) =R1−1 (α)

for any β ∈ {0, . . . , s}.

α∈τ −1 (i20 )両辺の濃度を実際に計算すると，前述の命題から以下が言えて成り立つ:

#(t × t)−1 (R2−1 (β)) =X
x∈X1#G

X

R2 (θ(x),y)=β

Ri = #X1i∈τ −1 (i0 )#θ−1 (y) = #X1 lβ (#X1 /#X2 ),Xkα .

α∈τ −1 (β)

(証明了)

4.2

補題 8 の証明

任意の (#X1 , k, λ)-等分布函数 f に対して，θ∗ (f ) が (#X2 , k, λ#X1 /#X2 )-等分布函数であることを示す。
任意の i0 ∈ {1, . . . s} をとる。命題 11 よりX(Bβ θ(f )|θ(f ))X2 = ((θ† Bβ θ)f |f )X1 =(Aα f |f )X1α∈τ −1 (β)となる。f は等分布函数なので，(Aα f |f )X1 = λki より，X(Aα f |f )X1 = λα∈τ −1 (β)

Xkαα∈τ −1 (β)となり，命題 13 と合わせると(Bβ θ(f )|θ(f ))X2 = λ(#X/#Y )lβより，f は (#X2 , k, λ#X1 /#X2 )-等分布函数である。

参考文献[1] Bruck, R. Hubert, Difference sets in a finite group, 1995, Trans. Amer. Math. Soc.
9

[2] GAP - Groups, Algorithms, Programming -a System for Computational DiscreteAlgebra, https://www.gap-system.org/, 2021/10/15 閲覧.
[3] Hiroki Kajiura, Makoto, Matsumoto, Takayuki Okuda, A generalization of Bruck’s
condition pre-difference sets and equi distributed functions in association schemes,
2020, preprint.
[4] J. H. van Lint, R. M. Wilson, A Course in Combinatorics (2nd), 2001, Cambridge
University Press,[5] Paul E. Becker, Investigation of Solvable (120, 35, 10) Difference Sets, 2004, Wiley
InterScience.
[6] Robert E. Kibler, A summary of noncyclic difference sets, k < 20, J. Combinatorial
Theory Ser, 1978.
[7] Dylan Peifer, DifSets, an algorithm for enumerating all difference sets in a group,
Version 2.3.1, 2019, https://dylanpeifer.github.io/difsets., 2021/10/15 閲
覧.

10