make iter(ZZ^n) useful

[yyyyx4]

At the moment, iterating over ZZ^n only ever produces vectors in ℤ × {0}^(n-1):

sage: for i,v in enumerate(ZZ^5):
....:     print(v)
....:     if i > 10: break
....:
(0, 0, 0, 0, 0)
(1, 0, 0, 0, 0)
(-1, 0, 0, 0, 0)
(2, 0, 0, 0, 0)
(-2, 0, 0, 0, 0)
(3, 0, 0, 0, 0)
(-3, 0, 0, 0, 0)
(4, 0, 0, 0, 0)
(-4, 0, 0, 0, 0)
(5, 0, 0, 0, 0)
(-5, 0, 0, 0, 0)
(6, 0, 0, 0, 0)

This patch makes Sage iterate over ZZ^n in a more natural order: Sorted primarily by 1‑norm, secondarily by ∞‑norm.

There are two motivations to prefer this behavior in particular:

1. It is mathematically more correct — iter(ZZ^n) now actually enumerates all of ℤ^n rather than just a subset.
2. It can be useful in some situations (such as in cryptography) when searching for a small error vector of some sort.

CC: @tscrim

Component: categories

Author: Lorenz Panny, Aleksei Udovenko

Branch: a001b6d

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/33287

[mkoeppe]

comment:2

I think this should be fixed on the level of categories:

sage: ZZ^2 in EnumeratedSets()
False

[mkoeppe]

comment:3

CartesianProduct has the same defect, but at least emits a warning:

sage: i = iter(ZZ.cartesian_product(ZZ))
sage: next(i)
/Users/mkoeppe/s/sage/sage-rebasing/worktree-gcc11/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/categories/sets_cat.py:2249: UserWarning: Sage is not able to determine whether the factors of this Cartesian product are finite. The lexicographic ordering might not go through all elements.
  warn("Sage is not able to determine whether the factors of "
(0, 0)
sage: 
sage: next(i)
(0, 1)
sage: next(i)
(0, -1)
sage: next(i)
(0, 2)
sage: next(i)
(0, -2)
sage: next(i)
(0, 3)
sage: next(i)
(0, -3)
sage: next(i)
(0, 4)
sage: next(i)
(0, -4)
sage: next(i)
(0, 5)

[tscrim]

comment:5

I agree that it would be good to have such an implementation at the category level. Although we did have a reason for not doing something like this IIRC. I forget if it was backward compatibility, breaking doctests, slowdowns, or something else.

For this ticket, can you also add a doctest that shows it works over other enumerated rings, such as GF(2)[‘t’]? It should work for any infinite enumerated ring.

[yyyyx4]

comment:6

Replying to @tscrim:

For this ticket, can you also add a doctest that shows it works over other enumerated rings, such as GF(2)[‘t’]? It should work for any infinite enumerated ring.

Well... It doesn't:

sage: GF(2)['t'] in InfiniteEnumeratedSets()
False

Indeed, iter(GF(2)['t']) throws a NotImplementedError.

It looks like ZZ is the only ring that's registered as an InfiniteEnumeratedSet.

[tscrim]

comment:7

You get the same category result for changing the base ring to ZZ:

sage: ZZ['t'] in InfiniteEnumeratedSets()
False

which IMO is a bug. (You also get a NotImplementedError for iter(ZZ['t']).)

However, there should still be other infinite enumerated rings that are not so nice.

Interestingly

sage: QQ in InfiniteEnumeratedSets()
False

but it iterates just fine. IMO also a bug. I also cannot iterate the braid groups, which I should be able to since they are finitely generated as a monoid. Group algebras over enumerated monoids should also work for this, but they don't as they fail through a strange (IMO) code path:

sage: G = groups.misc.CoxeterGroup(['A',2,1])
sage: G in InfiniteEnumeratedSets()
True
sage: A = G.algebra(GF(2))
sage: A in InfiniteEnumeratedSets()
False
sage: next(iter(A))
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-49-8fa11f66d58c> in <module>
----> 1 next(iter(A))

~/sage-build/local/lib/python3.9/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.__getitem__ (build/cythonized/sage/structure/parent.c:11472)()
   1274             except AttributeError:
   1275                 return self.list()[n]
-> 1276         return meth(n)
   1277 
   1278     #########################################################################

~/sage-build/local/lib/python3.9/site-packages/sage/categories/rings.py in __getitem__(self, arg)
   1175 
   1176             from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
-> 1177             return PolynomialRing(self, elts)
   1178 
   1179         def free_module(self, base=None, basis=None, map=True):

~/sage-build/local/lib/python3.9/site-packages/sage/rings/polynomial/polynomial_ring_constructor.py in PolynomialRing(base_ring, *args, **kwds)
    630             raise TypeError("you must specify the names of the variables")
    631 
--> 632     names = normalize_names(n, names)
    633 
    634     # At this point, we have only handled the "names" keyword if it was

~/sage-build/local/lib/python3.9/site-packages/sage/structure/category_object.pyx in sage.structure.category_object.normalize_names (build/cythonized/sage/structure/category_object.c:8565)()
    898         return dir_with_other_class(self, self.category().parent_class)
    899 
--> 900 cpdef normalize_names(Py_ssize_t ngens, names):
    901     r"""
    902     Return a tuple of strings of variable names of length ngens given

~/sage-build/local/lib/python3.9/site-packages/sage/structure/category_object.pyx in sage.structure.category_object.normalize_names (build/cythonized/sage/structure/category_object.c:8407)()
   1012                 names = sage.misc.defaults.variable_names(ngens, names)
   1013 
-> 1014     certify_names(names)
   1015     if ngens >= 0 and len(names) != ngens:
   1016        raise IndexError("the number of names must equal the number of generators")

~/sage-build/local/lib/python3.9/site-packages/sage/structure/category_object.pyx in sage.structure.category_object.certify_names (build/cythonized/sage/structure/category_object.c:8923)()
   1064             raise ValueError("variable name {!r} is not alphanumeric".format(N))
   1065         if not N[0].isalpha():
-> 1066             raise ValueError("variable name {!r} does not start with a letter".format(N))
   1067         if N in s:
   1068             raise ValueError("variable name {!r} appears more than once".format(N))

ValueError: variable name '0' does not start with a letter

Nothing in this code seems to be specific to ZZ, just Sage doesn't have put enough objects into the correct category (with the corresponding implementations) to support it.

Perhaps for now we can just change the documentation to say this works for any infinite enumerated (commutative) ring?

[sagetrac-git]

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

a8a2ba2	Merge tag '9.6.beta1' into public/iter_ZZ_n
a001b6d	mention category in documentation

[sagetrac-git]

Changed commit from 0401135 to a001b6d

[yyyyx4]

comment:9

Replying to @tscrim:

Perhaps for now we can just change the documentation to say this works for any infinite enumerated (commutative) ring?

Done.

[tscrim]

comment:10

Thank you.

I agree that a category level solution would be better, but that might involve some subtleties with speed, mixing finite sets, and things (unfortunately) assuming a particular order on the objects.

[tscrim]

Reviewer: Travis Scrimshaw

[yyyyx4]

comment:11

Thank you for reviewing!

[vbraun]

Changed branch from public/iter_ZZ_n to a001b6d

[yyyyx4]

Changed commit from a001b6d to none

[yyyyx4]

Changed author from Lorenz Panny to Lorenz Panny, Aleksei Udovenko