"R.<a> =" syntactic sugar incorrect for EquationOrder

[emassop]

After typing

sage: f = x^2+1
sage: R.<i> = ZZ.extension(f)

I expect variable i to be the element of R named 'i'. However, it is not. It is the element 1.

This is due to the generators of an order in Sage being its module generators (as noted by EquationOrder?):

sage: R.gens()
[1, i]

We fix this by redefining _first_ngens() (which is what the preparser uses to implement the R.<x> = syntax) to use _defining_names(), which we override for orders.

[bruno]

Is it really the syntactic sugar that poses problem? It seems that inject_variables() is the problem.

sage: f = x^2+1
sage: R = ZZ.extension(f,'i')
sage: R.inject_variables()
Defining i
sage: i
1

The problem seems to come from the fact that R.variable_names() is ('i',) while R.gens() is [1,i], and a zip is called on these two objects, resulting in [('i',1)].

[jdemeyer]

I would prefer solution (1) which is most consistent with other uses of gens().

[emassop]

Changing gens() would definitely also be my preferred solution. My concern is that there might be code that assumes that gens() returns a list of module generators, which would no longer be the case.

[jdemeyer]

Replying to emassop:

Changing gens() would definitely also be my preferred solution. My concern is that there might be code that assumes that gens() returns a list of module generators, which would no longer be the case.

That's not a major problem. For R.<x> = to work, it suffices to change the _first_ngens() method (without deprecation).

We could then add a boolean argument ring to gens(), defaulting to False (deprecated) which returns the ring generator (i.e. new-style gens()) if ring=True.

[tscrim]

I agree with Jeroen that you should do (1). If something is dependent on assuming they are module generators, then they can use something like module_generators() (perhaps this needs such an implementation). See also #15381.

[jdemeyer]

Replying to tscrim:

If something is dependent on assuming they are module generators, then they can use something like module_generators()

No need for a new method, there is already basis() which does exactly that (currently gens() simply calls basis()).

[cremona]

Just a comment: not every order is monogenic, so it is not so clear what gens() should return in general if not module generators, though of course this particular construction will always produce a monogenic order.

Back to the original task I was trying, it is a pity if there is not a simple one-liner to define a ring of the form Z[a] from a polynomial (min poly of a) and simultaneously assigne the value a to a variable called a.

[jdemeyer]

Replying to cremona:

Just a comment: not every order is monogenic, so it is not so clear what gens() should return in general

I wouldn't mind raise ArithmeticError...

[jdemeyer]

New commits:

​dac0a4c

Let "R.<x> =" syntax use ring_generators if possible

[emassop]

I don't really like unconditionally preferring ring_generators() in such a general place as _first_n_gens() is. Perhaps this should be something like defining_generators() instead of ring_generators(). This would be set when defining something by generators, and always refer to the generators from the definition. That said, s/ring/defining/ can be done later, so out of pragmatism I'm not against the current approach.

However, the current approach with ring_generators() doesn't always work as expected, which could be considered be a separate bug (namely lack of prepopulating ring_generators if defining something by ring generators). For instance

K.<i> = NumberField(x^2+1)
O = K.order(-i+1)
gens = O.ring_generators()
if gens == [-i+1]:
  print "O.<a> = K.order(-i+1) would work as expected"
else:
  print "O.<a> = K.order(-i+1) would make a equal to %r, not as -i+1 as expected." % gens[0]

prints

O.<a> = K.order(-i+1) would make a equal to i, not as -i+1 as expected.

on ​https://sagecell.sagemath.org/.

What do you think? Which ?_gens should generally be used and should populating ?_gens with the defining generators be separate bugs?

[jdemeyer]

Replying to emassop:

K.<i> = NumberField(x^2+1)
O = K.order(-i+1)

That's a bit harder to solve since there currently is no way to recover the -i+1 used to create the order. We would need to change def order(...) to store the given generators.

[jdemeyer]

If you want this to work:

sage: K.<i> = NumberField(x^2+1)
sage: O.<a> = K.order(-i+1)
sage: a
-i + 1

you'll need to drop unique representation for orders: currently, the following two return the exact same object:

