Opened 2 years ago
Last modified 7 weeks ago
#29410 new enhancement
Combinatorial designs: add some difference matrices and related objects
Reported by:  ghIvoMaffei  Owned by:  

Priority:  major  Milestone:  sage9.7 
Component:  combinatorics  Keywords:  symmetric_nets orthogonal_arrays transversal_designs difference_matrices 
Cc:  dimpase, slelievre  Merged in:  
Authors:  Ivo Maffei  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/ghIvoMaffei/symmetric_nets (Commits, GitHub, GitLab)  Commit:  b3c3bd573187c03f43414b913523a04dd609017c 
Dependencies:  Stopgaps: 
Description (last modified by )
We add a few constructions of difference matrices whose lambda parameter is not 1.
We then modify the orthogonal arrays and transversal designs constructions
to take advantage of these additions. Finally, we add a new function symmetric_net
.
Change History (17)
comment:1 Changed 2 years ago by
comment:2 Changed 2 years ago by
 Commit changed from 5cd8a3c3671efc12e6a511a1b79c854111f0b296 to 6c362d817d58b2b7db17f1420ddaf78a7cd6d20b
Branch pushed to git repo; I updated commit sha1. New commits:
6c362d8  fixed old doctests and bugs

comment:3 Changed 2 years ago by
Do you run tests using GitHub Actions? (see #29401 for details)
In your code, to build docs, one needs

src/sage/combinat/designs/orthogonal_arrays.py
a b def symmetric_net(n, lmbda=1, check=True, existence=False): 80 80 Set to ``True`` by default 81 81 82 82  ``existence``  bolean. Instead of returnig a symmetric net, return: 83  ``True``  such a net can be constructed by Sage84  ``False``  no such a net exists85  ``Unknown``  Sage does not know how to build such a design86 so such design may or may not exist83  ``True``  such a net can be constructed by Sage 84  ``False``  no such a net exists 85  ``Unknown``  Sage does not know how to build such a design 86 so such design may or may not exist 87 87 88 88 EXAMPLES:: 89 89 
src/sage/combinat/designs/difference_matrices.py
a b def subgroup_construction(g,k,lmbda,existence=False): 428 428  ``g,k,\lambda``  (integers) parameters of the difference matrix to construct 429 429 430 430  ``existence``  (boolean) instead of building the design, return: 431  ``True`` if Sage can build the difference matrix using the subgroup construction432  ``False`` if Sage can't build the difference matrix using this construction433 Note that Sage may be able to build such difference matrix in other ways431  ``True`` if Sage can build the difference matrix using the subgroup construction 432  ``False`` if Sage can't build the difference matrix using this construction 433 Note that Sage may be able to build such difference matrix in other ways 434 434 435 435 EXAMPLES:: 436 436
(sphinx is very sensitive to correct indentation)
comment:4 Changed 2 years ago by
 Milestone changed from sage9.1 to sage9.2
Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.
comment:5 followup: ↓ 6 Changed 2 years ago by
 Cc slelievre added
 Description modified (diff)
 Summary changed from Addition of some difference matrices and all related objects to Combinatorial designs: add some difference matrices and related objects
One occurrence of "more than 1 time" should be "more than once" as elsewhere.
Can you do a round of pep8 formatting?
I would use lamda
as an alternate name for lambda
(since lambda is a reserved keyword in Python).
I find it makes code easier to read than lambd or lmbda.
comment:6 in reply to: ↑ 5 Changed 2 years ago by
Replying to slelievre:
I would use
lamda
as an alternate name for lambda
Another option is la
which I like too.
comment:7 Changed 2 years ago by
 Commit changed from 6c362d817d58b2b7db17f1420ddaf78a7cd6d20b to b3c3bd573187c03f43414b913523a04dd609017c
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
f22eec1  All changes to this new branch

371e4c9  removed garbage code and cleaned some whitespaces

d3550ca  removed more whitespaces and typos

b0b020a  fixed trivial cases and BIG mistake

0547de1  fixed old doctests and bugs

f9bdc65  fixed doc string

07f6a79  subgroup construction handles 'any' group; some code formatting

59d1be9  some more formatting

b3c3bd5  fixed docstring; added GAP group to subgroup constructions; group_law; is_difference_matrix

comment:8 Changed 2 years ago by
I did some more work on the "subgroup_construction" method and added support for GAP groups in other places. Sage's tests pass and the documentation builds without errors. However, I've probably missed some formatting issues here and there.
lmbda
is the keyword used throughout the "designs_pyx.pyx" and the "difference_matrices.py" files. I introduced it only in the "orthogonal_arrays.py" file. If it bothers you, then I'll change it in all three files as I believe it should be consistent across them.
Finally, the definition of difference matrices in the doctoring doesn't seem right and needs some checking.
comment:9 Changed 2 years ago by
I looked into the definition of difference matrices.
The book "Design Theory" by Beth et. al. (Cambridge University Press, 1999) defines a (g, k, \lambda)
difference matrix as a k \times \lambda g
matrix such that for any two distinct rows R_i, R_j
each element of G
appears \lambda
times in the sequence (R_i[l]R_j[l])
. This is basically, the definition given in the docstring, but the dimensions of the matrix are flipped (hence the docstring is wrong).
The docstring in is_difference_matrix
, gives the same definition without specifying the dimensions.
What the codes actually do is redirecting the call to is_quasi_difference_matrix
which, in this specific case, checks that in any 2 columns C_i, C_j
each element of G
appears \lambda
times in the sequence (C_i[l]  C_j[l])
. However we need G
to be Abelian since the code doesn't check both C_i  C_j
and C_j  C_i
.
So there are 2 issues to fix:
 change the docstring of difference matrices to use columns or change the code by taking transposes when needed;
 limit difference matrices to Abelian groups or change the
is_quasi_difference_matrix
function to allow for nonAbelian groups
Personally, I would change the docstring for the difference matrices so that it matches the definition of quasidifference matrices and then change the code of is_quasi_difference_matrix
to allow for nonAbelian groups. Are there any reasons I should not go this way?
comment:10 Changed 2 years ago by
do you meanwhile have nontrivial examples of difference sets for nonabelian groups?
comment:11 Changed 2 years ago by
I think changing the docstring is the obvious best option  as it does not break any code.
In the nonabelian case, do you still use additive notation for the group? This is unusual, perhaps needs commenting...
comment:12 Changed 2 years ago by
While there exist nonabelian difference sets (e.g. http://mathonline.wikidot.com/differencesetsinnonabeliangroups), the difference_family
function explicitly states that it only returns difference families for abelian groups.
As far as the notation is concerned, it seems standard to use +
and 
for difference matrices despite I haven't found any definition that restricts to abelian groups. If we end up allowing nonabelian groups, then I'll add a note in the docstrings.
comment:13 Changed 19 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:14 Changed 15 months ago by
 Milestone changed from sage9.3 to sage9.4
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:15 Changed 10 months ago by
 Milestone changed from sage9.4 to sage9.5
comment:16 Changed 5 months ago by
 Milestone changed from sage9.5 to sage9.6
comment:17 Changed 7 weeks ago by
 Milestone changed from sage9.6 to sage9.7
I see failing doctests: