redesign projective plane

[videlec]

Projective planes are currently implemented as block designs but are very slow to construct (see timings in #16272). Moreover the specifications and the behaviour are contradictory.

In this ticket

• we remove ProjectivePlaneDesign
• we create a function DesarguesianProjectivePlane that return the corresponding projective plane or raise a ValueError
• we create a function projective_plane that return a projective plane if there is an available construction, or raise a EmptySetError if no construction is possible or raise a NotImplementedError if no construction is currently available.

We also implement two translation functions projective_plane_to_OA and OA_to_projective_plane that make the translation between orthogonal arrays (with parameters k=n+1 and t=2) and projective planes.

This is an intermediate step for #16272. See also the follow up #16283 about construction of more projective planes.

CC: @nathanncohen

Component: combinatorics

Keywords: design, projective plane

Author: Vincent Delecroix

Branch/Commit: 51daa7f

Reviewer: Nathann Cohen

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

[videlec]

comment:1

Here it is...

---

New commits:

429d815

16281: rewrite projective planes (as 2-designs)

[videlec]

Commit: 429d815

[videlec]

Branch: u/vdelecroix/16281

[nathanncohen]

comment:3

Heeeeeeeeereis the review !

• Designs end with "Design", i.e. DesarguesianProjectivePlaneDesign. I don't say that it is a good idea, but that we should change it for all of them or not at all. Plus Dima will complain.

• Why not use deprecated_function_alias for designs.ProjectivePlaneDesign ?

• You can do this instead

  relabel = {x:i for i,x in enumerate(K)}
  Klist = relabel # Klist represent the set of elements of K
  

• projective_plane_to_OA: there is a function in bibd.py called _relabel_BIBD that takes a BIBD on n points as input (here it would be a projective plane) and relabels its elements in such a way that [[0,..,k-2,n],[k-1,...,2*k-2,n],...,[n-k-1,n-1]] are sets of the BIBD. So well. It actually does what you are doing : it relabels the BIBD such that when you remove all blocks containing n-1 you get a well-labelled TD.

• OA_to_projective_plane I implemented something VERY SIMILAR in BIBD from Transversal Designs #16279 but not equivalent :-)

• OA_to_projective_plane : Why do you need to relabel anything ?

  +    # add the n^2 lines that correspond to transversals
  +    for l in OA:
  +        blcks.append([i+(n+1)*j for i,j in enumerate(l)])
  

  The OA is already well labelled. The BIBD is exactly the blocks from the OA plus the k groups union the new element, isn't it ? This should just be a deepcopy.

• Isn't the triangle a Projective Plane of order 1 ?

Nathann

[videlec]

comment:4

Replying to @nathanncohen:

Heeeeeeeeereis the review !

Thanks!

• Designs end with "Design", i.e. DesarguesianProjectivePlaneDesign. I don't say that it is a good idea, but that we should change it for all of them or not at all. Plus Dima will complain.

Ok.

• Why not use deprecated_function_alias for designs.ProjectivePlaneDesign ?

Because of the argument "type"... funny isn't it?

• You can do this instead

  relabel = {x:i for i,x in enumerate(K)}
  Klist = relabel # Klist represent the set of elements of K
  

All right.

• projective_plane_to_OA: there is a function in bibd.py called _relabel_BIBD that takes a BIBD on n points as input (here it would be a projective plane) and relabels its elements in such a way that [[0,..,k-2,n],[k-1,...,2*k-2,n],...,[n-k-1,n-1]] are sets of the BIBD. So well. It actually does what you are doing : it relabels the BIBD such that when you remove all blocks containing n-1 you get a well-labelled TD.

• OA_to_projective_plane I implemented something VERY SIMILAR in BIBD from Transversal Designs #16279 but not equivalent :-)

• OA_to_projective_plane : Why do you need to relabel anything ?

  +    # add the n^2 lines that correspond to transversals
  +    for l in OA:
  +        blcks.append([i+(n+1)*j for i,j in enumerate(l)])
  

  The OA is already well labelled. The BIBD is exactly the blocks from the OA plus the k groups union the new element, isn't it ? This should just be a deepcopy.

I do not know what is a bibd and I did not have a look at it (except changing the call to ProjectivePlaneDesign). If you feel like removing more code I am happy with that but I will not do it (if you do, wait until the other remarks are implemented).

• Isn't the triangle a Projective Plane of order 1 ?

Nope: in a projective plane there should be a quadrilateral.

Vincent

[nathanncohen]

comment:5

Yo !

Because of the argument "type"... funny isn't it?

Come on.... I am not even sure this thing ever appeared in a public release, and it does nothing.... I think it is safe to use a deprecated_function_alias. Actually it is even safe to remove it without warning...

I do not know what is a bibd and I did not have a look at it (except changing the call to ProjectivePlaneDesign). If you feel like removing more code I am happy with that but I will not do it (if you do, wait until the other remarks are implemented).

Well. If you have a ProjectivePlane (a Projective Plane is a BIBD) named PP and do PP = _relabel_BIBD(PP) then if you remove from the new PP all blocks that contain the "maximum point" (i.e. n-1) then you have a properly labeled TD.

Nope: in a projective plane there should be a quadrilateral.

Right. I had some (theoretical) problems with degenerate projective planes recently :-P

Nathann

[videlec]

comment:6

Replying to @nathanncohen:

Yo !

Because of the argument "type"... funny isn't it?

Come on.... I am not even sure this thing ever appeared in a public release, and it does nothing.... I think it is safe to use a deprecated_function_alias. Actually it is even safe to remove it without warning...

All right. I remove it.

I do not know what is a bibd and I did not have a look at it (except changing the call to ProjectivePlaneDesign). If you feel like removing more code I am happy with that but I will not do it (if you do, wait until the other remarks are implemented).

Well. If you have a ProjectivePlane (a Projective Plane is a BIBD) named PP and do PP = _relabel_BIBD(PP) then if you remove from the new PP all blocks that contain the "maximum point" (i.e. n-1) then you have a properly labeled TD.

Ok. I see. Perfect.

Vincent

[nathanncohen]

comment:7

by the way: a BIBD is an edge-decomposition of a Complete graph on n elements with complete graphs of k elements. It is a collection of sets of size k such that any pair of elements in [n] belong to exactly one of these sets of size k. Somehow it is a projective plane with uniform lines, but two lines do not necessarily intersect.

Nathann

[sagetrac-git]

Changed commit from 429d815 to 3e5628a

[sagetrac-git]

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

3e5628a

16281: reviewer's comment 1

[videlec]

comment:9

I was not able to use the function '_relabel_bibd'. If you want to play with it...

[nathanncohen]

comment:11

I was not able to use the function '_relabel_bibd'. If you want to play with it...

Do you think that the "pt" argument is useful ? If it is not, I can rewrite this in 4-5 lines.

I do not think that it is useful, given that from the pair "PP,pt" there is not an "unique" resulting OA. So well, the function just creates a OA from a PP, and we cannot say much more.

Nathann

[nathanncohen]

comment:12

I added a commit that does that in public/16281

Nathann

[videlec]

comment:13

The thing is that the pair (pp,pt) gives a unique stuff up to isomorphism if and only if the automorphism group of the pp acts enough transitively... it is the case for Desarguesian planes but I do not no yet for the others.

[nathanncohen]

comment:14

The thing is that the pair (pp,pt) gives a unique stuff up to isomorphism if and only if the automorphism group of the pp acts enough transitively... it is the case for Desarguesian planes but I do not no yet for the others.

Do you think we could leave this for later, until somebody actually ... cares to compute this with Sage ?...

Nathann

[nathanncohen]

comment:15

new version in 10 minutes that leaves the feature.

Nathann

[nathanncohen]

comment:16

Here it is, in public/16281.

Nathann

[videlec]

comment:17

Hi Nathann,

Looks cool like that. Thanks.

Is that ready to go?

Vincent

[nathanncohen]

comment:18

In your construction of the projective plane I do not understand what you mean by the coordinates, especially while reading the code.

A way to make it clearer would be to define the following functions. If you have another idea I really don't mind, I just want to understand the code ^^;

pair_to_int = lambda x,y : relabel[x] + n*relabel[y]
infinity = lambda x : x + n2

This way we can read the code without trying to translate the coordinates ^^;

Nathann

[videlec]

comment:19

Hi,

The projective plane over a field is the set of equivalence classes of non-zero vectors (x,y,z) up to multiplication by a non-zero scalar. You can decompose the projective plane into:

• an affine plane: (x,y,1)
• an affine line "at infinity": (x,1,0)
• a point "at infinity": (1,0,0)
  I would prefer the names

affine_plane   = lambda x,y : relabel[x] + n*relabel[y]
line_infinity  = lambda x : x + n2
point_infinity = n2 + n 

I am making it.

Vincent

[nathanncohen]

comment:20

Well, what I find confusing is that you give all these things 3 coordinates, and I do not see the point O_o

For me there are three kinds of points, one with two coordinates one with 1, and the last one.

Nathann

[videlec]

comment:21

Three because of the definition I know... quotient out K^3 \ {0} by the positive scalar acting by multiplication. Then, you can manage to decompose into plane+line+point.

How about a HUGE comment as follows

# we decompose the points (x:y:z) of the projective space into an affine
# plane, an affine line and a point. At the same time, we relabel the points
# with the integers from 0 to n^2 + n. It is done as follows:
# the affine plane is the set of points (x:y:1) and gets relabeled
# from 0 to n^2-1
affine_plane   = lambda x,y: relabel[x] + n * relabel[y]
    
# the affine line is the set of points (x:1:0)
# and gets relabeld from n^2 to n^2 + n - 1
line_infinity  = lambda x: n2 + relabel[x]
    
# the point is (1:0:0)
# and gets relabeld n^2 + n
point_infinity = n2 + n

[nathanncohen]

comment:22

.......

Really, what force is making you define three coordinates for those points ? In which 3d space do they live ? O_O

Nathann

[nathanncohen]

comment:23

OOhhhhhhhhhh I see how you see it now... T_T

Well, I personally find the explanation clearer without any mention of the 3d coordinates... But well, it's up to you.. Tastes, I guess T_T

Nathann

[videlec]

comment:24

It is the standard definition of the projective plane: it is the set of vectorial lines in K^3. You need the coordinates to see which point is at infinity...

[nathanncohen]

comment:25

Defined as equivalence classes okay, but it stays abstract and you still have no coordinates. But then you say "I can either normalize the third coordinate if it is nonzero, otherwise I normalize the second coordinate,and if I can't I normalize the first".

Well... I am used to defined this thing with "three kinds of points" :-P

Anyway, if you can put this inside of the branch then no problem :-)

Nathann

[videlec]

comment:26

here you go

[sagetrac-git]

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

0812a73	trac #16281: Simplification
61dc86b	16281: long comment for the construction of the projective plane

[sagetrac-git]

Changed commit from 3e5628a to 61dc86b

[videlec]

comment:28

Oups: there is a warning in docbuild

.../block_design.py:docstring of sage.combinat.designs.block_design.projective_plane_to_OA:1: WARNING: Inline literal start-string without end-string.

[nathanncohen]

comment:29

Oh right. The ` after pplane. Well, you can set this to positive_review after this is fixed. Thanks for this patch !

Nathann

[nathanncohen]

Reviewer: Nathann Cohen

[sagetrac-git]

Changed commit from 61dc86b to 51daa7f

[sagetrac-git]

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

51daa7f

trac #16281: correct a doctest

[videlec]

comment:31

Great. Let's go back to #16272 and manage the merge...

[nathanncohen]

comment:32

Come ooooooooon. That will be easy.

Hey Vincent, I'm not sure I told you but it is great to work together on something. Stuff happens, gets merged and written. Much better than the usual "write a patch, then wait forever" :-P

Nathann

[vbraun]

Changed branch from u/vdelecroix/16281 to 51daa7f