mog project: IVA Reading: Chapter 02, Section 01 Exercises

6.09.2014

IVA Reading: Chapter 02, Section 01 Exercises

IVA読書会 chap02-sect01 宿題

No.1

$f(x)=x^2-3x+2=(x-1)(x-2) \Rightarrow f \in I$

$f(x)=x^5-4x+1=(x+1)(x^3-x^2+x) - x^2-4x+1 \Rightarrow f \notin I$

$I=\langle\text{GCD}(x^4-6x^2+12x-8, 2x^3-10x^2+16x-8)\rangle=\langle1\rangle \Rightarrow f \in I$

$I=\langle\text{GCD}(x^9-1, x^5+x^3-x^2-1)\rangle=\langle x^3-1\rangle \Rightarrow f \in I$

PARI/GP を使ってGCDを求めてみる

インストール => brew install pari (if Mac)

実行

$ /usr/local/bin/gp
                                                 GP/PARI CALCULATOR Version 2.5.5 (released)
                                         i386 running darwin (x86-64/GMP-6.0.0 kernel) 64-bit version
                                    compiled: Jun  8 2014, gcc-5.1 (clang-503.0.40) (based on LLVM 3.4svn)
                                                (readline v6.3 enabled, extended help enabled)
 
                                                    Copyright (C) 2000-2013 The PARI Group
 
PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY WHATSOEVER.
 
Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.
 
parisize = 8000000, primelimit = 500509
? gcd(x^9 - 1, x^5 + x^3 - x^2 - 1)
%1 = x^3 - 1
? \q
Goodbye!

No.5

$f(u,t), g(u,t), h(u,t)$ の全次数が高々 $n$ であるとする。

$a+b+c\le m$ を満たすとき、 $[f(u,t)]^a[g(u,t)]^b[h(u,t)]^c$ の $u,t$ についての全次数は高々 $nm = \text{O}(m)$ 。
∵ $\text{deg}([f(u,t)]^a[g(u,t)]^b[h(u,t)]^c) \le na+nb+nc =n(a+b+c) \le nm$

一方、 $x^a y^b z^c$ の線形結合の係数は、 $x^a y^b z^c 1^d, a+b+c+d=m$ と考えると重複組合せ問題となり、
${}_{4} H _{m} = {}_{4+m-1} C _{m} = \begin{eqnarray} {}_{m+3} C _3 \end{eqnarray} = (m+3)(m+2)(m+1)/(3\cdot 2\cdot 1)=\Theta(m^3)$ 個存在することがわかる。

十分大きな $m$ に対しては $nm \le (m+3)(m+2)(m+1)/(3\cdot 2\cdot 1)$ が満たされるため
全問までの議論と同様、
$F(f(t),g(t),h(t))$ が $t,u$ の多項式として $0$ になるような $F \in k[x,y,z]$ をとることが可能。