Opened 6 years ago
Closed 6 years ago
#16866 closed enhancement (fixed)
Radical difference families
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  combinatorial designs  Keywords:  sd66 
Cc:  ncohen  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  74c869b (Commits)  Commit:  74c869bd5a48565e373c4ad79771feb3003ff497 
Dependencies:  #16863  Stopgaps: 
Description (last modified by )
Exhaustive search for radical difference families through dancing links.
Attachments (1)
Change History (43)
comment:1 Changed 6 years ago by
 Branch set to u/vdelecroix/16866
 Commit set to 91412d70ae74fb018d3ecd0d34d809392880ef4b
 Dependencies set to #16863
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Milestone changed from sage6.4 to sageduplicate/invalid/wontfix
 Status changed from needs_review to positive_review
comment:3 Changed 6 years ago by
(Vincent found a more general version of this construction, and it is not worth merging this only to remove it later)
comment:4 Changed 6 years ago by
 Description modified (diff)
 Milestone changed from sageduplicate/invalid/wontfix to sage6.4
 Status changed from positive_review to needs_work
 Summary changed from (q,4,1) and (q,5,1) difference families (Buratti 1995) to Radical difference families
I will use the ticket for the more general version...
comment:5 Changed 6 years ago by
 Commit changed from 91412d70ae74fb018d3ecd0d34d809392880ef4b to 7203d58b247c0a80b96e1d4f64a6a976539110b4
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
7203d58  trac #16866: dlx for radical difference family

comment:6 Changed 6 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
comment:7 Changed 6 years ago by
 Commit changed from 7203d58b247c0a80b96e1d4f64a6a976539110b4 to e26d574fcd0d42199d9ef3a36f4ec269399feefc
Branch pushed to git repo; I updated commit sha1. New commits:
e26d574  trac #16866: remove trailing whitespaces

comment:8 Changed 6 years ago by
 Commit changed from e26d574fcd0d42199d9ef3a36f4ec269399feefc to 81fb94d08a5fd382d3e9930929af11a4ed79737e
Branch pushed to git repo; I updated commit sha1. New commits:
81fb94d  trac #16866: avoid dlx for difference_set

comment:9 Changed 6 years ago by
 Commit changed from 81fb94d08a5fd382d3e9930929af11a4ed79737e to 58fed55ef22232a32f3beffae76f4121e775c58e
comment:10 Changed 6 years ago by
Hi,
I ended up with some modifs in incidence_structure.py
that has nothing to do with this ticket... sorry for the forced push.
Vincent
comment:11 followup: ↓ 12 Changed 6 years ago by
Hello !
I am trying to review this patch but I am lost in many places for the moment, so it may not be ligthning quick. About one_cyclic_tiling
: the DLX algorithm is a pure exhaustive search. It enumerates all subsets of tiles, and explores everything until the current set cannot be extended anymore. There is no "smart cut" to detect easily that something cannot be completed. That algorithm is nothing but a "very careful and smart" implementation of that search, and so I do not believe that it is always the best.
Theoretically, what should be called there is IncidenceStructure.packing
(this is exactly the problem that you want to solve).
Nathann
comment:12 in reply to: ↑ 11 Changed 6 years ago by
Replying to ncohen:
Hello !
About
one_cyclic_tiling
: the DLX algorithm is a pure exhaustive search.
I do not expect it to be the best.
Theoretically, what should be called there is
IncidenceStructure.packing
(this is exactly the problem that you want to solve).
I would agree but the timings I got are not convincing. Please test the file I attached to the ticket
sage: timeit("t = test_all1(5,10)") 5 loops, best of 3: 78 ms per loop sage: timeit("t = test_all1(6,12)") 5 loops, best of 3: 444 ms per loop
against
sage: timeit("t = test_all2(5,10)") 5 loops, best of 3: 267 ms per loop sage: timeit("t = test_all2(6,12)") 5 loops, best of 3: 1.21 s per loop
The case of one tile on a circle is very symmetric and there might even be something better. Note also that for my instances the size of the tile is small compared to the size of the set.
Vincent
Changed 6 years ago by
comment:13 Changed 6 years ago by
 Commit changed from 58fed55ef22232a32f3beffae76f4121e775c58e to 721af75ec2b2c6ca904f2feaf86e75e054cb089d
