Lattice可以被想象成是一個空間中很多有規律分佈的、離散的點。
我們可以對此Lattice進行任意的線性變換(Linear Transformation)B,然後可以得到新的Lattice。
Lattice與Bases(格與基)
更好的描述一個格的方法是使用基向量。
同理可得,我們可以用線性代數中學到的基變更(Change of basis)給這個Lattice找到一組新的基C。
如果系統性的定義一下Lattice的話,那麼我們可以說Lattice是Rn這個空間中的一個離散的、具有加法運算的子群(A discrete additive subgroup)。
Lattice的基本屬性
同理可得,一個Lattice的Determinant也是一樣的——對應的基向量所組成的Parallelepiped的體積。
同理,我們換了一組基向量,也可以計算它的Determinant。
值得注意的是,無論我們怎麼更換基向量,Determinant的大小,即基向量組成的多面體的體積是相同的。給定任意的一組基向量,我們都可以有效的找到這個Lattice空間的Determinant。
Lattice的密度
我們可以用一個Lattice的Determinant來衡量這個格的點陣分佈的密度。
首先,我們把上一部分基向量組成的多面體的中心挪到原點上來。這樣,空間P仍然保持相同的體積。
隨後,我們可以把這個多面體複製多份,然後平移到每一個Lattice中的點上。這樣我們就會得到很多份P,並且這些多面體可以平分整個多維空間Rn。
此時,我們如果在這個空間中任意的畫一個球體(多維空間即超球體),然後可以數數看這個球體中覆蓋了多少Lattice裡的點。點的數量平均於球體的體積,就是這個格的密度了。
這個概念理解起來也非常簡單。我們的球體中有多少個Lattice的點,其實大概和球體的體積中有多少個det(L)的多面體,這兩個比例大致相同。
最短距離
距離函式(Distance Function)與覆蓋半徑(Covering Radius)
給定任意一個點t(這個點不需要在Lattice上),我們可以定義距離函式u(t,L)為這個點到附近的Lattice點的最短距離。
同理可得,我們也可以左右移動t的位置,然後就可以找到在這個Lattice中可以得到的最大的u。我們一般稱這個最大值叫覆蓋半徑(Covering Radius)。
為什麼稱這個最遠距離為覆蓋半徑呢,其實很簡單。我們可以假設在這個Lattice中,以每個格點為圓心畫很多歌圓。
如果逐漸把圓的半徑擴大的話, 那麼所有的圓就會逐漸開始覆蓋整個Rn空間。
直到所有的圓正好完美的覆蓋了所有的空間的時候,這個時候的半徑,就是我們之前得到的u了。這就是覆蓋半徑這一名字的由來。
Lattice的Smoothing
如果我們把上面的覆蓋圓的概念稍微轉換一下,假設我們不是在每個格點上疊加一個圓形,而是疊加一個圓形範圍內取值的隨機噪音,那麼當圓的半徑達到覆蓋半徑之後,這個Lattice本身就和背後的連續空間Rn合二為一了。
但是如果就只是在覆蓋半徑上的話,可以在圖上發現,噪音覆蓋的分佈非常的不平均,因為格點之間相互的位置的問題。這也就是說,疊加了噪音之後,最後得到在Rn上的取值分佈也不平均。
如果想讓取值分佈更加平均的話,我們就需要更多的Smooth(平滑化?)這個Lattice,即繼續擴大圓的半徑。理論上當半徑接近於無限大的時候,我們得到的分佈是最完美、最平均的。但是當圓無限大了之後,這個構造就沒有太多實際操作的意義了。
所以一般來說,我們都會給這個Smoothing的半徑一個最大上限。這個最大上限是由這個Lattice中距離最大的最短向量來決定的。因為當我們的半徑大於了這個最短向量之後,那麼這個圓就會覆蓋太多的點(因為最短距離決定了點到點之間的距離),然後這個構造就失去了意義。
Minkowski凸集定理(Convex body theorem)
對於Lattice,Minkowski給出了幾個比較有意思的定理。第一個定理是用於尋找一個格點周圍最近的其他格點的,即凸集定理。
在整數格Zn中非常好理解,因為以原點出發到所有下一個點這段距離構成的空間,恰好就是2n,所以說任何凸集(集合的表面不能有凹陷)只要體積大於2n,那就一定會溢位這段空間,進而覆蓋某個非0的格點。透過Pigeonhole Principle(鴿子洞原理)就可以很生動的理解了。
接下來,如果我們換成一個不規則的Lattice,即在原有的Zn上疊加線性變換,這個定理還是成立的。
Minkowski第二定理