Opened 2 years ago

Closed 2 years ago

# Combinatorial designs: generate GQ with spread

Reported by: Owned by: gh-Ivo-Maffei major sage-9.2 combinatorial designs generalised_quadrangle Dima Pasechnik Ivo Maffei Samuel Lelièvre, Dima Pasechnik N/A 5d16394

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

### comment:1 follow-up:  3 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, ... PLEASE CHANGE → enhancement

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 ; follow-up:  24 Changed 2 years ago by Dima Pasechnik

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: 7555255d1f36e114affe73d46c6af602515c849b → ee0e18f36993d4b6529f2c3509d786b3a0249b05

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

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

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

Description: modified (diff) new → needs_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 follow-up:  9 Changed 2 years ago by Dima Pasechnik

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

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: ee0e18f36993d4b6529f2c3509d786b3a0249b05 → a464a9c08d164470bb744ded7bdb386cbc79e62b

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`

### 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:
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:
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
```

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

Reviewers: Samuel Lelièvre, ... → Samuel Lelièvre, Dima Pasechnik needs_review → positive_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
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
File "/usr/lib/python3.7/multiprocessing/queues.py", line 170, in _start_thread
File "/usr/lib/python3.7/threading.py", line 852, in start
```

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: fd8d1baa2f65ae46567d39415bba4552f7f75607 → 250e3d77c71dac8fd23a1184f1a52a01820d4c0e 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 Dima Pasechnik

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

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/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]   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```
• ## 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```
• ## 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```

### comment:20 Changed 2 years ago by git

Commit: 250e3d77c71dac8fd23a1184f1a52a01820d4c0e → 5d16394c5bd7ba038f2a525a4759b7c197120100

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

 ​a0463d5 `fix docsrtings; renamed module` ​5d16394 `renamed in design_catalog`

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

Status: needs_work → needs_review

### comment:22 Changed 2 years ago by Dima Pasechnik

Status: needs_review → positive_review

### comment:23 Changed 2 years ago by Volker Braun

Branch: u/gh-Ivo-Maffei/gen_quad → 5d16394c5bd7ba038f2a525a4759b7c197120100 → fixed positive_review → closed

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

Commit: 5d16394c5bd7ba038f2a525a4759b7c197120100

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.