sage: O1 = K.order(-i+1)
sage: O2 = K.order(-i)
sage: O1 is O2
True

You cannot have O1.defining_generators() and O2.defining_generators() be different if O1 is the same object as O2. So this cannot be fixed without making major changes.

[cremona]

We don't have unique representation for fields:

sage: K1 = QQ[sqrt(2)]                                                                                
sage: K2 = QQ[1+sqrt(2)] 
sage: K1
Number Field in sqrt2 with defining polynomial x^2 - 2
sage: K2
Number Field in a with defining polynomial x^2 - 2*x - 1                                                                         
sage: K1 is K2
False
sage: K1 == K2                                                                                        
False
sage: K1.is_isomorphic(K2)                                                                            
True

in a rather similar context.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e857c9a

New method defining_generators() to implement R.<a> =

[jdemeyer]

Replying to emassop:

I don't really like unconditionally preferring ring_generators() in such a general place as _first_n_gens() is. Perhaps this should be something like defining_generators() instead of ring_generators(). This would be set when defining something by generators, and always refer to the generators from the definition.

Done.

[jdemeyer]

Replying to cremona:

We don't have unique representation for fields:

Well, it all boils down to the difference between "equal" and "isomorphic" which is really a difference in how we use mathematics and not in mathematics itself.

In your example with K1 and K2, one could argue that those fields are not equal because there is no canonical (again, this is not a mathematically well-defined term) isomorphism.

For orders on the other hand, it makes a lot of sense to see orders as subsets of a number field. Then obviously two orders are equal if they are the same subset of the number field. That's the view that Sage uses. I admit that it's all quite subtle.

Regardless, I don't think that this should hold back this ticket. I'm sure that many people have stumbled on the bug on this ticket, so let's just fix it. It also makes it possible to implement #7545. We can still look at further subtleties later.

[emassop]

My point about wanting O.<foo> = K.order(-i+1) to work is moot, because .order doesn't take a names argument, so that the syntactic sugar doesn't work in this case anyway.

As far as I can tell these patches indeed fix R.<a> = EquationOrder(f) and R.<a> = ZZ.extension(f), where f is a polynomial. Also AFAICT, this is by virtue of NumberField using 1, a, a^2, ... as basis, and other things normalizing to that basis.

I tried for instance the following to make sure ring_generators could not be distracted:

from sage.rings.number_field.order import AbsoluteOrder
K.<i> = NumberField(x^2+1)
V, from_v, to_v = K.vector_space()
O = AbsoluteOrder(K, span([to_v(1), to_v(-i)], ZZ))
print O.ring_generators() == [i]  # True, so the ring generator is i, not -i.

However, these patches do not fix the case of R<several letters> = .... For instance

O.<a,b> = EquationOrder([x^2+1, x^2+2])
print O.ring_generators()

prints [-b*a - 1, -3*a + 2*b] which for this patch to work should be [a,b]. (Incidentally, that first and confusing line is used in the docstring of EquationOrder. Can you get rid of that, or comment on its unexpected consequences for variables a and b?)

Replying to jdemeyer:

Replying to emassop:

I don't really like unconditionally preferring ring_generators() in such a general place as _first_n_gens() is. Perhaps this should be something like defining_generators() instead of ring_generators(). This would be set when defining something by generators, and always refer to the generators from the definition.

Done.

Changing defining_generators is indeed dangerous. Perhaps there could be defining_generators.set(...) that would

• populate the cache if it has no value,
• do nothing if the cache and the argument agree,
• populate the cache with an invalid value when the argument and the cache disagree.

The invalid value would make a call to defining_generators raise an exception. Also, how does the cache behaving with pickling? Does a cache override get saved?

Finally, does it make sense to define defining_generators in category_object.pyx as simply gens(), and put the override to ring_generators in class Order?

Pain, pain, pain. I think it's okay to pragmatically go with this approach now.

