이번 포스팅에서는 다음 정리를 증명한다.
Theorem 3: Lévy-Steinitz Theorem (Lévy 1905, Steinitz 1913, Gross 1917)
\(\mathbb{R}^n\)의 벡터들로 이루어진 series \(\sum v_n\)에 대하여, 도달 가능한 극한값들의 집합 \(V\)는 공집합이거나, 적당한 \(\mathbb{R}^n\)의 subspace \(W\)과 \(v \in \mathbb{R}^n\)에 대해 \(v+W\)꼴로 표현된다. 즉, \(V\)는 공집합이거나 \(\mathbb{R}^n\)의 subspace를 적당히 translate한 형태이다.
먼저, Theorem 3을 증명하기 위해 자주 사용할 정리를 하나 소개한다.
Theorem 4: Polygonal Confinement Theorem
임의의 자연수 \(n\)에 대하여, 적당한 상수 \(C_n\)이 존재하여 다음이 성립한다.
\(v_1, v_2, \cdots v_M\)이 임의의 \(1 \le i \le M\)에 대하여 \(|v_i| \le 1\)을 만족하고, \(v_1+v_2+ \cdots v_M = \vec{0}\)을 만족하는 \(\mathbb{R}^n\)의 벡터들이라면, \( (2, 3, \cdots M) \)의 적당한 permutation \(P\)가 존재하여 $$ \left| v_1 + \sum_{i=2}^j v_{P(i)} \right| \le C_n $$이 모든 \(2 \le j \le M\)에 대해 성립한다. 또한, \(C_1=1\)과 \(C_n = \sqrt{4C^2_{n-1}+1} \) (단, \(n \ge 2\))으로 잡아도 괜찮다.
Proof of Theorem 4: \(n\)에 대한 귀납법으로 문제를 해결하자. 우선 \(n=1\)부터 처리하자.
\(n=1\)인 경우에는, \(v_1, v_2, \cdots v_M\)은 모두 절댓값이 \(1\) 이하인 실수다.
만약 \(v_1 > 0\)이라면, 부분합이 \(0\) 미만이 되는 시점까지 \(v_i \le 0\)인 \(v_i\)들을 더해준다.
부분합이 음수가 되면, 다시 부분합이 \(0\) 초과가 되는 시점까지 \(v_i \ge 0\)인 \(v_i\)들을 더해준다.
모든 실수들의 합이 \(0\)이기 때문에 이 방법을 통해서 모든 벡터를 한 번씩 나열할 수 있다.
또한, 각 \(v_i\)들은 절댓값이 \(1\) 이하이므로, 부분합은 절대 절댓값이 \(1\) 초과가 될 수 없다.
\(v_1 \le 0\)인 경우도 마찬가지 알고리즘으로 permutation을 찾을 수 있다. 그러므로 \(C_1=1\)을 잡아도 ok.
이제 귀납적으로 생각해보자. \(n-1\)에 대한 명제에서 \(n\)에 대한 명제로 넘어가보자.
벡터의 개수가 유한하므로, \(v_1\)을 포함하는 벡터들의 합 중 가장 길이가 긴 것을 생각하자.
이를 \(L=v_1+u_1+u_2+ \cdots + u_s\)라 하자. 단, \(\{u_1, u_2, \cdots u_s \} \subset \{v_2, v_3, \cdots v_M\} \)이다.
\(L\)에서 등장하지 않은 벡터들을 \(w_1, w_2, \cdots w_t\)라 하자. 즉, \(L+w_1+w_2+ \cdots w_t = \vec{0} \)이다.
Claim 1: 각 \(1 \le i \le s\)에 대해서, \(u_i \cdot L \ge 0\)이 성립한다.
Claim 2: \(v_1 \cdot L \ge 0\)이 성립한다.
Claim 3: 각 \(1 \le i \le t\)에 대해서, \(w_i \cdot L \le 0\)이 성립한다.
이 Claim들의 증명은 아주 간단하므로 sketch만 한다. 모두 귀류법이고, 모순은 다음과 같이 발생한다.
Claim 1: \(u_i\) 빼면 길이가 더 길어진다.
Claim 2: \(v_1+u_1+u_2+\cdots +u_s\)보다 \(v_1+w_1 +w_2 +\cdots + w_t\)가 더 길어진다.
Claim 3: \(w_i\) 추가하면 길이가 더 길어진다.
본격적으로 귀납 가정을 쓸 준비를 하자. \(L^\perp = \{v \in \mathbb{R}^n | v \cdot L = 0\} \)를 생각하자.
\(L = \vec{0}\)이면 결과는 자명하므로 이 경우는 넘어가고, \(L \neq \vec{0}\)인 경우를 보자.
그러면 \(L^\perp\)는 \(n-1\)차원 벡터공간이고, 여기서 귀납 가정을 사용할 각을 생각할 수 있다.
\(\mathbb{R}^n\)의 벡터 \(v\)에 대하여, \(v' = v - \frac{v \cdot L}{|L|^2} L \)을 \(v\)의 \(L^\perp\) 성분이라고 하자.
그러면 정의에 의해 \(v'_1 + u'_1 + u'_2 + \cdots u'_s = w'_1 + w'_2 + \cdots w'_t = \vec{0}\)이다.
게다가, \(v'_1, u'_1, u'_2, \cdots u'_s, w'_1, w'_2, \cdots w'_t\)는 모두 \(n-1\)차원 벡터공간 \(L^\perp\)에 속하는 벡터들이다.
그러므로, 차원이 \(n-1\)인 경우에 대한 귀납 가정을 쓰기 위해 필요한 조건을 모두 갖추고 있다! (why?)
귀납 가정에 의하여, \((1,2, \cdots s)\)의 적당한 permutation \(Q\)가 있어 $$ \left| v'_1 + \sum_{i=1}^j u'_{Q(i)} \right| \le C_{n-1} $$이 모든 \(1 \le j \le s\)에 대해 성립한다.
귀납 가정에 의하여, \((2, 3, \cdots t)\)의 적당한 permutation \(R\)가 있어 $$ \left| w'_1 + \sum_{i=2}^j w'_{R(i)} \right| \le C_{n-1} $$이 모든 \(2 \le j \le t\)에 대해 성립한다. \(R(1)=1\)이라 하자.
이제 남은 것은 이를 합치는 것 뿐이다. \(v_1, u_1, u_2, \cdots u_s\)는 모두 \(v_1, u_{Q(1)}, u_{Q(2)}, \cdots u_{Q(s)} \) 순서로 등장하게 하고, \(w_1, w_2, \cdots w_t\)는 모두 \(w_{R(1)}, w_{R(2)}, \cdots w_{R(t)}\) 순서로 등장하게 하자.
이제 \(L^\perp\)에 어떤 부분합을 사영시키면 그 길이는 최대 \(2C_{n-1}\)임이 보장된다.
문제는 \(L\) 방향으로 사영시킨 길이를 bound시키는 건데, 여기서 Claim 1, 2, 3이 역할을 한다.
모든 벡터들의 합이 \(\vec{0}\)이므로, \(L\)에 해당하는 성분의 합도 \(0\)이다. 즉, 앞서 \(n=1\)에 대해 Theorem 4를 증명한 것과 동일한 방법으로 \(u_i\)들과 \(w_i\)들을 적당히 번갈아가며 배치해, \(L\)에 어떤 부분합을 사영시키면 그 길이가 최대 \(1\)이 되도록 보장할 수 있다.
여기서 \(n=1\) 증명에서 '0 이상' 역할을 \(v_1\)과 \(u_i\)들이, '0 이하' 역할을 \(w_i\)들이 한다.
다시 강조하지만 \(u_i\)들 사이의 순서는 앞서 말했듯이 유지한다. \(w_i\)들 사이의 순서도 마찬가지로 유지한다
이렇게 해서 permutation을 잡아주면 임의의 부분합의 길이는 최대 \(\sqrt{4C^2_{n-1}+1}\)임을 알 수 있다. 증명 끝.
이제 Polygonal Confinement Theorem을 활용해서, 다양한 보조정리/정리들을 이끌어내보자.
Lemma 5: \(v_1, v_2, \cdots v_m \in \mathbb{R}^n\)은 \(|v_1+v_2+ \cdots v_m| \le \epsilon\)과 \(|v_i| \le \epsilon \) (\(1 \le i \le m \))를 만족한다.
그러면, \((1,2, \cdots m)\)의 permutation \(P\)가 존재하여, $$ \left| v_{P(1)}+v_{P(2)} + \cdots v_{P(j)} \right| \le \epsilon (C_n + 1) $$가 모든 \(1 \le j \le m\)에 대해서 성립한다.
Proof of Lemma 5: \(v_{m+1} = -v_1 - v_2 - \cdots - v_m\)을 잡자. 이제 \(v_1 + v_2+ \cdots v_{m+1} = \vec{0}\)이다.
또한, 각 벡터 \(v_1, v_2, \cdots v_{m+1}\)의 크기는 최대 \(\epsilon\)이다. \(\frac{1}{\epsilon} v_1, \frac{1}{\epsilon} v_2, \cdots \frac{1}{\epsilon} v_{m+1}\)에 대해서 Theorem 4를 적용해보자.
적당한 permutation이 존재하여 \(v_{P(i)}\)들의 임의의 부분합의 크기가 \(\epsilon C_n\)이하이도록 할 수 있다.
이제 여기서 \(v_{m+1}\)을 제거해야 하는데, 이미 \(\left|v_{m+1}\right| \le \epsilon\)을 알고 있으니 삼각부등식으로 처리할 수 있다.
삼각부등식을 적용하면, 결국 임의의 부분합의 크기가 \(\epsilon (C_n+1)\) 이하가 되도록 할 수 있음을 확인할 수 있다.
Theorem 6: Rearrangement Theorem
\(\{v_i\}\)는 \(\mathbb{R}^n\)에 속한 벡터들의 수열이다. 이 수열의 부분합을 \(s_1, s_2, \cdots \)라 하자.
만약 \(S \in \mathbb{R}^n\)으로 수렴하는 \(\{s_i\}\)의 부분수열이 존재하고, \(|v_n|\)이 \(n \rightarrow \infty\)에서 \(0\)으로 수렴한다면, 적당한 \(\{v_i\}\)의 rearrangement가 존재하여 rearrange된 수열의 합이 \(S\)로 수렴한다.
Proof of Theorem 6: \(s_{m_1}, s_{m_2}, \cdots , s_{m_k}, \cdots \)가 \(S\)로 수렴한다고 하자.
핵심은 각 \(i=1, 2, \cdots\)에 대하여 \(v_{m_i+1} , v_{m_i+2}, \cdots v_{m_{i+1}}\)를 하나의 패키지로 보는 것이다.
각 패키지에 속한 벡터들을 Lemma 5를 활용해 적당히 rearrange 하여, 각 \(m_k < T <m_{k+1}\)에 대해 \(s_T\)와 \(s_{m_k}\) 사이의 차이가 충분히 작도록 만드는 것이 핵심 아이디어다.
\(\delta_k = |s_{m_k}-S| \)라 하면, \(\delta_k \rightarrow 0\)이다. 한편, $$ \left| \sum_{i=m_k+1}^{m_{k+1}-1} v_i \right| = \left| s_{m_{k+1}} - s_{m_k} - v_{m_{k+1}} \right| \le \delta_{k+1} + \delta_k + |v_{m_{k+1}}| $$이고, \( \epsilon_k = \text{max}(\delta_{k+1}+\delta_k, \text{sup}_{i \ge m_k} |v_i|) \)라 정의하면 \(\epsilon_k \rightarrow 0\)이고 앞선 관찰에 의해 $$ \left| \sum_{i=m_k+1}^{m_{k+1}-1} v_i \right| < 2 \epsilon_k $$이 성립한다.
이제, Lemma 5에 의해 \((m_k+1, m_k+2, \cdots m_{k+1}-1)\)의 permutation \(P_k\)가 존재하여, $$ \left| \sum_{i=m_k+1}^r v_{P_k(i)} \right| \le 2\epsilon_k (C_n+1) $$가 모든 \(m_k+1 \le r \le m_{k+1}-1\)에 대해 성립한다.
각 패키지를 저렇게 rearrange했다고 가정하자. \(m_k < T <m_{k+1}\)라고 하면, \(|s_T-S| \le \delta_k + 2\epsilon_k (C_n+1) \)가 성립함을 삼각부등식으로 쉽게 확인할 수 있다. 또한, 이를 통해 rearrange된 수열은 그 합이 \(S\)로 수렴하게 됨을 확인할 수 있다.
Lemma 7: \(v_1, v_2, \cdots , v_m\)은 모두 \(\mathbb{R}^n\)의 벡터들이고, \(w=\sum_{i=1}^m v_i\)이다. \(t\)는 \(0<t<1\)을 만족하는 실수이며, \(|v_i| \le \epsilon\)가 모든 \(1 \le i \le m\)에 대하여 성립한다고 한다. 이때, 다음 둘 중 적어도 하나가 성립한다.
1. \(|v_1 - tw| \le \epsilon \sqrt{C^2_{n-1}+1} \)
2. \((2,3, \cdots , m)\)의 적당한 permutation \(P\)과 \(2 \le r \le m\)이 존재하여, $$ \left| v_1 + \sum_{i=2}^r v_{P(i)} - tw \right| \le \epsilon \sqrt{C^2_{n-1}+1} $$
Proof of Lemma 7: \(w = \vec{0}\)인 경우는 자명하므로, \(w \neq \vec{0}\)을 가정하자.
\(n\)에 대한 귀납법으로 보이자. (Theorem 4의 증명 느낌이 많이 나는 증명이다.)
우선 \(n=1\)부터 보자. 일반성을 잃지 않고, \(w>0\)을 가정한다.
\(v_1+v_2+ \cdots v_i > tw\)가 성립하는 최소의 \(i\)를 \(s\)라 하자. (\(i=m\)인 경우에 성립하니 최소의 \(i\)도 존재한다.)
그러면 \(v_1+v_2+ \cdots + v_{s-1} \le tw\)이므로, \(|v_1+v_2+ \cdots v_s - tw| \le \epsilon \)이 성립한다.
\(w^\perp\)를 생각하자. \(v'\)를 \(v - \frac{w \cdot v}{|w|^2} w\)라 정의하면, \(v'_1 + v'_2 + \cdots + v'_m = \vec{0}\)이다.
한편, \(|v_i| \le \epsilon\)이므로 \(|v'_i| \le \epsilon\)도 성립하고, Theorem 4에 의해 적당한 \((2,3, \cdots m)\)의 permutation \(P\)가 존재하여 $$ \left|v'_1 + \sum_{i=2}^j v'_{P(i)} \right| \le \epsilon C_{n-1} $$가 모든 \(2 \le j \le m\)에 대해 성립한다.
또한, \( \sum_{i=1}^m \frac{v_{P(i)} \cdot w}{|w|} = |w| \)가 성립하므로, \(n=1\)인 경우를 생각하면 적당한 \(r\)이 있어 $$ \left| \sum_{i=1}^r \frac{v_{P(i)} \cdot w}{|w|} - t|w| \right| \le \epsilon$$이 성립한다. 여기서 \(P(1)=1\)이며, \(\frac{v_i \cdot w}{|w|} \le |v_i| \le \epsilon\)임에 주목하자.
두 부등식은 각각 \(w\)와 수직한 성분, \(w\)와 평행한 성분에 대한 부등식을 보여준다.
두 부등식을 합치면 \( \left| v_1 + \sum_{i=2}^r v_{P(i)} - tw \right| \le \epsilon \sqrt{C^2_{n-1}+1} \)을 바로 얻을 수 있다. 증명 끝.
이제 모든 준비가 끝났다.
Theorem 3: Lévy-Steinitz Theorem (Lévy 1905, Steinitz 1913, Gross 1917)
\(\mathbb{R}^n\)의 벡터들로 이루어진 series \(\sum v_n\)에 대하여, 도달 가능한 극한값들의 집합 \(V\)는 공집합이거나, 적당한 \(\mathbb{R}^n\)의 subspace \(W\)과 \(v \in \mathbb{R}^n\)에 대해 \(v+W\)꼴로 표현된다. 즉, \(V\)는 공집합이거나 \(\mathbb{R}^n\)의 subspace를 적당히 translate한 형태이다.
Proof of Theorem 3: 기본 밑밥부터 깔아놓자. \(V\)가 공집합이 아니라고 가정하고, \(v \in V\)를 하나 가져온 후, \(v_1\)을 \(v_1- v\)로 교체하자. 그러면 \(0 \in V\)라고 가정할 수 있으며, 이제 \(V\)가 subspace임을 보이기만 하면 충분하다. 이를 위해서는 \(s_1, s_2 \in V \implies s_1+s_2 \in V\)를 보이고, \(s_1 \in V, t \in \mathbb{R} \implies ts_1 \in V\)를 보여야 한다.
Step 1. \(s_1, s_2 \in V \implies s_1+s_2 \in V\)를 보이자.
\(0\)으로 수렴하는 양의 실수로 이루어진 수열 \(\{\epsilon_m\}\)을 잡자.
\(s_1\)으로 수렴하는 rearrangement가 존재하므로, 유한집합 \( I_1\)이 있어 \(1 \in I_1\)과 \(|\sum_{i \in I_1} v_i - s_1 | < \epsilon_1 \)을 만족한다.
\(0\)으로 수렴하는 rearrangement가 존재하므로, 유한집합 \(J_1\)이 있어 \(I_1 \subseteq J_1\)과 \(|\sum_{i \in J_1} v_j| < \epsilon_1\)을 만족한다.
\(s_2\)으로 수렴하는 rearrangement가 존재하므로, 유한집합 \(K_1\)이 있어 \(J_1 \subseteq K_1\)과 \(|\sum_{i \in K_1} v_j - s_2| < \epsilon_1\)을 만족한다.
\(s_1\)으로 수렴하는 rearrangement가 존재하므로, 유한집합 \( I_2\)이 있어 \(K_1 \in I_2\)과 \(|\sum_{i \in I_2} v_i - s_1 | < \epsilon_2 \)을 만족한다.
이를 반복해주면, 결국 $$ \{1,2, \cdots , m-1\} \subset K_{m-1} \subset I_m \subset J_m \subset K_m $$ $$\left |\sum_{i \in I_m} v_i - s_1 \right| < \epsilon_m \text{, } \left|\sum_{i \in J_m} v_i \right| < \epsilon_m \text{, } \left|\sum_{i \in K_m} v_i - s_2 \right| < \epsilon_m$$
이제 다음 순서로 벡터들을 배치한다.
1. 먼저, \(I_1\)에 속한 벡터들을 배치한다.
2. 그 뒤에, \(J_1 \cap I^C_1\)에 속한 벡터들을 배치한다.
3. 그 뒤에, \(K_1 \cap J^C_1\)에 속한 벡터들을 배치한다.
4. 그 뒤에, \(I_2 \cap K^C_1\)에 속한 벡터들을 배치한다.
5. 이를 계속해서 반복한다.
이렇게 벡터들을 배치하면, 하나의 rearrangement가 된다는 사실은 자명하다. 이 permutation을 \(P\)라 하자.
이제 \(i_m=|I_m|\), \(j_m=|J_m|\), \(k_m=|K_m|\)이라 하면 $$\left |\sum_{i=1}^{i_m} v_{P(i)} - s_1 \right| < \epsilon_m \text{, } \left|\sum_{i=1}^{j_m} v_{P(i)} \right| < \epsilon_m \text{, } \left|\sum_{i=1}^{k_m} v_{P(i)} - s_2 \right| < \epsilon_m$$임을 바로 확인할 수 있다.
삼각부등식을 사용해주면, $$ \left| \sum_{i=1}^{i_m} v_{P(i)} + \sum_{i=j_m+1}^{k_m} v_{P(i)} - (s_1+s_2) \right| < 3\epsilon_m $$이 성립함을 확인할 수 있다. 이제 Rearrangement Theorem을 사용할 각을 재자.
여기서 \(v_{P(j_m+1)}, v_{P(j_m+2)}, \cdots v_{P(k_m)}\)와 \(v_{P(i_m+1)}, v_{P(i_m+2)} , \cdots v_{P(j_m)} \)을 통째로 자리바꿈하자.
우선 현재 벡터들의 배치는 여전히 하나의 rearrangement이다.
또한, 이 최종 수열의 부분합 수열을 생각하면 \(s_1+s_2\)로 수렴하는 부분수열이 존재한다.
그러므로, Rearrangement Theorem에 의해 \(s_1+s_2 \in V\)임을 확인할 수 있다. Step 1 끝.
Step 2: \(s_1 \in V, t \in \mathbb{R} \implies ts_1 \in V\)를 보이자.
'수학 > 해석학' 카테고리의 다른 글
| Variation of Riemann Sum / Convergence Preserving Map (0) | 2020.05.22 |
|---|---|
| Generalization of Riemann Sum (0) | 2019.05.19 |
| Rearrangements: Series in R^n (#1) (0) | 2018.12.07 |