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:  sage6.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: 
Description (last modified by )
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 sagent.
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
 Branch set to u/vdelecroix/16464
 Commit set to e77da55feea62fea023bb8f8760b146e38744d10
 Status changed from new to needs_review
comment:2 Changed 7 years ago by
Oups... wait a minute!
comment:3 Changed 7 years ago by
 Commit changed from e77da55feea62fea023bb8f8760b146e38744d10 to 6afe17cced6a3ad00653a9f71013b9bb5c02f71a
Branch pushed to git repo; I updated commit sha1. New commits:
6afe17c  trac #16464: multiplicative cosets of finite field

comment:4 Changed 7 years ago by
 Description modified (diff)
comment:5 Changed 7 years ago by
 Commit changed from 6afe17cced6a3ad00653a9f71013b9bb5c02f71a to 9b1544b90970887f5e22a4aa1e93db04cd18ce90
Branch pushed to git repo; I updated commit sha1. New commits:
9b1544b  trac #16464: generic implementation

comment:6 Changed 7 years ago by
 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
For some reason the function does not appear in the doc _
comment:8 Changed 7 years ago by
 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 followup: ↓ 10 Changed 7 years ago by
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
 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 catchTypeErrors
raised inDuadicCodeEvenPair
that are real bugs and not created by thisif 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

comment:11 Changed 7 years ago by
 Commit changed from f0474bb138221ffa139ede31f6e04ed47d02e6ea to 21cb1a83280c9a0c7ddd6c418dad4d053024b570
Branch pushed to git repo; I updated commit sha1. New commits:
21cb1a8  trac #16464: handle correctly arguments for cyclotomic_cosets

comment:12 followup: ↓ 15 Changed 7 years ago by
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
 Commit changed from 21cb1a83280c9a0c7ddd6c418dad4d053024b570 to b07ad014b69fc326233a570e41fbdad93402049c
Branch pushed to git repo; I updated commit sha1. New commits:
b07ad01  trac #16464: Second review

comment:14 Changed 7 years ago by
 Status changed from needs_review to needs_info
comment:15 in reply to: ↑ 12 ; followup: ↓ 17 Changed 7 years ago by
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,...,n1}
(+ a condition on the partition). So I just changed the code to avoid the concatenation and the max.
Do you agree?
comment:16 followup: ↓ 18 Changed 7 years ago by
Before the end, I would also like to change len(S1.union(S2)) != n1
in is_a_splitting
by S1.difference(S2)
. Makes more sense.
comment:17 in reply to: ↑ 15 ; followup: ↓ 19 Changed 7 years ago by
Do you agree?
Turns out that I am an idiot.
Nathann
comment:18 in reply to: ↑ 16 ; followup: ↓ 20 Changed 7 years ago by
1> Before the end, I would also like to change len(S1.union(S2)) != n1
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
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 ; followup: ↓ 21 Changed 7 years ago by
Replying to ncohen:
1> Before the end, I would also like to change
len(S1.union(S2)) != n1
inis_a_splitting
byS1.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
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
 Commit changed from b07ad014b69fc326233a570e41fbdad93402049c to 136e870dfd215fd1b75521dafa04888f3601bf40
Branch pushed to git repo; I updated commit sha1. New commits:
136e870  trac #16464: tiny improvements for is_a_splitting

comment:23 followup: ↓ 24 Changed 7 years ago by
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
50ns... it will save a lot of time!
Indeed. I have been living as a fool.
Nathann
comment:25 Changed 7 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_info to positive_review
Well, then ...
Nathann
comment:26 Changed 7 years ago by
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
Add it, and set the ticket back to its current state.
Nathann
comment:28 Changed 7 years ago by
 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:
965f550  trac #16464: replace bool(S1&S2) by S1.isdisjoint(S2)

comment:29 Changed 7 years ago by
 Status changed from needs_review to positive_review
comment:30 Changed 7 years ago by
 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
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
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
 Commit changed from 965f550d72c999d0cefece8cbd253a843af2528b to ee39f861f87799d5c880cebbce87491205f08f91
Branch pushed to git repo; I updated commit sha1. New commits:
ee39f86  trac #16464: move code in commutative_rings and fix doctests

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

comment:35 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:36 Changed 7 years ago by
 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
 Commit changed from ee39f861f87799d5c880cebbce87491205f08f91 to 7941224f132111e4a0a2809d9ed7052fe2d530de
Branch pushed to git repo; I updated commit sha1. New commits:
7941224  trac #16464: fix doctests

comment:38 Changed 7 years ago by
 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
 Status changed from needs_review to positive_review
comment:40 Changed 7 years ago by
 Branch changed from public/16464 to 7941224f132111e4a0a2809d9ed7052fe2d530de
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #16461: difference families
trac #16461: reviewer comment 1 ++
trac #16461: more doc
trac #16464: multiplicative cosets of finite field