SharedPolynomials.ipynbOpen in CoCalc
Author: Keita Xagawa
Views : 35

復習編

整数

まずはsagemathでの演算に慣れましょう。

In [1]:
f = 7 g = 2 print f + g print f * g
9 14

と、整数の足し算と掛け算が出来ます。 次にこれを法10で (mod10\bmod{10}の世界で) 考えましょう。

nnで割った余りだけ考える剰余環を Zn:=Z/(nZ)\mathbb{Z}_n := \mathbb{Z}/(n\mathbb{Z})とします。

In [4]:
Z_10 = Integers(10) print ZZ print Z_10 f = Z_10(7) g = Z_10(2) print f + g print f * g
Integer Ring Ring of integers modulo 10 9 4

4=72mod104 = 7 * 2 \bmod{10}が出力されていることがわかります。

多項式

次に多項式の演算をしてみましょう。

f=1+x2+x3f = 1 + x^2 + x^3g=2+x1+x6g = 2 + x^1 + x^6の足し算と掛け算をやってみます。

In [3]:
f = 1 + x^2 + x^3 g = 2 + x^1 + x^6 print f + g print f * g
x^6 + x^3 + x^2 + x + 3 (x^6 + x + 2)*(x^3 + x^2 + 1)

はい。簡単に演算が出来ました。

多項式でも整数の場合と同様に剰余環を考えることができます。 x51x^5-1で割った余りだけ考える剰余環を R5:=Z[x]/(x51)R5 := \mathbb{Z}[x]/(x^5-1)と書くことにします。

In [10]:
R.<x> = ZZ[] R5 = R.quotient(x^5-1) print R print R5 f = R5(1 + x^2 + x^3) g = R5(2 + x^1 + x^6) print f + g print f * g
Univariate Polynomial Ring in x over Integer Ring Univariate Quotient Polynomial Ring in xbar over Integer Ring with modulus x^5 - 1 xbar^3 + xbar^2 + 2*xbar + 3 2*xbar^4 + 4*xbar^3 + 2*xbar^2 + 2*xbar + 2

ここで変数名がxbarになっているのは、R5の定義で変数を指定していないからです。 R5.<y> = R.quotient(x^5-1)とすると, xbarがすべてyに代わります。

今、法x51x^5-1を考えているので, x510(modx51)x^5 - 1 \equiv 0 \pmod{x^5-1}です。 これはx51(modx51)x^5 \equiv 1 \pmod{x^5-1}ということです。 よって、この剰余環ではx5x^511になってしまうわけです。 掛け算した結果, x5+ix^{5+i}という項が出てきたら、すべてxix^iに置き換えることになります。

確認してみましょう。

あってますね。

さらに整数環も剰余環にして, R510:=Z10[x]/(x51)R5_{10} := \mathbb{Z}_{10}[x]/(x^5-1)を考えて演算してみましょう。

In [7]:
R_10.<x> = Z_10[] R5_10 = R_10.quotient(x^5-1) print R_10 print R5_10 f = R5_10(1 + x^2 + x^3) g = R5_10(2 + x^1 + x^6) print f + g print f * g
Univariate Polynomial Ring in x over Ring of integers modulo 10 Univariate Quotient Polynomial Ring in xbar over Ring of integers modulo 10 with modulus x^5 + 9 xbar^3 + xbar^2 + 2*xbar + 3 2*xbar^4 + 4*xbar^3 + 2*xbar^2 + 2*xbar + 2

はい、できました。 R_10R5_10の要素をRの要素に__自然に__戻すには以下のようにします。

In [8]:
f = R_10(1 + x^2 + x^3) print f.change_ring(ZZ) print f.change_ring(ZZ).parent() g = R5_10(2 + x^1 + x^6) # print g.change_ring(ZZ) -> Error print g.lift() print g.lift().parent() print g.lift().change_ring(ZZ) print g.lift().change_ring(ZZ).parent()
x^3 + x^2 + 1 Univariate Polynomial Ring in x over Integer Ring 2*x + 2 Univariate Polynomial Ring in x over Ring of integers modulo 10 2*x + 2 Univariate Polynomial Ring in x over Integer Ring

