#30223 closed enhancement (fixed)
Combinatorial designs: generate GQ with spread
Reported by:  ghIvoMaffei  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  combinatorial designs  Keywords:  generalised_quadrangle 
Cc:  Dima Pasechnik  Merged in:  
Authors:  Ivo Maffei  Reviewers:  Samuel Lelièvre, Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  5d16394 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
Implement a few functions to generate and work on generalised quadrangles with spreads.
In particular we construct H(3,q^2)
.
Change History (24)
comment:1 followup: 3 Changed 2 years ago by
comment:2 Changed 2 years ago by
Reviewers:  → Samuel Lelièvre, ... 

Type:  PLEASE CHANGE → enhancement 
Minor suggestions, no hurry.
 YOUR NAME (20050103): initial version + Ivo Maffei (20200726): initial version
# Copyright (C) 2013 IVO MAFFEI <ivomaffei@gmail.com> +# Copyright (C) 2013 Ivo Maffei <ivomaffei@gmail.com>
 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)`.
comment:3 followup: 24 Changed 2 years ago by
Replying to ghIvoMaffei:
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
comment:4 Changed 2 years ago by
Commit:  7555255d1f36e114affe73d46c6af602515c849b → ee0e18f36993d4b6529f2c3509d786b3a0249b05 

comment:5 Changed 2 years ago by
Description:  modified (diff) 

Status:  new → needs_review 
comment:7 Changed 2 years ago by
The point graph of a GQ removed its spread is distanceregular. It's shown in BCN 12.5. I haven't yet made a ticket that puts the required code in distance_regular.pyx.
comment:8 followup: 9 Changed 2 years ago by
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.
comment:9 Changed 2 years ago by
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
...
comment:10 Changed 2 years ago by
I meant a member function that verifies that a given set of blocks is a spread.
comment:11 Changed 2 years ago by
Commit:  ee0e18f36993d4b6529f2c3509d786b3a0249b05 → a464a9c08d164470bb744ded7bdb386cbc79e62b 

comment:12 Changed 2 years ago by
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: ...
comment:13 Changed 2 years ago by
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?
comment:14 Changed 2 years ago by
Commit:  a464a9c08d164470bb744ded7bdb386cbc79e62b → fd8d1baa2f65ae46567d39415bba4552f7f75607 

Branch pushed to git repo; I updated commit sha1. New commits:
fd8d1ba  Merge 9.2.beta10 into 30223

comment:15 Changed 2 years ago by
Reviewers:  Samuel Lelièvre, ... → Samuel Lelièvre, Dima Pasechnik 

Status:  needs_review → positive_review 
The nonlong 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 DocTestWorker1: Traceback (most recent call last): File "/usr/lib/python3.7/multiprocessing/process.py", line 297, in _bootstrap self.run() File "/mnt/opt/Sage/sagedev/local/lib/python3.7/sitepackages/sage/doctest/forker.py", line 2185, in run task(self.options, self.outtmpfile, msgpipe, self.result_queue) File "/mnt/opt/Sage/sagedev/local/lib/python3.7/sitepackages/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=s1=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).
comment:16 Changed 2 years ago by
Commit:  fd8d1baa2f65ae46567d39415bba4552f7f75607 → 250e3d77c71dac8fd23a1184f1a52a01820d4c0e 

Status:  positive_review → needs_review 
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
250e3d7  change doctest to easier check

comment:17 Changed 2 years ago by
Status:  needs_review → positive_review 

perhaps on another ticket one should change the is_generalised_quadrangle to use this approach, it is faster.
comment:18 Changed 2 years ago by
Status:  positive_review → needs_work 

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/sagedev/local/lib/python3.7/sitepackages/sage_setup/docbuild/__main__.py", line 2, in <module> [dochtml] main() [dochtml] File "/mnt/opt/Sage/sagedev/local/lib/python3.7/sitepackages/sage_setup/docbuild/__init__.py", line 1721, in main [dochtml] builder() [dochtml] File "/mnt/opt/Sage/sagedev/local/lib/python3.7/sitepackages/sage_setup/docbuild/__init__.py", line 328, in _wrapper [dochtml] getattr(get_builder(document), 'inventory')(*args, **kwds) [dochtml] File "/mnt/opt/Sage/sagedev/local/lib/python3.7/sitepackages/sage_setup/docbuild/__init__.py", line 553, in _wrapper [dochtml] self._build_everything_except_bibliography(lang, format, *args, **kwds) [dochtml] File "/mnt/opt/Sage/sagedev/local/lib/python3.7/sitepackages/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/sagedev/local/lib/python3.7/sitepackages/sage_setup/docbuild/__init__.py", line 281, in build_many [dochtml] _build_many(target, args, processes=NUM_THREADS) [dochtml] File "/mnt/opt/Sage/sagedev/local/lib/python3.7/sitepackages/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: dochtml] Error 1
comment:19 Changed 2 years ago by
I suppose one needs

src/doc/en/reference/combinat/module_list.rst
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 b Comprehensive Module list 104 104 sage/combinat/designs/difference_matrices 105 105 sage/combinat/designs/evenly_distributed_sets 106 106 sage/combinat/designs/ext_rep 107 sage/combinat/designs/gen_quadrangles 107 sage/combinat/designs/gen_quadrangles_with_spread 108 108 sage/combinat/designs/incidence_structures 109 109 sage/combinat/designs/latin_squares 110 110 sage/combinat/designs/orthogonal_arrays 
src/sage/combinat/designs/__init__.py
diff git a/src/sage/combinat/designs/__init__.py b/src/sage/combinat/designs/__init__.py index f8de34936f..4808cf1a55 100644
a b design catalog: 27 27  :ref:`sage.combinat.designs.steiner_quadruple_systems` 28 28  :ref:`sage.combinat.designs.twographs` 29 29  :ref:`sage.combinat.designs.database` 30  :ref:`sage.combinat.designs.gen_quadrangles `30  :ref:`sage.combinat.designs.gen_quadrangles_with_spread` 31 31 32 32 **Technical things** 33 33 
src/sage/combinat/designs/design_catalog.py
diff git a/src/sage/combinat/designs/design_catalog.py b/src/sage/combinat/designs/design_catalog.py index 3a3c11597a..a9572e119c 100644
a b This module gathers the following designs: 59 59 :meth:`~sage.combinat.designs.steiner_quadruple_systems.steiner_quadruple_system` 60 60 :meth:`~sage.combinat.designs.block_design.projective_plane` 61 61 :meth:`~sage.combinat.designs.biplane` 62 :meth:`~sage.combinat.designs.gen_quadrangles `62 :meth:`~sage.combinat.designs.gen_quadrangles_with_spread` 63 63 64 64 And the :meth:`designs.best_known_covering_design_from_LJCR 65 65 <sage.combinat.designs.covering_design.best_known_covering_design_www>` function
comment:20 Changed 2 years ago by
Commit:  250e3d77c71dac8fd23a1184f1a52a01820d4c0e → 5d16394c5bd7ba038f2a525a4759b7c197120100 

comment:21 Changed 2 years ago by
Status:  needs_work → needs_review 

comment:22 Changed 2 years ago by
Status:  needs_review → positive_review 

comment:23 Changed 2 years ago by
Branch:  u/ghIvoMaffei/gen_quad → 5d16394c5bd7ba038f2a525a4759b7c197120100 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:24 Changed 2 years ago by
Commit:  5d16394c5bd7ba038f2a525a4759b7c197120100 

Replying to dimpase:
Replying to ghIvoMaffei:
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 inrange(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.
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:
I wonder if I'm missing something or if
==
is returning some weird output.