Thanks for the explanation. Perhaps we need to change the
implementation to be more like what Magma does, namely it gives either
2 O_K-generators or a Z_K-basis by default, but if you ever ask if an
ideal is principal then it works that out and stores the result, with
the generator if principal so that it never has to do that twice.
This would suffice for many purposes, and only if the user asked if an
ideal is principal would it have to work out the class group etc.
John
On 30/12/2007, Bill Hart <[EMAIL PROTECTED]> wrote:
>
> Actually, even that is not correct. It creates the ideal objects in no
> time. It seems that it is when it comes to display them that it wants
> to determine if they are principal, presumably so it can display them
> with as simple a representation as possible.
>
> Bill.
>
> On 30 Dec, 11:39, Bill Hart <[EMAIL PROTECTED]> wrote:
> > What is happening is that at a certain point it is checking to see if
> > ideals are principal. That requires bnfisprincipal and hence bnfinit
> > which requires computation of the unit and class group.
> >
> > Essentially the way it is implemented is that it expresses the ideal
> > in hermite normal form. Then it factors it using Pari. None of this
> > takes any time.
> >
> > Then for each of the ideal factors, in hermite normal form, it has to
> > construct a SAGE ideal object. In the process of doing this, it checks
> > each one to see if it is principal. This appears to be what is taking
> > all the time.
> >
> > Bill.
> >
> > On 30 Dec, 10:27, "John Cremona" <[EMAIL PROTECTED]> wrote:
> >
> > > But pari provides two number field structures (see page 117 of the
> > > pari manual), nf and bnf. nfinit() creates a number field with more
> > > "elementary" capabilities, including the ring of integers and prime
> > > decompositions. bnfinit() works a lot harder and gives the class and
> > > unit groups.
> >
> > > Hence it is not correct to say the nfint() computes class groups etc,
> >
> > > Within Sage we could first call nfinit(), and only if some of the
> > > deeper functionality was needed would bnfinit() be called. Note that
> > > pari will not automatically call bnfinit() for you; but Sage could
> > > try to be clever and use the most appropriate structure.
> >
> > > John
> >
> > > On 30/12/2007, David Roe <[EMAIL PROTECTED]> wrote:
> >
> > > > The issue is that since Sage uses pari to do everything in the
> > > > background,
> > > > one needs to create the pari data structures, which means that you
> > > > currently
> > > > call nfinit on the number field, which computes the class group and unit
> > > > group. This should change eventually, but right now...
> > > > David
> >
> > > > On Dec 29, 2007 2:10 PM, Enrique Gonzalez-Jimenez
> > > > <[EMAIL PROTECTED]> wrote:
> >
> > > > > As John Cremona said at the sage.forum: "But why would Sage be
> > > > > computing the class group in order to factor 2 in K?"
> >
> > > > > For me that is strange too. Since it would be easier to compute the
> > > > > factorization of an ideal generate by a prime.
> >
> > > > > For example: Using the Proposition that asserts that if K is a number
> > > > > field and the ring of integers is of the form O_K=Z[alpha] (where f(t)
> > > > > is the minimal polynomial over Z of alpha) then to compute the
> > > > > factorization of the ideal <p>O_K where p is a rational prime is
> > > > > enough to factorize f(t)mod p. That is, if
> > > > > f(t)=f_1(t)^r_1...f_s(t)^r_s (mod p) then the factorization on prime
> > > > > ideal is of the form
> >
> > > > > <p>O_K=<p,f_1(alpha)>^r_1...<p,f_s(alpha)>^r_s.
> >
> > > > > Enrique
> >
> > > > > On 29 dic, 21:42, Bill Hart < [EMAIL PROTECTED]> wrote:
> > > > > > It presumably can't compute the class group, because of the
> > > > > > proof=true
> > > > > > thing. Basically if you want a proven result, it is going to take
> > > > > > forever and will need more primes than Pari has precomputed.
> >
> > > > > > It's not clear to me if SAGE is actually catching the error message,
> > > > > > or if it is just raising an exception because Pari did something it
> > > > > > wasn't expecting (i.e. print an error message).
> >
> > > > > > Bill.
> >
> > > > > > On 29 Dec, 20:27, mabshoff
> > > > <[EMAIL PROTECTED]
> >
> > > > > > dortmund.de> wrote:
> > > > > > > On Dec 29, 9:17 pm, [EMAIL PROTECTED] wrote:
> >
> > > > > > > > Hello:
> >
> > > > > > > > I am working at my Number Theory lectures and I have found a bug
> > > > (?). This is
> > > > > > > > the output:
> >
> > > > > > > > /////////////////// SAGE 2.9.1 ///////////////////
> > > > > > > > sage: K.<a>=CyclotomicField(23)
> > > > > > > > sage: O=K.maximal_order()
> > > > > > > > sage: (2*O).factor()
> > > > > > > > *** Warning: large Minkowski bound: certification will be VERY
> > > > long.
> > > > > > > > Traceback (most recent call last):
> > > > > > > > File "<stdin>", line 1, in <module>
> > > > > > > > File
> > > > "/home/notebook/sage_notebook/worksheets/admin/3/code/13.py",
> > > > > > > > line 4, in <module>
> > > > > > > > exec compile(ur'(Integer(2)*O).factor()' +
> > > > '\n', '', 'single')
> > > > > > > > File
> >
> > > > "/usr/local/sage/local/lib/python2.5/site-packages/sympy/plotting/",
> > > > > > > > line 1, in <module>
> >
> > > > > > > > File "sage_object.pyx", line 92, in
> > > > > > > > sage.structure.sage_object.SageObject.__repr__
> > > > > > > > File
> >
> > > > "/usr/local/sage/local/lib/python2.5/site-packages/sage/structure/factor\
> > > > > > > > ization.py", line 187, in _repr_
> > > > > > > > t = str(self[i][0])
> > > > > > > > File
> >
> > > > "/usr/local/sage/local/lib/python2.5/site-packages/sage/rings/number_fie\
> > > > > > > > ld/number_field_ideal.py", line 218, in __repr__
> > > > > > > > return "Fractional ideal %s"%self._repr_short()
> > > > > > > > File
> >
> > > > "/usr/local/sage/local/lib/python2.5/site-packages/sage/rings/number_fie\
> > > > > > > > ld/number_field_ideal.py", line 235, in _repr_short
> > > > > > > > return '(%s)'%(', '.join([str(x) for x in self.gens_reduced()]))
> > > > > > > > File
> >
> > > > "/usr/local/sage/local/lib/python2.5/site-packages/sage/rings/number_fie\
> > > > > > > > ld/number_field_ideal.py", line 553, in gens_reduced
> > > > > > > > dummy = self.is_principal(proof)
> > > > > > > > File
> >
> > > > "/usr/local/sage/local/lib/python2.5/site-packages/sage/rings/number_fie\
> > > > > > > > ld/number_field_ideal.py", line 714, in is_principal
> > > > > > > > bnf = self.number_field().pari_bnf(proof)
> > > > > > > > File
> >
> > > > "/usr/local/sage/local/lib/python2.5/site-packages/sage/rings/number_fie\
> > > > > > > > ld/number_field.py", line 1464, in pari_bnf
> > > > > > > > self.pari_bnf_certify()
> > > > > > > > File
> >
> > > > "/usr/local/sage/local/lib/python2.5/site-packages/sage/rings/number_fie\
> > > > > > > > ld/number_field.py", line 1497, in pari_bnf_certify
> > > > > > > > if self.pari_bnf(certify=False, units=True).bnfcertify() != 1:
> > > > > > > > File "gen.pyx", line 6474, in sage.libs.pari.gen._pari_trap
> > > > > > > > sage.libs.pari.gen.PariError: not enough precomputed primes,
> > > > > > > > need
> > > > > > > > primelimit ~ (35)
> >
> > > > > > > Hi Enrique,
> >
> > > > > > > this looks like a bug to me. I have seen this issue discussed
> > > > > > > before,
> > > > > > > but I cannot find any ticket in our bug tracker that relates to
> > > > > > > it. So
> > > > > > > I am hoping for somebody more familiar with the pari interface to
> > > > > > > voice an opinion.
> >
> > > > > > > Cheers.
> >
> > > > > > > Michael
> >
> > > > > > > > But if you type the following lines using gp interface, it
> > > > > > > > works:
> >
> > > > > > > > sage: K=gp.bnfinit(cyclotomic_polynomial(23))
> > > > > > > > sage: gp.idealfactor (K,2)
> >
> > > > > > > > [[2, [1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0,
> > > > > > > > 0, 0,
> > > > > > > > 0]~, 1, 11, [1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0,
> > > > > > > > 0,
> > > > 0, 0,
> > > > > > > > 0, 0]~], 1; [2, [1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0,
> > > > > > > > 0, 0,
> > > > 0,
> > > > > > > > 0, 0, 0, 0]~, 1, 11, [1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0,
> > > > > > > > 0,
> > > > 0, 0,
> > > > > > > > 0, 0, 0, 0, 0]~], 1]
> >
> > > > > > > > All the best,
> >
> > > > > > > > Enrique
> >
> > > > --------------------------------------------------------------------------
> > > > > > > > Mensaje enviado mediante una herramienta Webmail integrada en
> > > > > > > > *El
> > > > Rincon*:
> > > > > > > > ------------->>>>>>>> https://rincon.uam.es
> > > > <<<<<<<<--------------
> >
> > > --
> > > John Cremona
> >
>
--
John Cremona
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