多項式とベクトルと巡回行列

多項式環は加法だけ考えて群とみなせば、(無限次元)ベクトル空間となります。適当な次数以上の項を無視してベクトルに表してみましょう。

In [11]:
# 多項式をベクトルに直す関数 # f_0 + f_1 x + ... + f_{n-1} x^{n-1} -> (f_0,f_1,...,f_{n-1}) # R(x^i)としておかないと, i=0のときにエラー def vectorize(f,n): return vector(ZZ,[f.monomial_coefficient(R(x^i)) for i in range(n)]) f = 1 + x^2 + x^3 g = 2 + x^1 + x^6 print f + g fv= vectorize(f,10) gv= vectorize(g,10) print fv + gv
x^6 + x^3 + x^2 + x + 3 (3, 1, 1, 1, 0, 0, 1, 0, 0, 0)

xn1x^n-1をとっても同様です。 都合上、R_10R5_10の要素はいったんRの要素とみなしてから、ベクトルに直します。

In [12]:
f = R_10(1 + x^2 + x^3) g = R5_10(2 + x^1 + x^6) # vectorize(f,5) -> TypeError fv = vectorize(f.change_ring(ZZ),5) gv = vectorize(g.lift().change_ring(ZZ),5) print fv print gv # ベクトルを多項式 in Rに直す関数 def vec_to_poly(z): tmp = R(0) for i in range(len(z)): tmp += R(z[i]*x**i) return tmp print vec_to_poly(fv) print vec_to_poly(gv)
(1, 0, 1, 1, 0) (2, 2, 0, 0, 0) x^3 + x^2 + 1 2*x + 2

足し算はうまくいきました。次に掛け算を考えましょう。 ベクトルとベクトルの間には掛け算という演算がないので、うまく定義する必要があります。

多項式での掛け算をうまく分解してやると となります。 これを踏まえて,

(f0,f1,f2,f3,f4)(gxgmodx51x2gmodx51x3gmodx51x4gmodx51)=i=04fi(xigmodx51)=fg(f_0,f_1,f_2,f_3,f_4) \cdot \begin{pmatrix} g \\ x g \bmod{x^5-1} \\ x^2 g \bmod{x^5-1} \\ x^3 g \bmod{x^5-1} \\ x^4 g \bmod{x^5-1} \\ \end{pmatrix} = \sum_{i=0}^{4} f_i \cdot (x^i \cdot g \bmod{x^5-1}) = f * g とベクトルと行列の積として考えることが出来ます。

今回は法がx51x^5-1なので、ggに対応する行列は__巡回行列__になります。

In [13]:
f = R5_10(1 + x^2 + x^3) g = R5_10(2 + x^1 + x^6) print f * g # 多項式 in Rを巡回行列に直す関数 def circulant_matrix(f,n): return matrix(ZZ,n,n,lambda i,j: f.monomial_coefficient(R(x^((j-i) % n)))) fv = vectorize(f.lift().change_ring(ZZ),5) fm = circulant_matrix(f.lift().change_ring(ZZ),5) gm = circulant_matrix(g.lift().change_ring(ZZ),5) print fv print fm print gm print fv * gm == vectorize((f*g).lift().change_ring(ZZ),5) print fm * gm == circulant_matrix((f*g).lift().change_ring(ZZ),5)
2*xbar^4 + 4*xbar^3 + 2*xbar^2 + 2*xbar + 2 (1, 0, 1, 1, 0) [1 0 1 1 0] [0 1 0 1 1] [1 0 1 0 1] [1 1 0 1 0] [0 1 1 0 1] [2 2 0 0 0] [0 2 2 0 0] [0 0 2 2 0] [0 0 0 2 2] [2 0 0 0 2] True True

ffの方も巡回行列にしてみましょう。 ffに対応する巡回行列とggに対応する巡回行列の積がfgf*gに対応する巡回行列になります。 ということで、可換環KKについて, K[x]/(xn1)K[x]/(x^n-1)は, nn次のKK要素巡回行列がなす環Cir(K,n)\mathrm{Cir}(K,n)と同型ということがいえます。