เดอะ การทดสอบสเปกตรัม ประกอบด้วยการเปรียบเทียบความยาวของเวกเตอร์ที่สั้นที่สุดในแลตทิซที่สัมพันธ์กับ เครื่องกำเนิดความสอดคล้องเชิงเส้น ด้วยตัวคูณ $a$ และโมดูลัส $m$ ถึงความยาวสูงสุดที่เป็นไปได้ของเวกเตอร์ที่สั้นที่สุดในแลตทิซใดๆ ที่มีมิติเดียวกัน
โดยเฉพาะอย่างยิ่งการทดสอบสเปกตรัมของตัวเลขของระดับ $d$ ประกอบด้วย
$$
\frac{\nu_d}{\gamma_d^{1/2}m^{1/d}}\,,
$$
ที่ไหน $\nu_d$ คือ $L_2$ บรรทัดฐานของเวกเตอร์ที่สั้นที่สุดของโครงตาข่ายที่สร้างโดยแถว
$$
\begin{patrix}
ม&0&0&\จุด&0\
ก&1&0&\จุด&0\
ก^2&0&1&\จุด&0\
&&\จุด&\
ก^{d-1}&0&0&\จุด&1
\end{pmatrix},
$$
และ $\gamma_d$ เป็น ค่าคงที่ของ Hermite สำหรับมิติ $d$หรือการประมาณของมัน เนื่องจากดีเทอร์มิแนนต์ของแลตทิซนี้คือ $m$,ระยะ $\gamma_d^{1/2}m^{1/d}$ เป็นขอบเขตบนที่แน่นสำหรับเวกเตอร์ที่สั้นที่สุดสำหรับโครงตาข่ายของมิติ $d$. (หมายเหตุ ร่างทรงบุญหากปริญญา $d$ มักจะถูกกำหนดให้เป็นขั้นต่ำของคะแนนทั้งหมดจาก $2$ จนถึง $d$; ฉันไม่สนใจที่นี่เพื่อความเรียบง่าย)
การคำนวณค่าเฉลี่ยที่แน่นอนสำหรับคะแนนนี้ค่อนข้างยาก อย่างไรก็ตาม เราสามารถผ่อนคลายปัญหาเล็กน้อยและแสร้งทำเป็นว่า lattices ของแบบฟอร์มด้านบนสามารถจำลองเป็น lattices แบบสุ่ม ซึ่งในกรณีนี้เราสามารถใช้ ฮิวริสติกแบบเกาส์ และประมาณค่าที่คาดหวังของเวกเตอร์ที่สั้นที่สุดในมิติ $d$ เช่น
$$
\left(\frac{\pi^{d/2}}{\Gamma(1+d/2)}\right)^{-1/d} m^{1/d}\,,
$$
ซึ่งเราสามารถได้รับคะแนนการทดสอบสเปกตรัมเฉลี่ยสำหรับมิติ $d$ เช่น
$$
\frac{ \left(\frac{\pi^{d/2}}{\Gamma(1+d/2)}\right)^{-1/d} }{\gamma_d^{1/2}} \,.
$$
ด้านล่างนี้เป็นค่าประมาณตามลำดับสำหรับขนาด $2$ ถึง $8$ซึ่งเป็นที่ทราบแน่ชัดว่าค่าคงที่เฮอร์ไมต์ โปรดทราบว่าเรากำลังทำบาปอย่างน้อยสองประการที่นี่:
- การปฏิบัติต่อโครงร่างที่มีโครงสร้างอย่างยุติธรรมเป็นโครงร่างสุ่มตัวอย่าง
- การใช้การประมาณแบบซีมโทติคในขนาดที่ค่อนข้างต่ำ ซึ่งอาจไม่ถูกต้องนัก
$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 |
คะแนนที่กำหนดโดย Knuth (เล่ม 2, §3.3.4),
$$
\mu_d = \frac{\pi^{d/2}\nu_d^d}{(d/2)! ม}\,,
$$
กำลังเปรียบเทียบโครงสร้างแลตทิซของ LCG กับค่าเฉลี่ยที่คาดไว้นี้ แต่มีขนาดต่างกัน โดยคนุธกล่าวว่า $\mu_d \ge 1$ เป็นคะแนนที่ดี หมายความว่าโครงตาข่ายของ LCG จะทำงานเหมือนโครงตาข่ายแบบสุ่ม