Opened 3 years ago

Closed 3 years ago

#19221 closed enhancement (fixed)

Some new (n,2^k,1)-BIBD

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.9
Component: combinatorial designs Keywords:
Cc: vdelecroix, dimpase Merged in:
Authors: Nathann Cohen Reviewers: Vincent Delecroix, Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: 030794c (Commits) Commit: 030794cc97e9c5534ab28f359bab16ba5837deff
Dependencies: Stopgaps:

Description

This ticket implements a new construction of BIBD from a desarguesian projective plane. This gives us the (232,8,1)-BIBD needed for the database of strongly regular graphs, as well as some others.

Nathann

Attachments (1)

hyperoval.py (986 bytes) - added by vdelecroix 3 years ago.
Hyperovals in GF(2n)

Download all attachments as: .zip

Change History (42)

comment:1 Changed 3 years ago by ncohen

  • Branch set to u/ncohen/19221
  • Commit set to 7d4f0d8fd42077f760725b5a82b8c8515f01cc05
  • Status changed from new to needs_review

New commits:

7d4f0d8trac #19221: Some new (n,2^k,1)-BIBD

comment:2 Changed 3 years ago by git

  • Commit changed from 7d4f0d8fd42077f760725b5a82b8c8515f01cc05 to 0643aea106482ec5ceabec1c6e2daa7134d18b14

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

0643aeatrac #19221: Some new (n,2^k,1)-BIBD

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

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to needs_info

In OA_and_oval I proposed a standard method to build oval and hyperoval and you complained about coordinates (here). Now you are doing the very same for hyperovals thing but specialized in a function... not mentioning the fact that #16552 is stuck.

Moreover, why do you need GAP to build a hyperoval? These are rather trivial to construct (look at Colbourn-Dinitz, p. 709).

Changed 3 years ago by vdelecroix

Hyperovals in GF(2n)

comment:4 Changed 3 years ago by vdelecroix

See hyperoval.py for a much simpler way of building hyperovals in GF(2n).

comment:5 follow-up: Changed 3 years ago by dimpase

Nathann builds a maximal n-arc, whereas a hyperoval is a maximal 2-arc.

comment:6 in reply to: ↑ 3 Changed 3 years ago by dimpase

Replying to vdelecroix:

In OA_and_oval I proposed a standard method to build oval and hyperoval and you complained about coordinates (here). Now you are doing the very same for hyperovals thing but specialized in a function... not mentioning the fact that #16552 is stuck.

Moreover, why do you need GAP to build a hyperoval? These are rather trivial to construct (look at Colbourn-Dinitz, p. 709).

Denniston's construction needs an irreducible binary quadratic form GF(q), for q power of 2. It is not 100% trivial, IMHO (well, I am not a number theorist), and GAP knows how to do it, that's why.

Last edited 3 years ago by dimpase (previous) (diff)

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

Replying to dimpase:

Nathann builds a maximal n-arc, whereas a hyperoval is a maximal 2-arc.

I see thanks for the clarification!

