Extended the construction of BIBDs to allow for \lambda different from 1

[gh-Ivo-Maffei]

Extended the function balanced_incomplete_block_design (aka BIBD) to allow arbitrary values for the parameter \lambda.

More on BIBDs may be found here: ​https://en.wikipedia.org/wiki/Block_design

[Dima Pasechnik]

looks great, adds a lot of nice stuff, but error messages need to be adjusted (lambda=1 is fixed there I suppose):

sage: designs.balanced_incomplete_block_design(79,13,2)
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-5-1a5677b9322f> in <module>()
----> 1 designs.balanced_incomplete_block_design(Integer(79),Integer(13),Integer(2))

/mnt/opt/Sage/sage-clang/local/lib/python3.7/site-packages/sage/combinat/designs/bibd.py in balanced_incomplete_block_design(v, k, lambd, existence, use_LJCR)
    271         return Unknown
    272     else:
--> 273         raise NotImplementedError("I don't know how to build a ({},{},1)-BIBD!".format(v, k))
    274 
    275 def steiner_triple_system(n):

NotImplementedError: I don't know how to build a (79,13,1)-BIBD!

(BIBD(79,13,2) is a largest known biplane (cf. ​https://en.wikipedia.org/wiki/Block_design#Biplanes), so it would eventually be nice to have, but not on this ticket.

[Dima Pasechnik]

here is the fix - and also a fix for 2 typos:

src/sage/combinat/designs/bibd.py

@@ -162 +162 @@
         sage: designs.balanced_incomplete_block_design(1171,10)
         (1171,10,1)-Balanced Incomplete Block Design
 
-    And we know some inexistence results::
+    And we know some nonexistence results::
 
         sage: designs.balanced_incomplete_block_design(21,6,existence=True)
         False
@@ -176 +176 @@
         sage: designs.balanced_incomplete_block_design(37,9,8)
         (37,9,8)-Balanced Incomplete Block Design
         sage: designs.balanced_incomplete_block_design(15,7,3)
-        g(15,7,3)-Balanced Incomplete Block Design
+        (15,7,3)-Balanced Incomplete Block Design
     """
 
     # Trivial BIBD
@@ -270 +270 @@
     if existence:
         return Unknown
     else:
-        raise NotImplementedError("I don't know how to build a ({},{},1)-BIBD!".format(v, k))
+        raise NotImplementedError("I don't know how to build a ({},{},{})-BIBD!".format(v, k, lambd))
 
 def steiner_triple_system(n):
     r"""

[Dima Pasechnik]

the typo tells me that you didn't run doctests :-)

[git]

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

​9a9705c

fixed typos

[gh-Ivo-Maffei]

Thanks for the review. The dockets pass, the issue with the g is that I often start typing "git" before the os has fully switch from the editor to the console. I should definitely be more careful, but they are tricky to catch as I have run all tests before I use git.

I'll try and implement the biplane now, otherwise I will end up forgetting.

[Dima Pasechnik]

not all doctests pass - namely, the following gets broken by this branch on Sage 9.1.beta2

sage -t --warn-long 67.2 src/sage/graphs/strongly_regular_db.pyx
**********************************************************************
File "src/sage/graphs/strongly_regular_db.pyx", line 487, in sage.graphs.strongly_regular_db.is_goethals_seidel
Failed example:
    g = t[0](*t[1:]); g
Exception raised:
    Traceback (most recent call last):
      File "/mnt/opt/Sage/sage-clang/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 680, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/opt/Sage/sage-clang/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1104, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.strongly_regular_db.is_goethals_seidel[5]>", line 1, in <module>
        g = t[Integer(0)](*t[Integer(1):]); g
      File "/mnt/opt/Sage/sage-clang/local/lib/python3.7/site-packages/sage/graphs/generators/families.py", line 1287, in GoethalsSeidelGraph
        for i in row])
      File "/mnt/opt/Sage/sage-clang/local/lib/python3.7/site-packages/sage/graphs/generators/families.py", line 1287, in <listcomp>
        for i in row])
    IndexError: pop from empty list

