Opened 6 years ago

Closed 6 years ago

#16866 closed enhancement (fixed)

Radical difference families

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.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 vdelecroix)

Exhaustive search for radical difference families through dancing links.

Attachments (1)

cyclic_tiling.py (1.1 KB) - added by vdelecroix 6 years ago.

Download all attachments as: .zip

Change History (43)

comment:1 Changed 6 years ago by vdelecroix

  • Branch set to u/vdelecroix/16866
  • Commit set to 91412d70ae74fb018d3ecd0d34d809392880ef4b
  • Dependencies set to #16863
  • Status changed from new to needs_review

Last 10 new commits:

f3f644dtrac #16763: code simplification
04936aatrac #16802: database of difference family
4bd8d69trac #16802: Review
4434d61trac #16802: review the review
33b4171trac #16863: twin prime difference set
acd60a2trac #16863: Handle all prime powers (not just primes)
5903ac6trac #16863: doc and simplification
f45b57atrac #16866: Buratti 1995 constructions
bb21dc0trac #16763: Double citation
91412d7trac #16866: merge #16763

comment:2 Changed 6 years ago by ncohen

  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Status changed from needs_review to positive_review

comment:3 Changed 6 years ago by ncohen

(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 vdelecroix

  • Description modified (diff)
  • Milestone changed from sage-duplicate/invalid/wontfix to sage-6.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 git

  • Commit changed from 91412d70ae74fb018d3ecd0d34d809392880ef4b to 7203d58b247c0a80b96e1d4f64a6a976539110b4

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

7203d58trac #16866: dlx for radical difference family

comment:6 Changed 6 years ago by vdelecroix

  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:7 Changed 6 years ago by git

  • Commit changed from 7203d58b247c0a80b96e1d4f64a6a976539110b4 to e26d574fcd0d42199d9ef3a36f4ec269399feefc

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

e26d574trac #16866: remove trailing whitespaces

comment:8 Changed 6 years ago by git

  • Commit changed from e26d574fcd0d42199d9ef3a36f4ec269399feefc to 81fb94d08a5fd382d3e9930929af11a4ed79737e

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

81fb94dtrac #16866: avoid dlx for difference_set

comment:9 Changed 6 years ago by git

  • Commit changed from 81fb94d08a5fd382d3e9930929af11a4ed79737e to 58fed55ef22232a32f3beffae76f4121e775c58e

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

657244btrac #16866: remove trailing whitespaces
bee446ftrac #16866: avoid dlx for difference_set
58fed55trac #16866: formatting

comment:10 Changed 6 years ago by vdelecroix

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 follow-up: Changed 6 years ago by ncohen

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 vdelecroix

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 vdelecroix

comment:13 Changed 6 years ago by git

  • Commit changed from 58fed55ef22232a32f3beffae76f4121e775c58e to 721af75ec2b2c6ca904f2feaf86e75e054cb089d

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

721af75trac #16866: ALGORITHM block with explanations

comment:14 follow-up: Changed 6 years ago by ncohen

  • 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 ; follow-up: Changed 6 years ago by vdelecroix

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 of A, and why you seem to solve a tiling problem on A and not on \Delta A.

A appears explicitly when you compute \Delta {1,r,r^2,...,r^(k-1)\}. 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 ; follow-up: Changed 6 years ago by ncohen

Yo !

A appears explicitly when you compute \Delta {1,r,r^2,...,r^(k-1)\}. Its definition is obtained from differences already.

I still don't get it. I expect to have a set of cardinality k(k-1) 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 ; follow-up: Changed 6 years ago by vdelecroix

Replying to ncohen:

Yo !

A appears explicitly when you compute \Delta {1,r,r^2,...,r^(k-1)\}. Its definition is obtained from differences already.

I still don't get it. I expect to have a set of cardinality k(k-1) 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(k-1).

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 2-dimensional tilings with polyominos.

Vincent

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

Yo !

And you can check that # (A H^{mt}) = #A # H^{mt} has cardinality k(k-1).

Do you create this set of cardinality k(k-1) in your code ?

Right, tiling/packing I do not care but there exists sage.combinat.tiling for some 2-dimensional tilings with polyominos.

Oh nice.

Nathann

comment:19 in reply to: ↑ 18 ; follow-up: Changed 6 years ago by vdelecroix

Replying to ncohen:

Yo !

And you can check that # (A H^{mt}) = #A # H^{mt} has cardinality k(k-1).

Do you create this set of cardinality k(k-1) 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 Hmt, you can quotient out by Hmt (i.e. reasoning in terms of the cosets xHmt).

Once you checked that the elements of A belong to distinct cosets mod Hmt, you need to find a set of translates {x_1 A, x_2 A, ..., x_k A} that tile (or pack) the quotient H/Hmt

Vincent

comment:20 in reply to: ↑ 19 ; follow-up: Changed 6 years ago by 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 Hmt, you can quotient out by Hmt (i.e. reasoning in terms of the cosets xHmt).

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 ; follow-up: Changed 6 years ago by vdelecroix

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 Hmt, you can quotient out by Hmt (i.e. reasoning in terms of the cosets xHmt).

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 ; follow-up: Changed 6 years ago by 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 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 0-1). 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 ; follow-up: Changed 6 years ago by vdelecroix

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 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.

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 expected -K.one() (i.e. the difference 0-1). Then I do not understand the cut with the len(set(logA)).