Though, the complaints about coordinates (as in #16552 comment:4) is still valid. If we change the way the Sage Desarguesian plane is labeled, this code will not be valid anymore.

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

Though, the complaints about coordinates (as in #16552 comment:4) is still valid. If we change the way the Sage Desarguesian plane is labeled, this code will not be valid anymore.

I had had in on my computer for the last 10 minutes, but no way to push it yet. Oddly I can access web pages and ssh, but git doesn't want to hear anything.

comment:9 Changed 3 years ago by git

  • Commit changed from 0643aea106482ec5ceabec1c6e2daa7134d18b14 to 35c3de21f36e73a91e37207e4fb781bc51aadff9

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

35c3de2trac #19221: Labellings of Projective Planes

comment:10 Changed 3 years ago by ncohen

  • Status changed from needs_info to needs_review

comment:11 Changed 3 years ago by git

  • Commit changed from 35c3de21f36e73a91e37207e4fb781bc51aadff9 to 78d008dce6ad2f415dc703861b529f6fa0e95841

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

78d008dtrac #19221: Labellings of Projective Planes

comment:12 Changed 3 years ago by vdelecroix

  • Status changed from needs_review to positive_review

I feel better this way. I think I might recycle #16552 for gathering all known constructions of maximal arcs in Desarguesian projective planes.

comment:13 follow-up: Changed 3 years ago by dimpase

  • Status changed from positive_review to needs_info

hmm, I have done an analogous change to ProjectiveGeometryDesign in #19226, but I called coordinates "coordinates", not "labels", and I have chosen no coordinates as the default. How about we unify this?

I also do not understand how an invasive change of changing the behaviour to use by default coordinates for the DesarguesianProjectivePlaneDesign was done without an appropriate deprecation...

Last edited 3 years ago by dimpase (previous) (diff)

comment:14 Changed 3 years ago by dimpase

I also don't understand why there is a separate implementation of DesarguesianProjectivePlaneDesign(q), which can be replaced by ProjectiveGeometryDesign(2,1,q). How about just making DesarguesianProjectivePlaneDesign into an alias to the latter?

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

hmm, I have done an analogous change to ProjectiveGeometryDesign in #19226, but I called coordinates "coordinates", not "labels", and I have chosen no coordinates as the default. How about we unify this?

1) 'labels' occurs is many Sage methods, and so I chose this term as users will after a time 'get used' to it. 'coordinates' is also meaningful in the context of projective planes, but will not be meaningful for all functions that [will/will not] add labels. And I would like to avoid this: Graph.is_tree(certificate=True),is_prime(get_data=True),Graph.is_strongly_regular(parameters=True),IncidenceStructrure.is_t_design(return_parameters=True). In terms of interface, I think that 'certificate' everywhere would have been better.

For the choice of coordinates, I made the usual choice: from most user-friendly to least user-friendly. Like we have a 'check' argument (enabled by default) that can be diabled if needed, like Graph.edges() returns edge labels are Graph.edges(labels=False) does not.

I also do not understand how an invasive change of changing the behaviour to use by default coordinates for the DesarguesianProjectivePlaneDesign was done without an appropriate deprecation...

Because it apparently does not break anything that was claimed previously by its documentation. Also, because it is clearly an improvement.

I also don't understand why there is a separate implementation of DesarguesianProjectivePlaneDesign?(q), which can be replaced by ProjectiveGeometryDesign?(2,1,q). How about just making DesarguesianProjectivePlaneDesign? into an alias to the latter?

If I remember correctly, the explanation to that lies in the running times.

Nathann

comment:16 Changed 3 years ago by ncohen

  • Status changed from needs_info to needs_review

Please set to positive_review if your doubts have been cleared.

Nathann

comment:17 Changed 3 years ago by vbraun

  • Branch changed from u/ncohen/19221 to 78d008dce6ad2f415dc703861b529f6fa0e95841
  • Resolution set to fixed
  • Status changed from needs_review to closed

comment:18 Changed 3 years ago by ncohen

  • Commit 78d008dce6ad2f415dc703861b529f6fa0e95841 deleted

Okayyyyyyy... That settles it I guess XD

comment:19 Changed 3 years ago by vbraun

  • Resolution fixed deleted
  • Status changed from closed to new

When I merged it, this was positive review. Please figure out what you want to do first

comment:20 Changed 3 years ago by vbraun

  • Status changed from new to needs_info

comment:21 Changed 3 years ago by ncohen

Well, I personally don't mind if this gets merged. Dima asked something about it afterwards, let's see if he still wonders about it.

comment:22 Changed 3 years ago by dimpase

Volker, it's clearly a workflow bug that your "merge" is not recorded anywhere on the ticket. Just because different reviewers might have different opinions, and they need to converge on a consensus. IMHO an open ticket must be a fair game for its status change.

comment:23 follow-up: Changed 3 years ago by vbraun

As I said it before, the bug is that people still can make changes after "positive review". Really you should open a new ticket. If you have different opinions then talk about it before setting it to positive review. The only alternative is that the ticket is immediately closed when I merge it, in which case you don't get to change away from positive review either.

comment:24 in reply to: ↑ 15 ; follow-up: Changed 3 years ago by dimpase

Replying to ncohen:

hmm, I have done an analogous change to ProjectiveGeometryDesign in #19226, but I called coordinates "coordinates", not "labels", and I have chosen no coordinates as the default. How about we unify this?

1) 'labels' occurs is many Sage methods, and so I chose this term as users will after a time 'get used' to it. 'coordinates' is also meaningful in the context of projective planes, but will not be meaningful for all functions that [will/will not] add labels. And I would like to avoid this:

but labels are meant to be user-defineable. Calling a set of labels chosen by the implementation labels is unhelpful and uninformative, to say the least.

