Opened 7 years ago
Closed 7 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, GitHub, GitLab) | Commit: | 51daa7fe6e225714fa666aa778ef08cc207264fb |
Dependencies: | Stopgaps: |
Description (last modified by )
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 aValueError
- we create a function
projective_plane
that return a projective plane if there is an available construction, or raise aEmptySetError
if no construction is possible or raise aNotImplementedError
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 7 years ago by
- Branch set to u/vdelecroix/16281
- Commit set to 429d815568a0e4a90e4968e55d45548f2e0c7262
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 7 years ago by
- Description modified (diff)
comment:3 follow-up: ↓ 4 Changed 7 years ago by
- 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: ↓ 5 Changed 7 years ago by
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: ↓ 6 Changed 7 years ago by
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
comment:6 in reply to: ↑ 5 Changed 7 years ago by
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 doPP = _relabel_BIBD(PP)
then if you remove from the newPP
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 7 years ago by
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 7 years ago by
- Commit changed from 429d815568a0e4a90e4968e55d45548f2e0c7262 to 3e5628a2be9e09a15962dafba7a235d72b222888
Branch pushed to git repo; I updated commit sha1. New commits:
3e5628a | 16281: reviewer's comment 1
|
comment:9 follow-up: ↓ 11 Changed 7 years ago by
I was not able to use the function '_relabel_bibd'. If you want to play with it...
comment:10 Changed 7 years ago by
- Description modified (diff)
- Status changed from needs_info to needs_review
comment:11 in reply to: ↑ 9 Changed 7 years ago by
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 7 years ago by
- Status changed from needs_review to needs_info
I added a commit that does that in public/16281
Nathann
comment:13 follow-up: ↓ 14 Changed 7 years ago by
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 7 years ago by
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 7 years ago by
new version in 10 minutes that leaves the feature.
Nathann
comment:16 Changed 7 years ago by
Here it is, in public/16281.
Nathann
comment:17 Changed 7 years ago by
- Status changed from needs_info to needs_review
Hi Nathann,
Looks cool like that. Thanks.
Is that ready to go?
Vincent
comment:18 Changed 7 years ago by
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 7 years ago by
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 7 years ago by
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 7 years ago by
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 7 years ago by
.......
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 7 years ago by
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 7 years ago by
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 7 years ago by
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 7 years ago by
here you go
comment:27 Changed 7 years ago by
- Commit changed from 3e5628a2be9e09a15962dafba7a235d72b222888 to 61dc86b759c59bbeb707bb6a35ce3e7b6b5d36aa
comment:28 Changed 7 years ago by
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 7 years ago by
- 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 7 years ago by
- Commit changed from 61dc86b759c59bbeb707bb6a35ce3e7b6b5d36aa to 51daa7fe6e225714fa666aa778ef08cc207264fb
Branch pushed to git repo; I updated commit sha1. New commits:
51daa7f | trac #16281: correct a doctest
|
comment:31 Changed 7 years ago by
- Status changed from needs_review to positive_review
Great. Let's go back to #16272 and manage the merge...
comment:32 Changed 7 years ago by
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 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:34 Changed 7 years ago by
- Branch changed from u/vdelecroix/16281 to 51daa7fe6e225714fa666aa778ef08cc207264fb
- Resolution set to fixed
- Status changed from positive_review to closed
Here it is...
New commits:
16281: rewrite projective planes (as 2-designs)