rkm0959

github.com/rkm0959/rkm0959_implements/tree/main/Chebyshev%20Acceleration

매우 최근에 올라온 Acceleration에 대한 Survey Paper arxiv.org/abs/2101.09545을 읽는다. 이 글은 2장을 정리한다.

일단은 관심가는 부분만 읽을 예정인데, 아마 3장을 제일 마지막에 읽을 것 같다. 사전지식이 부족한 경우 이 자료 참고.

Acceleration Survey Paper + OSPEP + Proximal Algorithms Survey Paper 이렇게 읽으면 지식이 좀 쌓이지 않을까 생각중이다..

모든 정리의 번호는 Survey Paper와 같은 번호를 사용한다. 단순히 정리 블로그니까 논문 표현을 그대로 가져다 쓰는 일도 많을 것이다.

이 글에서는 unconstrained quadratic minimization 문제, 즉 $f(x) = \frac{1}{2} x^T Hx - b^Tx$를 최소화하는 문제를 다룬다. 물론 $H$는 symmetric.

이 문제의 optimal point는 $x^{*} = H^{-1}b$임이 자명하다. 즉, 이 문제는 결국 linear system의 해를 빠르게 구하는 문제와 같다.

보통 이러한 minimization 문제를 만나면, 많은 사람들이 Gradient Descent를 생각할 것이다. 

즉, initial point $x_0$와 step-size $\gamma$를 잡고, $x_{i+1} = x_i - \gamma \nabla f(x_i)$를 반복하는 것이다.

이 식을 정리하면 $x_{i+1} = (I - \gamma H) x_i + \gamma b$를 얻고, $x^{*}$의 식을 이용하면 $$x_{k+1} - x^{*} = (I - \gamma H) (x_k - x^{*})$$를 얻는다. 이제 우리의 목표는 $I - \gamma H$의 matrix norm을 최소화하는 것이다. 우리는 일반적으로 2-norm, 즉 Spectral Norm을 생각한다.

이제 잠시 $H$로 가능한 행렬의 범위를 좁혀, 적당한 $\mu, L > 0$에 대해 $\mu I \le H \le L I$가 성립한다고 가정하자.

그러면 우리는 $\gamma$를 선택하는 과정에서 worst-case convergence를 최선으로 하기 위해서 $$\max_{\mu I \le H \le LI} ||I - \gamma H||_2$$를 최소화할 필요가 있다. 이 문제는 결국 $\text{max}(|1-\mu \gamma|, |L \gamma - 1|)$를 최소화하는 것이다. 그러니 $\displaystyle \gamma = \frac{2}{\mu + L}$를 잡을 수 있다.

특히 이 경우 $\displaystyle ||I - \gamma H||_2 \le \frac{L - \mu}{L + \mu} = \frac{\kappa - 1}{\kappa + 1}$이고 ($\kappa = L / \mu$는 condition number) $$||x_k - x^{*}||_2 \le \left( \frac{\kappa - 1}{\kappa + 1} \right)^{k} ||x_0 - x^{*}||_2$$를 얻는다. 이것이 Gradient Descent의 수렴 속도가 되겠다. 이를 더 빠르게 하는 것이 우리의 목표다.

이번에는 조금 더 넓은 class의 알고리즘을 생각해보자. $x_{k+1}$을 $x_k$에 $\nabla f(x_k)$의 상수배를 더한 것만 고려하지 말고, 아예 $$x_{k+1} \in x_0 + \text{span} \{ \nabla f(x_0), \cdots , \nabla f(x_k) \}$$를 고려하자. 이 경우, 단순한 수학적 귀납법으로 다음을 보일 수 있다.

Proposition 2.1. : 위와 같은 방식으로 $x_k$를 계산한 경우, 다항식 $P_k$가 있어 $\text{deg}(P_k) \le k$, $P_k(0) = 1$이고 $$x_k - x^{*} = P_k(H)(x_0 - x^{*})$$ 이제 우리는 앞선 사고방식을 그대로 따라가면 $$\displaystyle \max_{\mu I \le H \le LI} ||P_k(H)||_2$$를 최소화하고 상수항이 $1$인 $k$차 이하 다항식 $P_k$를 찾아야 한다. 그런데 $H$가 symmetric이므로, 이 문제는 사실 $$\max_{\mu \le \lambda \le L} |P_k(\lambda)|$$를 최소화하는 것과 같다. 이제 짬이 좀 찬 독자들은 Chebyshev라는 단어가 왜 나왔는지 알 것이다. 저런 문제에서 최적의 다항식이 Chebyshev Polynomial이기 때문이다. 이들은 $[-1, 1]$ 위에서 최적이기 때문에, $[\mu, L]$을 $[-1, 1]$로 shift 하는 처리 작업이 필요하다. 즉, $$t : x \rightarrow \frac{2x - (L + \mu)}{L - \mu}$$의 처리를 하자. 또한, $P_k(0)=1$이라는 조건이 있으니 이것도 처리해야 한다. 결과적으로 우리는 $$C_k^{[\mu, L]}(x) = \frac{T_k(t(x))}{T_k(t(0))}$$라는 다항식을 정의할 수 있다. 이제 목표는 $$x_k - x^{*} = C_k^{[\mu, L]}(H) (x_0 - x^{*})$$가 성립하도록 효율적인 iteration을 설계하는 것이다. 이를 위해서는 $C_k^{[\mu, L]}$에 대한 점화식이 필수적이다. 결과적으로, $$\delta_0 = -1, \quad \delta_k = \frac{L - \mu}{2(L + \mu) - \delta_{k-1}(L - \mu)}$$ $$C_0^{[\mu, L]}(x) = 1, \quad C_1^{[\mu, L]}(x) = 1 - \frac{2}{L + \mu}x, \quad C_k^{[\mu, L]}(x) = \frac{2\delta_k (L+\mu - 2x)}{L - \mu} C_{k-1}^{[\mu, L]}(x) + \left( 1 - \frac{2\delta_k (L+\mu)}{L - \mu} \right) C_{k-2}^{[\mu, L]}(x)$$가 성립함을 보일 수 있다. Chebyshev Polynomial의 점화식을 가지고 열심히 계산하면 될 것으로 예상한다.

