4207.sagews

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]

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]

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]

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)

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

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]

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]

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]

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)

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

i=2
LHS = ((3/4) * norm(b2_gs)).n()
RHS = norm(m32*b2_gs + b3_gs).n()
LHS <= RHS

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]

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]

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]

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)

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

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]

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]

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]

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)

Check Lov\'asz condition.

i=1
LHS = ((3/4) * norm(b1_gs)).n()
RHS = norm(m21*b1_gs + b2_gs).n()
LHS <= RHS

True

i=2
LHS = ((3/4) * norm(b2_gs)).n()
RHS = norm(m32*b2_gs + b3_gs).n()
LHS <= RHS

True

Done.

Answer = matrix(ZZ, [b1,b2,b3])
Answer

[ 3 0 0] [-1 5 0] [ 0 1 16]