힐베르트 17번째 문제

이론 전산학과 관련해서 무척 훌륭한 (그리고 읽기도 무척 빡센 ㅋㅋ) 블로그인 Windows on Theory에 힐베르트 17번째 문제에 관한 포스팅[1]이 올라왔다.

본인은 힐베르트 문제들을 그닥 열심히 본게 아니라서 사실 무슨 문제인지 몰랐는데-_-, 위 글에 설명을 엄청 잘 해놨다. ㅎㅎ 위 블로그에 든 예를 들어보자.

다음 다항식이 주어진다고 하자.

\displaystyle P(x) = x^4 - 24x^3 +185x^2 - 484x + 409

이 funciton의 최소값을 찾는 문제는 정상적인 교육과정을 이수한-_- 고교생이면 누구나 다 하는 계산이다. 미분해서 영을 찾아서 확인해보면 간단하게 (사실 나는 귀찮아서 계산 안해봤음 ㅋ) P(2) =5에서 local minimum이자 global minimum임을 확인할 수 있다. 근데 이 다항식을 이렇게 바꿔보면 어떨까?

\displaystyle P(x) = 5 + (x-2)^2 + (x-2)^2 (x-10)^2

장난하나-_- 이렇게 바꾸면 애시당초 미분하고 자시고 할 껀덕지도 없다. 다른 예를 들어볼까? 2변수 polynomial

\displaystyle M(x,y) = (x^4 y^2 + x^2 y^4 +1)/3 -x^2 y^2

은 앞의 항이 산술평균이고 뒤의 항이 기하평균이므로 항상 non-negative이다. 이건 다음과 같이 변형된다.

\displaystyle M(x,y) = \tfrac{x^4 y^2 (x^2 + y^2 -2)^2}{3(x^2 + y^2 )^2} + \tfrac{x^2 y^4 (x^2 + y^2 -2)^2}{3(x^2 + y^2 )^2} + \tfrac{(x^2 + y^2 -2)^2}{3(x^2 + y^2 )^2} + \tfrac{(x^2 - y^2 )^2}{3(x^2 + y^2 )^2}

뭐야 이거-_- 이런 짓들을 Polynomial SOS (sum of square)라고 부르는 모양.

근데 문제는 non-negative값만 나오는 polynomial은 항상 이런 짓이 가능할까? 하고 물으면 대답이 곤란해진다. ㅋ

힐베르트 17번째 문제는 뭐냐하면 항상 non-negative값을 취하는 multivariable polynomial f : \mathbb{R}^n \to \mathbb{R}이 주어져 있을 때, 이 polynomial을 rational square들의 합으로 항상 표현가능한가 하는 문제이다. 이 문제는 1927년 Emil Artin에 의해 그렇다는 것이 증명되었다고 한다. 헐.. 어떤 method를 써야 모든 polynomial이 그렇다는 걸 보일 수 있는지 상상도 안 가는구만. ㅋ 놀랍게도 1984년에는 Charles Delzell에 의해 이런 변형법을 만드는 알고리즘[2]도 만든 모양이다.

위 Windows on Theory의 포스트는 이러한 알고리즘의 complexity가 어느정도인지 가늠하는 내용 같은데, 원체 모르는 용어가 많이 나와서 이해는 잘 안된다 -_- 본인도 잘 모르는 분야라서… 켁. 흥미있으신 분들은 읽어보시라.

 


2014.10.6
방금 고딩 문제를 보다가

n은 2 이상의 짝수이고 x^n +x(x-1)^2으로 나눈 몫을 g(x)라 할 때, 모든 실수에 대해 g(x) >0임을 보여라

는 문제가 나와 있던데, 문득 힐베르트 17번째 문제를 이용해보고 싶어졌다. 과연 될까 싶었다.

먼저 조립제법으로 g=x^{n-2}+ 2x^{n-3} + 3x^{n-4} +\cdots +(n-2)x +(n-1)임을 보인다. n=2일 때는 자명하고, 2보다 클 때는

\displaystyle \begin{aligned} g & = x^{n-4}(x+1)^2 + 2x^{n-6}(x+1)^2 +3x^{n-8}(x+1)^2 + \\ & \qquad \cdots + \frac{n-4}{2}x^2 (x+1)^2 + \frac{n-2}{2}(x+1)^2 + \frac{n}{2}\end{aligned}

된다! 근데 딸린 문제를 보니 출제자의 의도가 아닌 듯-_-

 


2016.9.18
Proofs, beliefs and algorithms through the lens of Sum of Squares in Windows on Theory

 


[1] Fun and Games with Sums of Squares in Windows on Theory
[2] Delzell, C.N. (1984). “A continuous, constructive solution to Hilbert’s 17th problem”. Inventiones Mathematicae. 76: 365–384. doi:10.1007/BF01388465

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중