Opened 7 years ago

Closed 7 years ago

#16464 closed enhancement (fixed)

cyclotomic_cosets for any finite ring

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.3
Component: number theory Keywords:
Cc: ncohen Merged in:
Authors: Vincent Delecroix Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: 7941224 (Commits, GitHub, GitLab) Commit: 7941224f132111e4a0a2809d9ed7052fe2d530de
Dependencies: Stopgaps:

Status badges

Description (last modified by 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.

Change History (40)

comment:1 Changed 7 years ago by vdelecroix

  • Branch set to u/vdelecroix/16464
  • Commit set to e77da55feea62fea023bb8f8760b146e38744d10
  • Status changed from new to needs_review

New commits:

fa45dd3trac #16461: difference families
491d669trac #16461: reviewer comment 1 ++
5d91e5ftrac #16461: more doc
e77da55trac #16464: multiplicative cosets of finite field

comment:2 Changed 7 years ago by vdelecroix

Oups... wait a minute!

comment:3 Changed 7 years ago by git

  • Commit changed from e77da55feea62fea023bb8f8760b146e38744d10 to 6afe17cced6a3ad00653a9f71013b9bb5c02f71a

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

6afe17ctrac #16464: multiplicative cosets of finite field

comment:4 Changed 7 years ago by vdelecroix

  • Description modified (diff)

comment:5 Changed 7 years ago by git

  • Commit changed from 6afe17cced6a3ad00653a9f71013b9bb5c02f71a to 9b1544b90970887f5e22a4aa1e93db04cd18ce90

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

9b1544btrac #16464: generic implementation

comment:6 Changed 7 years ago by vdelecroix

  • Description modified (diff)
  • Summary changed from method to list multiplicative cosets of finite field to cyclotomic_cosets for any finite ring

comment:7 Changed 7 years ago by ncohen

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

comment:8 Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_info

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

comment:9 follow-up: Changed 7 years ago by 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

comment:10 in reply to: ↑ 9 Changed 7 years ago by vdelecroix

  • Branch changed from u/vdelecroix/16464 to public/16464
  • Commit changed from 9b1544b90970887f5e22a4aa1e93db04cd18ce90 to f0474bb138221ffa139ede31f6e04ed47d02e6ea
  • Status changed from needs_info to needs_review

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:

f0a2958trac #16464: Docstring work
f0474bbtrac #16464: be more careful with errors

comment:11 Changed 7 years ago by git

  • Commit changed from f0474bb138221ffa139ede31f6e04ed47d02e6ea to 21cb1a83280c9a0c7ddd6c418dad4d053024b570

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

21cb1a8trac #16464: handle correctly arguments for cyclotomic_cosets

comment:12 follow-up: Changed 7 years ago by 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

comment:13 Changed 7 years ago by git

  • Commit changed from 21cb1a83280c9a0c7ddd6c418dad4d053024b570 to b07ad014b69fc326233a570e41fbdad93402049c

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

b07ad01trac #16464: Second review

comment:14 Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:15 in reply to: ↑ 12 ; follow-up: Changed 7 years ago by 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?

comment:16 follow-up: Changed 7 years ago by 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.

comment:17 in reply to: ↑ 15 ; follow-up: Changed 7 years ago by ncohen

Do you agree?

Turns out that I am an idiot.

Nathann

comment:18 in reply to: ↑ 16 ; follow-up: Changed 7 years ago by 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

comment:19 in reply to: ↑ 17 Changed 7 years ago by 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):

comment:20 in reply to: ↑ 18 ; follow-up: Changed 7 years ago by 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__.

comment:21 in reply to: ↑ 20 Changed 7 years ago by ncohen

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

Is it ? Either way, add a commit !

Nathann

comment:22 Changed 7 years ago by git

  • Commit changed from b07ad014b69fc326233a570e41fbdad93402049c to 136e870dfd215fd1b75521dafa04888f3601bf40

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

136e870trac #16464: tiny improvements for is_a_splitting

comment:23 follow-up: Changed 7 years ago by 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!

comment:24 in reply to: ↑ 23 Changed 7 years ago by ncohen

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

Indeed. I have been living as a fool.

Nathann

comment:25 Changed 7 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_info to positive_review

Well, then ...

Nathann

comment:26 Changed 7 years ago by vdelecroix

Cool. Thanks for the review.

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

comment:27 Changed 7 years ago by ncohen

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

Nathann

comment:28 Changed 7 years ago by git

  • Commit changed from 136e870dfd215fd1b75521dafa04888f3601bf40 to 965f550d72c999d0cefece8cbd253a843af2528b
  • Status changed from positive_review to needs_review

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

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

comment:29 Changed 7 years ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:30 Changed 7 years ago by vbraun

  • Status changed from positive_review to needs_work
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

comment:31 Changed 7 years ago by 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

comment:32 Changed 7 years ago by 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..

comment:33 Changed 7 years ago by git

  • Commit changed from 965f550d72c999d0cefece8cbd253a843af2528b to ee39f861f87799d5c880cebbce87491205f08f91

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

ee39f86trac #16464: move code in commutative_rings and fix doctests

comment:34 Changed 7 years ago by 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:

ee39f86trac #16464: move code in commutative_rings and fix doctests

comment:35 Changed 7 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:36 Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_work
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

comment:37 Changed 7 years ago by git

  • Commit changed from ee39f861f87799d5c880cebbce87491205f08f91 to 7941224f132111e4a0a2809d9ed7052fe2d530de

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

7941224trac #16464: fix doctests

comment:38 Changed 7 years ago by vdelecroix

  • Status changed from needs_work to needs_review

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

comment:39 Changed 7 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:40 Changed 7 years ago by vbraun

  • Branch changed from public/16464 to 7941224f132111e4a0a2809d9ed7052fe2d530de
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.