Exercise 13

110 days ago by nela

Given lattice basis b_1, b_2, b_3 Sage gives the LLL-reduced basis:
b1 = vector(QQ,[8,6,16]) b2 = vector(QQ,[-1, 5, 0]) b3 = vector(QQ,[2, 5, 0]) A = matrix(ZZ, [b1,b2,b3]) A.LLL() 
        
[ 3  0  0]
[-1  5  0]
[ 0  1 16]
[ 3  0  0]
[-1  5  0]
[ 0  1 16]

Solve it now step by step. Compute first Gram-Schmidt orthogonalization to obtain \mu_{k,i}'s and b_i^*'s.
b1_gs = b1 m21 = (b2*b1_gs)/(b1_gs*b1_gs) b2_gs = b2 - m21*b1 m31 = (b3*b1_gs)/(b1_gs*b1_gs) m32 = (b3*b2_gs)/(b2_gs*b2_gs) b3_gs = b3 - (m31*b1 + m32*b2_gs) matrix([b1_gs, b2_gs, b3_gs]) 
        
[       8        6       16]
[ -133/89   412/89   -88/89]
[1600/731  320/731 -920/731]
[       8        6       16]
[ -133/89   412/89   -88/89]
[1600/731  320/731 -920/731]

Size reduce b_i's.
b2 = b2 - m21.round()*b1 b3 = b3 - (m31.round()*b1 + m32.round()*b2) matrix(ZZ, [b1,b2,b3]) 
        
[ 8  6 16]
[-1  5  0]
[ 3  0  0]
[ 8  6 16]
[-1  5  0]
[ 3  0  0]

Update \mu_{k,i}'s.
m21 = (b2*b1_gs)/(b1_gs*b1_gs) m31 = (b3*b1_gs)/(b1_gs*b1_gs) m32 = (b3*b2_gs)/(b2_gs*b2_gs) m21, m31, m32 
        
(11/178, 6/89, -133/731)
(11/178, 6/89, -133/731)

Check if Lov\'asz condition is violated.
i=1 LHS = ((3/4) * norm(b1_gs)).n() RHS = norm(m21*b1_gs + b2_gs).n() LHS <= RHS 
        
False
False

Yes. So swap b_1 and b_2.
x = b1 b1 = b2 b2 = x matrix(ZZ, [b1,b2,b3]) 
        
[-1  5  0]
[ 8  6 16]
[ 3  0  0]
[-1  5  0]
[ 8  6 16]
[ 3  0  0]

Compute Gram-Schmidt orthogonalization again.
b1_gs = b1 m21 = (b2*b1_gs)/(b1_gs*b1_gs) b2_gs = b2 - m21*b1 m31 = (b3*b1_gs)/(b1_gs*b1_gs) m32 = (b3*b2_gs)/(b2_gs*b2_gs) b3_gs = b3 - (m31*b1 + m32*b2_gs) matrix([b1_gs, b2_gs, b3_gs]) 
        
[      -1        5        0]
[  115/13    23/13       16]
[1600/731  320/731 -920/731]
[      -1        5        0]
[  115/13    23/13       16]
[1600/731  320/731 -920/731]

Size reduce b_i's.
b2 = b2 - m21.round()*b1 b3 = b3 - (m31.round()*b1 + m32.round()*b2) matrix(ZZ, [b1,b2,b3]) 
        
[-1  5  0]
[ 9  1 16]
[ 3  0  0]
[-1  5  0]
[ 9  1 16]
[ 3  0  0]

Update \mu_{k,i}'s.
m21 = (b2*b1_gs)/(b1_gs*b1_gs) m31 = (b3*b1_gs)/(b1_gs*b1_gs) m32 = (b3*b2_gs)/(b2_gs*b2_gs) m21, m31, m32 
        
(-2/13, -3/26, 115/1462)
(-2/13, -3/26, 115/1462)

Check if Lov\'asz condition is violated.
i=1 LHS = ((3/4) * norm(b1_gs)).n() RHS = norm(m21*b1_gs + b2_gs).n() LHS <= RHS 
        