Graph.is_tree(certificate=True),is_prime(get_data=True),Graph.is_strongly_regular(parameters=True),IncidenceStructrure.is_t_design(return_parameters=True). In terms of interface, I think that 'certificate' everywhere would have been better.

For the choice of coordinates, I made the usual choice: from most user-friendly to least user-friendly. Like we have a 'check' argument (enabled by default) that can be diabled if needed, like Graph.edges() returns edge labels are Graph.edges(labels=False) does not.

I also do not understand how an invasive change of changing the behaviour to use by default coordinates for the DesarguesianProjectivePlaneDesign was done without an appropriate deprecation...

Because it apparently does not break anything that was claimed previously by its documentation. Also, because it is clearly an improvement.

well, as you know, even Sage library code used the implementation's labellings in some places, instead of doing this via ground_set()...

I also don't understand why there is a separate implementation of DesarguesianProjectivePlaneDesign?(q), which can be replaced by ProjectiveGeometryDesign?(2,1,q). How about just making DesarguesianProjectivePlaneDesign? into an alias to the latter?

If I remember correctly, the explanation to that lies in the running times.

Indeed, it's 50 times faster on PG(2,16). I wonder why...

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

but labels are meant to be user-defineable

Whaaaat? I don't know what makes you think that. labels=False makes sense to me. There is nothing in that word that says 'user-defineable' or anything. If you want to change the labels, .relabel is there for you.

Calling a set of labels chosen by the implementation labels is unhelpful and uninformative, to say the least.

It just means that the structure is not integer-labelled. Any way I cannot care less: if you chose to overlook that all our functions will have as many ways to call the same thing (labels, coordinate, ... do you see this end?) then I will not fight again, it's your win anytime because you are the reviewer and by Sage's laws you can make my life hell until I give up.

So add a commit.

If I remember correctly, the explanation to that lies in the running times.

Indeed, it's 50 times faster on PG(2,16). I wonder why...

Surprising. Might be because we are multiplying the elements of the ground set using Sage, which is always slow for ... well, everything. Perhaps the way PG is called changed in the meantime, I do not remember. If you feel bad about it you can write a ticket, it's always good to see speed improvements.

Nathann

comment:26 in reply to: ↑ 23 Changed 3 years ago by dimpase

Replying to vbraun:

As I said it before, the bug is that people still can make changes after "positive review". Really you should open a new ticket.

