Lattice Basis Reduction

60 Lattice Basis Reduction

which is clear since β >

4

3

. We now have

|x

i

|

2

≤ β

i−1

|x

∗

i

|

2

. (4.2)

Using this and equation (4.1) gives

|x

j

|

2

≤ β

j−1

|x

∗

j

|

2

≤ β

i−1

|x

∗

i

|

2

(1 ≤ j ≤ i ≤ n),

which proves (a). Fr om Theorem 3.4 we know that

det(L) = |x

∗

1

||x

∗

2

| ··· |x

∗

n

| ≤ |x

1

||x

2

| ··· |x

n

|,

which proves the left inequality in (b). Equation (4.2) implies

|x

1

|

2

|x

2

|

2

··· |x

n

|

2

≤ β

0+1+2+···+(n−1)

|x

∗

1

|

2

|x

∗

2

|

2

··· |x

∗

n

|

2

,

and therefore

|x

1

||x

2

| ··· |x

n

| ≤ β

n(n−1)/4

|x

∗

1

||x

∗

2

| ··· |x

∗

n

| = β

n(n−1)/4

det(L),

which proves the right inequality in (b). Setting j = 1 in (a) gives

|x

1

|

2

≤ β

i−1

|x

∗

i

|

2

(1 ≤ i ≤ n),

and taking the product over i = 1, 2, . . . , n gives

|x

1

|

2n

≤ β

0+1+2+···+(n−1)

|x