Opened 7 years ago

Last modified 6 years ago

#16552 needs_work enhancement

oval in finite projective plane

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.4
Component: combinatorial designs Keywords:
Cc: ncohen, brett Merged in:
Authors: Vincent Delecroix Reviewers:
Report Upstream: N/A Work issues:
Branch: u/vdelecroix/16552 (Commits) Commit: f7989eb77ceb0f23b07568e8433d7a27b74861de
Dependencies: #16500, #16553 Stopgaps:

Description (last modified by vdelecroix)

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

Change History (12)

comment:1 Changed 7 years ago by ncohen

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

comment:2 Changed 7 years ago by vdelecroix

  • Branch set to u/vdelecroix/16552
  • Commit set to f7989eb77ceb0f23b07568e8433d7a27b74861de
  • Status changed from new to needs_review

Needs review.

And great speedup in the recursive constructions!!


Last 10 new commits:

9ff5062trac #16423: Table of MOLS from the handbook and comparison with Sage
e64be98trac #16423: tiny code improvement and alignment
e948cf6trac #16423: Aligning the alignment
0a7d853trac #16423: Broken doctests
b329351trac #16499: Cheap speedup in the OA recursive constructions
a67c04ftrac #16500: New recursive constructions of Orthogonal Arrays
41c50d5trac #16500: Simplified find_recursive_construction
e1992cetrac #16500: doc + speedup
697dd0ctrac #16500: Typoes in the doc
f7989ebtrac #16552: implement oval for projective plane

comment:3 follow-up: Changed 7 years ago by vdelecroix

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

comment:4 in reply to: ↑ 3 ; follow-up: Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_info

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

comment:5 in reply to: ↑ 4 ; follow-up: Changed 7 years ago by vdelecroix

Replying to ncohen:

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

comment:6 Changed 7 years ago by vdelecroix

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

comment:7 in reply to: ↑ 5 ; follow-up: Changed 7 years ago by ncohen

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

comment:8 in reply to: ↑ 7 ; follow-up: Changed 7 years ago by vdelecroix

Replying to ncohen:

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

comment:9 Changed 7 years ago by vdelecroix

and rewriting IncidenceStructure might overlap with #16534.

comment:10 in reply to: ↑ 8 Changed 7 years ago by ncohen

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

comment:11 Changed 7 years ago by vdelecroix

  • Dependencies changed from #16500 to #16500, #16553
  • Description modified (diff)
  • Status changed from needs_info to needs_work

Ok. Let us do that in #16553

comment:12 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.