[Dima Pasechnik]

you managed to break incidence_matrix:

sage: designs.balanced_incomplete_block_design(16,2).incidence_matrix()
16 x 240 sparse matrix over Integer Ring (use the '.str()' method to see the entries)

it should be 16x120.

[Dima Pasechnik]

or perhaps just blocks in such a trivial case:

sage: d=designs.balanced_incomplete_block_design(3,2,1)
sage: d.blocks()
[[0, 1], [0, 1], [0, 2], [0, 2], [1, 2], [1, 2]]

[gh-Ivo-Maffei]

I have fixed the issue. However, I think I'm missing something when running the doctests. Usually, I execute sage -t src/sage/combinat/designs/bibd.py. How did you end up testing strongly_regular_db? Do I need to run all doctests (make ptest) or is there a way to only test the dependencies?

[Dima Pasechnik]

I ran sage -tp src/sage/combinat/ and sage -tp src/sage/graphs/ Yes, ideally you should run make ptestlong - takes time.

[Dima Pasechnik]

don't forget to push the fixes.

[git]

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

​437afc8

fixed bug with k=2

[gh-Ivo-Maffei]

I run make ptest this time and all seem to work.

[Dima Pasechnik]

Replying to gh-Ivo-Maffei:

I'll try and implement the biplane now, otherwise I will end up forgetting.

in any event, it makes sense to implement ​https://en.wikipedia.org/wiki/Bruck%E2%80%93Ryser%E2%80%93Chowla_theorem to rule out sets of parameters for symmetric BIBDs - so far it is only done in Sage for pojective planes, see projective_plane in src/sage/combinat/designs/block_design.py

[Dima Pasechnik]

OK, good.

[Samuel Lelièvre]

The patchbots report pyflakes and pycodestyles errors.

[gh-Ivo-Maffei]

If I interpret the pyflakes report correctly, it complains about ".block_design.BlockDesign imported but unused". That's wrong as BlockDesign is used at line 227. However, I think we could (and should) use BalancedIncompleteBlockDesign there. I'm now running the doctests to make sure I'm not wrong.

I fixed the pycodestyle errors, but I personally believe that code (especially the 10 lines of if ... else if ...) looked better before. Anyway, I'll push the changes as soon as the tests pass.

[Samuel Lelièvre]

Thanks for explaining. I don't feel strongly about it, feel free to set back to positive review.

[Dima Pasechnik]

OK.

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​5186f8f

small code formatting

[gh-Ivo-Maffei]

I apologise for the delay, but I finally got round to swap the BlockDesign use to BalancedIncompleteBlockDesign. It took longer than expected as some tests were failing, but they are completely unrelated.

[git]

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

​d2d340e

forgot to delete old import

[Dima Pasechnik]

a typo in docstring:

In particular, Sage can build a `(v,k,1)`-BIBD when one exists for all `k\leq

there should be \lambda instead of 1.

[Dima Pasechnik]

a typo in docstring:

In particular, Sage can build a `(v,k,1)`-BIBD when one exists for all `k\leq

there should be \lambda instead of 1.

Also, change the previous line

    sage: BIBD = designs.balanced_incomplete_block_design(7,3)

to use (7,3,1).

[gh-Ivo-Maffei]

I'll change the (7,3,1), but I'm not sure the other sentence should be changed. On my computer designs.balanced_incomplete_block_design(6,3,2) raises a NotImplementedError and Wikipedia states that there is such a BIBD (​https://en.wikipedia.org/wiki/Block_design#Examples).

[git]

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

​a607693

changed docstring

[Dima Pasechnik]

OK

[Dima Pasechnik]

Bibd(6,3,2) is probably another story. Not sure how it is built from what we have already