이제 이를 $x_k - x^{*} = C_k^{[\mu, H]}(x_0 - x^{*})$에 집어넣고 $\nabla f(x_k) = Hx_k - b = H(x_k - x^{*})$를 이용하면, iteration $$x_k = \frac{2\delta_k}{L-\mu} ((L+\mu) x_{k-1} - 2 \nabla f(x_{k-1})) + \left( 1 - \frac{2\delta_k (L + \mu)}{L - \mu} \right) x_{k-2}$$를 얻는다. 이 iteration에 대해서 몇 가지 고찰을 해보자. 이 식은 $$x_k = x_{k-1} - \frac{4 \delta_k}{L - \mu} \nabla f(x_{k-1}) + \left( 1  - \frac{2\delta_k (L+\mu)}{L - \mu} \right)(x_{k-2} - x_{k-1})$$이라 쓸 수 있다. 결국 Gradient Descent Term (step size는 변화함) + Momentum Term (변화함) 으로 볼 수 있다.

특히, $\delta_k$의 극한을 취하면 $\displaystyle \frac{\sqrt{L}-\sqrt{\mu}}{\sqrt{L} + \sqrt{\mu}}$로 수렴함을 알 수 있으며, 이 값을 iteration에 그대로 대입하면 Heavy Ball Method를 얻는다고 한다.

이제 이 새로운 iteration의 수렴 속도를 알아보자. 결국 $\lambda \in [\mu, L]$에 대하여 $$|C_k^{[\mu, L]}(\lambda)| \le \frac{1}{|T_k(t(0))|}$$이 성립하고, 여기서 $\displaystyle \xi = \frac{\sqrt{\kappa}+ 1}{\sqrt{\kappa} - 1}$라 하면 위 식의 우변이 정확하게 $\displaystyle \frac{2}{\xi^k + \xi^{-k}}$와 같음을 알 수 있다. 그러니 이를 그대로 대입하여 $$||x_k - x^{*} ||_2 \le \frac{2}{\xi^k + \xi^{-k}} ||x_0 - x^{*}||_2$$를 얻는다. 이제 이를 기존의 Gradient Descent와 비교할 일만 남았다. 이를 위해서는 원하는 정확도를 위해서 iteration이 얼마나 필요한지 보면 된다.

Corollary 2.2. : 고정된 $\mu, L$에 대하여, $||x_k - x^{*}||_2 \le \epsilon$을 얻기 위하여 필요한 $k$의 값은

• 기존 Gradient Descent의 경우 $\displaystyle k \ge 2 \kappa  \log (||x_0-x^{*}||_2 / \epsilon)$
• 새로운 Chebyshev Method의 경우 $\displaystyle k \ge 2 \sqrt{\kappa} \log(2 ||x_0-x^{*}||_2 / \epsilon)$

그러니 Chebyshev Method의 강력함을 알 수 있다. 특히 $\kappa$가 큰 경우 더욱 강력한 힘을 발휘한다.

Stickelberger’s Criterion : $K$가 NF고 $n = [K : \mathbb{Q}]$이라 하자. $\alpha_1, \cdots , \alpha_n \in \mathcal{O}_K$에 대하여, $d = \text{disc}(\alpha_1, \cdots, \alpha_n) \equiv 0, 1 \pmod{4}$.

• 특히, 여기서 $\text{disc}(\mathcal{O}_K) \equiv 0, 1 \pmod{4}$를 얻는다.

Discriminant는 결국 determinant의 제곱이고, determinant는 결국 짝순열 곱의 합에 홀순열 곱의 합을 뺀 것이다.

짝순열 곱의 합을 $P$, 홀순열 곱의 합을 $N$이라고 하면, $d = (P - N)^2 = (P + N)^2 - 4 PN$이 성립한다.

그러므로, 만약 $P+N$과 $PN$이 정수임을 보일 수 있다면, 제곱수의 성질에 의해서 원하는 것이 증명될 것이다.

한편, $P, N$이 각각 AI라는 점은 자명하므로, $P+N, PN$이 유리수임을 보이면 충분하다.

이를 위해서는 적당한 Galois group을 꺼내고, 모든 경우에 대해서 $P+N$, $PN$이 fix 된다는 것을 보이는 방식이 사용된다.

하지만 우리가 지금 normal extension 위에서 놀고 있다는 것은 모르므로, normal closure를 꺼내야 한다.

즉, $K$가 $\mathbb{Q}$의 finite extension이므로, 그 normal closure $L$을 생각할 수 있다. 그러니 $\text{Gal}(L/\mathbb{Q})$에서 놀아보자.

여기서 $K$ embedding을 $\sigma_1, \cdots , \sigma_n$이라고 하자. $L = \sigma_1(K) \cdot \sigma_2(K) \cdots \sigma_n(K)$임은 잘 알려져 있다.

또한, 각 $\phi \in \text{Gal}(L/\mathbb{Q})$에 대하여, $\{\phi \circ \sigma_i\} = \{\sigma_i \}$임도 잘 알려져 있다. 그렇다면 $\phi$에 $S_n$의 원소가 대응된다는 건데...

결과적으로, 이 대응되는 $\phi$가 짝순열이라면 $\phi$는 $P, N$을 고정시키고, 홀순열이라면 $\phi$는 $P, N$을 swap 한다. 증명은 어렵지 않다.

그러니 $P+N$, $PN$은 홀짝 여부에 관계없이 항상 고정되며, 그러니 Galois Theory의 결과에서 $\mathbb{Q}$의 원소가 된다.

이제 우리는 다음 결과를 증명할 준비가 완료되었다.

정리 : $\omega = e^{2\pi i / m}$이고, $K = \mathbb{Q}(\omega)$라면, $\mathcal{O}_K = \mathbb{Z}[\omega]$다.

물론, $\mathbb{Z}[\omega] \subset \mathcal{O}_K$는 자명하다. 반대방향이 핵심이다.

Step 1 : Discriminant Facts

$p$를 홀수 소수라고 하고, $\omega = e^{2\pi i / p}$라 하자. $f(x) = \text{irr}(\omega, \mathbb{Q}) = \Phi_p(x) = \frac{x^p-1}{x-1}$이라 하자.

