oval in finite projective plane

[videlec]

Build oval from conics in Desarguesian projective plane and use MILP to look for ovals in non-Desarguesian ones.

We use it to speed up some of the Wilson construction which requires an oval.

To be rewritten over #16553

Depends on #16500
Depends on #16553

CC: @nathanncohen @brettpim

Component: combinatorial designs

Author: Vincent Delecroix

Branch/Commit: u/vdelecroix/16552 @ f7989eb

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

[nathanncohen]

comment:1

Oh... And would you know how to compute hyperovals too ? I used a LP to compute the one I needed in #16528. It's precomputer so it does not matter, but well... :-)

Nathann

P.S. : Some day, all these functions will become methods of something, but I am really scared to know "what" :-D

[videlec]

Branch: u/vdelecroix/16552

[videlec]

Commit: f7989eb

[videlec]

comment:2

Needs review.

And great speedup in the recursive constructions!!

---

Last 10 new commits:

9ff5062	trac #16423: Table of MOLS from the handbook and comparison with Sage
e64be98	trac #16423: tiny code improvement and alignment
e948cf6	trac #16423: Aligning the alignment
0a7d853	trac #16423: Broken doctests
b329351	trac #16499: Cheap speedup in the OA recursive constructions
a67c04f	trac #16500: New recursive constructions of Orthogonal Arrays
41c50d5	trac #16500: Simplified find_recursive_construction
e1992ce	trac #16500: doc + speedup
697dd0c	trac #16500: Typoes in the doc
f7989eb	trac #16552: implement oval for projective plane

[videlec]

comment:3

and hyperovals are here too for GF(2^k) ;-)

[nathanncohen]

comment:4

and hyperovals are here too for GF(2^k) ;-)

Ahem. Vincent, I thank you for the feature but the code really needs some reorganization :-P

First, why wouldn't the system of coordinates be provided by DesarguesianProjectivePlane when you create one ? Clearly getting the "coordinates" of the points can be useful, and the only reason why it is not already the case is that BlockDesign only supports integers as a ground set. But you could return the dictionary along with the projective plane, couldn't you ?

additional question : is the _desarguesian_projective_plane_coordinates properly defined anyway ? Or is that why it is just an internal function ?

Similarly, the oval functions have no reason to return integers. They can just return the triples of coordinates.

Besides, we can't just dump "Oval functions" like that in block_designs.py. And... Well, though you were not the worst in the crowd, I think I can easily gather 50+ emails that were exchanged just because I created a ProjectivePlane function which returned a desarguesian projective plane. How can you now create a function as well defined as OvalInDesarguesianProjectivePlaneDesign ?.. :-P

Nathann

[videlec]

comment:5

Replying to @nathanncohen:

and hyperovals are here too for GF(2^k) ;-)

Ahem. Vincent, I thank you for the feature but the code really needs some reorganization :-P

First, why wouldn't the system of coordinates be provided by DesarguesianProjectivePlane when you create one ? Clearly getting the "coordinates" of the points can be useful, and the only reason why it is not already the case is that BlockDesign only supports integers as a ground set. But you could return the dictionary along with the projective plane, couldn't you ?

doable... You would like the answer of DesarguesianProjectivePlane to be a pair (projective plane, coordinates). But not very standardized with comparison to BIBD, OA, MOLS, etc.

I would rather create a class

class DesarguesianProjectivePlaneDesign(IncidenceStructure):
    def label(self, x, y, z):
        r"""
        Return the label of the class `[x:y:z]`
        """

but it is too much work for this ticket.

additional question : is the _desarguesian_projective_plane_coordinates properly defined anyway ? Or is that why it is just an internal function ?

No. What is well defined are the classes [x:y:z] which are elements of K^3 \ {0} up to multiplication by a non-zero scalar (i.e. lines in K^3). The labeling choice mapping it to integers is not canonical.

Similarly, the oval functions have no reason to return integers. They can just return the triples of coordinates.

Right, but in that case there is no need for a function:

sage: K = GF(17)
sage: oval = [(t,t^2,K.one()) for t in K] + [(K.zero(),K.one(),K.zero())]

Besides, we can't just dump "Oval functions" like that in block_designs.py. And... Well, though you were not the worst in the crowd, I think I can easily gather 50+ emails that were exchanged just because I created a ProjectivePlane function which returned a desarguesian projective plane. How can you now create a function as well defined as OvalInDesarguesianProjectivePlaneDesign ?.. :-P

The name is not quite appropriate for sure. I can call them PointOfTheConic_t_t2_1 if you prefer but if we would return triple of elements of GF(q) then there is no need for these functions.

