千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2021年8月実施 専門 B10

标签：

• Bipartite-Graph
• Quotient-Ring

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

各頂点がどの元であるか明示して、次のグラフ $(V,E)$ を図示せよ。

1. $V=\mathbb F_{11}$、$\mathcal E$ をその原始元全体とし、$E=\{(x,ax):x\in V,a\in\mathcal E\}$。
2. $V=\mathbb F_2[X]/(X^4+X+1)$、$\mathcal E$ をその原始元全体とし、$E=\{(x,x+a):x\in V,a\in\mathcal E\}$。

题目描述

画出以下图，并标清各顶点所对应的域元素：(1) 顶点为 $\mathbb F_{11}$，当 $a$ 为本原元时连接 $x$ 与 $ax$；(2) 顶点为 $\mathbb F_2[X]/(X^4+X+1)$，当 $a$ 为本原元时连接 $x$ 与 $x+a$。

Kai

(1) $2$ は $\mathbb F_{11}^\times$ の生成元であり、原始元は

$$\mathcal E=\{2^j:\gcd(j,10)=1\}=\{2,8,7,6\}.$$

$0$ にはループが一つある。他の頂点を $2^j$（$j\in\mathbb Z/10\mathbb Z$）と表示すると、隣接条件は $j-k\equiv\pm1,\pm3\pmod{10}$。従って偶数指数と奇数指数に分けた $K_{5,5}$ から、指数差 $5$ の完全マッチングを除いたグラフである。

原始元の逆元も原始元なので、以下の無向辺はそれぞれ逆向きの二本の有向辺を表す。

(2) $\alpha=X\bmod(X^4+X+1)$ とおく。$\alpha^4=\alpha+1$ より計算すると $\alpha^{15}=1$、$\alpha^3\ne1$、$\alpha^5\ne1$ なので $\alpha$ は位数 $15$ の原始元である。従って

$$\mathcal E=\{\alpha^j:j=1,2,4,7,8,11,13,14\}.$$

$1,\alpha,\alpha^2,\alpha^3$ を基底として、$b_0+b_1\alpha+b_2\alpha^2+b_3\alpha^3$ を二進ラベル $b_3b_2b_1b_0$ で表示する。この表示で

$$\mathcal E=\{0010,0100,0011,1011,0101,1110,1101,1001\}.$$

二頂点のラベルの XOR がこの集合に属する場合に辺を結ぶ。以下が全 $16$ 頂点・$64$ 本の無向辺の図である。各辺は問題の有向辺二本に対応し、ループはない。