True
True
i=2 LHS = ((3/4) * norm(b2_gs)).n() RHS = norm(m32*b2_gs + b3_gs).n() LHS <= RHS 
        
False
False

Yes. Swap b_2 and b_3.
x = b2 b2 = b3 b3 = x matrix(ZZ, [b1,b2,b3]) 
        
[-1  5  0]
[ 3  0  0]
[ 9  1 16]
[-1  5  0]
[ 3  0  0]
[ 9  1 16]

Gram-Schmidt orthogonalization.
b1_gs = b1 m21 = (b2*b1_gs)/(b1_gs*b1_gs) b2_gs = b2 - m21*b1 m31 = (b3*b1_gs)/(b1_gs*b1_gs) m32 = (b3*b2_gs)/(b2_gs*b2_gs) b3_gs = b3 - (m31*b1 + m32*b2_gs) matrix([b1_gs, b2_gs, b3_gs]) 
        
[   -1     5     0]
[75/26 15/26     0]
[    0     0    16]
[   -1     5     0]
[75/26 15/26     0]
[    0     0    16]

Size reduce b_i's.
b2 = b2 - m21.round()*b1 b3 = b3 - (m31.round()*b1 + m32.round()*b2) matrix(ZZ, [b1,b2,b3]) 
        
[-1  5  0]
[ 3  0  0]
[ 0  1 16]
[-1  5  0]
[ 3  0  0]
[ 0  1 16]

Update \mu_{k,i}'s.
m21 = (b2*b1_gs)/(b1_gs*b1_gs) m31 = (b3*b1_gs)/(b1_gs*b1_gs) m32 = (b3*b2_gs)/(b2_gs*b2_gs) m21, m31, m32 
        
(-3/26, 5/26, 1/15)
(-3/26, 5/26, 1/15)

Check if Lov\'asz is satisfied.
i=1 LHS = ((3/4) * norm(b1_gs)).n() RHS = norm(m21*b1_gs + b2_gs).n() LHS <= RHS 
        
False
False

No. Swap b_1 and b_2.
x = b1 b1 = b2 b2 = x matrix(ZZ, [b1,b2,b3]) 
        
[ 3  0  0]
[-1  5  0]
[ 0  1 16]
[ 3  0  0]
[-1  5  0]
[ 0  1 16]

Gram-Schmidt orthogonalization again.
b1_gs = b1 m21 = (b2*b1_gs)/(b1_gs*b1_gs) b2_gs = b2 - m21*b1 m31 = (b3*b1_gs)/(b1_gs*b1_gs) m32 = (b3*b2_gs)/(b2_gs*b2_gs) b3_gs = b3 - (m31*b1 + m32*b2_gs) matrix([b1_gs, b2_gs, b3_gs]) 
        
[ 3  0  0]
[ 0  5  0]
[ 0  0 16]
[ 3  0  0]
[ 0  5  0]
[ 0  0 16]

Size reduce b_i's.
b2 = b2 - m21.round()*b1 b3 = b3 - (m31.round()*b1 + m32.round()*b2) matrix(ZZ, [b1,b2,b3]) 
        
[ 3  0  0]
[-1  5  0]
[ 0  1 16]
[ 3  0  0]
[-1  5  0]
[ 0  1 16]

Update \mu_{k,i}'s.
m21 = (b2*b1_gs)/(b1_gs*b1_gs) m31 = (b3*b1_gs)/(b1_gs*b1_gs) m32 = (b3*b2_gs)/(b2_gs*b2_gs) m21, m31, m32 
        
(-1/3, 0, 1/5)
(-1/3, 0, 1/5)

Check Lov\'asz condition.
i=1 LHS = ((3/4) * norm(b1_gs)).n() RHS = norm(m21*b1_gs + b2_gs).n() LHS <= RHS 
        
True
True
i=2 LHS = ((3/4) * norm(b2_gs)).n() RHS = norm(m32*b2_gs + b3_gs).n() LHS <= RHS 
        
True
True

Done.
Answer = matrix(ZZ, [b1,b2,b3]) Answer 
        
[ 3  0  0]
[-1  5  0]
[ 0  1 16]
[ 3  0  0]
[-1  5  0]
[ 0  1 16]