This comes from computing what is Delta {1, r, r2, ..., rk-1} (where r is a k-th root of unity). If you do that you will see that it is the same as {+1, -1} A Hmt. In the case of k even you want to compute Delta {0, 1, r, ..., rk-2} (where r is a (k-1)-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 q-1 while H/Hmt has cardinality mt = (q-1)/(k-1) or (q-1)/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 ; follow-up: Changed 6 years ago by ncohen

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, r2, ..., rk-1} (where r is a k-th root of unity). If you do that you will see that it is the same as {+1, -1} A Hmt. In the case of k even you want to compute Delta {0, 1, r, ..., rk-2} (where r is a (k-1)-th root of unity).

I have absolutely no intuition of what Hmt 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 non-reduced problem ? If so, that would make it easier for me to understand.

Nathann

comment:25 in reply to: ↑ 24 ; follow-up: Changed 6 years ago by vdelecroix

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 H2mt = A Hmt is your basic block (see below for explanation). If two class of A belong to the same set modulo Hmt them it means that in the product A Hmt 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, r2, ..., rk-1} (where r is a k-th root of unity). If you do that you will see that it is the same as {+1, -1} A Hmt. In the case of k even you want to compute Delta {0, 1, r, ..., rk-2} (where r is a (k-1)-th root of unity).

I have absolutely no intuition of what Hmt represents.

H is the set of invertible elements in the finite field (it has cardinal q-1 and form a group under multiplication. Hj is the set of j-th power in H.

In our context, Hmt is the set of (2k)-th root of unity or 2(k-1)-th root of unity depending on the parity of k. It is also {+1, -1} H2mt where H2mt is the set of k-th root of unity or (k-1)-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 non-reduced 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 ; follow-up: Changed 6 years ago by 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.

Nathann

comment:27 in reply to: ↑ 26 Changed 6 years ago by vdelecroix

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 Hmt. And I do not want to compute these cosets and then forgot about them...

Vincent

comment:28 Changed 6 years ago by vdelecroix

  • Status changed from needs_info to needs_review

comment:29 Changed 6 years ago by git

  • Commit changed from 721af75ec2b2c6ca904f2feaf86e75e054cb089d to 4af94610f2c5b09e5f233770526219680551a924

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

4af9461Trac 16866: dlx for radical difference family

comment:30 Changed 6 years ago by ncohen

  • 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 k-1. 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 git

  • Commit changed from 4af94610f2c5b09e5f233770526219680551a924 to 4227487fe3aa6dfd84f0009458c1f3acbdd1811f

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

ae0c9cctrac #16866: Doc rewrite
4aa4732Trac 16866: takes care of +1/-1 in the doc
4227487remove wilson

comment:32 Changed 6 years ago by vdelecroix

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 vdelecroix

  • Status changed from needs_info to positive_review

comment:34 Changed 6 years ago by vdelecroix

  • Status changed from positive_review to needs_work

comment:35 Changed 6 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:36 Changed 6 years ago by ncohen

  • 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 ncohen

  • Keywords sd66 added

comment:38 Changed 6 years ago by git

  • Commit changed from 4227487fe3aa6dfd84f0009458c1f3acbdd1811f to ae7c4f166ffd32ec9d2d8a12c2c0f0e50fe15d93

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

ba291f3trac #16866: Merged with rc2
13d3aadtrac #16866: Make doc and code match
ae7c4f1trac #16866: Change the output of print_tiling

comment:39 Changed 6 years ago by git

  • Commit changed from ae7c4f166ffd32ec9d2d8a12c2c0f0e50fe15d93 to 74c869bd5a48565e373c4ad79771feb3003ff497

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

74c869bTrac 16866: some typo in the doc

comment:40 Changed 6 years ago by vdelecroix

I am happy with the current situation.

comment:41 Changed 6 years ago by ncohen

  • 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 vbraun

  • Branch changed from u/vdelecroix/16866 to 74c869bd5a48565e373c4ad79771feb3003ff497
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.