Opened 2 years ago

Combinatorial designs: add some difference matrices and related objects

Reported by: Owned by: gh-Ivo-Maffei major sage-9.7 combinatorics symmetric_nets orthogonal_arrays transversal_designs difference_matrices dimpase, slelievre Ivo Maffei N/A u/gh-Ivo-Maffei/symmetric_nets b3c3bd573187c03f43414b913523a04dd609017c

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.

comment:1 Changed 2 years ago by dimpase

I see failing doctests:

sage -t --warn-long 94.4 src/sage/combinat/designs/latin_squares.py  # 2 doctests failed
sage -t --warn-long 94.4 src/sage/combinat/designs/designs_pyx.pyx  # 3 doctests failed


comment:2 Changed 2 years ago by git

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

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 def symmetric_net(n, lmbda=1, check=True, existence=False): Set to True by default - existence -- bolean. Instead of returnig a symmetric net, return: - True -- such a net can be constructed by Sage - False -- no such a net exists - Unknown -- Sage does not know how to build such a design so such design may or may not exist - True -- such a net can be constructed by Sage - False -- no such a net exists - Unknown -- Sage does not know how to build such a design so such design may or may not exist EXAMPLES::
• src/sage/combinat/designs/difference_matrices.py

 a def subgroup_construction(g,k,lmbda,existence=False): - g,k,\lambda -- (integers) parameters of the difference matrix to construct - existence -- (boolean) instead of building the design, return: - True if Sage can build the difference matrix using the subgroup construction - False if Sage can't build the difference matrix using this construction Note that Sage may be able to build such difference matrix in other ways - True if Sage can build the difference matrix using the subgroup construction - False if Sage can't build the difference matrix using this construction Note that Sage may be able to build such difference matrix in other ways EXAMPLES::

(sphinx is very sensitive to correct indentation)

comment:4 Changed 2 years ago by mkoeppe

• Milestone changed from sage-9.1 to sage-9.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 follow-up: ↓ 6 Changed 2 years ago by slelievre

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

• 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 gh-Ivo-Maffei

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 gh-Ivo-Maffei

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:

1. change the docstring of difference matrices to use columns or change the code by taking transposes when needed;
2. limit difference matrices to Abelian groups or change the is_quasi_difference_matrix function to allow for non-Abelian groups

Personally, I would change the docstring for the difference matrices so that it matches the definition of quasi-difference matrices and then change the code of is_quasi_difference_matrix to allow for non-Abelian groups. Are there any reasons I should not go this way?

comment:10 Changed 2 years ago by dimpase

do you meanwhile have non-trivial examples of difference sets for non-abelian groups?

comment:11 Changed 2 years ago by dimpase

I think changing the docstring is the obvious best option - as it does not break any code.

In the non-abelian case, do you still use additive notation for the group? This is unusual, perhaps needs commenting...

comment:12 Changed 2 years ago by gh-Ivo-Maffei

While there exist non-abelian difference sets (e.g. http://mathonline.wikidot.com/difference-sets-in-non-abelian-groups), 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 non-abelian groups, then I'll add a note in the docstrings.

Last edited 2 years ago by gh-Ivo-Maffei (previous) (diff)

comment:13 Changed 22 months ago by mkoeppe

• Milestone changed from sage-9.2 to sage-9.3

comment:14 Changed 18 months ago by mkoeppe

• Milestone changed from sage-9.3 to sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:15 Changed 13 months ago by mkoeppe

• Milestone changed from sage-9.4 to sage-9.5

comment:16 Changed 8 months ago by mkoeppe

• Milestone changed from sage-9.5 to sage-9.6

comment:17 Changed 4 months ago by mkoeppe

• Milestone changed from sage-9.6 to sage-9.7
Note: See TracTickets for help on using tickets.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.34835946559906006, "perplexity": 3835.2994337293953}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2022-33/segments/1659882570901.18/warc/CC-MAIN-20220809033952-20220809063952-00014.warc.gz"}