LatticeReduce

hbghlyj

en.wikipedia.org/wiki/Lattice_reduction
kconrad.math.uconn.edu/blurbs/grouptheory/SL(2,Z).pdf Example 2.1
尝试用Javascript写下2维LatticeReduce的Lagrange算法：

1. class Vector extends Array{
2.     // Add Vector v to this vector
3.     //   a.add(b);
4.     add (v) {
5.       var sum = new Vector();
6.       for (var i = 0; i < this.length; i++ ) {
7.         sum[i] = v[i] + this[i];
8.       }
9.       return sum;
10.     }
12.     // Dot product of Vector v and this vector
13.     //   a.dot(b); // should return 1*3+2*4+3*5 = 26
14.     dot (v) {
15.       var sum = 0;
16.       for (var i = 0; i < this.length; i++ ) {
17.         sum += this[i] * v[i];
18.       }
19.       return sum;
20.     }
22.     // Norm of this vector squared
23.     normSq () {
24.       var s = 0;
25.       for (var i = 0; i < this.length; i++ ) {
26.         s += Math.pow(this[i], 2);
27.       }
28.       return s
29.     }
31.     // scalar multiplication
32.     times (k) {
33.       var product = new Vector();
34.       for (var i = 0; i < this.length; i++ ) {
35.         product[i] = this[i] * k;
36.       }
37.       return product;
38.     }
39. }
41. // Input:  (u,v)  a basis for the lattice  L. Assume that  ||v|| \leq ||u|| , otherwise swap them.
42. //  Output: A basis  (u,v)  with  ||u|| = \lambda_1(L), ||v|| = \lambda_2(L) .
44. //  While  ||v|| < ||u|| :
45. //        q := \lfloor {\langle u, \frac{v}{||v||^2} \rangle } \rceil  # Round to nearest integer
46. //        r := u  - qv
47. //        u := v
48. //        v := r
49. function LLL(u,v){
50.     while (v.normSq() < u.normSq()){
51.         var q = Math.round(u.dot(v)/v.normSq());
52.         var r = u.add(v.times(-q));
53.         console.log("[" + u.toString() + "] - " + q.toString() + " * ["+v.toString()+"] = ["+r.toString()+"]");
54.         u = v;
55.         v = r;
56.     }
57.     console.log("result is: [" + u.toString() + "], [" + v.toString() + "]");
58. }

复制代码

上面while終止的條件是v.normSq() $\ge$ u.normSq()，所以有兩種可能：
終止時v.normSq() $>$ u.normSq()

1. LLL(new Vector(13, 4),new Vector(12, 2))

复制代码

輸出
[13,4] - 1 * [12,2] = [1,2]
[12,2] - 3 * [1,2] = [9,-4]
result is: [1,2], [9,-4]

終止時v.normSq() $=$ u.normSq()

1. LLL(new Vector(17, 29),new Vector(7, 12))

复制代码

輸出
[17,29] - 2 * [7,12] = [3,5]
[7,12] - 2 * [3,5] = [1,2]
[3,5] - 3 * [1,2] = [0,-1]
[1,2] - -2 * [0,-1] = [1,0]
result is: [0,-1], [1,0]

hbghlyj

两个平行四边形（通过平移）生成相同的格子，那么它们面积相等。
在下图中，粉色和青色的平行四边形生成相同的格子：

$v_1$ = {12, 2};  $v_2$ = {13, 4};
$w_1$ = {1, 2};  $w_2$ = {9, -4};

\[\Bbb Zv_1+\Bbb Zv_2=\Bbb Zw_1+\Bbb Zw_2\]

\begin{align*}
-1 v_1 + 1 v_2&= w_1&3 w_1 + 1 w_2&= v_1\\
4v_1 - 3v_2&= w_2&4 w_1 + 1 w_2&= v_2
\end{align*}
kuing.cjhb.site/forum.php?mod=viewthread&tid=12033

hbghlyj

如何把這個算法推廣到3維？生成相同格子的所有平行六面體中，“最接近方形”的平行六面體滿足何條件？
mathoverflow.net/questions/61933/lattice-reduction-in-r3-r4-or-w ... domain-for-sl3-z-sl4

hbghlyj

1#的代碼，應該只適用於2維的整數向量
雖然可以輸入3維的整數向量，但好像結果不是LatticeReduce

1. LLL(new Vector(17,29,1),new Vector(7,12,1))

复制代码

[17,29,1] - 2 * [7,12,1] = [3,5,-1]
[7,12,1] - 2 * [3,5,-1] = [1,2,3]
[3,5,-1] - 1 * [1,2,3] = [2,3,-4]
result is: [1,2,3], [2,3,-4]