There should be some grace period, at least, then. Say, 24 hours sounds reasonable (unless it's a blocker etc). Opening a new ticket is not very practical, as things to discuss are then not there...

If you have different opinions then talk about it before setting it to positive review.

yes, but the ticket was set to positive review at something like 5am my present (PST) time.

The only alternative is that the ticket is immediately closed when I merge it, in which case you don't get to change away from positive review either.

comment:27 in reply to: ↑ 25 ; follow-up: Changed 3 years ago by dimpase

Replying to ncohen:

but labels are meant to be user-defineable

Whaaaat? I don't know what makes you think that. labels=False makes sense to me. There is nothing in that word that says 'user-defineable' or anything. If you want to change the labels, .relabel is there for you.

well, .relabel() does relabel things in a user-defineable way (at least it has this option).

Calling a set of labels chosen by the implementation labels is unhelpful and uninformative, to say the least.

It just means that the structure is not integer-labelled. Any way I cannot care less: if you chose to overlook that all our functions will have as many ways to call the same thing (labels, coordinate, ... do you see this end?) then I will not fight again, it's your win anytime because you are the reviewer and by Sage's laws you can make my life hell until I give up.

I merely say that coordinates is more informative name for this parameter. Do you agree? If yes, I will change this on #19226, to make it uniform with ProjectiveGeometryDesign.

So add a commit.

this ticket is closed, as you know. How about #19226?

If I remember correctly, the explanation to that lies in the running times.

Indeed, it's 50 times faster on PG(2,16). I wonder why...

Surprising. Might be because we are multiplying the elements of the ground set using Sage, which is always slow for ... well, everything. Perhaps the way PG is called changed in the meantime, I do not remember. If you feel bad about it you can write a ticket, it's always good to see speed improvements.

probably it's because it handles the case of 1-dimensional subspaces by generic code, which does linear algebra on matrices...

comment:28 in reply to: ↑ 27 Changed 3 years ago by ncohen

well, .relabel() does relabel things in a user-defineable way (at least it has this option).

Yeah. That's why it is called *re*label. Saying that an object is labelled or unlabelled is not exactly new, is it? That's the meaning that it has in the function I defined.

I merely say that coordinates is more informative name for this parameter. Do you agree? If yes, I will change this on #19226, to make it uniform with ProjectiveGeometryDesign.

I agree that it is more informative, and I disagree that it is what should be used here. Because of the reason I mentionned earlier, i.e. having the same thing that goes under different names in different functions.

this ticket is closed, as you know. How about #19226?

I am not sure. I have no idea if it was merged or not in the end, to be honest. It is in needs_info, and I think that Volker 'unmerged it' because of the conversation you just had.

Nathann

comment:29 follow-up: Changed 3 years ago by dimpase

Are there any (combinatorial/graph theory) constructors in Sage with parameter labels= ?

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

Are there any (combinatorial/graph theory) constructors in Sage with parameter labels= ?

Don't know exactly. I was thinking of adding one in posets.BooleanLattice. You also have the 'digraphs.DeBruijn?(vertices="strings")', which I forgot in the list of the names that get adapted to every specific situation. Probably others, I don't know.

Nathann

comment:31 in reply to: ↑ 30 ; follow-up: Changed 3 years ago by dimpase

Replying to ncohen:

Are there any (combinatorial/graph theory) constructors in Sage with parameter labels= ?

Don't know exactly. I was thinking of adding one in posets.BooleanLattice. You also have the digraphs.DeBruijn(vertices="strings"), which I forgot in the list of the names that get adapted to every specific situation. Probably others, I don't k now.

vertices="blah" is a good one, it's right to the point. Perhaps point_coordinates=T/F would be even better than coordinates=T/F in our case. But labels=T/F is not clear at all: indeed what is being labelled, and how, can only be read in the docs...

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

vertices="blah" is a good one, it's right to the point. Perhaps point_coordinates=T/F would be even better than coordinates=T/F in our case. But labels=T/F is not clear at all: indeed what is being labelled, and how, can only be read in the docs...

It's probably just that I am dead tired of typing G.is_strongly_regular(parameters=True), just before getting an error because it should be return_parameters=True and to do the very same mistake in the other direction with is_t_design. I do this 10 times a day at least, no joke.

Add a commit. I won't fight for that.

Nathann

comment:33 Changed 3 years ago by dimpase

  • Status changed from needs_info to positive_review

let's get this closed; I'll do the changes we just discussed on #19226.

comment:34 Changed 3 years ago by ncohen

NONONONO, in another ticket. #19226 already does sufficiently many things.

comment:35 Changed 3 years ago by dimpase

  • Status changed from positive_review to needs_work

comment:36 in reply to: ↑ 32 ; follow-up: Changed 3 years ago by vbraun

Replying to ncohen:

It's probably just that I am dead tired of typing G.is_strongly_regular(parameters=True), just before getting an error because it should be return_parameters=True and to do the very same mistake in the other direction with is_t_design. I do this 10 times a day at least, no joke.

The solution is to have proper names for methods, not random (and not tab-discoverable) keyword arguments to change the output to contradict the method name:

sage: obj.is_foo(parameters=True)
(42, 'cherry')

What does that tell me without reading the docs? Nothing. VS:

sage: obj.enumerated_fruit()
(42, 'cherry')

comment:37 Changed 3 years ago by dimpase

and implementation-wise, it's matter of adding aliases: (say, G.parameters_strong_regularity := G.is_strongly_regular(parameters=True)), etc.

comment:38 Changed 3 years ago by dimpase

  • Branch changed from 78d008dce6ad2f415dc703861b529f6fa0e95841 to public/19221
  • Commit set to 030794cc97e9c5534ab28f359bab16ba5837deff
  • Reviewers changed from Vincent Delecroix to Vincent Delecroix, Dima Pasechnik
  • Status changed from needs_work to needs_review

comment:39 in reply to: ↑ 36 Changed 3 years ago by ncohen

The solution is to have proper names for methods, not random (and not tab-discoverable) keyword arguments to change the output to contradict the method name:

Probably. What should we do?

designs.DesarguesianProjectivePlaneWithHomogeneousCoordinates?

Look great.

Nathann

comment:40 Changed 3 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:41 Changed 3 years ago by vbraun

  • Branch changed from public/19221 to 030794cc97e9c5534ab28f359bab16ba5837deff
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.