Hình học lồi và rời rạc

Một tổ hợp lồi trong $\operatorname{conv}(S)$ thoạt nhìn có thể dùng tùy ý nhiều điểm của $S$, nhưng trong $\mathbb{R}^d$ bất kỳ $d + 2$ điểm trở lên đều phụ thuộc afin. Quan hệ tuyến tính đó cho phép khử từng điểm một mà vẫn giữ mọi trọng số không âm cho tới khi còn tối đa $d + 1$ điểm (một đơn hình). Định lý Helly — rằng một họ hữu hạn các tập lồi trong $\mathbb{R}^d$ có điểm chung mỗi khi mọi bộ $d + 1$ tập trong họ có điểm chung — là hệ quả song hành trực tiếp của chặn số chiều này.

Viết $x = \sum_{i=1}^{k} \lambda_i x_i$ với $x_i \in S$, $\lambda_i > 0$, và $\sum_{i=1}^{k} \lambda_i = 1$, được chọn sao cho số hạng tử $k$ là nhỏ nhất. Ta chứng minh $k \le d + 1$.

Giả sử phản chứng rằng $k \ge d + 2$. Khi đó $k - 1 \ge d + 1$ vectơ hiệu $x_2 - x_1, x_3 - x_1, \ldots, x_k - x_1$ trong $\mathbb{R}^d$ phụ thuộc tuyến tính, nên tồn tại các vô hướng $\mu_2, \ldots, \mu_k$ không đồng thời bằng không sao cho $\sum_{i=2}^{k} \mu_i (x_i - x_1) = 0$. Đặt $\mu_1 = -\sum_{i=2}^{k} \mu_i$ ta được $\sum_{i=1}^{k} \mu_i x_i = 0$ và $\sum_{i=1}^{k} \mu_i = 0$ với ít nhất một $\mu_i > 0$.

Với mọi số thực $t$ ta có $x = \sum_{i=1}^{k} (\lambda_i - t \mu_i) x_i$ với tổng các hệ số bằng $1$. Chọn $t = \min_{\mu_i > 0} (\lambda_i / \mu_i) > 0$; khi đó mọi hệ số mới $\lambda_i - t \mu_i$ đều không âm và ít nhất một hệ số bằng $0$, biểu diễn $x$ thành tổ hợp lồi của nhiều nhất $k - 1$ điểm thuộc $S$, mâu thuẫn với tính nhỏ nhất của $k$.

Đây là nguyên lý chuồng bồ câu liên tục của lý thuyết số: một khi vật thể lồi đối xứng lớn hơn $2^d$ ô cơ bản của dàn, co nó lại theo tỉ lệ $2$ vẫn để lại thể tích lớn hơn một ô, buộc hai điểm của vật thể đã co phải chênh nhau một vectơ dàn khác không — rồi tính đối xứng cộng với tính lồi kéo vectơ dàn đó vào lại bên trong $K$.

Xét vật thể co một nửa $\frac{1}{2} K = \{\, x / 2 : x \in K \,\}$. Co giãn trong không gian $d$ chiều nhân thể tích với $2^{-d}$, nên giả thiết $\operatorname{vol}(K) > 2^d \det(\Lambda)$ trở thành $\operatorname{vol}(\frac{1}{2} K) > \det(\Lambda)$.

Gọi $F$ là hình hộp cơ bản của $\Lambda$, sao cho $\mathbb{R}^d = \bigsqcup_{v \in \Lambda} (F + v)$ và $\operatorname{vol}(F) = \det(\Lambda)$. Cắt $\frac{1}{2} K$ thành các mảnh $A_v = (\frac{1}{2} K) \cap (F + v)$ rồi tịnh tiến từng mảnh về lại trong $F$ qua $B_v = A_v - v \subseteq F$. Vì tổng thể tích các $B_v$ bằng $\operatorname{vol}(\frac{1}{2} K) > \operatorname{vol}(F)$, nên các tập $B_v$ không thể rời nhau từng đôi một (nguyên lý Blichfeldt).

Chọn hai vectơ dàn phân biệt $u \neq v$ trong $\Lambda$ sao cho $B_u \cap B_v \neq \emptyset$. Khi đó tồn tại hai điểm phân biệt $p, q \in \frac{1}{2} K$ thỏa mãn $p - u = q - v$, suy ra $p - q = u - v \in \Lambda \setminus \{0\}$. Vì $p, q \in \frac{1}{2} K$, ta có $2p, 2q \in K$; tính đối xứng tâm của $K$ cho $-2q \in K$, và tính lồi của $K$ đặt trung điểm $\frac{1}{2}(2p) + \frac{1}{2}(-2q) = p - q$ vào trong $K$. Vậy $p - q$ là điểm dàn khác không nằm trong $K \cap (\Lambda \setminus \{0\})$.