Vincent

[videlec]

comment:6

And note that we already have from sage.schemes.projective.projective_space

sage: list(ProjectiveSpace(2,GF(2)))
[(0 : 0 : 1),
 (1 : 0 : 1),
 (0 : 1 : 1),
 (1 : 1 : 1),
 (0 : 1 : 0),
 (1 : 1 : 0),
 (1 : 0 : 0)]

[nathanncohen]

comment:7

Yo !

doable... You would like the answer of DesarguesianProjectivePlane to be a pair (projective plane, coordinates). But not very standardized with comparison to BIBD, OA, MOLS, etc.

Well.... You know how I would do it ... :-P

designs.DesarguesianProjectivePlane(return_coordinates=True)

I would rather create a class

That would the "most proper way".

but it is too much work for this ticket.

Hmmmm... Well, we will have to do that someday for many objects, it is just weird that we somehow need the objects and do not have so many functions to add to them...

Right, but in that case there is no need for a function:

sage: K = GF(17)
sage: oval = [(t,t^2,K.one()) for t in K] + [(K.zero(),K.one(),K.zero())]

Well, those three lines are all that the function should do. And as it is, it already helps dumb guys like me who did not even know (what ovals were) how to build an oval.

The name is not quite appropriate for sure. I can call them PointOfTheConic_t_t2_1 if you prefer but if we would return triple of elements of GF(q) then there is no need for these functions.

HMmmmmmmm.. I don't know how to implement that properly :-/

Nathann

[videlec]

comment:8

Replying to @nathanncohen:

Yo !

doable... You would like the answer of DesarguesianProjectivePlane to be a pair (projective plane, coordinates). But not very standardized with comparison to BIBD, OA, MOLS, etc.

Well.... You know how I would do it ... :-P

designs.DesarguesianProjectivePlane(return_coordinates=True)

I will create a decorator @output_type_depends_on_input especially for you!

I would rather create a class

That would the "most proper way".

If I do this I would rewrite partly the IncidenceStructure class (especially hide the attributes). For a class DesarguesianProjectivePlane there is no need to store the points or the blocks. It will be as fast as you whish to do it on the fly...

But then comes from the problem with labels... should we steal the implementation that is in graph?

Right, but in that case there is no need for a function:

sage: K = GF(17)
sage: oval = [(t,t^2,K.one()) for t in K] + [(K.zero(),K.one(),K.zero())]

Well, those three lines are all that the function should do. And as it is, it already helps dumb guys like me who did not even know (what ovals were) how to build an oval.

I was dump and wikipedia was my friend in that particular case.

The name is not quite appropriate for sure. I can call them PointOfTheConic_t_t2_1 if you prefer but if we would return triple of elements of GF(q) then there is no need for these functions.

HMmmmmmmm.. I don't know how to implement that properly :-/

For example:

sage: K = GF(3)
sage: P = designs.ProjectivePlane(K)
sage: R.<t> = K[t]
sage: oval = P.points_of_parametrized_curve((t,t^2))

Vincent

[videlec]

comment:9

and rewriting IncidenceStructure might overlap with #16534.

[nathanncohen]

comment:10

Yo !

I will create a decorator @output_type_depends_on_input especially for you!

We need a category of functions whose output depends on the input and combinatorial maps from there to everywhere else.

If I do this I would rewrite partly the IncidenceStructure class (especially hide the attributes).

Honestly, if you feel like working on IncidenceStructure we can rewrite it together. Up to now I have been alternatively 1) scared to use it because of the bugs I already found there 2) not sufficienty stuck to need to rewrite it.

For a class DesarguesianProjectivePlane there is no need to store the points or the blocks. It will be as fast as you whish to do it on the fly...

Ahahahah. Well, if you want to get better performances on this kind of stuff ...

But then comes from the problem with labels... should we steal the implementation that is in graph?

T_T

Well. If we .... sigh .... let block designs have a different ground set, we should do it in such a way that we can work with integers when we want to without being in trouble. Perhaps it just means that we need to have "integer" counterparts to every "labelled" function.

For example:

sage: K = GF(3)
sage: P = designs.ProjectivePlane(K)
sage: R.<t> = K[t]
sage: oval = P.points_of_parametrized_curve((t,t^2))

HMmmmm... I have no idea if it is the right place O_o

I really have no idea.... O_o

Nathann

[videlec]

Changed dependencies from #16500 to #16500, #16553

[videlec]

comment:11

Ok. Let us do that in #16553