Some speculation, since my ideas keep changing about this: Perhaps the preparser should translate a.<b> = c(d) to a,(b,) = c._call_and_also_return_names(d, names=('b',)). Then _call_and_also_return_names gets responsible for calling c and making sure the returned generators are the right ones. When c is a function, this can be implemented using a decorator, or next to c itself. For classes c, _call_and_also_return_names can be a class method of CategoryObject which calls instantiates an object and calls _first_n_gens on it. This would also circumvent the hack of prepopulating and having to change the cache of defining_generators. Of course this seems like a bigger change than this bug, so let's do the pragmatic thing first.

[jdemeyer]

Replying to emassop:

Perhaps there could be defining_generators.set(...) that would

• populate the cache if it has no value,
• do nothing if the cache and the argument agree,
• populate the cache with an invalid value when the argument and the cache disagree.

The invalid value would make a call to defining_generators raise an exception.

I see no reason for this additional layer of complexity. I don't know of any cached function in Sage which does this and I don't see why defining_generators would need it.

Also, how does the cache behaving with pickling? Does a cache override get saved?

Yes, it gets pickled although this might be changed in #15692.

Finally, does it make sense to define defining_generators in category_object.pyx as simply gens(), and put the override to ring_generators in class Order?

I don't really see why. Currently, Order is the only class with ring_generators but if a new class comes around implementing ring_generators, I guess (but this is really guessing) that it would make sense to use it as defining generators.

[jdemeyer]

Replying to emassop:

Finally, does it make sense to define defining_generators in category_object.pyx as simply gens(), and put the override to ring_generators in class Order?

Thinking twice about it, maybe this approach could help solving the problem for relative EquationOrders.

[emassop]

Replying to jdemeyer:

Replying to emassop:

Perhaps there could be defining_generators.set(...) that would

• populate the cache if it has no value,
• do nothing if the cache and the argument agree,
• populate the cache with an invalid value when the argument and the cache disagree.

The invalid value would make a call to defining_generators raise an exception.

I see no reason for this additional layer of complexity. I don't know of any cached function in Sage which does this and I don't see why defining_generators would need it.

It seems weird if the return value of .defining_generators changes during an object's life. If the value gets set only once during an object's life-time (and survives pickling), then not having this additional complexity is okay. The proposal above is merely to enforce that the value does not get changed accidentally.

Finally, does it make sense to define defining_generators in category_object.pyx as simply gens(), and put the override to ring_generators in class Order?

I don't really see why. Currently, Order is the only class with ring_generators but if a new class comes around implementing ring_generators, I guess (but this is really guessing) that it would make sense to use it as defining generators.

So all other rings with generators use gens() for their ring generators? Why is Order different, especially given that there also is basis()?

For instance

R.<i> = ZZ.extension(x^2+1)
S.<x> = QQ[]

A.<a> = QQ.extension(x^2-3)
B.<b> = ZZ.extension(x^2-3)
C.<c> = R.extension(x^2-3)
D.<d> = S.extension(x^2-3)

print A.gens(), B.gens(), C.gens(), D.gens()

prints (a,) [1, b] (c,) (d,) with B.gens() being the odd one out.

[jdemeyer]

Replying to emassop:

It seems weird if the return value of .defining_generators changes during an object's life. If the value gets set only once during an object's life-time (and survives pickling), then not having this additional complexity is okay. The proposal above is merely to enforce that the value does not get changed accidentally.

I don't see how the value could get changed accidentally. And like I said: there are many cached functions in Sage, what makes this one so special?

So all other rings with generators use gens() for their ring generators? Why is Order different, especially given that there also is basis()?

Very good question. Unfortunately, because of the deprecation policy, we cannot just change gens().

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​af00767

Deprecate Order.gens()

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​008fc69

_defining_generators() should be private

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b1a2b4f

Use _defining_generators to implement gens_dict()

[emassop]

Replying to jdemeyer:

Replying to emassop:

It seems weird if the return value of .defining_generators changes during an object's life. If the value gets set only once during an object's life-time (and survives pickling), then not having this additional complexity is okay. The proposal above is merely to enforce that the value does not get changed accidentally.

I don't see how the value could get changed accidentally. And like I said: there are many cached functions in Sage, what makes this one so special?

