On Jan 22, 2008 3:46 AM, John Cremona <[EMAIL PROTECTED]> wrote:
>
> Thoughts on this thread:
>
> For finite fields (or any other fields) the concept of additive
> generator makes no sense -- only finite prime fields have one and it
> is hardly a useful concept then since every nonzero element is one.
> It's different if talking about generators (plural!) which I think is
> what David Kohel meant, but here we are talking about what F.gen()
> should be.
Agreed. Also, I agree with David that additive_generators() (plural)
could be useful.
Though much more useful is an explicit isomorphism with a vector
space (which we have already).
> By contrast F.multiplicative_gen() does make sense for all finite
> fields so should be provided, though not necessarily computed until
> requested for the reasons given by Martin. (It seems that with the
> current implementation of non-prime fiinite fields this comes for
> free, but that might change.)
Only for the Givaro ones, i.e., up to 2^16. For general fields it is not
for free, unfortunately (I think).
> As for F.gen() it might be worth thinking more generally about what
> one means by "*the* generator" of a field.
It's a *choice* of generator which is part of the
structure of the object. In Sage -- like in Magma -- pretty much
every structure is generated by some explicit list of objects (possibly
modulo relations) over some canonical base, and that list of objects
is part of the definition of the structure -- e.g., there are vector spaces
with basis, not abstract vector spaces. That's the key idea
in the design of Magma, and Sage really benefits from taking the
same approach.
> Again the concept only
> makes sense for some fields: those which are generated by a single
> element over their prime field (so: any number field, any finite
> field, or the function fields in one variable over QQ or GF(p)); or,
> more generally for fields constructed as relative extensions of other
> fields, we could include finite (algebraic) extensions of any field at
> all, and function fields in one variable over any field.
Actually multiple generators make sense. That's why there
is a gens() method on objects. Vector spaces, e.g., have multiple
generators.
>
> Arguably, neither QQ nor GF(p) require any generators at all, but for
> consistency with general number fields and finite fields it would be
> reasonbly to have F.gen() return any nonzero element, and why not fix
> it as F(1).
It is incredibly useful if (1) things are consistent, so one can write
generic code, and (2) if it is easy to remember what the choices
are, which is possibly an argument for F(1) being the generator
for GF(p). In fact, I chose 1 as the generator for GF(p), for
consistency with other prime fields and the integers, which I
also had no choice but to choose 1. I also chose 1 since
it's what Magma does:
sage: magma.eval('GF(19).1')
'1'
In general, when implementing objects that are very similar
to things in Magma, I see no reason to radically
change the design of Sage from the
design of Magma, unless there is a compelling reason to do so.
Frankly, there is a lot I really like about the design
of Magma.
> There should certainly be no expectation that F.gen() be a
> multiplicative generator, even if it often is -- so perhaps a warning
> in the documentation should tell users to use F.multiplicative_gen()
> if that's what they really need.
+1
Warnings in the documentation with examples are a good idea
in this case.
> As for order(), I would be happy for it not to be implemented at all
> for elements of a field! For additive order it is completely
> redundant since all nonzero elements have the same order depending
> only on the characteristic.
I'm not sure that it is all bad that it is redundant. At least right now
I can write generic code that I might not be able to write were that
method removed. Say I write a function that does "blah blah" in an
additive group.
I can just toss it field elements and it will work. If I ban the
additive_order()
command then it breaks for no good reason.
Also the order and additive_order commands are automatically there because
there is a class hierarchy and they are defined in class higher up the
hierarchy.
> For multiplicative order it is useful
> (for nonzero elements of course), but would it not be better, if you
> needed mutiplicative orders, to create the multiplicative group of the
> field as an abelian group and ask for the order of an element in that
> context?
That's what you do in Magma right? And it's your only option, right?
I definitely think that functionality should be supported in Sage. But
I can't at all understand why that should be the only option.
On the other hand, maybe I'm wrong. Here is a cautionary tail that
is perhaps pointless, but I'll tell it.
I remember once thinking that was the natural way to do things in Magma.
So I wanted to demo discrete logs in finite fields for my students in
class once (in 2002), and did the very natural coercion to the multiplicative
group as an abstract group, discrete log, etc., and it was insanely slow.
I was baffled how Magma could be so slow at discrete log. It turned
out there was a special function for asking for the discrete log directly
in the finite field that was vastly faster (but accomplished the same thing).
> This links in with something I needed to be able to do: given an
> element a of GF(q) qith q a non-prime prime power, to return the
> degree of a, meaning the smallest n such that a is in GF(p^n). One
> could work this out from the (mutiplicative) order of a, which might
> be efficient if GF(q)'s multiplicative generator was already known
> together with the factorization of q-1. Or it's the degree of the
> minimal polynomial of a over GF(p).
>
> More generally, given a field F which is an extension of some base
> field k and an element a of F it would be nice to be able to construct
> the subfield k(a) of F together with a suitable embedding into F and
> an element in it which maps to a. But this is getting too far afield
> ;), so I'll shut up.
+1 to all your feature requests in the above two paragraphs. I think
those are excellent illustrations to motivative developing good
functionality.
-- William
--~--~---------~--~----~------------~-------~--~----~
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://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
