Minimum norm of an ideal lattice

[Cindy]

Hi,

Let K be a number field and O_k denote its ring of integers. For an ideal, J of O_k, we can have an ideal lattice (I,b_\alpha), where

b_\alpha: J\times J \to Z, b_\alpha(x,y)=Tr(\alpha xy), \forall x,y \in J

and \alpha is a totally positive element of K\{0}.

Suppose now I know J and \alpha, how can I get the minimum norm for the ideal lattice (J,\alpha) using sage?

Thanks a lot.

Cindy

[David Loeffler]

> how can I get the minimum norm for the
> ideal lattice (J,\alpha) using sage?

What have you tried so far?

David

[Cindy]

Let M denote the generator matrix of the lattice. Suppose M is a 2 by 2 matrix.

sage: var('x', domain=ZZ);
sage: var('y', domain=ZZ);
sage: v=vector((x,y));
sage: f=(M*v).norm();minimize(f,[1,1])

But the output is

Warning: Maximum number of iterations has been exceeded
         Current function value: 0.000000
         Iterations: 400
         Function evaluations: 804
         Gradient evaluations: 804
(1.07117779258e-121, -7.20701845996e-121)

[Cindy]

BTW, the generator matrix I used for the previous example is
[1 2]
[3 4]

Thanks.

Cindy

On Wednesday, September 5, 2012 7:31:48 PM UTC+8, David Loeffler wrote:

[David Loeffler]

Dear Cindy,

Without wishing to cause offence, I think your problem isn't a Sage
problem: it's that you don't understand the mathematical problem that
you're trying to solve.

Firstly, if V is an inner product space with basis v_1, ..., v_n and M
is its Gram matrix (the matrix whose i,j entry is v_i paired with
v_j), then the norm of the vector with coordinates x_1, .., x_n is not
the usual norm of (M * [x_1; ...; x_n]); it's [x_1, ..., x_n] * M *
[x_1; ...; x_n].

Secondly, the matrix [1, 2; 3, 4] is not symmetric or Hermitian and
its determinant is 0, so it is not the Gram matrix of a positive
definite inner product space.

Thirdly, the "minimize" function does what it says on the tin: it
finds the minimum value of a function, and it does so by using
calculus, assuming the function is differentiable. The minimum value
of the norm of a vector in a positive definite inner product space is
0, the norm of the zero vector. You want the minimum value at a
non-zero integer point and calculus is not going to help you with
that.

May I ask what motivates this long string of questions? Are you a
student? If so, you should go back and read your undergraduate linear
algebra notes a bit more carefully.

Regards, David Loeffler

> --
> You received this message because you are subscribed to the Google Groups
> "sage-support" group.
> To post to this group, send email to sage-s...@googlegroups.com.
> To unsubscribe from this group, send email to
> sage-support...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-support?hl=en.
>
>

[Cindy]

Hi, David,

Thanks for your explanation about the minimize function in sage. I didn't realize it's only for differentiable functions.

For the stuff regarding lattice, I think there may be some misunderstanding here.

What I want is to find the minimum of a lattice.

A lattice L can be defined as

L={x=\lambda M| \lambda\in Z^m},

where M is the generator matrix of L and the gram matrix of L is equal to MM^T.

The matrix
[1 2]
[3 4]
has determinant 4-2*3=-2, which is nonzero. Moreover, I use it as the generator matrix for lattice, not the gram matrix. Thus I don't think it needs to be symmetric or Hermitian.

As for the definition of minimum of a lattice, I assume it's defined for all lattice, thus there should be no other restrictions on the generator matrix (not gram matrix) except for it to be invertible.

 
According to the definition I found:

N(x)=x\cdot x=(x,x)=\sum x_i^2

for a vector x=(x_1,x_2,\dots,x_n) in a lattice and the minimum norm of lattice L is

min{N(x): x\in L, x\neq  0}.

When I calculate Mv (M is the generator matrix and v is the vector (x,y) with x,y both integers) I get a vector in L. Then I find the norm of Mv, which is the norm of this vector in L.

What I need is the minimum of this value.

Did I get the wrong definition of the minimum of lattice?

Best Regards,
Cindy

[David Loeffler]

On 6 September 2012 13:28, Cindy <cindy42...@gmail.com> wrote:
> Hi, David,
>
> Thanks for your explanation about the minimize function in sage. I didn't
> realize it's only for differentiable functions.
>
> For the stuff regarding lattice, I think there may be some misunderstanding
> here.
>
> What I want is to find the minimum of a lattice.
>
> A lattice L can be defined as
>
> L={x=\lambda M| \lambda\in Z^m},
>
> where M is the generator matrix of L and the gram matrix of L is equal to
> MM^T.

OK, I've never heard of this definition but if you want to take that
to be the definition that's up to you -- apparently for you all
lattices come with a fixed embedding into Euclidean space. But that
then changes the interpretation of your previous question, because in
your previous thread I assumed you wanted a Gram matrix, and that is
what the code I suggested calculates; the lattices coming from trace
pairings on number fields won't have any preferred embedding into
Euclidean space. To get *a* generator matrix (in your sense) from the
Gram matrix, you could use Cholesky decomposition, for example. But to
do this you will have to introduce square roots all over the place and
hence the computation becomes inexact; it is far simpler to just work
with the Gram matrix, which will be integer-valued in the examples
you've mentioned so far.

To find the shortest vector, you might want to use some of the
routines in Sage's quadratic forms module.

David

[David Loeffler]

PS. Apologies for my apparent inability to compute the determinant of
a 2x2 integer matrix correctly!

David

[Cindy]

Thanks.

Cindy