The docstring says "This is cached, so we can manually set the result if required". As such, it seems intended for the cache to contain a value that would not be the result of executing the function. (Otherwise you would not need to set it manually.) This is against the idea of a cache as an optimization that speeds up a function call by remembering the previous result.

Does the ​docstring change of RelativeOrder.basis affect the community's ability to change this function's behavior? It previously seemed to me that it could start returning a basis relative to the base order at any time.

Why is it okay to change gens_dict, but not gens itself?

Hack: What about reordering the result of gens() (or probably basis?) such that desired generators form a prefix? Then the syntactic sugar would work because it uses only the first n items.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a354f9e

Do not mention set_cache()

[jdemeyer]

Replying to emassop:

The docstring says "This is cached, so we can manually set the result if required".

Fixed.

Does the ​docstring change of RelativeOrder.basis affect the community's ability to change this function's behavior?

I don't think so. I simply changed the docstring to the reality.

Why is it okay to change gens_dict, but not gens itself?

Because of the way how gens_dict() is used: gens_dict is supposed to return a dict of generators with their name as key. For example, it is often used to name variables for an eval() statement. So philosophically this is closer to _defining_generators() than to gens().

Hack: What about reordering the result of gens() (or probably basis?) such that desired generators form a prefix?

I would guess that would break stuff. I wouldn't be surprised if there was code assuming that 1 is the first element of basis().

[emassop]

Replying to jdemeyer:

Replying to emassop:

The docstring says "This is cached, so we can manually set the result if required".

Fixed.

Yeah, this works :).

Why is it okay to change gens_dict, but not gens itself?

Because of the way how gens_dict() is used: gens_dict is supposed to return a dict of generators with their name as key. For example, it is often used to name variables for an eval() statement. So philosophically this is closer to _defining_generators() than to gens().

Reading gens_dict as a dict version of gens, I would expect the same values to be present in gens_dict as in gens. However, with gens deprecated, maybe this is okay.

Hack: What about reordering the result of gens() (or probably basis?) such that desired generators form a prefix?

I would guess that would break stuff. I wouldn't be surprised if there was code assuming that 1 is the first element of basis().