$x^p-1 = (x-1)f(x)$를 미분하면 $px^{p-1} = f(x) + (x-1) f'(x)$를 얻고, $x = \omega$를 대입하여 $f'(\omega) = \frac{p}{\omega (\omega - 1)}$을 얻는다. 

이제 Norm의 multiplicative 성질을 이용하고, 약간의 단순 계산을 하면, 결론적으로 $$N(f'(\omega)) = \frac{N(p)}{N(\omega) N(\omega - 1)} =  \frac{p^{p-1}}{1 \cdot p} = p^{p-2}$$를 얻는다. 이는 $\text{disc}(\omega) = \pm p^{p-2}$임을 의미한다. 비슷한 논의를 자연수 $m$에 대해서도 할 수 있다.

$\omega = e^{2\pi i / m}$이라 하고, $f(x) = \text{irr}(\omega, \mathbb{Q}) = \Phi_m(x)$라 하자.

이제 $x^m - 1 = f(x)g(x)$라 쓰고, 미분 후 $x = \omega$를 대입하면 $m = \omega f'(\omega)g(\omega)$를 얻는다.

Norm을 취하고 multiplicative 성질을 이용하면, $m^{\phi(m)} = \pm \text{disc}(\omega) N(\omega g(\omega))$를 얻는다.

그런데 $\omega g(\omega)$는 AI이므로, 그 norm은 정수임을 알 수 있다. 즉, $\text{disc}(\omega) | m^{\phi(m)}$. 이 정도 결과만 있어도 충분하다.

사실 여기서 홀수 소수 $p$에 대하여 $\mathbb{Q}(\zeta_p)$가 포함하는 quadratic field가 무엇인지를 바로 얻을 수 있다. 

discriminant의 제곱근을 생각하면, 이 값은 무조건 $\mathbb{Q}(\zeta_p)$에 속해야 한다. 이는 $\mathbb{Q}(\zeta_p)$가 splitting field이기 때문.

그러니 조금만 고민하면 $\mathbb{Q}(\sqrt{\pm p})$가 cyclotomic field의 subfield임을 확인할 수 있다.

단, $+$ 부호는 $p \equiv 1 \pmod{4}$일 때, $-$ 부호는 $p \equiv 3 \pmod{4}$일 때 얻어진다.

여기에 $\mathbb{Q}(\zeta_8)$이 $\sqrt{2}$와 $i$를 포함한다는 사실을 이용하면, 결국 우리는

• 모든 $m$에 대하여, $\mathbb{Q}(\sqrt{m})$은 cyclotomic field의 subfield다

라는 사실을 얻는다. 소인수분해를 한 다음, 대응되는 cyclotomic field의 composite을 생각하면 된다.

여기서 cyclotomic field의 composite은 cyclotomic field임을 이용하였다. 위 결과의 매우 강력한 강화는

• Kronecker–Weber Theorem : Finite Abelian Extension of $\mathbb{Q}$ is a subfield of cyclotomic field

Step 2 : Proof for Prime Power $m$

이제부터 $m = p^r$이라고 가정한다. $p$는 소수. 또한, $m = 2$인 경우는 자명하므로 생략한다.

보조정리 1 : $\text{disc}(1 - \omega) = \text{disc}(\omega)$가 성립한다.

이는 $\omega$의 conjugate이 $\{\alpha_i\}$라면, $1 - \omega$의 conjugate은 $\{1 - \alpha_i\}$이므로 자명하다.

보조정리 2 : $\prod_{1 \le k \le m, p \nmid k} (1 - \omega^k) = p$가 성립한다. $$\prod_{1 \le k \le m, p \nmid k} (x - \omega^k) = (x^{p^r}-1) / (x^{p^{r-1}} - 1) = 1 + x^{p^{r-1}} + \cdots + x^{p^{r-1}(p-1)}$$임은 매우 쉽게 보일 수 있으며, 이 식에 $x = 1$을 대입하면 원하는 결과를 얻는다. 증명 끝. 

이제 본 증명을 하자. $n = \phi(m) = p^{r-1}(p-1) = [K, \mathbb{Q}]$이라 하자. 

$1 - \omega$ 역시 degree $n$ over $\mathbb{Q}$이므로, $1, (1-\omega), \cdots , (1-\omega)^{n-1}$은 AI로 이루어진 $K$의 basis over $\mathbb{Q}$이다. 그러니, 각 $\alpha \in \mathcal{O}_K$에 대하여, $$ \alpha = \frac{1}{d} (m_0 + m_1(1 - \omega) + \cdots + m_{n-1} (1- \omega)^{n-1})$$이라 유일하게 쓸 수 있다. 물론 $d = \text{disc}(\omega)$이고 $m_i$들은 정수. 만약 $\mathcal{O}_K \neq \mathbb{Z}[\omega]$라면, 적당한 $\alpha$와 $i$가 있어 $d \nmid m_i$가 성립한다.

여기서 $d = \text{disc}(\omega)$는 앞선 결과에 의해 $p$의 거듭제곱이다. 이제 $\alpha$에 다음 작업을 걸어주자.

• $v_p(m_i)$가 최소인 $i$ 중 가장 작은 것을 $k$라고 하자. $v_p(m_k) < v_p(d)$임에 주목하자.
• $\alpha$를 $\alpha \cdot p^{v_p(d) - v_p(m_k) - 1}$로 교체한다. 여전히 $\alpha$는 AI.
• 이제 $\alpha$의 형태를 다시 보면, 결국 $$ \alpha = \frac{1}{p} (m'_0 + m'_1(1 - \omega) + \cdots + m'_{n-1} (1- \omega)^{n-1})$$이다. 그런데 $v_p(m'_0), \cdots v_p(m'_{k-1}) \ge 1$이므로, $\alpha$의 $(1-\omega)^0, \cdots (1-\omega)^{k-1}$ 부분은 전부 정수이다.
• 그러니 이 부분을 날려도 ($m'_0 = \cdots = m'_{k-1} = 0$으로 바꿔도) 여전히 $\alpha$는 AI. 
• 이제 우리의 최종 결론은 $\alpha$가 AI이고, $m'_k$는 $p$의 배수가 아니며, 각 $m'_i$는 정수이고, $$\alpha = \frac{1}{p} (m'_i (1-\omega)^k + \cdots + m'_{n-1}(1-\omega)^{n-1})$$

한편, 보조정리 2에서 $p / (1-\omega)^n$이 $\mathbb{Z}[\omega]$의 원소임을 얻는다. 그러니 $$m'_k/(1-\omega) + m'_{k+1} + \cdots + m'_{n-1}(1-\omega)^{n-k-2} = \alpha p / (1-\omega)^{k+1} \in  \mathcal{O}_K$$이다. 결과적으로는 $m'_k / (1-\omega)$가 AI. 그런데 norm을 생각하면 $1-\omega$의 norm은 $p$인데 $m'_k$의 norm은 $p$의 배수가 아니니 모순. 증명 끝.

Step 3 : Combining Prime Powers

$\text{gcd}(m_1, m_2) = 1$, $m = m_1m_2$이고, 증명하고자 하는 성질이 $m_1, m_2$에 대해 증명되었다면 $m$에 대해서도 성립함을 보이자.

우선 $\mathbb{Q}(\zeta_m)$이 $\mathbb{Q}(\zeta_{m_1})$과 $\mathbb{Q}(\zeta_{m_2})$의 composite임은 자명하다. 비슷하게, $\mathbb{Z}[\zeta_m]$이 $\mathbb{Z}[\zeta_{m_1}]$과 $\mathbb{Z}[\zeta_{m_2}]$의 composite임도 자명하다.

그러니 discriminant의 GCD 조건만 보면 되는데, Step 1에서 얻은 결과에 의해서 이는 자명하다. 그러니 composite의 ring of integers는 composite. ok.

$K$가 $n = [K : \mathbb{Q}]$인 NF라고 할 때, $\mathcal{O}_K$를 $K$에 속하면서 AI인 원소들의 집합이라고 하자. 이를 $K$의 ring of integers라고 한다.

우리의 첫 목표는 $\mathcal{O}_K$의 구조를 파악하는 것이다. 이를 위해서 free abelian group에 대한 이해가 필요하다. 

보조정리 : $\alpha$가 AN이면, 적당한 자연수 $m$이 존재하여 $m\alpha$가 AI이다. 증명은 쉬우니 넘어간다.

그러므로, $K$ over $\mathbb{Q}$에 대한 basis를 잡되, 각 원소가 전부 AI가 되도록, 즉 $\mathcal{O}_K$의 원소가 되도록 할 수 있다.

이제 $\{ \alpha_1, \cdots , \alpha_n\}$을 그 basis라고 하고, $$A = \mathbb{Z}\alpha_1 \oplus \cdots \oplus \mathbb{Z}\alpha_n$$이라고 정의하자. 이는 free abelian group of rank $n$이며, $A \subset \mathcal{O}_K$는 자명하다. 반대로, $d = \text{disc}(\alpha_1, \cdots , \alpha_n)$이라 할 때, 우리는 $$\mathcal{O}_K \subset \frac{1}{d} A$$임을 보일 수 있다. 정확하게 말하자면, $\alpha \in \mathcal{O}_K$라면 적당한 정수 $m_1, m_2, \cdots, m_n$이 존재하여 $$\alpha = \frac{1}{d} \sum_{i=1}^n m_i \alpha_i$$이고, 이때 $d|m_i^2$이 성립한다. 물론, 이런 $m_i$들이 유일함은 자명하다. 

증명의 아이디어를 보자. 우선 $\alpha = \sum_{i=1}^n x_i \alpha_i$인 $x_i \in \mathbb{Q}$를 잡는다. 이제 embedding $\sigma_1 , \cdots, \sigma_n$을 적용하면, $\sigma_j(\alpha) = \sum_{i=1}^n x_i \sigma_j(\alpha_i)$를 얻는다. 이제 Cramer's Rule을 적용하면, 각 $x_i^2$이 AI에 $d$를 나눈 형태임을 알 수 있다. 마무리는 쉽다.

첨언하자면 이인석 교수님의 대수학에서 Linear Algebra over $\mathbb{Z}$를 다룰 때 determinant/adjoint의 힘을 강조하는데, 여기서도 보인다.

이제 $\mathcal{O}_K$가 두 free abelian group of rank $n$ 사이에 끼어있으니, $\mathcal{O}_K$도 그렇다는 것을 알 수 있다.

정리 : $\mathcal{O}_K$ is a free abelian group of rank $n$

결국 $\mathcal{O}_K$가 basis over $\mathbb{Z}$를 갖는다는 것을 알 수 있다. 이는 $K$의 basis over $\mathbb{Q}$가 되기도 한다.

이를 number ring $\mathcal{O}_K$의 integral basis라고 부른다. 물론, 이는 유일하지 않다. 하지만, 두 integral basis는 같은 discriminant를 가짐을 보일 수 있다.

한쪽이 다른 쪽의 정수 계수 선형결합이 되어야 하므로, determinant를 생각하면 각 discriminant가 서로의 양수 배수여야 한다. 그

러니 discriminant가 같을 수 밖에 없으며, 이 값을 $\mathcal{O}_K$의 자체적인 값으로 이해해도 된다. 즉, $\text{disc}(\mathcal{O}_K)$라는 표현을 쓸 수 있다.  

다음 주제는, 두 NF $K, L$의 composite field $KL$의 ring of integers $\mathcal{O}_{KL}$을 보는 것이다.

$\{\alpha_1, \cdots , \alpha_m\}$이 $\mathcal{O}_K$의 integral basis, $\{\beta_1, \cdots , \beta_n\}$이 $\mathcal{O}_L$의 integral basis라 하자.

그러면 $\mathcal{O}_{KL}$이 $\mathcal{O}_K \mathcal{O}_L$을 포함하는 것은 자명하다. 반대방향이 문제다. 이때, $[KL : \mathbb{Q}] = mn$, $d = \text{gcd}(\text{disc}(\mathcal{O}_K), \text{disc}(\mathcal{O}_L))$이라면, $$\mathcal{O}_{KL} \subset \frac{1}{d} \mathcal{O}_K \mathcal{O}_L$$임을 증명할 수 있다. 특히 $d=1$이면 $\mathcal{O}_{KL} = \mathcal{O}_K \mathcal{O}_L$이 성립한다.

우선 $\alpha_i \beta_j$가 $\mathcal{O}_K \mathcal{O}_L$의 basis over $\mathbb{Z}$, $KL$의 basis over $\mathbb{Q}$임은 degree condition $[KL : \mathbb{Q}] = mn$에서 얻어진다. 그러므로, 각 $\alpha \in \mathcal{O}_{KL}$은 $$\alpha = \sum_{i, j} \frac{m_{i, j}}{r} \alpha_i \beta_j$$라고 쓸 수 있다. 단, $\text{gcd}(r, \text{gcd}(m_{i, j})) = 1$이라고 하자. 이제 목표를 보이기 위해서는 $r | d$임을 보이면 충분하고, 대칭성에서 $r| \text{disc}(\mathcal{O}_K)$만 보여도 된다. 각 $K$의 embedding $\sigma$를 $KL$의 embedding으로 확장하되, $L$을 고정하도록 하자. 이 역시 degree condition에 의해 가능한 것이다. 그러면 $$\sigma(\alpha) = \sum_{i, j} \frac{m_{i, j}}{r} \sigma(\alpha_i) \beta_j$$가 되고, 여기서 $$x_i = \sum_{j=1}^n \frac{m_{i, j}}{r} \beta_j$$라 하면 $$\sigma(\alpha) = \sum_{i=1}^m  x_i \sigma(\alpha_i)$$가 된다. 여기서 Cramer's Rule을 또 적용하면 $x_i^2$이 AI / discriminant 형태가 됨을 알 수 있다. 여기서 $\text{disc}(\mathcal{O}_K) x_i$는 AI임을 얻는다.

그러므로, 이 값은 정의상 $\mathcal{O}_L$에 속하고 $\beta_j$들의 정수 계수 선형결합으로 표현된다. 마무리는 쉽다.

마지막 주제는 integral basis의 표현이다. NF는 모두 $\mathbb{Q}(\alpha)$ 형태이니 (Primitive Element Theorem) integral basis 역시 모두 $\alpha$에 대한 식으로 표현할 수 있을 것이다. 이를 더욱 강화한 결과를 소개한다. 약간 Fundatemental Theorem of Finitely Generated Abelian Group 느낌이 난다.

정리 : $\alpha \in \mathcal{O}_K$고, $\text{deg}(\alpha, \mathbb{Q}) = n$이라 하자. 이때, $\mathcal{O}_K$의 integral basis $$1, \frac{f_1(\alpha)}{d_1}, \cdots , \frac{f_{n-1}(\alpha)}{d_{n-1}}$$이 존재한다. 단, $d_i \in \mathbb{Z}$이며 $d_1 | d_2 | \cdots | d_{n-1}$이고, $f_i$는 monic이며 $\mathbb{Z}[x]$에 속한다. 또한, $d_i$들은 유일하다.

이 결과로 quadratic field $\mathbb{Q}(\sqrt{m})$이나 pure cubic field $\mathbb{Q}(\sqrt[3]{m})$의 ring of integers의 integral basis를 구할 수 있다고 한다.

Step 1 : 기본 세팅 잡기

$d = \text{disc}(\mathcal{O}_K)$이라 하자. $\{1, \alpha, \cdots , \alpha^{n-1}\}$는 $K$의 basis over $\mathbb{Q}$다.

그러니, $\mathbb{O}_K$의 각 원소는 $1/d, \alpha/d, \cdots , \alpha^{n-1}/d$에 의해 generate 되는 free abelian group에 속한다.

특히, $F_k$를 $1/d, \cdots, \alpha^{k-1}/d$에 의해 generate 되는 free abelian group이라 하고, $R_k$를 $F_k$의 원소 중 AI인 것의 집합이라 하자.

$R_1 = \mathbb{Z}$이고, $\mathbb{R}_n = \mathcal{O}_K$임은 이제 자명하다. 목표는 $\mathbb{R_k}$의 integral basis를 귀납적으로 만들어가는 것이다.

Step 2 : 추가할 원소 잡기

$1, f_1(\alpha) / d_1, \cdots , f_{k-1}(\alpha) / d_{k-1}$이 $R_k$의 integral basis라고 가정하자. 

이제 canonical projection $\pi$를 생각하는데, 대충 $R_{k+1}$의 원소에서 $\alpha^k$ 항을 빼내는 것으로 생각하면 된다.

그런데 $\pi(R_{k+1})$은 자명히 $\alpha^k / d$가 generate 하는 cyclic group의 subgroup이므로, cyclic이다.

그러니, 적당한 $\beta \in R_{k+1}$이 있어 $\pi(\beta)$가 $\pi(R_{k+1})$을 생성하게 할 수 있다. 이제 $\beta$를 basis에 추가하면, $R_{k+1}$의 integral basis를 얻는다.

$R_{k+1}$의 원소가 있으면, $\pi$ 값이 0이 되도록 $\beta$를 적당히 빼주고, 남은 값을 $R_k$의 기존 basis로 표현하면 된다. 선형독립 성질 역시 자명하다. 

Step 3 : 각 성질 증명

이제 $\beta$가 어떤 형태를 가지고 있는지 보면 된다. 먼저 $f_{k-1}(\alpha) / d_{k-1}$이 AI이므로, $\alpha f_{k-1}(\alpha) / d_{k-1}$ 역시 AI가 된다. 이는 $\pi(R_{k+1})$에 $\alpha^k / d_{k-1}$이 포함된다는 의미고, $\pi(\beta) = \alpha^k / d_k$라고 쓰면 $d_{k-1} | d_k$라는 것이다. 이제 $\beta = f_k(\alpha) / d_k$이고, $f_k$가 monic이라고 쓸 수 있다. 결국 문제는 $f_k \in \mathbb{Z}[x]$가 성립하냐는 것이다. $f_k(\alpha) / d_{k-1}$이 $\beta$의 정수배이므로 AI이고, $\alpha f_{k-1}(\alpha) / d_{k-1}$ 역시 AI이므로, $$ \frac{f_k(\alpha) - \alpha f_{k-1}(\alpha)}{d_{k-1}} = \gamma$$ 역시 AI가 된다. $\gamma$는 $R_k$에 속하므로, $\text{deg}(g) < k$인 $g \in \mathbb{Z}[x]$가 있어 $\gamma = g(\alpha) / d_{k-1}$이라 쓸 수 있다. 이제 $f_k - xf_{k-1} = g$임을 쉽게 얻을 수 있고 $f$ 역시 $\mathbb{Z}[x]$의 원소임을 얻는다. 마지막으로 $d_i$의 유일성을 보여야 하는데, 이는 $m R_{i+1} \subset \mathbb{Z}[\alpha]$인 최소 $m$이 $d_i$와 같다는 것에서 보여진다.  

Marcus의 Number Fields를 읽는다. 딱 학부 수준에서 대수적 정수론 맛보기 좋은 책이라고 생각한다.

Chapter 1은 책 내용의 맛보기를 페르마의 마지막 정리를 통해 소개하는 내용이니 생략.

Chapter 7 이후부터는 복소해석에 대한 기초가 필요한 것 같아, 미래의 나에게 미룬다.

현대대수학 1, 2 정도의 사전지식을 가정한다. 본인은 프렐라이 + 이인석 교수님의 대수학 책을 어느 정도 읽은 상태다.

증명을 다 쓰고 싶지는 않고, 최대한 압축해서 쓰려고 한다. 일단 내가 읽으려고 쓰는 목적이 커서...

지금까지 읽은 간단한 후기는

• 이거 겁나 재밌다 ㅋㅋㅋ 벌써부터 되게 강력한 결과들이 많은데, 뒤에서는 훨씬 더 많아진다
• $\mathbb{Q}, \overline{\mathbb{Q}}, \mathbb{C}$ 위에서 노는 메리트가 굉장히 많다 : 일단 char 0인게 너무 편하다.
• Perfect Field, Separability, Primitive Element Theorem을 정말 마음 편하게 적용할 수 있다 
• 현대대수를 재밌게 복습/강화할 수 있는 좋은 공부가 되고 있는 것 같다
• Evan Chen의 Napkin은 먼저 흐름만 쓱 보고, Stein은 읽은 후 코드만 쓱 보면 딱 좋은 것 같다

이제부터 본문 시작인데, 먼저 현대대수 복습부터 빠르게 하자.

정의: $\alpha$가 적당한 $\mathbb{Q}[x]$의 원소의 근이라면, $\alpha$를 Algebraic Number라 한다.

정의: $\alpha$가 적당한 monic인 $\mathbb{Z}[x]$의 원소의 근이라면, $\alpha$를 Algebraic Integer라 한다.

정의: $\mathbb{C}$의 subfield이면서 $\mathbb{Q}$의 finite extension인 것을 Number Field라 한다.

이제부터 그냥 Algebraic Number를 AN, Algebraic Integer를 AI, Number Field를 NF라 하겠다.

일단 여기서 바로 얻을 수 있는 중요한 결과들이 있다. 모두 Gauss' Lemma로 증명이 된다.

• $\alpha$가 $\mathbb{Z}[x]$라 하고, $\text{irr}(\alpha, Q)$를 생각하면 이는 $\mathbb{Z}[x]$의 원소.
• $\alpha$가 AI면서 유리수라면 정수여야 한다.  

또한, 현대대수학에서 우리는 Cyclotomic Field에 대한 중요한 결과를 배웠다.

• $\omega = e^{2\pi i / m}$이라 하면 $\text{deg}(\omega, \mathbb{Q}) = \phi(m)$
• Cyclotomic Polynomial은 irreducible, 정수 계수 다항식
• 특히 $\mathbb{Q}(\omega)$ over $\mathbb{Q}$의 Galois group은 $\mathbb{Z}_m^{\times}$와 isomorphic

이제 대수적 정수론의 "진짜" 첫 결과를 보자. $\alpha \in \mathbb{C}$에 대하여 다음이 동치이다.

• 1. $\alpha$가 AI
• 2. additive group of $\mathbb{Z}[\alpha]$ is finitely generated
• 3. $\alpha$ is a member of some subring of $\mathbb{C}$ with a finitely generated additive group
• 4. $\alpha A \subset A$ for some finitely generated additive subgroup $A \subset \mathbb{C}$

증명을 스케치하자면, 먼저 1 => 2 => 3 => 4 방향은 자명하다. 4 => 1이 핵심이다. 이를 위해서는 $A$의 generating set $a_1, a_2, \cdots , a_n$을 잡고, $\alpha$를 곱하는 것을 정수 계수를 갖는 선형변환으로 생각하면 된다. 이러면 $\alpha$가 정수 항을 가지는 행렬의 eigenvalue임을 확인할 수 있고, 특성다항식을 생각하면 ok.

2, 3번 조건이 상당히 강력하다. 여기서 AI가 ring 구조를 가짐을 얻는다.

• $\alpha, \beta$가 AI면 additive group of $\mathbb{Z}[\alpha]$, $\mathbb{Z}[\beta]$가 finitely generated.
• 이들의 generating set을 가지고 additive group of $\mathbb{Z}[\alpha, \beta]$ 역시 finitely generated임을 안다.
• 그런데 $\alpha + \beta$, $\alpha \beta$가 모두 $\mathbb{Z}[\alpha, \beta]$에 속하므로, ok.

또한, algebraic integer를 계수로 갖는 monic polynomial의 근도 algebraic integer임을 얻을 수 있다. (이인석 교수님의 대수학 책의 "그 trick")

이제 우리가 볼 다음 대상은 Trace와 Norm이다. $K, L$이 NF고 $K \le L$이라 하자. $n = [L : K]$라 하고, $\sigma_1, \sigma_2, \cdots, \sigma_n$이 $K$를 fix하는 embedding $L \rightarrow \mathbb{C}$이라 하자. 이제 각 $\alpha \in L$에 대하여 Trace, Norm을 

• Trace : $T^L_K(\alpha) = \sum_{i=1}^n \sigma_i(\alpha)$,  Norm : $N^L_K(\alpha) = \prod_{i=1}^n \sigma_i(\alpha)$

라고 한다. 이 함수들이 linear/multiplicative임은 자명하다. 또한, 이 값들이 $K$에 속함도 익숙할 것이다.

또한, $\alpha$가 AI라면 Trace, Norm 모두가 AI임도 이제 AI가 ring임을 아니 쉽게 증명할 수 있다.

추가적으로, Trace/Norm은 transitivity를 갖는다. 즉, $T^L_K(T^M_L(\alpha)) = T^M_K(\alpha)$, $N^L_K(N^M_L(\alpha)) = N^M_K(\alpha)$이다. 물론 $K \le L \le M$.

이를 위한 증명은 특별한 아이디어를 쓰지 않으므로 (현대대수학에서 다 보이는 아이디어) 생략한다.

다음으로 볼 대상은 Discriminant. $K$가 NF고 $n = [K : \mathbb{Q}]$이라 하자. $\alpha_1, \alpha_2, \cdots , \alpha_n \in K$에 대하여, $\alpha_1, \alpha_2, \cdots , \alpha_n$의 discriminant를 $$\text{disc}(\alpha_1, \cdots , \alpha_n) = \text{det}([\sigma_i(\alpha_j)])^2$$라고 정의한다. 여기서 $\text{det}(A)^2 = \text{det}(AA^T)$임을 적용하면, $$\text{disc}(\alpha_1, \cdots , \alpha_n) = \text{det}([T(\alpha_i \alpha_j)])$$를 얻는다. 그러니, $\alpha_i$들이 전부 AI면 discriminant 역시 AI가 된다. 또한, 간단한 선형대수를 통해서 $\text{disc}$를 통해서 $\alpha_i$들이 linearly independent over $\mathbb{Q}$인지 확인할 수 있음을 보일 수 있다. Trace의 성질을 활용해주면 된다. 이러한 면에서 determinant와 유사한 점이 있다고 생각할 수 있겠다.

이제 $K = \mathbb{Q}(\alpha)$라 하고, $n = [K : \mathbb{Q}]$라 하자. 이때, $$\text{disc}(\alpha) = \text{disc}(1, \alpha, \cdots , \alpha^{n-1})$$이라고 정의한다. discriminant의 첫 정의를 생각하면 이는 Vandermonde 형태를 가진다. $\alpha_1, \cdots , \alpha_n$을 $\alpha$의 conjugate이라 하면, 결국 $$\text{disc}(\alpha) = \prod_{1 \le r < s \le n} (\alpha_r - \alpha_s)^2 = \pm N^K (f'(\alpha))$$를 얻는다. 여기서 $f = \text{irr}(\alpha, \mathbb{Q})$이다. 또한, $\pm$은 $n \equiv 0, 1 \pmod{4}$일 때 성립한다.

첫 등식은 Vandermonde에서 나오고, 두 번째 식은 $r$이 $f$의 근일 때 $f'(r)$의 식 형태에서 나온다. 당연하지만 $f$는 중근이 없다.

여기서는 간략하게 행렬의 characteristic polynomial을 계산하는 방법에 대해서 다룬다.

먼저 당연한 이야기부터. characteristic polynomial을 계산하면 행렬의 determinant 역시 계산할 수 있다.

$n \times n$ 행렬의 determinant를 계산하는데 걸리는 시간이 $\mathcal{O}(n^\omega)$라고 하자. 

현재 기술력으로는 $\omega \approx 2.373$ 정도임이 알려져 있다. (행렬 곱/행렬 역과 마찬가지)

그러니 기본적으로 기대할 수 있는 최적의 시간복잡도는 $\mathcal{O}(n^\omega)$이며, 실제로도 $\mathcal{O}(n^{\omega} \log n)$의 알고리즘이 존재한다.

관심이 있는 사람들은 krylov subspace와 Keller-Gehrig Algorithm을 찾아보면 된다. 난 모르겠다 ㅋㅋ

하지만 PS를 하는 입장에서나 실제로 계산을 하는 입장에서는, 일반적으로 행렬 연산들은 $\mathcal{O}(n^3)$으로 구현한다.

그러니 여기서는 목표를 $\mathcal{O}(n^3)$ 시간 안에 characteristic polynomial을 계산하는 것으로 하자.

또한, $\mathbb{F}_p$, $\mathbb{R}$, $\mathbb{C}$ 등 임의의 field에 대한 계산을 할 수 있도록 알고리즘을 생각해보도록 하자.

여기서 기본적으로 field의 크기는 크다고 가정을 하는데, field의 크기가 작은 경우에서도 아래의 내용이 적용된다. 약간의 머리를 더 쓰면 된다.

가장 쉬운 아이디어는 뭘까? 어쨌든 characteristic polynomial은 $n$차 다항식이니, $n$개의 점에서 다항식의 값을 각각 계산한 다음 Lagrange Interpolation을 덮어주면 된다. 다항식의 값을 한 번 계산하는 것은 쉽게 생각하면 determinant를 한 번 계산하는 것과 같으니, 총 $\mathcal{O}(n^4)$의 시간이 걸린다. 물론, interpolation은 간단하게 $\mathcal{O}(n^2)$에도 할 수 있으며 굳이 빡세게 하고 싶다면 $\mathcal{O}(n \log^2 n)$에도 된다. $n$을 하나 줄이는 것이 목표다.

어떻게 최적화를 할까? interpolation의 아이디어는 포기하기에는 너무 깔끔하다. 한 번 determinant를 계산하는데 $\mathcal{O}(n^2)$이 들도록 할 수는 없을까? 이를 위해서는 기존의 행렬과 similar 한 "예쁜 행렬"을 만들어주는 방법이 많이 사용된다. 가장 대표적인 예시는 역시 대각화. 행렬이 대각화가 된다면 그 자체로 characteristic polynomial의 계산은 끝이다. 하지만 대각화는 항상 가능한 것이 아니라는 것이 잘 알려져 있다. 또 다른 예시는 슈르 삼각화. 이 역시 가능하다면 그 자체로 끝난다. 이는 field가 algebraically closed field라면 (예를 들어, $\mathbb{C}$라면) 항상 가능하겠다. 하지만 우리가 다룰 대상은 훨씬 일반적이다. 이는 다르게 말하면 upper triangular보다 더 넓은 마음가짐으로 similar transformation 각도를 재야 한다는 뜻이다.

그래서 생각할 수 있는 형태는 Hessenberg Matrix다. 이는 결국 upper triangular인데 주대각선 바로 하나 아래의 대각선에도 nonzero element가 존재할 수 있는 형태의 행렬이다. 즉, $h_{i, j} = 0$ for all $i > j+1$를 만족하는 행렬이다. 이제 우리가 확인해야 하는 것은 두 가지다. 

첫 번째로, similar transformation을 통해서 Hessenberg 형태를 만들 수 있는 것이 보장되는가? 

두 번째로, Hessenberg 형태를 만들면 determinant의 계산이 $\mathcal{O}(n^2)$ 안에 되는가?

첫 번째부터 확인해보자. 우리는 Gaussian Elimination의 과정을 그대로 밟되, 목표를 Hessenberg 형태로 할 것이다.

첫 번째 column을 보자. 만약 $(2,1), (3,1), \cdots , (n,1)$에 있는 모든 원소가 $0$이라면, 다음 column으로 넘어간다.

이제 nonzero 원소가 있다고 하자. 그러면 Gaussian Elimination의 경우와 같이 $(2,1)$에 nonzero 원소를 하나 넣어줄 필요가 있다. $(k,1)$에 nonzero element가 있다고 하자. 그러면 우리가 해야하는 것은 $2$번째, $k$번째 행을 swap하는 것이다. 이는 두 원소를 swap 하는 permutation matrix를 행렬 앞에 곱하는 것과 같다. 우리는 항상 similar transformation을 해야 하므로, 같은 permutation matrix의 역을 행렬 뒤에 곱해야 한다. 이는 생각해보면 $2$번째, $k$번째 열을 swap하는 것과 같다. 이렇게 해도 $(2,1)$에는 결국 nonzero element가 온다. 이 과정을 손으로 써보면, Hessenberg 형태의 묘미를 느낄 수 있다. 

자, 이제 $(2,1)$의 nonzero element를 가지고 $(3,1), (4,1), \cdots ,(n,1)$의 원소를 전부 $0$으로 만들어야 한다.

이는 각 $k \ge 3$에 대하여 $k$번째 행에 $2$번째 행의 배수를 더하는 것과 같다.

이는 $LU$ 분해를 생각해보면, 일종의 lower triangular matrix를 앞에 곱하는 것과 같다. 

역시 우리는 similar transformation을 적용해야 하므로, 이 행렬의 역을 뒤에 곱해야 한다.

이는 식을 써보면 $2$번째 열에 $k$번째 열의 배수를 더하는 것과 같다. 정확히 어떤 계수를 넣어야 하는지는 직접 계산해보자.

이를 반복하면, $(3,1), \cdots , (n,1)$을 다 날릴 수 있다. 이제 이를 각 column에 대하여 순서대로 반복하자.

두 번째를 확인하자. Hessenberg 행렬에서 $\lambda I$ 형태의 행렬을 빼도 여전히 Hessenberg 행렬이다.

그러니, Hessenberg 행렬의 determinant를 $\mathcal{O}(n^2)$에 구할 수 있으면 된다.

그런데 이건 단순하게 Gaussian Elimination을 하면 된다. 실제로 행렬을 그려보고 생각하면 자명하다.

그러니 이 과정을 모두 합치면 $\mathcal{O}(n^3)$에 characteristic polynomial을 계산할 수 있다.

$f : [0, 1] \rightarrow \mathbb{R}$이 연속함수라면, $\displaystyle \lim_{n \to \infty} \frac{1}{\phi(n)} \sum_{1 \le k \le n, \text{gcd}(k, n)=1} f \left(\frac{k}{n}\right) = \int_0^1 f(x) dx$임을 보여라.

$f : \mathbb{R} \rightarrow \mathbb{R}$은 임의의 실수 수열 $\{u_n\}$에 대하여, 다음을 만족한다.

조건: $\sum_{n=1}^\infty u_n$이 수렴하면 $\sum_{n=1}^\infty f(u_n)$이 수렴한다.

이때, 적당한 $\epsilon > 0$과 $\alpha \in \mathbb{R}$이 존재하여, $\forall x \in (-\epsilon, \epsilon)$, $f(x) = \alpha x$임을 보여라.

책 소개 링크 // 책 링크

이번에 이 책을 읽게 된 계기는 크게 3가지다.

• 수학 공부를 좀 하고 싶었다. 1학년 동안 수강한 수학 과목 중에서 내용이 새로웠던 과목이 선형대수학 2 하나여서 아쉬운 점이 많았다. 2학기에는 ICPC/Project Euler를 하면서 프로그래밍을 하는 시간이 더 많았고, 종강 직전에는 교양 과제를 마무리하느라 고생하다보니 수학 공부가 하고 싶어졌다. 이런 책이 있다는 사실은 오래 전부터 알고 있었고, 책 제본까지 이미 해두었던 상황이었다. 마침 선형대수학 2도 수강했으니, 이제 이 책을 읽을 수 있지 않을까 싶기도 했다.
• 선형대수학에 대한 새로운 시각/직관을 얻고 싶었다. 책 소개 링크에 들어가서 저자의 글을 보면 대강 무슨 뜻인지 느낌을 알 수 있다. “correct abstract viewpoint of linear algebra”가 어떤 관점인지를 알고 싶었다. 선형대수학 2의 교재인 "선형대수와 군"에서도 철학이나 직관을 강조했고, 교재를 읽으면서 이 점이 굉장히 매력적이라고 생각했다. 이번에 읽은 책도 "correct viewpoint"를 잡기 위한 책이라고 소개가 되어 있으니 더 읽고 싶어졌다. 저자는 순수수학으로 진로를 잡을 게 아니면 굳이 필요가 없다고 적긴 했는데, 아무튼 내가 재밌으면 된 거 아닐까 싶어서 그냥 읽었다.
• 현대대수학 입문 준비. 다음 1학기에 가능하면 현대대수학 수업을 들을 예정이다. 책의 내용 중 일부가 현대대수학 수업 내용과 겹친다. 다음 학기 수업을 위한 좋은 준비가 될 것 같아서 이 책을 읽게 되었다. 이인석 교수님의 "대수학" 책도 사긴 샀는데, 시간 문제상 방학 도중 읽을 것 같지는 않다. 그래도 현대대수학 언어는 많이 배워간 것 같아서 좋다.