Further Examples: LatticeReduce

These vectors span a subspace of .

In[1]:=

This gives the reduced basis for the lattice spanned by B. These new vectors are closer to being orthogonal than B.

In[2]:=

Out[2]=

This gives a basis for a pair of vectors with rational coordinates.

In[3]:=

Out[3]=

In[4]:=

Using LatticeReduce to construct a polynomial given an approximation to one of its roots

Here is a polynomial with small Gaussian integer coefficients.

In[5]:=

Here is an approximate root.

In[6]:=

Out[6]=

We will construct a polynomial (of degree at most seven) related to poly that has a root close (or equal) to r. First augment an identity matrix with a column whose entries are a large multiple of powers of r.

In[7]:=

Out[7]//MatrixForm=

LatticeReduce produces a new set of vectors that span the same lattice.

In[8]:=

Out[8]//MatrixForm=

Each new row is an integer linear combination of the old rows. The norms of the first several new rows, in particular the first one, are small in comparison to the norms of the rows of the original lattice. (This is the purpose of LatticeReduce). The specific linear combination for the first row can be read off from the construction of the original lattice.

In[9]:=

Out[9]=

This polynomial must have r for an approximate root.

In[10]:=

Out[10]=

It does, since the new polynomial turns out to be z times the original polynomial.

In[11]:=

Out[11]=

In[12]:=