Yeah, that seems likely :(. We can use such a trick to fix R.<several letters> = though, by prepending [x for x in self.number_field().gens() if x in self] to remaining in .ring_generators. I don't like it very much, but I think it could work.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​496f5ac

Implement Order._defining_generators() using the number field gens

[jdemeyer]

I now changed _defining_generators() to use the number field gens instead. This fixes the case of relative extensions.

[emassop]

Replying to jdemeyer:

I now changed _defining_generators() to use the number field gens instead. This fixes the case of relative extensions.

Disregarding the change to gen_dict(), this makes sense to me. I would on first sight argue that defining_generators should not be defined for an order that has not been defined by generators, but since this is a private method used only by R.<...> (disregarding gen_dict), which moreover throws an exception if the elements are not in the order, I think it's fine here.

Taking gen_dict() back into the picture, I'm not so happy with its elements not necessarily generating the order anymore (as a module, or as a ring), as there is nothing in the name gen_dict that suggests this would not be the case. For instance

K.<a> = QuadraticField(-163)
R = K.ring_of_integers()
dict_gens_values = [R(x) for x in K.gens()]
S = K.order(dict_gens_values)
print S.index_in(R)

prints 2 instead of the expected 1.

Tangentially, NumberField.ring_of_integers should pass its arguments to self.maximal_order, in the same way that NumberField.OK does. (For the deprecation policy, this is probably not currently feasible, but we can deprecate non-empty arguments.) As a side-effect, this prohibits the syntax R.<w> = K.ring_of_integers(), in the same that R.<w> = K.order(...) is prohibited (which made one of my earlier points moot). This also makes the following impossible, where w does not become the expected generator:

K.<a> = QuadraticField(-163)
R.<w> = K.ring_of_integers()
w = a # Since I'm not running the version with the patch.
print K.order(w).index_in(R)  # R.<w> suggests this prints 1, but it actually prints 2.

[jdemeyer]

Replying to emassop:

K.<a> = QuadraticField(-163)
R.<w> = K.ring_of_integers()
w = a # Since I'm not running the version with the patch.
print K.order(w).index_in(R)  # R.<w> suggests this prints 1, but it actually prints 2.

I don't see why R.<w> suggests that K.order(w) == K.ring_of_integers(). I do agree that ring_of_integers, OK and maximal_order should all behave exactly the same.

[jdemeyer]

Replying to emassop:

Taking gen_dict() back into the picture, I'm not so happy with its elements not necessarily generating the order anymore (as a module, or as a ring), as there is nothing in the name gen_dict that suggests this would not be the case.

Well, gens_dict() is used to extract all "variable names" (that is what the docstring says and that is how it is used in practice). Perhaps the name gens_dict() is badly chosen, but I would not change that now. Maybe a better name would have been variables_dict() or named_elements() or something.

If you see it this way, using _defining_generators() is a better choice than gens().

[emassop]

Replying to jdemeyer:

Replying to emassop:

K.<a> = QuadraticField(-163)
R.<w> = K.ring_of_integers()
w = a # Since I'm not running the version with the patch.
print K.order(w).index_in(R)  # R.<w> suggests this prints 1, but it actually prints 2.

I don't see why R.<w> suggests that K.order(w) == K.ring_of_integers(). I do agree that ring_of_integers, OK and maximal_order should all behave exactly the same.

What do you expect w to become in R.<w> =, if not a generator of R?

[emassop]

Replying to jdemeyer:

Replying to emassop:

Taking gen_dict() back into the picture, I'm not so happy with its elements not necessarily generating the order anymore (as a module, or as a ring), as there is nothing in the name gen_dict that suggests this would not be the case.

Well, gens_dict() is used to extract all "variable names" (that is what the docstring says and that is how it is used in practice). Perhaps the name gens_dict() is badly chosen, but I would not change that now. Maybe a better name would have been variables_dict() or named_elements() or something.

If you see it this way, using _defining_generators() is a better choice than gens().

Okay, that makes sense. Perhaps _defining_generators should be renamed too then? Perhaps _definition_names or some such? (I like 'names' because it corresponds to the argument names that is passed to f when doing a.<x> = f(...).)

[jdemeyer]

Replying to emassop:

What do you expect w to become in R.<w> =, if not a generator of R?

The element named "w".

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c41d59c	Pass *args and **kwds in ring_of_integers()
​64618f5	Rename _defining_generators -> _defining_names

[emassop]

Replying to jdemeyer:

Replying to emassop:

What do you expect w to become in R.<w> =, if not a generator of R?

The element named "w".

Sure, but which element would be named "w"? Anyway, this is moot now :).

[emassop]

Some comments on the docstring of _defining_names:

• There is a test for orders, which have this method overridden, so I think it would be better to move this test.
• I'm not sure about the example "For vector spaces and free modules, we get a basis", given that submodules normalize the basis they are given as input, so that _defining_names does not necessarily return the basis that the submodule was defined with. For instance

  V = ZZ^3
  vectors = [(0,1,0), (1,3/2,0)]
  M = V.span(vectors)
  print M.basis()
  

  prints

  [
  (1, 1/2, 0),
  (0, 1, 0)
  ]
  

  Could you mention something like this as a caveat for this method? Or perhaps get rid of this example, given that this method really only is interesting for things defined by some explicitly named elements?
• Please get rid of "generator" and perhaps mention the names argument used by R.<...> =

Otherwise, this all looks good to me.

[jdemeyer]

Replying to emassop:

Some comments on the docstring of _defining_names:

• There is a test for orders, which have this method overridden, so I think it would be better to move this test.

There are already two tests for orders in order.py, so I don't think we need to add an additional test. I think the test in category_object.pyx is useful to refer to this ticket and the general discussion of _defining_names().

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​bae80ec

Minor documentation improvements

[jdemeyer]

Thanks for the review!

Remember to fill in your name as Reviewer.

[vbraun]

Reviewer name

[emassop]

Putting my name in Reviewers this time. Why can't Trac fill that in?

[jdemeyer]

Volker, it would make a lot of sense to merge this in Sage 7.0, is that still possible?