개요
격자(lattice)는 기하학과 군론에서 사용되는 수학적 개념으로, 실수 좌표 공간 $\mathbb{R}^n$에서 정의되는 무한한 점들의 집합이다. 격자는 다음과 같은 세 가지 속성을 갖는다.
- 격자 내 임의의 두 점의 좌표별 덧셈 또는 뺄셈은 다시 다른 격자점을 생성한다.
- 격자점들은 모두 일정한 최소 거리 이상으로 서로 분리되어 있다.
- 공간의 모든 점은 어떤 격자점으로부터 일정한 최대 거리 이내에 위치한다.
정의와 형식적 표현
격자의 가장 단순한 예는 정수 격자 $\mathbb{Z}^n$이다. 이는 평면 $\mathbb{R}^2$에서 두 좌표가 모두 정수인 점 $(a, b)$들의 집합으로 구성되며, 고차원으로 자연스럽게 일반화된다.
더 형식적으로, $\mathbb{R}^n$의 격자 $\Lambda$는 다음과 같이 표현된다.
$$ \Lambda = \left{ \sum_{i=1}^{n} a_i v_i ;\middle|; a_i \in \mathbb{Z} \right} $$
여기서 ${v_1, v_2, \ldots, v_n}$은 $\mathbb{R}^n$의 기저(basis)이다. 즉, 격자는 기저 벡터들의 정수 계수 선형 결합으로 생성되는 점들의 집합이다. 서로 다른 기저가 동일한 격자를 생성할 수 있으나, 기저 벡터들의 그람 행렬(Gram matrix)의 행렬식의 절댓값은 격자에 의해 고유하게 결정되며, 이를 격자의 공부피(covolume)라고 부른다. 공부피가 1인 격자는 유니모듈러 격자(unimodular lattice)라고 한다.
추상적인 관점에서 격자는 벡터 공간 $\mathbb{R}^n$을 선형 생성하는 차원 $n$의 자유 아벨 군(free abelian group)으로 설명할 수 있다.
대칭과 분류
격자는 $n$개 방향에서 이산 병진 대칭의 대칭군을 갖는다. 군으로서 (기하학적 구조를 제외하고) 격자는 유한 생성 아벨 군이며, 따라서 $\mathbb{Z}^n$과 동형이다.
2차원 평면의 격자는 결정학적 제한 정리(crystallographic restriction theorem)에 따라 다섯 가지 유형으로 분류된다. 구체적으로는 정사각형 격자, 직사각형 격자, 마름모 격자(중심 직사각형 격자), 육각형 격자(정삼각형 격자), 빗면 격자(평행사변형 격자)가 있다.
3차원 공간의 격자는 14가지 유형으로 분류되며, 이를 브라베 격자(Bravais lattice)라고 부른다.
주요 예시
- $\mathbb{Z}^n$: 정수 격자
- E8 격자: $\mathbb{R}^8$에서 정의되는 유명한 격자로, 같은 이름의 리 대수(Lie algebra)와 관련이 있다.
- 리치 격자(Leech lattice): $\mathbb{R}^{24}$에서 정의되는 격자이다.
- 가우스 정수 $\mathbb{Z}[i] = \mathbb{Z} + i\mathbb{Z}$: 복소 평면 $\mathbb{C} = \mathbb{C}^1$에서 격자를 형성한다.
응용 분야
격자는 순수 수학에서 리 대수(Lie algebra), 수론(number theory), 군론(group theory) 등 다양한 분야에 응용된다. 응용 수학에서는 부호 이론(coding theory), 침투 이론(percolation theory)에서 나타나며, 컴퓨터 과학에서는 여러 격자 문제의 추정되는 계산적 난해성 때문에 암호학(격자 기반 암호)에 활용된다.
물리 과학에서는 재료 과학 및 고체 물리학에서 격자가 결정 구조의 틀, 즉 결정 내 원자 또는 분자의 규칙적인 배열 위치와 일치하는 3차원 점 배열을 지칭하는 데 사용된다. 또한 물리학에서는 격자 모형(lattice model)이 연구되며, 종종 계산 물리학 기법이 동원된다.
계산 격자 문제
격자 문제는 컴퓨터 과학에서 중요한 응용을 가진다. 렌스트라-렌스트라-로바즈 격자 기저 감소 알고리즘(LLL 알고리즘)은 여러 공개 키 암호 방식의 암호 해독에 사용되었으며, 많은 격자 기반 암호 방식은 특정 격자 문제(예: 최단 벡터 문제 SVP, 최근접 벡터 문제 CVP)가 계산적으로 어렵다는 가정에 기반하여 안전성이 입증된다. 이는 양자 내성 암호(post-quantum cryptography)의 주요 이론적 기반이기도 하다.
리 군에서의 일반화
보다 일반적으로, 리 군(Lie group) $G$의 격자 $\Gamma$는 이산 부분군으로서, $G$에서 상속된 하르 측도(Haar measure)에 대해 몫군 $G/\Gamma$가 유한 측도를 가질 때 정의된다. $G/\Gamma$가 콤팩트하면 해당 격자는 균일 또는 코콤팩트(cocompact)하다고 하며, 그렇지 않으면 비균일하다고 한다. 2차원 실수 특수선형군 $\mathrm{SL}(2,\mathbb{R})$의 모듈러 군은 비균일 격자의 대표적인 예이다.
관련 개념
- 격자의 원시 원소(primitive element)는 격자 내 다른 원소의 양의 정수배로 표현되지 않는 원소를 말한다.
- 쌍대 격자(dual lattice)는 내적 공간인 벡터 공간에서 정의되며, 모든 격자 원소와의 내적이 주어진 환이 되는 벡터들의 집합으로 주어진다.
참고 문헌
- Gruber, Peter M.; Lekkerkerker, Cornelis G. (1987). Geometry of Numbers, 2nd ed. North-Holland.
- Conway, John Horton; Sloane, Neil J. A. (1999). Sphere Packings, Lattices and Groups, 3rd ed. Springer-Verlag.
- Nguyen, Phong; Stern, Jacques (2001). "The Two Faces of Lattices in Cryptology." Cryptography and Lattices, LNCS 2146, pp. 146–180.
- Regev, Oded (2005). "On lattices, learning with errors, random linear codes, and cryptography." STOC '05, pp. 84–93.
