Combinatorial designs: generate GQ with spread

[Ivo-Maffei]

Implement a few functions to generate and work on generalised quadrangles with spreads.
In particular we construct H(3,q^2).

CC: @dimpase

Component: combinatorial designs

Keywords: generalised_quadrangle

Author: Ivo Maffei

Branch: 5d16394

Reviewer: Samuel Lelièvre, Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/30223

[Ivo-Maffei]

comment:1

At the moment the examples at the top of the file fail and they shouldn't.
In particular using the objects defined there one gets:

sage: set(GQ2._points) == set(range(1,1106))
False
sage: for i in GQ2._points:
....:     if i not in range(1,1106):
....:         print(i)
....:         
sage: for i in range(1,1106):
....:     if i not in GQ2._points:
....:         print(i)
....:      
sage:

I wonder if I'm missing something or if == is returning some weird output.

[slel]

Reviewer: Samuel Lelièvre, ...

[slel]

comment:2

Minor suggestions, no hurry.

-- YOUR NAME (2005-01-03): initial version
+- Ivo Maffei (2020-07-26): initial version

-#       Copyright (C) 2013 IVO MAFFEI <[email protected]>
+#       Copyright (C) 2013 Ivo Maffei <[email protected]>

-    Construct the generalised quadrangle `H(3,q^2)` with an ovoid
-    The GQ has order `(q^2,q)`
+    Construct the generalised quadrangle `H(3,q^2)` with an ovoid.
+
+    The GQ has order `(q^2,q)`.

[dimpase]

comment:3

Replying to @Ivo-Maffei:

At the moment the examples at the top of the file fail and they shouldn't.
In particular using the objects defined there one gets:

sage: set(GQ2._points) == set(range(1,1106))
False
sage: for i in GQ2._points:
....:     if i not in range(1,1106):
....:         print(i)
....:         
sage: for i in range(1,1106):
....:     if i not in GQ2._points:
....:         print(i)
....:      
sage:

I wonder if I'm missing something or if == is returning some weird output.

set(GQ2._points) consists of GAP's Integers, but in range(1,1106) you have Python <int>.

There is no automatic conversion between these set elements when you compare them:

sage: libgap(1)==int(1)
True
sage: type(libgap(1))
<class 'sage.libs.gap.element.GapElement_Integer'>
sage: set([libgap(1)])==set([int(1)])
False

[sagetrac-git]

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

0e82896	removed gap int; fixed some docstrings
ee0e18f	added references

[sagetrac-git]

Changed commit from 7555255 to ee0e18f

[dimpase]

comment:6

where is this supposed to be used?

[Ivo-Maffei]

comment:7

The point graph of a GQ removed its spread is distance-regular. It's shown in BCN 12.5.
I haven't yet made a ticket that puts the required code in distance_regular.pyx.

[dimpase]

comment:8

The description of
https://en.wikipedia.org/wiki/Generalized_quadrangle

How about renaming gen_quadrangles.pyx to gen_quadrangles_with_spread.pyx

Also, generalised_quadrangle_hermitian should be renamed to something like
generalised_quadrangle_hermitian_with_ovoid

