Các kiểm tra quang phổ bao gồm việc so sánh độ dài của một vectơ ngắn nhất trong một mạng liên kết với một trình tạo đồng dư tuyến tính với số nhân $a$ và mô đun $m$ đến độ dài tối đa có thể của một vectơ ngắn nhất trong bất kỳ mạng nào có cùng kích thước.
Đặc biệt là con số bằng cấp của bài kiểm tra quang phổ $d$ bao gồm
$$
\frac{\nu_d}{\gamma_d^{1/2}m^{1/d}}\,,
$$
ở đâu $\nu_d$ là $L_2$ định mức của vectơ ngắn nhất của mạng được tạo bởi các hàng
$$
\begin{pmatrix}
m&0&0&\dots&0\
a&1&0&\dấu chấm&0\
a^2&0&1&\dots&0\
&&\dấu chấm&\
a^{d-1}&0&0&\dots&1
\end{pmatrix},
$$
và $\gamma_d$ Là Hằng số Hermite cho kích thước $d$, hoặc một xấp xỉ của nó. Vì yếu tố quyết định của mạng tinh thể này là $m$, thuật ngữ $\gamma_d^{1/2}m^{1/d}$ là một giới hạn trên chặt chẽ cho vectơ ngắn nhất cho một mạng có kích thước $d$. (Lưu ý: con số bằng khen nếu bằng cấp $d$ thường được định nghĩa là mức tối thiểu của tất cả các điểm từ $2$ lên đến $d$; Tôi đang bỏ qua điều đó ở đây để đơn giản).
Tính trung bình chính xác cho điểm số này có vẻ khá khó khăn. Tuy nhiên, chúng ta có thể nới lỏng vấn đề một chút và giả sử rằng các mạng ở dạng trên có thể được mô hình hóa như các mạng ngẫu nhiên, trong trường hợp đó chúng ta có thể sử dụng kinh nghiệm Gaussian và ước tính giá trị mong đợi của một vectơ ngắn nhất theo thứ nguyên $d$ như
$$
\left(\frac{\pi^{d/2}}{\Gamma(1+d/2)}\right)^{-1/d} m^{1/d}\,,
$$
từ đó chúng ta có thể đạt được điểm kiểm tra quang phổ trung bình cho thứ nguyên $d$ như
$$
\frac{ \left(\frac{\pi^{d/2}}{\Gamma(1+d/2)}\right)^{-1/d} }{\gamma_d^{1/2}} \,.
$$
Dưới đây là các xấp xỉ tương ứng cho kích thước $2$ đến $8$, trong đó hằng số Hermite được biết chính xác. Hãy lưu ý rằng chúng tôi đang phạm phải ở đây ít nhất hai tội lỗi:
- Xử lý các mạng có cấu trúc khá là các mạng được lấy mẫu ngẫu nhiên;
- Sử dụng các xấp xỉ tiệm cận ở các kích thước khá thấp, có thể không quá chính xác.
| $d$ |
$\mathbf{E}\left[\frac{\nu_d}{\gamma_d^{1/2}m^{1/d}}\right]$ |
| 2 |
0.525 |
| 3 |
0.552 |
| 4 |
0.564 |
| 5 |
0.583 |
| 6 |
0.589 |
| 7 |
0.595 |
| 8 |
0.593 |
Thật kỳ lạ, điểm số được xác định bởi Knuth (Tập 2, §3.3.4),
$$
\mu_d = \frac{\pi^{d/2}\nu_d^d}{(d/2)! m}\,,
$$
đang so sánh cấu trúc mạng của LCG với giá trị trung bình dự kiến này, nhưng với một tỷ lệ khác. Theo Knuth, $\mu_d \ge 1$ là một điểm tốt, nghĩa là mạng của LCG hoạt động giống như một mạng ngẫu nhiên.
