Opened 9 years ago

Closed 9 years ago

# unrank via R[i] conflicts with notation for constructing polynomial rings in CartesianProduct

Reported by: Owned by: Darij Grinberg major sage-6.3 algebra notation, algebra, polynomial Marc Mezzarobba, Sage Combinat CC user Nicolas M. Thiéry Travis Scrimshaw N/A 79d4698 79d469861431ac8d6be5ad4edeace1c6ac8a62c8

FF = IntegerModRing(29)
tester = FF._tester()
list(tester.some_elements(CartesianProduct(FF, FF, FF)))

This should give a list of 3-arrays of elements of Z/29. Instead I get:

sage: FF = IntegerModRing(29)
sage: tester = FF._tester()
sage: list(tester.some_elements(CartesianProduct(FF, FF, FF)))
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-3-5d7e71a13340> in <module>()
----> 1 list(tester.some_elements(CartesianProduct(FF, FF, FF)))

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/misc/sage_unittest.pyc in some_elements(self, S)
498             if n > self._max_runs:
499                 from random import sample
--> 500                 S = sample(S, self._max_runs)
501         except (TypeError, AttributeError):
502             # We already can't tell what the length of n is, so

/home/darij/gitsage/sage-5.13.beta1/local/lib/python/random.pyc in sample(self, population, k)
342                         j = _int(random() * n)
--> 344                     result[i] = population[j]
345             except (TypeError, KeyError):   # handle (at least) sets
346                 if isinstance(population, list):

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/combinat/combinat.pyc in __getitem__(self, i)
1220             ValueError: the value must be between 0 and 2 inclusive
1221         """
-> 1222         return self.unrank(i)
1223
1224     def __str__(self):

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/combinat/cartesian_product.pyc in unrank(self, x)
258             raise IndexError("x larger than the size of the Cartesian Product")
259         positions.reverse()
--> 260         return [L[i] for L,i in zip(self.iters, positions)]
261
262     def random_element(self):

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__getitem__ (sage/structure/parent.c:11060)()

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/categories/rings.pyc in __getitem__(self, arg)
859
860             from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
--> 861             return PolynomialRing(self, elts)
862
863     class ElementMethods:

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_ring_constructor.pyc in PolynomialRing(base_ring, arg1, arg2, sparse, order, names, name, var_array, implementation)
467                 raise TypeError("if second arguments is a string with no commas, then there must be no other non-optional arguments")
468             name = arg1
--> 469             R = _single_variate(base_ring, name, sparse, implementation)
470         else:
471             # 2-4. PolynomialRing(base_ring, names, order='degrevlex'):

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_ring_constructor.pyc in _single_variate(base_ring, name, sparse, implementation)
518 def _single_variate(base_ring, name, sparse, implementation):
519     import sage.rings.polynomial.polynomial_ring as m
--> 520     name = normalize_names(1, name)
521     key = (base_ring, name, sparse, implementation if not sparse else None)
522     R = _get_from_cache(key)

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/structure/parent_gens.so in sage.structure.parent_gens.normalize_names (sage/structure/parent_gens.c:2759)()

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/structure/parent_gens.so in sage.structure.parent_gens._certify_names (sage/structure/parent_gens.c:2322)()

ValueError: first letter of variable name must be a letter

And 29 is the smallest number where this seems to throw this error; also, it doesn't fail if I only take the cartesian product of two copies of the field.

I get a similar error if I do CartesianProduct(FF, FF).unrank(3), and this has been around for a while (not just since beta4):

sage: FF = IntegerModRing(3)
sage: CartesianProduct(FF, FF).unrank(3)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-15-98d0a571cc61> in <module>()
----> 1 CartesianProduct(FF, FF).unrank(Integer(3))

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/combinat/cartesian_product.pyc in unrank(self, x)
258             raise IndexError("x larger than the size of the Cartesian Product")
259         positions.reverse()
--> 260         return [L[i] for L,i in zip(self.iters, positions)]
261
262     def random_element(self):

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__getitem__ (sage/structure/parent.c:11060)()

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/categories/rings.pyc in __getitem__(self, arg)
859
860             from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
--> 861             return PolynomialRing(self, elts)
862
863     class ElementMethods:

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_ring_constructor.pyc in PolynomialRing(base_ring, arg1, arg2, sparse, order, names, name, var_array, implementation)
467                 raise TypeError("if second arguments is a string with no commas, then there must be no other non-optional arguments")
468             name = arg1
--> 469             R = _single_variate(base_ring, name, sparse, implementation)
470         else:
471             # 2-4. PolynomialRing(base_ring, names, order='degrevlex'):

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_ring_constructor.pyc in _single_variate(base_ring, name, sparse, implementation)
518 def _single_variate(base_ring, name, sparse, implementation):
519     import sage.rings.polynomial.polynomial_ring as m
--> 520     name = normalize_names(1, name)
521     key = (base_ring, name, sparse, implementation if not sparse else None)
522     R = _get_from_cache(key)

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/structure/parent_gens.so in sage.structure.parent_gens.normalize_names (sage/structure/parent_gens.c:2759)()

/home/darij/gitsage/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/structure/parent_gens.so in sage.structure.parent_gens._certify_names (sage/structure/parent_gens.c:2322)()

ValueError: first letter of variable name must be a letter

So it seems that both bugs are due to the fancy R[x] syntax for polynomial rings conflicting with the R[i] syntax for the i-th element of an enumerated set R, and #8389 didn't cause the error, but at most exposed it better.

This reworks the unrank function in sage.combinat.ranker and uses it for the Cartesian product (this doesn't work for ZZ, see #16239). In followup tickets, we also want to be more systematic about using unrank in TestSuite and do better construction of some_elements() #16244.

### comment:1 Changed 9 years ago by Darij Grinberg

Cc: Marc Mezzarobba added; mmezarobba removed

### comment:2 Changed 9 years ago by Nils Bruin

I think the bug is in unrank, not in the fact that rings use __getitem__ in a funny way. The problem is that a Cartesian product can easily be constructed from iterables, and then should probably be iterable itself, but iterables are not necessarily indexable:

sage: V={1,2,3}
sage: CartesianProduct(V,V).unrank(2)
TypeError: 'set' object does not support indexing
sage: [i for i in CartesianProduct(V,V)]
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]

The function "unrank" should only be applied to indexable cartesian products, i.e., cartesian products of indexables. That's not the same as iterables. In particular,

So the problem is really in tester.some_elements. Indeed, the offending code:

try:
n = _len(S)
if n > self._max_runs:
from random import sample
S = sample(S, self._max_runs)
except (TypeError, AttributeError):

tries sample on S, which apparently leads to calls of the type S[i]. As you can see, the code is prepared to fail, but doesn't expect that to happen with a ValueError. I think this just shows that it's a bit callous to just try and index a structure and hope for the best.

### comment:3 Changed 9 years ago by Darij Grinberg

Hmm. So Sets are not required to define getitem in a reasonable way? Good to know.

### comment:4 Changed 9 years ago by Marc Mezzarobba

Nicolas Thiéry suggested deprecating R[n] in favor of R.unrank(n) at least when R is a ring (see http://trac.sagemath.org/ticket/8389#comment:13), and I tend to agree. If you don't, could you please leave a comment at #15885?

### comment:5 Changed 9 years ago by Darij Grinberg

I agree too if we can do this quickly enough. This is causing problems in #10963...

### comment:6 Changed 9 years ago by Nicolas M. Thiéry

Branch: → u/nthiery/ticket/15919 Mar 12, 2014, 4:51:49 AM → Mar 12, 2014, 4:51:49 AM Mar 12, 2014, 1:39:26 PM → Mar 12, 2014, 1:39:26 PM

### comment:7 Changed 9 years ago by Nicolas M. Thiéry

The above branch takes a first step toward using more systematically the unrank protocol, in that case in CartesianProduct. This should improve the situation and could be deemed good enough for now, but is certainly not a final solution. Also, the unrank function I introduced might be too paranoid: it makes CartesianProduct?.unrank work only with lists, tuples, Parents, xranges; there might be other inputs that are used around. All tests pass though (haven't tried long tests yet).

I agree with Nils though: the sampling in the TestSuite? should not be using [i] to do unranking, and probably should just assume that the object is iterable, and not necessarily unrankable. I'll have a look unless someone beats me to it.

The third alternative, explored by Darij in his branch, is to reinstate temporarily the notation FF[i] for unranking for IntegerModRing? and friends.

What do you think?

New commits:

 ​a4f7fc3 15919: a first step toward using more systematically the unrank protocol

### comment:8 Changed 9 years ago by Nicolas M. Thiéry

Status: new → needs_review

### comment:9 follow-up:  14 Changed 9 years ago by Travis Scrimshaw

Hey Nicolas,

I've expanded upon what unrank can accept (all iterables, even if not in enumerated sets, should now work). I agree the sampling should not use [i] to do unranking, but should we push that to another ticket?

New commits:

 ​5dfb2a2 Merge branch 'u/nthiery/ticket/15919' of trac.sagemath.org:sage into u/tscrim/ticket/15919 ​9b8d022 Expanded what unrank can handle. ​d9b5fcd Added warning about iterator objects.

### comment:10 Changed 9 years ago by Peter Bruin

Not a review, just a tiny remark: the colon before the doctest in cartesian_product.py should be doubled.

### comment:11 Changed 9 years ago by git

Commit: d9b5fcd5df001b38300788a963279bc0c8edf4b6 → 2a5eaa5afc10079d97a122e50372eb19c06d390a

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

 ​2a5eaa5 Fixed double-colon.

### comment:12 Changed 9 years ago by Nicolas M. Thiéry

Hi Travis!

Thanks for the improvement! I made one further step, in particular to avoid trapping too many exceptions; typical situation: a parent L that implements unranking as L[i] and raises an "out of bound" value error.

I am still unhappy about the unrank(ZZ,i) returning something completely wrong (Integer Ring). In case a parent is iterable, I wonder if I would not prefer to prefer the Iterable strategy, and only use __getitem__ if everything else has failed.

Cheers,

Nicolas

Last edited 9 years ago by Nicolas M. Thiéry (previous) (diff)

### comment:13 Changed 9 years ago by Nicolas M. Thiéry

Branch: u/tscrim/ticket/15919 → u/nthiery/ticket/15919

### comment:14 in reply to:  9 Changed 9 years ago by Nicolas M. Thiéry

Commit: 2a5eaa5afc10079d97a122e50372eb19c06d390a → bbd22f1422f7b643a55afabeb44cfd8204b7dd3b

I agree the sampling should not use [i] to do unranking, but should we push that to another ticket?

+1. Let's focus here on what's needed for #10963.

New commits:

 ​f9b59fa Merge branch 'develop=6.2.rc0' into ticket/15919-unrank ​bbd22f1 - Use __getitem__ only on sequences and Parents not in EnumeratedSets

### comment:15 Changed 9 years ago by Nicolas M. Thiéry

Ah shoot, the sampling issue actually occurs with #10963.

At this point I am tempted to remove the sampling altogether in InstanceTester?.some_elements, and instead have it always return a list (or iterator?) of the first max_run elements (or less if S does not have that many). Then, the only requirement on S would be to be iterable.

The code would then just be:

def some_elements(self, S=None):
if S is None:
if self._elements is None:
S = self._instance.some_elements()
else:
S = self._elements
import itertools
return list(itertools.islice(S,0,self._max_runs))

I am now running the tests with #10963 and this change.

Cheers,

Nicolas

### comment:16 Changed 9 years ago by Nicolas M. Thiéry

With just this change (and not the rest of the stuff in this branch), #10963 passes all tests.

At this point, I am tempted to split this ticket into two tickets:

What do you think?

### comment:17 follow-up:  19 Changed 9 years ago by Travis Scrimshaw

(Much) More of me says this change to InstanceTester.some_elements() is significantly better (and might even be faster for things that are hard to repeatably iterate over like crystals) than loosing the possibility that (over enough repeated tests) we get "most" elements of a very large finite set (and without calculating __len__(), which also might be expensive or error catching). So I'm saying let's make this change, the question is where. I'd be happy doing it right here.

I'd say the problem with ZZ is that it is not in the correct category, which is now #16239. I've also made some very minor doctweaks, so I'm pos_rev with the current state (up to where to make the change above).

Best,
Travis

### comment:18 Changed 9 years ago by Travis Scrimshaw

Branch: u/nthiery/ticket/15919 → u/tscrim/ticket/15919 bbd22f1422f7b643a55afabeb44cfd8204b7dd3b → 79d469861431ac8d6be5ad4edeace1c6ac8a62c8

New commits:

 ​5d2d335 Merge branch 'develop' into u/tscrim/ticket/15919 ​382b9ff Merge branch 'u/nthiery/ticket/15919' of trac.sagemath.org:sage into u/tscrim/ticket/15919 ​79d4698 Some last very minor tweaks to ranker.py.

### comment:19 in reply to:  17 Changed 9 years ago by Nicolas M. Thiéry

(Much) More of me says this change to InstanceTester.some_elements() is significantly better (and might even be faster for things that are hard to repeatably iterate over like crystals) than loosing the possibility that (over enough repeated tests) we get "most" elements of a very large finite set (and without calculating __len__(), which also might be expensive or error catching). So I'm saying let's make this change, the question is where. I'd be happy doing it right here.

Ok, glad to see we are on the same line. I have created #16244 for just this piece. I'll push my little change there later.

I'd say the problem with ZZ is that it is not in the correct category, which is now #16239. I've also made some very minor doctweaks, so I'm pos_rev with the current state (up to where to make the change above).

Ok, I am happy with your change. So I guess this can be positive reviewed. There remains to update the description of this ticket to better reflect what has actually been done, and refer to the other ticket for the actual solution of the original issue.

### comment:20 Changed 9 years ago by Travis Scrimshaw

Description: modified (diff) needs_review → positive_review Notation S[i] for i-th element of enumerated set S conflicts with notation R[x] for polynomial ring → unrank via R[i] conflicts with notation for constructing polynomial rings in CartesianProduct

Done and done.

### comment:21 Changed 9 years ago by Travis Scrimshaw

Authors: → Nicolas M. Thiéry → Travis Scrimshaw

Thanks Travis!

### comment:23 follow-up:  24 Changed 9 years ago by Darij Grinberg

The only thing that somewhat worries me is the speed. Before:

sage: T = range(20)
sage: C = CartesianProduct(T,T,T)
sage: %timeit C.unrank(3)
100000 loops, best of 3: 15 µs per loop

After:

sage: T = range(20)
sage: C = CartesianProduct(T,T,T)
sage: %timeit C.unrank(3)
10000 loops, best of 3: 35.5 µs per loop

(These timings are fairly independent on the 20 and the 3...)

I don't know how often this unranking is used, though, and whether these µs add up...

Last edited 9 years ago by Darij Grinberg (previous) (diff)

### comment:24 in reply to:  23 Changed 9 years ago by Nicolas M. Thiéry

The only thing that somewhat worries me is the speed. Before: ... I don't know how often this unranking is used, though, and whether these µs add up...

Ah good point; the isinstance and in EnumeratedSets checks cause a little overhead which is non negligible for inputs that have super fast unranking (like lists).

My impression is that this unranking is not used much. If it really became a bottleneck, a reasonable fix would be to have CartesianProduct? build unranking functions once for all upon the first unrank (I started toying with this in u/nthiery/15919-unrank-unrank-from), so that the above checks would be done only once.

Besides, things should eventually resolve by themselves as CartesianProduct? gets progressively replaced by cartesian_product (for which the inputs are parents, or coerced into parents), and parents implement more systematically the unrank protocol.

So altogether, in this balance between overhead and correctness, I would lean here toward correctness. What do you think?

### comment:25 follow-up:  26 Changed 9 years ago by Darij Grinberg

I am not suggesting to go against correctness! My original idea on this ticket was to de-prioritize the notation R[x] for a polynomial ring or a subalgebra generated by x, because that notation is really syntactic sugar. So it's speed vs. convenience. But looking at Travis's posts I am no longer sure if this would have fixed all issues. Anyway, since unrank and CartesianProduct? aren't very much used together, this is not an issue.

### comment:26 in reply to:  25 Changed 9 years ago by Nicolas M. Thiéry

I am not suggesting to go against correctness!

Oops, sorry if my wording involuntarily implied this :-) I just meant that I was ready paying a little speed overhead as a price for a solution of the problem. And I agree the problem worked on this ticket (being cleaner with unrank versus __getitem__) has deviated from the original one. Not so bad since I believe this + #16244 fixes reasonably the original problem.

Unless someone raises an objection now, this is good to go!

Thanks to both of you.

### comment:27 Changed 9 years ago by For batch modifications

Milestone: sage-6.2 → sage-6.3

### comment:28 Changed 9 years ago by Volker Braun

Branch: u/tscrim/ticket/15919 → 79d469861431ac8d6be5ad4edeace1c6ac8a62c8 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.