민코프스키 정리
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
민코프스키 정리는 격자, 볼록집합, 원점에 대한 대칭 조건을 만족하는 집합에 대해, 특정 부피 조건을 만족하면 격자가 집합 내에 격자점을 갖는다는 정리이다. 이 정리는 수론, 특히 수체의 유수와 관련된 민코프스키 상계, 라그랑주 네 제곱수 정리, 페르마의 두 제곱수 합 정리 등의 증명에 활용된다. 또한 격자 암호학과 수론에서 최단 벡터의 길이에 대한 상한을 제공하며, LLL 기저 축소 알고리즘과 같은 계산 문제와도 관련된다.
더 읽어볼만한 페이지
- 헤르만 민코프스키 - 민코프스키 거리
민코프스키 거리는 n차원 공간에서 두 점 사이의 거리를 정의하는 일반화된 방법으로, p값에 따라 맨해튼 거리, 유클리드 거리, 체비셰프 거리 등을 포함하며, 기계 학습에서 데이터 유사성 비교에 활용된다. - 헤르만 민코프스키 - 민코프스키 물음표 함수
민코프스키 물음표 함수는 헤르만 민코프스키가 정의한 함수로, 실수를 연분수와 이진수 표현 사이의 관계로 변환하며, 유리수를 이진 유리수로, 이차 무리수를 비-이진 유리수로 매핑하고, 프랙탈 모양의 그래프와 자기 유사성을 보이는 특이 연속 함수이다. - 볼록 해석 - 옌센 부등식
옌센 부등식은 볼록 함수 f에 대해 f의 기댓값은 f의 인수의 기댓값에 적용된 함수 값보다 크거나 같다는 부등식으로, 산술-기하 평균 부등식을 포함한 여러 부등식 유도에 사용되며 다양한 분야에 응용된다. - 볼록 해석 - 볼록 함수
볼록 함수는 실수 벡터 공간의 볼록 집합에서 정의되고 그래프 상의 두 점을 연결한 선분이 항상 그래프 위에 있거나 접하는 특징을 가지며 다양한 수학적 성질과 여러 분야에 응용되는 함수이다. - 수론 정리 - 페르마의 마지막 정리
페르마의 마지막 정리는 3 이상의 정수 n에 대해 xⁿ + yⁿ = zⁿ을 만족하는 양의 정수 x, y, z는 존재하지 않는다는 정리이며, 앤드루 와일스가 모듈러성 정리를 이용하여 1995년에 증명했다. - 수론 정리 - 라그랑주 네 제곱수 정리
라그랑주 네 제곱수 정리는 모든 양의 정수를 네 개의 정수 제곱수의 합으로 나타낼 수 있다는 정리이다.
민코프스키 정리 |
---|
2. 정의
격자 과 볼록집합 이 주어졌고, (즉, 는 원점에 대하여 대칭)라고 하자. '''민코프스키 정리'''에 따르면, 만약
인 경우, 민코프스키 정리는 다음과 같이 증명할 수 있다.[1]
:
이라면 이다. 즉, 는 적어도 하나의 격자점을 포함한다.[6]
''L''영어이 격자이고, 실수 벡터 공간에서 행렬식 d(''L'')영어을 갖는다고 하자. ''S''영어가 원점에 대해 대칭인 의 볼록 집합이라고 할 때, ''S''영어의 부피가 보다 엄격하게 크면, ''S''영어는 원점 이외에 적어도 하나의 격자점을 포함해야 한다. 집합 ''S''영어가 대칭이므로, 원점 0과 ()인 점 쌍을 포함하여 적어도 세 개의 격자점을 포함하게 된다.[6]
3. 증명
함수 를 생각하자. 이 함수는 평면을 2x2 크기의 정사각형으로 자른 후 겹쳐 쌓는 것으로 생각할 수 있다. 이렇게 겹쳐진 집합 의 면적은 4보다 작거나 같다. 만약 가 단사 함수라면, 의 각 부분들이 겹치지 않게 쌓여 의 면적이 의 면적과 같아져 4보다 커진다. 이는 모순이므로 는 단사 함수가 아니다. 따라서 를 만족하는 서로 다른 두 점 가 존재한다.
의 정의에 의해 를 만족하는 정수 , (둘 다 0은 아님)가 존재한다. 즉, 두 점의 좌표는 짝수만큼 차이난다. 가 원점에 대해 대칭이므로 도 에 속한다. 가 볼록 집합이므로 과 를 잇는 선분은 내부에 존재하며, 특히 이 선분의 중간점 는 에 속한다. 이 점 는 정수 점이고 원점이 아니므로, 는 0이 아닌 정수 점을 포함한다.
이 증명에서 사용된 논증은 체적이 보다 큰 임의의 집합이 격자 벡터에 의해 서로 다른 두 점을 포함한다는 블리흐펠트 정리의 특별한 경우이다.[1] 또한, 항이 격자 의 공체적임을 보여준다.
일반적인 격자의 경우, 모든 전체 랭크 격자는 어떤 선형 변환 에 대해 으로 쓸 수 있다. 원점에 대한 볼록성과 대칭성은 선형 변환에 의해 보존되며, 의 공체적은 이고 물체의 체적은 만큼 적용되므로, 에 대한 민코프스키 정리를 증명하는 것으로 충분하다.
3. 1. 블리흐펠트 정리
블리흐펠트 정리는 체적이 보다 큰 볼록 집합은 을 법으로 서로 합동인 두 점을 갖는다는 내용이다.[7] 즉, 다음을 만족하는 를 고를 수 있다.
:
증명 과정은 다음과 같다.
의 기저 을 택하고, 다음을 이 기저에 대한 의 기본 영역이라고 하자.
:
그러면 다음이 성립한다.
:
이제, 에 대해 다음을 대응시킨다.
:
는 '''R''''' n''에서 로의 사상이며, 다음이 성립한다.
:
게다가 는 평행 이동의 접합으로 나타낼 수 있으므로, 가 상에서 단사 함수이면 가 성립한다. 그러나 의 상은 에 포함되므로 다음이 성립한다.
:
따라서 는 상에서 단사 함수가 아니므로, 다음을 만족하는 점 를 택할 수 있다.
:
이므로, 다음이 성립한다.
:
3. 2. 민코프스키 정리 증명
Blichfeldt's theorem|블리흐펠트 정리영어를 이용하여 민코프스키 정리를 증명할 수 있다.[7] 증명 과정은 다음과 같다.
먼저, 벡터 집합 S에 대해 T를 다음과 같이 정의한다.
:
S의 부피가 보다 크므로, T의 부피는 다음과 같이 표현된다.
:
따라서 블리흐펠트 정리에 의해 다음 조건을 만족하는 두 점 를 찾을 수 있다.
:
이제, , 라고 하면, 이다. S는 원점에 대해 대칭이므로, 도 성립한다. S는 볼록 집합이므로, 다음이 성립한다.
:
또한, 다음이 성립한다.
:
따라서 S는 원점과 다른 L 위의 점 를 갖는다.
의 특정 경우에 대한 증명은 다음과 같다.[1]
다음과 같은 함수 f를 정의한다.
:
이 함수는 평면을 2x2 크기의 정사각형들로 자른 다음, 이 정사각형들을 서로 겹쳐 쌓는 것으로 생각할 수 있다. 이렇게 겹쳐진 집합은 2x2 정사각형 안에 포함되므로, 의 면적은 4보다 작거나 같다. 만약 함수 f가 단사 함수라고 가정하면, S의 각 부분들이 겹치지 않고 쌓이게 된다. 함수 f는 국소적으로 면적을 보존하는 성질을 가지므로, 의 면적은 S의 면적과 같아져서 4보다 크게 된다. 이는 모순이므로, f는 단사 함수가 아니다. 결과적으로, 다음 조건을 만족하는 서로 다른 두 점 가 존재한다.
:
함수 f의 정의에 따라, 다음을 만족하는 정수 , (둘 다 0은 아님)가 존재한다.
:
즉, 두 점의 좌표는 각각 짝수인 정수만큼 차이가 난다. S가 원점에 대해 대칭이므로, 도 S에 속한다. S가 볼록 집합이므로, 과 를 잇는 선분은 S 내부에 존재하며, 특히 이 선분의 중간 지점은 S 내부에 위치한다. 따라서,
:
는 S에 속하는 점이다. 이 점 는 정수 점이고, 와 가 모두 0이 아니므로 원점이 아니다. 결론적으로, S는 0이 아닌 정수 점을 포함한다.
4. 예시
정수 격자 는 모든 점이 정수 계수를 가지는 가장 간단한 격자의 예이며, 그 행렬식은 1이다. 인 경우, 이 정리는 유클리드 평면에서 원점에 대해 대칭이고 면적이 4보다 큰 볼록 도형은 원점 외에 적어도 하나의 격자점을 포함한다는 것을 의미한다. 면적 경계는 sharp하다. 만약 가 꼭짓점 을 갖는 정사각형의 내부라면, 는 대칭적이고 볼록하며 면적은 4이지만, 그것이 포함하는 유일한 격자점은 원점이다. 이 예시는 정리의 경계가 sharp하다는 것을 보여주며, 모든 차원 의 hypercube로 일반화된다.[6]
5. 응용
민코프스키 정리는 수체의 유수에 대한 민코프스키 상계를 증명하여 수체의 유수가 항상 유한함을 보인다.[6] 또한, 라그랑주 네 제곱수 정리와 페르마의 두 제곱수 합 정리 증명에도 응용된다.[8]
민코프스키 정리는 정수를 이차 형식으로 나타내는 문제에도 응용된다.
5. 1. 최단 벡터 문제
민코프스키 정리는 최단 비영 벡터의 길이에 대한 상한을 제공한다. 이 결과는 격자 암호학과 수론에 응용된다.'''정리(최단 벡터에 대한 민코프스키 경계):''' 을 격자라고 할 때, 을 만족하는 가 존재한다. 특히, 와 노름 간의 표준 비교를 통해, 이다.
이 정리에서 보장하는 짧은 격자 벡터를 찾는 것은 일반적으로 어려운 계산 문제이다. 민코프스키 경계에 의해 보장되는 인수 내에서 벡터를 찾는 것은 민코프스키 벡터 문제(MVP)라고 하며, 쌍대 격자의 전이 특성을 사용하여 근사 SVP가 이 문제로 축소됨이 알려져 있다.[3] 이 계산 문제는 때때로 에르미트SVP라고도 불린다.[3]
LLL 기저 축소 알고리즘은 최단 벡터에 대한 민코프스키 경계의 약하지만 효율적인 알고리즘 버전으로 볼 수 있다.[3]
5. 2. 수론적 응용
민코프스키 정리는 수체의 유수(class number)에 대한 민코프스키 상계(Minkowski bound) 증명에 사용되며, 이를 통해 수체의 유수가 항상 유한함을 보일 수 있다.[6] 또한, 라그랑주 네 제곱수 정리 증명에도 활용된다.민코프스키 정리에 따르면, '''R'''''n'' 위의 격자 ''L''에 대해, ''d''(''L'')을 ''L''에 대응하는 행렬의 행렬식이라 할 때, '''R'''''n'' 내에서 원점에 대해 대칭이고 부피가 보다 큰 볼록 집합은 내부에 원점 외의 ''L'' 위의 점을 포함한다.[6] 특히, 부피가 2''n''보다 큰 원점 대칭 볼록 집합은 반드시 원점 외의 정수점을 갖는다.
이러한 민코프스키 정리로부터 유도되는 일차 형식에 관한 정리는 다음과 같다.
:
를 ''n'' =''r'' +2''s'' 개의 일차 형식이라 하자. 이 중 ''l''1, ''l''2, ..., ''l''''r'' 는 실수 계수를 가지며, ''l'' ''r'' +''j'' 와 ''l'' ''r'' +''s'' +''j'' ( ''j'' = 1, 2, ..., ''s'' )는 서로 켤레 복소수이다. 또한 계수 행렬식 Δ ≠ 0 이다.
이때, 실수 ''k''1, ''k''2, ..., ''k''''r'' +''s'' 에 대해,
:
를 만족하면,
:
가 되는 정수 ''x''1, ''x''2, ..., ''x''''n'' 이 존재한다.
또한 실수 ''k''1, ''k''2, ..., ''k''''r'' +''s'' 에 대해,
:
를 만족한다면,
:
가 되는 정수 ''x''1, ''x''2, ..., ''x''''n'' 이 존재한다.
5. 2. 1. 페르마의 두 제곱수 합 정리
페르마의 두 제곱수 합 정리에서 어려운 부분은 최단 벡터에 대한 민코프스키 정리를 사용하여 증명할 수 있다.'''정리:''' 인 모든 소수는 두 제곱수의 합으로 쓸 수 있다.[6]
일 때, 가 소수 에 대한 이차 잉여인 것은 일 경우뿐이다(오일러 기준). 따라서 에서 의 제곱근이 존재한다. 그 중 하나를 선택하고 에서 그 대표자를 라고 하자. 벡터 로 정의된 격자 을 고려하고, 를 관련 행렬로 나타낸다. 이 격자의 행렬식은 이므로, 민코프스키 경계에 따르면 인 가 존재한다.
이고 정수 를 정의한다. 민코프스키 경계에 따르면 이고, 간단한 모듈러 산술은 임을 보여주므로, 임을 결론 내린다.
또한, 격자 관점은 페르마의 두 제곱수 합 정리에 대한 계산 효율적인 접근 방식을 제공한다. 증명에서 사용된 격자 에서 노름이 미만인 0이 아닌 벡터를 찾는 것은 를 두 제곱수의 합으로 분해하는 것을 의미한다. 이러한 벡터는 LLL-알고리즘을 사용하여 효율적으로 찾을 수 있다. 가 -LLL 감소 기저인 경우, 라는 속성에 의해, 이다. 따라서 로 LLL-격자 기저 감소 알고리즘을 실행하면 를 제곱수의 합으로 분해할 수 있다. 의 모든 벡터는 노름 제곱이 의 배수이므로, 이 경우 LLL-알고리즘으로 찾은 벡터는 실제로 최단 벡터이다.
를 형태의 소수라고 하면, 가 되는 를 잡을 수 있다 (''p''를 법으로 하는 위수 4의 잉여류에서 숫자를 하나 선택). 를 만족하는 점 전체는 를 기저로 하는 격자 ''L''과 일치하며, 가 성립한다. 원점을 중심으로 하는 반지름 의 열린 원반은 면적 의, 원점에 대해 대칭인 볼록 집합이므로 민코프스키 정리에 의해 원점과 다른 ''L''의 격자점 를 포함한다. 이므로 이다. 한편 는 원점이 아니고, 원점으로부터의 거리는 보다 작으므로
6. 계산 복잡도
민코프스키 정리 또는 밀접하게 관련된 블리흐펠트 정리가 보장하는 점을 찾는 복잡성은 TFNP 탐색 문제의 관점에서 연구되어 왔다. 특히, 민코프스키 정리의 증명에서 도출되는 따름정리인 블리흐펠트 정리의 계산적 유사성은 PPP-완전임이 알려져 있다.[4] 또한 민코프스키 정리의 계산적 유사성이 PPP 클래스에 속하며 PPP-완전일 것이라고 추측되었다.[5]
7. 역사
헤르만 민코프스키가 1896년에 증명하였다.[10]
참조
[1]
서적
The Geometry of Numbers
Mathematical Association of America, Washington, DC
[2]
서적
Symmetric Bilinear Forms
http://dx.doi.org/10[...]
1973
[3]
서적
The LLL Algorithm
Springer Berlin Heidelberg
[4]
웹사이트
PPP-Completeness with Connections to Cryptography
https://eprint.iacr.[...]
2018-08-15
[5]
간행물
Reductions in PPP
https://www.scienced[...]
2019-05-01
[6]
문서
[7]
문서
[8]
문서
[9]
문서
[10]
문서
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com