Opened 2 years ago

Closed 2 years ago

Last modified 2 years ago

#30223 closed enhancement (fixed)

Combinatorial designs: generate GQ with spread

Reported by: gh-Ivo-Maffei Owned by:
Priority: major Milestone: sage-9.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:

Status badges

Description (last modified by gh-Ivo-Maffei)

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 Changed 2 years ago by gh-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.

comment:2 Changed 2 years ago by Samuel Lelièvre

Reviewers: Samuel Lelièvre, ...
Type: PLEASE CHANGEenhancement

Minor suggestions, no hurry.

-- YOUR NAME (2005-01-03): initial version
+- Ivo Maffei (2020-07-26): 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 in reply to:  1 ; Changed 2 years ago by Dima Pasechnik

Replying to gh-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

comment:4 Changed 2 years ago by git

Commit: 7555255d1f36e114affe73d46c6af602515c849bee0e18f36993d4b6529f2c3509d786b3a0249b05

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

0e82896removed gap int; fixed some docstrings
ee0e18fadded references

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

Description: modified (diff)
Status: newneeds_review

comment:6 Changed 2 years ago by Dima Pasechnik

where is this supposed to be used?

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

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.

comment:8 Changed 2 years ago by Dima Pasechnik

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 in reply to:  8 Changed 2 years ago by gh-Ivo-Maffei

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 Dima Pasechnik

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

comment:11 Changed 2 years ago by git

Commit: ee0e18f36993d4b6529f2c3509d786b3a0249b05a464a9c08d164470bb744ded7bdb386cbc79e62b

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

9c44a33Merge branch 9.2.beta9 into 30223
fdd9ae5renamed method and file; some pep8
7f5dc6ffix bugs due to renaming
9a56f1eadded is_spread method to incidence structures
a464a9cstronger check for spread

comment:12 Changed 2 years ago by Dima Pasechnik

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

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 git

Commit: a464a9c08d164470bb744ded7bdb386cbc79e62bfd8d1baa2f65ae46567d39415bba4552f7f75607

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

fd8d1baMerge 9.2.beta10 into 30223

comment:15 Changed 2 years ago by Dima Pasechnik

Reviewers: Samuel Lelièvre, ...Samuel Lelièvre, Dima Pasechnik
Status: needs_reviewpositive_review

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).

comment:16 Changed 2 years ago by git

Commit: fd8d1baa2f65ae46567d39415bba4552f7f75607250e3d77c71dac8fd23a1184f1a52a01820d4c0e
Status: positive_reviewneeds_review

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

250e3d7change doctest to easier check

comment:17 Changed 2 years ago by Dima Pasechnik

Status: needs_reviewpositive_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 Dima Pasechnik

Status: positive_reviewneeds_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/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

comment:19 Changed 2 years ago by Dima Pasechnik

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 
    104104    sage/combinat/designs/difference_matrices
    105105    sage/combinat/designs/evenly_distributed_sets
    106106    sage/combinat/designs/ext_rep
    107     sage/combinat/designs/gen_quadrangles
     107    sage/combinat/designs/gen_quadrangles_with_spread
    108108    sage/combinat/designs/incidence_structures
    109109    sage/combinat/designs/latin_squares
    110110    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: 
    2727- :ref:`sage.combinat.designs.steiner_quadruple_systems`
    2828- :ref:`sage.combinat.designs.twographs`
    2929- :ref:`sage.combinat.designs.database`
    30 - :ref:`sage.combinat.designs.gen_quadrangles`
     30- :ref:`sage.combinat.designs.gen_quadrangles_with_spread`
    3131
    3232**Technical things**
    3333
  • 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: 
    5959    :meth:`~sage.combinat.designs.steiner_quadruple_systems.steiner_quadruple_system`
    6060    :meth:`~sage.combinat.designs.block_design.projective_plane`
    6161    :meth:`~sage.combinat.designs.biplane`
    62     :meth:`~sage.combinat.designs.gen_quadrangles`
     62    :meth:`~sage.combinat.designs.gen_quadrangles_with_spread`
    6363
    6464And the :meth:`designs.best_known_covering_design_from_LJCR
    6565<sage.combinat.designs.covering_design.best_known_covering_design_www>` function

comment:20 Changed 2 years ago by git

Commit: 250e3d77c71dac8fd23a1184f1a52a01820d4c0e5d16394c5bd7ba038f2a525a4759b7c197120100

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

a0463d5fix docsrtings; renamed module
5d16394renamed in design_catalog

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

Status: needs_workneeds_review

comment:22 Changed 2 years ago by Dima Pasechnik

Status: needs_reviewpositive_review

comment:23 Changed 2 years ago by Volker Braun

Branch: u/gh-Ivo-Maffei/gen_quad5d16394c5bd7ba038f2a525a4759b7c197120100
Resolution: fixed
Status: positive_reviewclosed

comment:24 in reply to:  3 Changed 2 years ago by Vincent Delecroix

Commit: 5d16394c5bd7ba038f2a525a4759b7c197120100

Replying to dimpase:

Replying to gh-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.

Note: See TracTickets for help on using tickets.