Branch pushed to git repo; I updated commit sha1. New commits:
721af75  trac #16866: ALGORITHM block with explanations

comment:14 followup: ↓ 15 Changed 6 years ago by
 Status changed from needs_review to needs_info
Hello,
I tried to simplify the explanations a bit but I still do not understand the implementation. In particular I do not understand why you have this 1
in the definition of A
, and why you seem to solve a tiling problem on A
and not on \Delta A
.
Also, what would you think of removing the one_cyclic_tiling
function? The name is not particularly meaningful, it is three lines long, only used once?...
Could you also add your new functions to the index at the top of the file?
My modifications can be found at u/ncohen/16866
, but of course in that version your comments in the code use notations that I removed from the function's doc.
I can change that once I understand the implementation better.
Thanks,
Nathann
comment:15 in reply to: ↑ 14 ; followup: ↓ 16 Changed 6 years ago by
Replying to ncohen:
Hello,
I tried to simplify the explanations a bit but I still do not understand the implementation. In particular I do not understand why you have this
1
in the definition ofA
, and why you seem to solve a tiling problem onA
and not on\Delta A
.
A
appears explicitly when you compute \Delta {1,r,r^2,...,r^(k1)\}
. Its definition is obtained from differences already.
Also, what would you think of removing the
one_cyclic_tiling
function? The name is not particularly meaningful, it is three lines long, only used once?...
True. But I wonder if we can do better for that particular problem. I also thought about moving it in some tiling stuff in sage.combinat
. That way it would be better advertised.
Could you also add your new functions to the index at the top of the file?
Right
My modifications can be found at
u/ncohen/16866
, but of course in that version your comments in the code use notations that I removed from the function's doc.
I am having a look right now.
Vincent
comment:16 in reply to: ↑ 15 ; followup: ↓ 17 Changed 6 years ago by
Yo !
A
appears explicitly when you compute\Delta {1,r,r^2,...,r^(k1)\}
. Its definition is obtained from differences already.
I still don't get it. I expect to have a set of cardinality k(k1)
and I don't find it anywhere.
True. But I wonder if we can do better for that particular problem. I also thought about moving it in some tiling stuff in
sage.combinat
. That way it would be better advertised.
Well, if it belongs to some tiling library (but really, for me tiling and packing are the same things..) and has a more meaningful name then no problem of course.
Nathann
comment:17 in reply to: ↑ 16 ; followup: ↓ 18 Changed 6 years ago by
Replying to ncohen:
Yo !
A
appears explicitly when you compute\Delta {1,r,r^2,...,r^(k1)\}
. Its definition is obtained from differences already.I still don't get it. I expect to have a set of cardinality
k(k1)
and I don't find it anywhere.
True but there is a formula in my docstring:
It is easy to verify (see [Wi72]_) that we have for `k` odd `\Delta H^{2mt} = A H^{mt}` while for `k` even `\Delta (H^{2mt} \cup \{0\}) = A H^{mt}`. Here `\Delta B` is the set of differences of distinct elements in `B`.
And you can check that # (A H^{mt}) = #A # H^{mt}
has cardinality k(k1).
True. But I wonder if we can do better for that particular problem. I also thought about moving it in some tiling stuff in
sage.combinat
. That way it would be better advertised.Well, if it belongs to some tiling library (but really, for me tiling and packing are the same things..) and has a more meaningful name then no problem of course.
Right, tiling/packing I do not care but there exists sage.combinat.tiling
for some 2dimensional tilings with polyominos.
Vincent
comment:18 in reply to: ↑ 17 ; followup: ↓ 19 Changed 6 years ago by
Yo !
And you can check that
# (A H^{mt}) = #A # H^{mt}
has cardinality k(k1).
Do you create this set of cardinality k(k1) in your code ?
Right, tiling/packing I do not care but there exists
sage.combinat.tiling
for some 2dimensional tilings with polyominos.
Oh nice.
Nathann
comment:19 in reply to: ↑ 18 ; followup: ↓ 20 Changed 6 years ago by
Replying to ncohen:
Yo !
And you can check that
# (A H^{mt}) = #A # H^{mt}
has cardinality k(k1).Do you create this set of cardinality k(k1) in your code ?
Nope, and I do not need to do so. I want that my set of differences cover the whole H. Because all differences are a union of cosets of H^{mt}, you can quotient out by H^{mt} (i.e. reasoning in terms of the cosets xH^{mt}).
Once you checked that the elements of A belong to distinct cosets mod H^{mt}, you need to find a set of translates {x_1 A, x_2 A, ..., x_k A} that tile (or pack) the quotient H/H^{mt}
Vincent
comment:20 in reply to: ↑ 19 ; followup: ↓ 21 Changed 6 years ago by
Yo!
Nope, and I do not need to do so. I want that my set of differences cover the whole H. Because all differences are a union of cosets of H^{mt}, you can quotient out by H^{mt} (i.e. reasoning in terms of the cosets xH^{mt}).
Hmmmm... I spent the last hour in front of that code, and I still don't understand how exactly it works. Besides, I wonder: do you think that it makes any difference in the computations? If you want to compute a tiling with the sets A0, A1, ... it will take the same time as doing it on A0 U A0', A1 U A1', ... where the Ai' are copies of the Ai on a disjoint set.
What do you think ?
Nathann
comment:21 in reply to: ↑ 20 ; followup: ↓ 22 Changed 6 years ago by
Replying to ncohen:
Yo!
Nope, and I do not need to do so. I want that my set of differences cover the whole H. Because all differences are a union of cosets of H^{mt}, you can quotient out by H^{mt} (i.e. reasoning in terms of the cosets xH^{mt}).
Hmmmm... I spent the last hour in front of that code, and I still don't understand how exactly it works.
Too bad. If you tell me where, I can be clearer in the comments.
Besides, I wonder: do you think that it makes any difference in the computations? If you want to compute a tiling with the sets A0, A1, ... it will take the same time as doing it on A0 U A0', A1 U A1', ... where the Ai' are copies of the Ai on a disjoint set.
What do you mean by "the same time". There is the same number of tiles in the packing at the end but if you ignore the symmetries there are much more possible translations.
What do you think ?
That my code works and that it is good to have smaller instances of the problem to solve.
Vincent
comment:22 in reply to: ↑ 21 ; followup: ↓ 23 Changed 6 years ago by
Yo!
Too bad. If you tell me where, I can be clearer in the comments.
Well, for a start I had no idea at first what was this "A" that you defined, least of all why you have this 1
. Then you seemed to say that all differences belonged to different cosets of H^{mt}
(I don't understand what this set is), but it seems to mean that you can only consider the differences obtained with 1.
I don't get why you have this A.append(K.one())
, I would have expected K.one()
(i.e. the difference 01). Then I do not understand the cut with the len(set(logA))
.
What do you mean by "the same time". There is the same number of tiles in the packing at the end but if you ignore the symmetries there are much more possible translations.
I do not get exactly what your reduction of the ground set means with respect to the partition instance. What I mean is that an instance with the A0 U A0', A1 U A1', ... above is totally equivalent (in terms of resolution, and in terms of time) to an instance with A0, A1, ...
I was wondering if that was the difference that there is, in this branch, between considering the cosets that you mention and not considering them.
That my code works and that it is good to have smaller instances of the problem to solve.
It is not necessarily an improvement to reduce the number of vertices, e.g. the example above. And so far I do not understand how your code works.
Nathann
comment:23 in reply to: ↑ 22 ; followup: ↓ 24 Changed 6 years ago by
Replying to ncohen:
Yo!
Too bad. If you tell me where, I can be clearer in the comments.
Well, for a start I had no idea at first what was this "A" that you defined, least of all why you have this
1
. Then you seemed to say that all differences belonged to different cosets ofH^{mt}
(I don't understand what this set is), but it seems to mean that you can only consider the differences obtained with 1.
No. I want that all differences belong to different coset. This is something that need to be checked and which are precisely the two lines
if len(set(logA)) != m: return None
I don't get why you have this
A.append(K.one())
, I would have expectedK.one()
(i.e. the difference 01). Then I do not understand the cut with thelen(set(logA))
.
This comes from computing what is Delta {1, r, r^{2}, ..., r^{k1}} (where r is a kth root of unity). If you do that you will see that it is the same as {+1, 1} A H^{mt}. In the case of k even you want to compute Delta {0, 1, r, ..., r^{k2}} (where r is a (k1)th root of unity).
For the cut, see above.
What do you mean by "the same time". There is the same number of tiles in the packing at the end but if you ignore the symmetries there are much more possible translations.
I do not get exactly what your reduction of the ground set means with respect to the partition instance. What I mean is that an instance with the A0 U A0', A1 U A1', ... above is totally equivalent (in terms of resolution, and in terms of time) to an instance with A0, A1, ...
H has cardinality q1 while H/H^{mt} has cardinality mt = (q1)/(k1) or (q1)/k depending on the parity of k.
I was wondering if that was the difference that there is, in this branch, between considering the cosets that you mention and not considering them.
That my code works and that it is good to have smaller instances of the problem to solve.
It is not necessarily an improvement to reduce the number of vertices, e.g. the example above. And so far I do not understand how your code works.
Good point
Vincent
comment:24 in reply to: ↑ 23 ; followup: ↓ 25 Changed 6 years ago by
No. I want that all differences belong to different coset.
Why can you make that assumption ?
This comes from computing what is Delta {1, r, r^{2}, ..., r^{k1}} (where r is a kth root of unity). If you do that you will see that it is the same as {+1, 1} A H^{mt}. In the case of k even you want to compute Delta {0, 1, r, ..., r^{k2}} (where r is a (k1)th root of unity).
I have absolutely no intuition of what H^{mt} represents.
And so far I do not understand how your code works.
Good point
Do you think that the tiling problem that you solve is equivalent, by the previous remarks, to the nonreduced problem ? If so, that would make it easier for me to understand.
Nathann
comment:25 in reply to: ↑ 24 ; followup: ↓ 26 Changed 6 years ago by
Replying to ncohen:
No. I want that all differences belong to different coset.
Why can you make that assumption ?
Because you want a difference family at the end! Let me recall that B = \Delta H^{2mt} = A H^{mt} is your basic block (see below for explanation). If two class of A belong to the same set modulo H^{mt} them it means that in the product A H^{mt} you have zero. Which contradict the definition of difference family which needs to cover K \ {0}.
This comes from computing what is Delta {1, r, r^{2}, ..., r^{k1}} (where r is a kth root of unity). If you do that you will see that it is the same as {+1, 1} A H^{mt}. In the case of k even you want to compute Delta {0, 1, r, ..., r^{k2}} (where r is a (k1)th root of unity).
I have absolutely no intuition of what H^{mt} represents.
H is the set of invertible elements in the finite field (it has cardinal q1 and form a group under multiplication. H^{j} is the set of jth power in H.
In our context, H^{mt} is the set of (2k)th root of unity or 2(k1)th root of unity depending on the parity of k. It is also {+1, 1} H^{2mt} where H^{2mt} is the set of kth root of unity or (k1)th root of unity (depending on the parity.
And so far I do not understand how your code works.
Good point
Do you think that the tiling problem that you solve is equivalent, by the previous remarks, to the nonreduced problem ? If so, that would make it easier for me to understand.
Yes. If you solve the big one, you solve the small one (and conversly).
Vincent
comment:26 in reply to: ↑ 25 ; followup: ↓ 27 Changed 6 years ago by
Yes. If you solve the big one, you solve the small one (and conversly).
Do you have reasons to believe that it would make a difference in the runtimes to solve the non reduced version? It is the only one that I understand so far.
Nathann
comment:27 in reply to: ↑ 26 Changed 6 years ago by
Replying to ncohen:
Yes. If you solve the big one, you solve the small one (and conversly).
Do you have reasons to believe that it would make a difference in the runtimes to solve the non reduced version? It is the only one that I understand so far.
I do have reasons (but it is not very important though).
More importantly, I want to keep the shortcut if some element of A belong to the same coset of H^{mt}. And I do not want to compute these cosets and then forgot about them...
Vincent
comment:28 Changed 6 years ago by
 Status changed from needs_info to needs_review
comment:29 Changed 6 years ago by
 Commit changed from 721af75ec2b2c6ca904f2feaf86e75e054cb089d to 4af94610f2c5b09e5f233770526219680551a924
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
4af9461  Trac 16866: dlx for radical difference family

comment:30 Changed 6 years ago by
 Status changed from needs_review to needs_info
Helloooo Vincent !
I added at public/16866 a commit that rewrites the documentation. I began to touch the code itself but so far I do not understand the reason behind this m=k//2
, and why your set A
has cardinality k/2
instead of k1
. I made that change and many doctests broke, so could you please enlighten me?
Thanks,
Nathann
P.S.: the doc's notations match the code
comment:31 Changed 6 years ago by
 Commit changed from 4af94610f2c5b09e5f233770526219680551a924 to 4227487fe3aa6dfd84f0009458c1f3acbdd1811f
comment:32 Changed 6 years ago by
Thanks! I adopted your commit and added two:
 one to explain in the doc the
m/2
 the other one to get rid of the
wilson_XXX
that can be thought as a special case of the newly created one
Vincent
comment:33 Changed 6 years ago by
 Status changed from needs_info to positive_review
comment:34 Changed 6 years ago by
 Status changed from positive_review to needs_work
comment:35 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:36 Changed 6 years ago by
 Reviewers set to Nathann Cohen
Helloooooooooooooo !
I am finally convinced by everything that was done in this patch. I only have two commits to offer at public/16866.
1) One that makes the notations of the doc and code match
2) One that changes print_tiling
to display '.' instead of blank spaces.
You turn ;)
Nathann
comment:37 Changed 6 years ago by
 Keywords sd66 added
comment:38 Changed 6 years ago by
 Commit changed from 4227487fe3aa6dfd84f0009458c1f3acbdd1811f to ae7c4f166ffd32ec9d2d8a12c2c0f0e50fe15d93
comment:39 Changed 6 years ago by
 Commit changed from ae7c4f166ffd32ec9d2d8a12c2c0f0e50fe15d93 to 74c869bd5a48565e373c4ad79771feb3003ff497
Branch pushed to git repo; I updated commit sha1. New commits:
74c869b  Trac 16866: some typo in the doc

comment:40 Changed 6 years ago by
I am happy with the current situation.
comment:41 Changed 6 years ago by
 Status changed from needs_review to positive_review
Making you happy is Sage's purpose.
Thanks for the branch,
Nathann
comment:42 Changed 6 years ago by
 Branch changed from u/vdelecroix/16866 to 74c869bd5a48565e373c4ad79771feb3003ff497
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
trac #16763: code simplification
trac #16802: database of difference family
trac #16802: Review
trac #16802: review the review
trac #16863: twin prime difference set
trac #16863: Handle all prime powers (not just primes)
trac #16863: doc and simplification
trac #16866: Buratti 1995 constructions
trac #16763: Double citation
trac #16866: merge #16763