Perhaps it makes sense to introduce spreads for general Sage's incidence systems
(sets of blocks that don't pairwise intersect and cover all the points) - then spreads here will be a particular case.

[Ivo-Maffei]

comment:9

Replying to @dimpase:

Perhaps it makes sense to introduce spreads for general Sage's incidence systems
(sets of blocks that don't pairwise intersect and cover all the points) - then spreads here will be a particular case.

Do you have any idea on how to do so? We could add a field to the IncidenceStructure class or make a subclass IncidenceStructureWithSpread...

[dimpase]

comment:10

I meant a member function that verifies that a given set of blocks is a spread.

[sagetrac-git]

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

9c44a33	Merge branch 9.2.beta9 into 30223
fdd9ae5	renamed method and file; some pep8
7f5dc6f	fix bugs due to renaming
9a56f1e	added is_spread method to incidence structures
a464a9c	stronger check for spread

[sagetrac-git]

Changed commit from ee0e18f to a464a9c

[dimpase]

comment:12

I get a memory error here:

File "src/sage/combinat/designs/gen_quadrangles_with_spread.pyx", line 257, in sage.combinat.designs.gen_quadrangles_with_spread.generalised_quadrangle_hermitian_with_ovoid
Failed example:
    t[0].is_generalized_quadrangle()  # long time
Exception raised:
...

and even worse crash (Bad Exit) here:

File "src/sage/combinat/designs/gen_quadrangles_with_spread.pyx", line 271, in sage.combinat.designs.gen_quadrangles_with_spread.generalised_quadrangle_hermitian_with_ovoid
Failed example:
    is_GQ_with_spread(*t, s=3, t=9)
Exception raised:
...

[Ivo-Maffei]

comment:13

I merged 9.2.beta10 and tried both:

sage -tp src/sage/combinat/designs/gen_quadrangles_with_spread.pyx
sage -tp --long src/sage/combinat/designs/gen_quadrangles_with_spread.pyx

They both terminate with all tests passed.
Could you try again with the merged branch and post the traceback?

[sagetrac-git]

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

fd8d1ba

Merge 9.2.beta10 into 30223

[sagetrac-git]

Changed commit from a464a9c to fd8d1ba

[dimpase]

comment:15

The non-long tests pass, but the long ones end up with

$ ./sage -tp 1 --long src/sage/combinat/designs/gen_quadrangles_with_spread.pyx 2>&1 >/tmp/p
Process DocTestWorker-1:
Traceback (most recent call last):
  File "/usr/lib/python3.7/multiprocessing/process.py", line 297, in _bootstrap
    self.run()
  File "/mnt/opt/Sage/sage-dev/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 2185, in run
    task(self.options, self.outtmpfile, msgpipe, self.result_queue)
  File "/mnt/opt/Sage/sage-dev/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 2535, in __call__
    result_queue.put(result, False)
  File "/usr/lib/python3.7/multiprocessing/queues.py", line 87, in put
    self._start_thread()
  File "/usr/lib/python3.7/multiprocessing/queues.py", line 170, in _start_thread
    self._thread.start()
  File "/usr/lib/python3.7/threading.py", line 852, in start
    _start_new_thread(self._bootstrap, ())
RuntimeError: can't start new thread

in

sage: t[0].is_generalized_quadrangle()  # long time ## line 257 ##

This seems to be limited to this machine, though. If I run the test in question at the Sage prompt
it takes about 30 sec and takes a lot of RAM.
A much quicker test for t[0] being GQ(16,4) is to look at the dual graph

sage: tt=t[0]                                                                                                                        
sage: ig=tt.intersection_graph([1])                                                                                                  
sage: ig.is_strongly_regular(parameters=True)                                                                                        
(325, 68, 3, 17)
sage: set(tt.block_sizes())                                                                                                          
{17}

Indeed, we got the collinearity graph of GQ(s,t)=GQ(4,16), as 68=s(t+1)=4*17, lambda=s-1=3, mu=t+1=17, and each of 325 blocks has size 17 (i.e. dually each of the 325 points has 17 blocks
of size s+1=5 on it).

[dimpase]

Changed reviewer from Samuel Lelièvre, ... to Samuel Lelièvre, Dima Pasechnik

[sagetrac-git]

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

250e3d7

change doctest to easier check

[sagetrac-git]

Changed commit from fd8d1ba to 250e3d7

[dimpase]

comment:17

perhaps on another ticket one should change the is_generalised_quadrangle to use this approach, it is faster.

[dimpase]

comment:18

I spoke too soon - docs don't build:

...
[dochtml] [combinat ] The inventory files are in local/share/doc/sage/inventory/en/reference/combinat.
[dochtml] Error building the documentation.
[dochtml] Traceback (most recent call last):
[dochtml]   File "/usr/lib/python3.7/runpy.py", line 193, in _run_module_as_main
[dochtml]     "__main__", mod_spec)
[dochtml]   File "/usr/lib/python3.7/runpy.py", line 85, in _run_code
[dochtml]     exec(code, run_globals)
[dochtml]   File "/mnt/opt/Sage/sage-dev/local/lib/python3.7/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module>
[dochtml]     main()
[dochtml]   File "/mnt/opt/Sage/sage-dev/local/lib/python3.7/site-packages/sage_setup/docbuild/__init__.py", line 1721, in main
[dochtml]     builder()
[dochtml]   File "/mnt/opt/Sage/sage-dev/local/lib/python3.7/site-packages/sage_setup/docbuild/__init__.py", line 328, in _wrapper
[dochtml]     getattr(get_builder(document), 'inventory')(*args, **kwds)
[dochtml]   File "/mnt/opt/Sage/sage-dev/local/lib/python3.7/site-packages/sage_setup/docbuild/__init__.py", line 553, in _wrapper
[dochtml]     self._build_everything_except_bibliography(lang, format, *args, **kwds)
[dochtml]   File "/mnt/opt/Sage/sage-dev/local/lib/python3.7/site-packages/sage_setup/docbuild/__init__.py", line 539, in _build_everything_except_bibliography
[dochtml]     build_many(build_ref_doc, non_references)
[dochtml]   File "/mnt/opt/Sage/sage-dev/local/lib/python3.7/site-packages/sage_setup/docbuild/__init__.py", line 281, in build_many
[dochtml]     _build_many(target, args, processes=NUM_THREADS)
[dochtml]   File "/mnt/opt/Sage/sage-dev/local/lib/python3.7/site-packages/sage_setup/docbuild/utils.py", line 283, in build_many
[dochtml]     raise worker_exc.original_exception
[dochtml] OSError: WARNING: autodoc: failed to import module 'gen_quadrangles' from module 'sage.combinat.designs'; the following exception was raised:
make[3]: *** [Makefile:1866: doc-html] Error 1

[dimpase]

comment:19

I suppose one needs

diff --git a/src/doc/en/reference/combinat/module_list.rst b/src/doc/en/reference/combinat/module_list.rst
index 39ca27c4a6..c8eca43954 100644
--- a/src/doc/en/reference/combinat/module_list.rst
+++ b/src/doc/en/reference/combinat/module_list.rst
@@ -104,7 +104,7 @@ Comprehensive Module list
     sage/combinat/designs/difference_matrices
     sage/combinat/designs/evenly_distributed_sets
     sage/combinat/designs/ext_rep
-    sage/combinat/designs/gen_quadrangles
+    sage/combinat/designs/gen_quadrangles_with_spread
     sage/combinat/designs/incidence_structures
     sage/combinat/designs/latin_squares
     sage/combinat/designs/orthogonal_arrays
diff --git a/src/sage/combinat/designs/__init__.py b/src/sage/combinat/designs/__init__.py
index f8de34936f..4808cf1a55 100644
--- a/src/sage/combinat/designs/__init__.py
+++ b/src/sage/combinat/designs/__init__.py
@@ -27,7 +27,7 @@ design catalog:
 - :ref:`sage.combinat.designs.steiner_quadruple_systems`
 - :ref:`sage.combinat.designs.twographs`
 - :ref:`sage.combinat.designs.database`
-- :ref:`sage.combinat.designs.gen_quadrangles`
+- :ref:`sage.combinat.designs.gen_quadrangles_with_spread`
 
 **Technical things**
 
diff --git a/src/sage/combinat/designs/design_catalog.py b/src/sage/combinat/designs/design_catalog.py
index 3a3c11597a..a9572e119c 100644
--- a/src/sage/combinat/designs/design_catalog.py
+++ b/src/sage/combinat/designs/design_catalog.py
@@ -59,7 +59,7 @@ This module gathers the following designs:
     :meth:`~sage.combinat.designs.steiner_quadruple_systems.steiner_quadruple_system`
     :meth:`~sage.combinat.designs.block_design.projective_plane`
     :meth:`~sage.combinat.designs.biplane`
-    :meth:`~sage.combinat.designs.gen_quadrangles`
+    :meth:`~sage.combinat.designs.gen_quadrangles_with_spread`
 
 And the :meth:`designs.best_known_covering_design_from_LJCR
 <sage.combinat.designs.covering_design.best_known_covering_design_www>` function

[sagetrac-git]

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

a0463d5	fix docsrtings; renamed module
5d16394	renamed in design_catalog

[sagetrac-git]

Changed commit from 250e3d7 to 5d16394

[vbraun]

Changed branch from u/gh-Ivo-Maffei/gen_quad to 5d16394

[videlec]

Changed commit from 5d16394 to none

[videlec]

comment:24

Replying to @dimpase:

Replying to @Ivo-Maffei:

At the moment the examples at the top of the file fail and they shouldn't.
In particular using the objects defined there one gets:

sage: set(GQ2._points) == set(range(1,1106))
False
sage: for i in GQ2._points:
....:     if i not in range(1,1106):
....:         print(i)
....:         
sage: for i in range(1,1106):
....:     if i not in GQ2._points:
....:         print(i)
....:      
sage:

I wonder if I'm missing something or if == is returning some weird output.

set(GQ2._points) consists of GAP's Integers, but in range(1,1106) you have Python <int>.

There is no automatic conversion between these set elements when you compare them:

sage: libgap(1)==int(1)
True
sage: type(libgap(1))
<class 'sage.libs.gap.element.GapElement_Integer'>
sage: set([libgap(1)])==set([int(1)])
False

To my mind this is a serious issue, see #30498.