cyclotomic_cosets for any finite ring

[vdelecroix]

In order to implement difference families (see #16461), I need a method to list multiplicative cosets of a finite field. Here it is.

See also ​this thread on sage-nt.

The method cyclotomic_cosets is implemented at the level of rings (in sage.categories.rings) and the corresponding global function is deprecated. The code is also adapted in sage.coding.coding_constructions to take care of the change.

We also correct a bug in sage.coding.coding_constructions where is_a_splitting returned a pair and hence always evaluated to True in if statements.

[vdelecroix]

New commits:

​fa45dd3	trac #16461: difference families
​491d669	trac #16461: reviewer comment 1 ++
​5d91e5f	trac #16461: more doc
​e77da55	trac #16464: multiplicative cosets of finite field

[vdelecroix]

Oups... wait a minute!

[git]

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

​6afe17c

trac #16464: multiplicative cosets of finite field

[git]

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

​9b1544b

trac #16464: generic implementation

[ncohen]

For some reason the function does not appear in the doc -_-

[ncohen]

Hello Vincent !

There is a small commit on public/16464 for typos.

I've got a question on the documentation, however : you say at the beginnig that "the orbits of the group action of R^* on R are called the cyclotomic cosets". From which it follows that the only two cyclotomic cosets of a finite Field are R^* and 0, doesn't it ?

I mean : your function takes q as an argument, though your definition of what a cyclotomic coset is does not involve q in any way. Sooooo I don't get it : shouldn't they be called "cyclotomic cosets with respect to q" or something ?

Nathann

[ncohen]

About this part of the code

+    try:
+        return DuadicCodeEvenPair(F,Q,N)
+    except TypeError:
+        raise TypeError("No quadratic residue code exists for these parameters.")

Is there any reason why your replaced the if not(is_a_splitting(Q,N,n)) by this try/catch ? What worries me is that it could catch TypeErrors raised in DuadicCodeEvenPair that are real bugs and not created by this if not(is_a_splitting(Q,N,n)).

Nathann

[vdelecroix]

Replying to ncohen:

About this part of the code

+    try:
+        return DuadicCodeEvenPair(F,Q,N)
+    except TypeError:
+        raise TypeError("No quadratic residue code exists for these parameters.")

Is there any reason why your replaced the if not(is_a_splitting(Q,N,n)) by this try/catch ? What worries me is that it could catch TypeErrors raised in DuadicCodeEvenPair that are real bugs and not created by this if not(is_a_splitting(Q,N,n)).

Ok. I modified the function... the errors are clearer and there is no try/except anymore.

---

New commits:

​f0a2958	trac #16464: Docstring work
​f0474bb	trac #16464: be more careful with errors

[git]

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

​21cb1a8

trac #16464: handle correctly arguments for cyclotomic_cosets

[ncohen]

A new commit, with two questions :

1)

+    if n <= 2 or not n.is_prime():
+        raise ValueError("the argument n must be an odd prime")

Why don't you test that n is odd ?

2) Why would this be allowed ? It really does NOT have the same behaviour.

-    n = max(S1+S2)+1
-    if not(is_a_splitting(S1,S2,n)):
+    n = len(S1) + len(S2) + 1
+    if not is_a_splitting(S1,S2,n):

Nathann

[git]

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

​b07ad01

trac #16464: Second review

[vdelecroix]

Replying to ncohen:

A new commit, with two questions :

1)

+    if n <= 2 or not n.is_prime():
+        raise ValueError("the argument n must be an odd prime")

Why don't you test that n is odd ?

Hum. If n is prime and not 2 it is necessarily odd.

2) Why would this be allowed ? It really does NOT have the same behaviour.

-    n = max(S1+S2)+1
-    if not(is_a_splitting(S1,S2,n)):
+    n = len(S1) + len(S2) + 1
+    if not is_a_splitting(S1,S2,n):

