Opened 6 years ago

Closed 6 years ago

#16281 closed enhancement (fixed)

redesign projective plane

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.3
Component: combinatorics Keywords: design, projective plane
Cc: ncohen Merged in:
Authors: Vincent Delecroix Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: 51daa7f (Commits) Commit: 51daa7fe6e225714fa666aa778ef08cc207264fb
Dependencies: Stopgaps:

Description (last modified by vdelecroix)

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.

Change History (34)

comment:1 Changed 6 years ago by vdelecroix

  • Branch set to u/vdelecroix/16281
  • Commit set to 429d815568a0e4a90e4968e55d45548f2e0c7262
  • Description modified (diff)
  • Status changed from new to needs_review

Here it is...


New commits:

429d81516281: rewrite projective planes (as 2-designs)

comment:2 Changed 6 years ago by vdelecroix

  • Description modified (diff)

comment:3 follow-up: Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_info

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

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

Replying to ncohen:

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

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

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

Last edited 6 years ago by ncohen (previous) (diff)

comment:6 in reply to: ↑ 5 Changed 6 years ago by vdelecroix

Replying to ncohen:

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

comment:7 Changed 6 years ago by ncohen

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

comment:8 Changed 6 years ago by git

  • Commit changed from 429d815568a0e4a90e4968e55d45548f2e0c7262 to 3e5628a2be9e09a15962dafba7a235d72b222888

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

3e5628a16281: reviewer's comment 1

comment:9 follow-up: Changed 6 years ago by vdelecroix

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

comment:10 Changed 6 years ago by vdelecroix

  • Description modified (diff)
  • Status changed from needs_info to needs_review

comment:11 in reply to: ↑ 9 Changed 6 years ago by ncohen

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

comment:12 Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_info

I added a commit that does that in public/16281

Nathann

comment:13 follow-up: Changed 6 years ago by vdelecroix

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.

comment:14 in reply to: ↑ 13 Changed 6 years ago by ncohen

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

comment:15 Changed 6 years ago by ncohen

new version in 10 minutes that leaves the feature.

Nathann

comment:16 Changed 6 years ago by ncohen

Here it is, in public/16281.

Nathann

comment:17 Changed 6 years ago by vdelecroix

  • Status changed from needs_info to needs_review

Hi Nathann,

Looks cool like that. Thanks.

Is that ready to go?

Vincent

comment:18 Changed 6 years ago by ncohen

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

comment:19 Changed 6 years ago by vdelecroix

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

comment:20 Changed 6 years ago by ncohen

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

comment:21 Changed 6 years ago by vdelecroix

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

comment:22 Changed 6 years ago by ncohen

.......

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

Nathann

comment:23 Changed 6 years ago by ncohen

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

comment:24 Changed 6 years ago by vdelecroix

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

comment:25 Changed 6 years ago by ncohen

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

comment:26 Changed 6 years ago by vdelecroix

here you go

comment:27 Changed 6 years ago by git

  • Commit changed from 3e5628a2be9e09a15962dafba7a235d72b222888 to 61dc86b759c59bbeb707bb6a35ce3e7b6b5d36aa

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

0812a73trac #16281: Simplification
61dc86b16281: long comment for the construction of the projective plane

comment:28 Changed 6 years ago by vdelecroix

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.

comment:29 Changed 6 years ago by ncohen

  • Reviewers set to Nathann Cohen

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

Nathann

comment:30 Changed 6 years ago by git

  • Commit changed from 61dc86b759c59bbeb707bb6a35ce3e7b6b5d36aa to 51daa7fe6e225714fa666aa778ef08cc207264fb

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

51daa7ftrac #16281: correct a doctest

comment:31 Changed 6 years ago by vdelecroix

  • Status changed from needs_review to positive_review

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

comment:32 Changed 6 years ago by ncohen

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

comment:33 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:34 Changed 6 years ago by vbraun

  • Branch changed from u/vdelecroix/16281 to 51daa7fe6e225714fa666aa778ef08cc207264fb
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.