Re: [sage-support] Minimum norm of an ideal lattice
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.00 Iterations: 400 Function evaluations: 804 Gradient evaluations: 804 (1.07117779258e-121, -7.20701845996e-121) On Wednesday, September 5, 2012 7:31:48 PM UTC+8, David Loeffler wrote: how can I get the minimum norm for the ideal lattice (J,\alpha) using sage? What have you tried so far? David -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Minimum norm of an ideal lattice
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: how can I get the minimum norm for the ideal lattice (J,\alpha) using sage? What have you tried so far? David -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Minimum norm of an ideal lattice
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, Xiaolu On Thursday, September 6, 2012 6:50:00 PM UTC+8, David Loeffler wrote: 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 On 6 September 2012 10:38, Cindy cindy42...@gmail.com javascript: wrote: 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: how can I get the minimum norm for the ideal lattice (J,\alpha) using sage? What have you tried so far? David -- 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.comjavascript:. To unsubscribe from this group, send email to sage-support...@googlegroups.com javascript:. Visit this group at http://groups.google.com/group/sage-support?hl=en. -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Minimum norm of an ideal lattice
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 On Thursday, September 6, 2012 6:50:00 PM UTC+8, David Loeffler wrote: 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 On 6 September 2012 10:38, Cindy cindy42...@gmail.com javascript: wrote: 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: how can I get the minimum norm for the ideal lattice (J,\alpha) using sage? What have you tried so far? David -- 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.comjavascript:. To unsubscribe from this group, send email to sage-support...@googlegroups.com javascript:. Visit this group at http://groups.google.com/group/sage-support?hl=en. -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Minimum norm of an ideal lattice
Thanks. Cindy On Thursday, September 6, 2012 9:03:47 PM UTC+8, David Loeffler wrote: On 6 September 2012 13:28, Cindy cindy42...@gmail.com javascript: 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 -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Dual of an ideal
Hi, David, Could you please explain a little bit about the code? For the example you use, it seems I is an ideal above 17, what does [0] mean? In the end do we get a basis of the dual of I? Why do we need to put I.basis() in the bracket of trace_dual_basis? Thanks a lot. Cindy On Wednesday, September 5, 2012 4:21:22 PM UTC+8, David Loeffler wrote: On 5 September 2012 02:41, Cindy cindy42...@gmail.com javascript: wrote: Hi, David, Yes, that's what I mean. Can I find it using sage? Thanks. Cindy sage: K.z = NumberField(x^3 - x + 17) sage: I = K.primes_above(17)[0] sage: K.trace_dual_basis(I.basis()) [4/132583*z^2 + 6/7799*z + 2597/132583, -153/7799*z^2 - 2/7799*z + 102/7799, -6/7799*z^2 - 153/7799*z + 4/7799] hth, David -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Dual of an ideal
Hi, David, Thanks a lot. I tried trace_dual_basis? to find out the meaning. I didn't realize I should use K.trace_dual_basis? Thanks. :) Cindy On Wednesday, September 5, 2012 5:15:19 PM UTC+8, David Loeffler wrote: On 5 September 2012 09:34, Cindy cindy42...@gmail.com javascript: wrote: Hi, David, Could you please explain a little bit about the code? Sure, but you should make a little effort to play with it yourself for a bit first. For the example you use, it seems I is an ideal above 17, what does [0] mean? The command K.primes_above(...) returns a list of the prime ideals above the given rational prime. The [0] selects the first (zeroth?) from the list. So yes, I is an ideal above 17 which I am just using as an example (any number field ideal, except the zero ideal, would work here). There are lots of examples like this in the Sage documentation. In the end do we get a basis of the dual of I? Yes, that's the whole point of the exercise :-). Did you read the documentation for trace_dual_basis? You should know that you can get documentation on any method of any Sage object by typing its name then ?, e.g. sage: K.trace_dual_basis? will tell you lots more about this method. Why do we need to put I.basis() in the bracket of trace_dual_basis? Because trace_dual_basis takes a list of generators as its argument -- it can calculate the trace dual of any Z-submodule of K, it needn't be an ideal. Regards, David -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Generator matrix of ideal lattice
Hi, David, Thanks a lot! It works.^^ Cindy On Wednesday, September 5, 2012 4:30:40 PM UTC+8, David Loeffler wrote: On 5 September 2012 02:56, Cindy cindy42...@gmail.com javascript: wrote: 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 generator matrix for the ideal lattice (J,\alpha) using sage? Thanks a lot. Cindy The first thing I tried was this, and it seems to work fine: sage: K.z = NumberField(x^3 - x + 17) sage: I = K.primes_above(17)[1] sage: alpha = 13*z + 4 sage: matrix([[(u*v*alpha).trace() for u in I.basis()] for v in I.basis()]) [ 3468646 -11339] [ 646 -591 -871] [-11339 -871225] David -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
[sage-support] Minimum norm of an ideal lattice
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 -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Generator matrix of ideal lattice
Hi, David, BTW, do you know how to find the minimum norm of the lattice? I posted a question regarding this in this group. Do you know which function I should use? Thanks. Cindy On Wednesday, September 5, 2012 4:30:40 PM UTC+8, David Loeffler wrote: On 5 September 2012 02:56, Cindy cindy42...@gmail.com javascript: wrote: 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 generator matrix for the ideal lattice (J,\alpha) using sage? Thanks a lot. Cindy The first thing I tried was this, and it seems to work fine: sage: K.z = NumberField(x^3 - x + 17) sage: I = K.primes_above(17)[1] sage: alpha = 13*z + 4 sage: matrix([[(u*v*alpha).trace() for u in I.basis()] for v in I.basis()]) [ 3468646 -11339] [ 646 -591 -871] [-11339 -871225] David -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Dual of an ideal
Hi, David, Yes, that's what I mean. Can I find it using sage? Thanks. Cindy On Tuesday, September 4, 2012 3:12:25 PM UTC+8, David Loeffler wrote: What exactly do you mean by the dual of an ideal? Do you mean dual with respect to the trace pairing, so the dual of the ideal (1) is the inverse different? David On 4 September 2012 04:15, Cindy cindy42...@gmail.com javascript: wrote: Hi, How can I calculate the dual of an ideal using sage? Thanks. Cindy -- 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.comjavascript:. To unsubscribe from this group, send email to sage-support...@googlegroups.com javascript:. Visit this group at http://groups.google.com/group/sage-support?hl=en. -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Dual of an ideal
Hi, Vijay, Let K be a number field and O_k be its ring of integers. Given an ideal J of O_k, I want to find the dual of J, which is defined as the O_k-module: J^*={x\in K| Tr(xJ)\subset Z}. Thanks. Cindy On Tuesday, September 4, 2012 3:20:35 PM UTC+8, Vj wrote: Cindy, Could you elaborate little more, what is precisely you need. Regards, Vijay On Tue, Sep 4, 2012 at 12:42 PM, David Loeffler d.a.lo...@warwick.ac.ukjavascript: wrote: What exactly do you mean by the dual of an ideal? Do you mean dual with respect to the trace pairing, so the dual of the ideal (1) is the inverse different? David On 4 September 2012 04:15, Cindy cindy42...@gmail.com javascript: wrote: Hi, How can I calculate the dual of an ideal using sage? Thanks. Cindy -- 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.comjavascript: . To unsubscribe from this group, send email to sage-support...@googlegroups.com javascript:. Visit this group at http://groups.google.com/group/sage-support?hl=en. -- 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.comjavascript: . To unsubscribe from this group, send email to sage-support...@googlegroups.com javascript:. Visit this group at http://groups.google.com/group/sage-support?hl=en. -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Dual of an ideal
Hi, BTW, the ideals I am dealing with are ideals of the ring of integers of a number field. Cindy On Tuesday, September 4, 2012 3:12:25 PM UTC+8, David Loeffler wrote: What exactly do you mean by the dual of an ideal? Do you mean dual with respect to the trace pairing, so the dual of the ideal (1) is the inverse different? David On 4 September 2012 04:15, Cindy cindy42...@gmail.com javascript: wrote: Hi, How can I calculate the dual of an ideal using sage? Thanks. Cindy -- 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.comjavascript:. To unsubscribe from this group, send email to sage-support...@googlegroups.com javascript:. Visit this group at http://groups.google.com/group/sage-support?hl=en. -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
[sage-support] Generator matrix of ideal lattice
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 generator matrix for the ideal lattice (J,\alpha) using sage? Thanks a lot. Cindy -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
[sage-support] Dual of an ideal
Hi, How can I calculate the dual of an ideal using sage? Thanks. Cindy -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Calculate discrimanent of relative number fields
Thanks a lot David! It works ^^ Cindy On Thursday, August 30, 2012 4:39:36 PM UTC+8, David Loeffler wrote: On 29 August 2012 12:54, Cindy cindy42...@gmail.com javascript: wrote: Hi, Given a cyclotomic field Q(zeta_n), where zeta_n is a primitive nth root of unity, with maximal real subfield F, how can I calculate the discriminant of K/F? You need to use the relativize command to create the field extension K / F. Here's an example for the 13th cyclotomic field: -- | Sage Version 5.2, Release Date: 2012-07-25 | | Type notebook() for the browser-based notebook interface.| | Type help() for help.| -- sage: K.zeta = CyclotomicField(13) sage: Krel = K.relativize(zeta + zeta^(-1), w) sage: Krel Number Field in w0 with defining polynomial x^2 - w1*x + 1 over its base field sage: Krel.base_field() Number Field in w1 with defining polynomial x^6 + x^5 - 5*x^4 - 4*x^3 + 6*x^2 + 3*x - 1 # so now Krel is QQ(zeta13) as an extension of F = QQ(zeta13 + zeta13^(-1)) sage: Krel.relative_discriminant() Fractional ideal (w1^5 - 5*w1^3 + 4*w1) # (an ideal of F) sage: Krel.relative_different() Fractional ideal ((w1^3 - 2*w1)*w0 - w1^2) # (an ideal of Krel) Regards, David -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
[sage-support] Calculate discrimanent of relative number fields
Hi, Given a cyclotomic field Q(zeta_n), where zeta_n is a primitive nth root of unity, with maximal real subfield F, how can I calculate the discriminant of K/F? Thanks. Cindy -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
[sage-support] Find the generator matrix and minimum norm of ideal lattice
Hi, Given an ideal I, I want to find the following properties of the ideal lattice (I,b), where b is the trace form. 1. generator matrix 2. minimum norm How can I do this in Sage? Thanks. Cindy -- You received this message because you are subscribed to the Google Groups sage-support group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.