It does. is_a_splitting(S1,S2,n) answers True if the input is a partition (S1,S2) of {1,...,n-1} (+ a condition on the partition). So I just changed the code to avoid the concatenation and the max.

Do you agree?

[vdelecroix]

Before the end, I would also like to change len(S1.union(S2)) != n-1 in is_a_splitting by S1.difference(S2). Makes more sense.

[ncohen]

Do you agree?

Turns out that I am an idiot.

Nathann

[ncohen]

1> Before the end, I would also like to change len(S1.union(S2)) != n-1 in is_a_splitting by S1.difference(S2). Makes more sense.

Or len(S1 & S2).

Nathann

[vdelecroix]

Replying to ncohen:

Do you agree?

Turns out that I am an idiot.

Nope. This is very cool

-        if GCD(b,n) == 1 and all(b*x in S2 for x in S1)  and all(b*x in S1 for x in S2):
+        if GCD(b,n) == 1 and all(b*x in S2 for x in S1):

[vdelecroix]

Replying to ncohen:

1> Before the end, I would also like to change len(S1.union(S2)) != n-1 in is_a_splitting by S1.difference(S2). Makes more sense.

Or len(S1 & S2).

or S1 & S2. It is faster to call __nonzero__ rather than __len__.

[ncohen]

or S1 & S2. It is faster to call __nonzero__ rather than __len__.

Is it ? Either way, add a commit !

Nathann

[git]

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

​136e870

trac #16464: tiny improvements for is_a_splitting

[vdelecroix]

Looks like it is

sage: S1=set(range(10))
sage: S2=set(range(10,20))
sage: timeit("if S1&S2: pass",number=1000000)
1000000 loops, best of 3: 446 ns per loop
sage: timeit("if len(S1&S2): pass",number=1000000)
1000000 loops, best of 3: 517 ns per loop

50ns... it will save a lot of time!

[ncohen]

50ns... it will save a lot of time!

Indeed. I have been living as a fool.

Nathann

[ncohen]

Well, then ...

Nathann

[vdelecroix]

Cool. Thanks for the review.

(Note: in the meantime I discovered that Python set have a nice method .is_disjoint()...)

[ncohen]

Add it, and set the ticket back to its current state.

Nathann

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​965f550

trac #16464: replace bool(S1&S2) by S1.isdisjoint(S2)

[vbraun]

sage -t src/sage/categories/category.py
**********************************************************************
File "src/sage/categories/category.py", line 1594, in sage.categories.category.Category._with_axiom_as_tuple
Failed example:
    Rings().Division()._with_axiom_as_tuple('Finite')
Expected:
    (Category of division rings,
     Category of finite monoids,
     Category of commutative magmas)
Got:
    (Category of division rings, Category of finite rings, Category of commutative magmas)

and related failures everywhere

[ncohen]

O_o

I have no idea how it could be caused by this patch. All it does is add a function and fix some doc O_o

Nathann

[vdelecroix]

Nope. I added a (nested) class Finite in sage.categories.rings.Rings... so it is likely that I would have to run all tests in sage.categories and see..

[git]

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

​ee39f86

trac #16464: move code in commutative_rings and fix doctests

[vdelecroix]

Hi Nathann,

Because of this error, I notice that in Sage rings are not necessarily commutative. It would hence be better have cyclotomic_cosets only at the level of commutative rings... (you do not want it for the set of 2x2 matrices over GF(3)).

Please review it again (it is only a cut and paste).

Vincent

---

New commits:

​ee39f86

trac #16464: move code in commutative_rings and fix doctests

[ncohen]

sage -t --long rings/finite_rings/integer_mod_ring.py  # 2 doctests failed
sage -t --long misc/c3_controlled.pyx  # 2 doctests failed
sage -t --long rings/ring.pyx  # 1 doctest failed

Nathann

[git]

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

​7941224

trac #16464: fix doctests

[vdelecroix]

Hi Nathann,

Thank you for running the long tests! I asked at my lab and will have a machine dedicated to Sage tests from tuesday... will be much better.

Vincent