McFarland 1973 construction for difference sets #19778

videlec · 2015-12-24T17:44:12Z

We implement McFarland 1973 construction that gives more difference sets (only for large lambda though).

CC: @nathanncohen

Component: combinatorial designs

Author: Vincent Delecroix

Branch/Commit: 071779b

Reviewer: Nathann Cohen

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

The text was updated successfully, but these errors were encountered:

videlec · 2015-12-24T17:49:47Z

Branch: u/vdelecroix/19778

videlec · 2015-12-24T17:49:47Z

Commit: 14bdcab

videlec · 2015-12-24T17:49:47Z

New commits:

`14bdcab`	`Trac 19778: McFarland 1973 difference set construction`

nathanncohen · 2015-12-25T11:21:55Z

comment:2

input sections would be nice. The docstring of mcfarland_1973_construction is rather minimalistic.

You moved code around in difference_family, and from the diff it is difficult to guess what and why. Could you be more verbose?

Nathann

sagetrac-git · 2015-12-28T11:43:41Z

Changed commit from 14bdcab to 8bd17be

sagetrac-git · 2015-12-28T11:43:41Z

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

`8bd17be`	`Trac 19778: input blocks`

videlec · 2015-12-28T11:46:20Z

comment:5

Hello,

I moved the code around in difference_family in order to have all constructions that does not need the factorisation of v before. In other words

if does_construction1_work(v,k,l):
    ....
elif does_construction2_work(v,k,l):
    ...
else:
    v = factor(v)
    ...

Vincent

nathanncohen · 2015-12-28T11:51:21Z

comment:6

I'm not being passive-aggressive here, just asking the question: considering the following timings, do you think that we should care?

sage: %timeit [factor(i) for i in range(2,10000)]
10 loops, best of 3: 78.7 ms per loop
sage: %timeit [designs.difference_family(i,3,existence=True) for i in range(10000)]
1 loops, best of 3: 1.58 s per loop

I don't know if another timing makes more sense. I merely tried the first I could think of.

Nathann

videlec · 2015-12-28T11:54:25Z

comment:7

Replying to @nathanncohen:

I'm not being passive-aggressive here, just asking the question: considering the following timings, do you think that we should care?
sage: %timeit [factor(i) for i in range(2,10000)]
10 loops, best of 3: 78.7 ms per loop
sage: %timeit [designs.difference_family(i,3,existence=True) for i in range(10000)]
1 loops, best of 3: 1.58 s per loop
I don't know if another timing makes more sense. I merely tried the first I could think of.

This is more about code organization rather than timings. The previous version of the code was

D = None
... # try some stuff
if D is None:
    ... # try other stuff
if D is None:
    ... # try another one

nathanncohen · 2015-12-28T11:57:10Z

comment:8

This is more about code organization rather than timings.

If we chose to not care about this call to 'factor', could we have something like that?

f = factor(v)
if does_construction1_work(v,k,l):
    ....
elif does_construction2_work(v,k,l):
    ...
elif <tests involving f>:
    ...
elif <tests involving f>:
    ...
return False

nathanncohen · 2015-12-28T11:58:20Z

comment:9

Err: to make it clear: I did not mean that your changes should be reverted because the call to 'factor' was negligible. Quite the contrary --> can we go even further?

sagetrac-git · 2015-12-28T12:06:57Z

Changed commit from 8bd17be to b3dd88a

sagetrac-git · 2015-12-28T12:06:57Z

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

`b3dd88a`	`Trac 19778: code reorganization in difference_family`

videlec · 2015-12-28T12:08:42Z

comment:11

done. But there is still something annoying at the begining with the construction of the finite field K.

nathanncohen · 2015-12-28T13:32:02Z

comment:12

Hello again,

I have been staring for a while at the parameters v,k,l, looking for a way to avoid the database. Now number theory really isn't my thing, but I wonder about that: shouldn't the gcd of 'v,l,m' be very close to q^s? Actually, in the factorization of gcd(v,l,m) into pi,si, aren't we sure that q^s is equal to the largest value of pi^si.

Actually (please tell me if I am wrong) by developping k as a series I get that k=lambda+q^(2s), thus gcd(lambda,k) is a power of q greater than q^s (because both k and l can be divided by q^s).

I'm getting very convinced that q^s is actually equal to gcd(lambda,k).

Well, what do you think? :-/

Nathann

nathanncohen · 2015-12-28T13:56:36Z

comment:13

(all this, however, depends on whether I added the missing ')' where it belongs in the explicit formula for 'k' that you provide in mcfarland_1973_construction)

nathanncohen · 2015-12-28T14:38:31Z

comment:14

Just noticed that I was an idiot. Instead of computing gcd, isn't g^s equal to sqrt(k-l)? :-P

nathanncohen · 2015-12-28T17:09:08Z

comment:15

Just another note: if one can obtain q^s with sqrt(k-l), then one can get the value of q. It looks easy: k/l is equal to (q<sup>{s+1}-1)/(q</sup>s-1). Thus we can compute kq^s/l which is equal to q^{s+1}-1 and so compute q^{s+1}, which we can divide by q^s to get q.

sagetrac-git · 2015-12-28T18:14:51Z

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

`04c7acf`	`Trac 19778: get rid of mcfarland_1973_parameters`

sagetrac-git · 2015-12-28T18:14:51Z

Changed commit from b3dd88a to 04c7acf

videlec · 2015-12-28T18:16:34Z

comment:17

You are right. The only problem is actually to compute s from qs and q... I used is_prime_power twice and opened #19792 to implement a better solution.

Vincent

nathanncohen · 2015-12-29T11:25:13Z

comment:24

You are still in 6.x?

vbraun · 2015-12-29T17:53:08Z

comment:25

merge conflict

videlec · 2015-12-29T17:58:41Z

comment:26

Do you have an idea of the conflicter?

nathanncohen · 2015-12-30T16:04:11Z

comment:27

Beta2 is out, and the "conflicter" is this f******* "upper case" ticket #19789.

It seems that others are on the way, for Eulerian, Hamiltonian, Abelian, ...

People have time to waste.

Nathann

dimpase · 2015-12-31T09:00:14Z

comment:28

Replying to @nathanncohen:

Beta2 is out, and the "conflicter" is this f******* "upper case" ticket #19789.

It seems that others are on the way, for Eulerian, Hamiltonian, Abelian, ...

People have time to waste.

Other people might need to learn to spell, you know...

nathanncohen · 2015-12-31T09:03:31Z

comment:29

Other people might need to learn to spell, you know...

I have received complaints because my posts on sage-devel had a space before "!?;:", and that while it is the rule in french it is not so in english.

You and I are both right.

Nathann

dimpase · 2015-12-31T09:08:02Z

comment:30

Replying to @nathanncohen:

Other people might need to learn to spell, you know...

I have received complaints because my posts on sage-devel had a space before "!?;:", and that while it is the rule in french it is not so in english.

You and I are both right.

depending on the language: e.g. "Def blah():" is wrong in Python...

dimpase · 2015-12-31T09:18:56Z

comment:31

rebased...

dimpase · 2015-12-31T09:18:56Z

Changed commit from b582040 to e8bc5ca

dimpase · 2015-12-31T09:18:56Z

Changed branch from u/vdelecroix/19778 to public/19778beta2

nathanncohen · 2015-12-31T09:21:48Z

comment:32

AAAAAAAnd now by magic you have commits of ticket #19777 in this branch.

dimpase · 2015-12-31T09:27:28Z

comment:33

ohh, I swear I took clean (?) develop branch with 7.0.beta2...

dimpase · 2015-12-31T10:03:51Z

comment:34

OK, mea culpa, I have had these #19777 commits merged. However, I cannot seem to be able to rebase to get rid of them - even if I check out clean develop, get this public/19778beta2 branch, and try
git rebase develop -i, I see

pick 4d2c2f4 trac #19777: Three new SRGs and db update
pick 93bd357 trac #19777: Convert the other 2-intersection set
pick 14bdcab Trac 19778: McFarland 1973 difference set construction
pick 8bd17be Trac 19778: input blocks
pick b3dd88a Trac 19778: code reorganization in difference_family
pick 04c7acf Trac 19778: get rid of mcfarland_1973_parameters
pick 8fe3844 Trac 19778: input block
pick cf852fa trac #19778: Reviewer's commit
pick b582040 trac #19778: DOI

# Rebase 036455f..e8bc5ca onto 036455f
...

now I delete the top two lines (the 19777 commits) and proceed, and get

$ git rebase develop -i
error: could not apply 14bdcab... Trac 19778: McFarland 1973 difference set construction
...

which makes no freaking sense to me. Note that for some reason I don't even see my last commit
from public/19778beta2 (commit e8bc5ca4... "it is now one Ring to rule them all")
in this list, even though it is duly in the branch.

sagetrac-git · 2015-12-31T10:07:39Z

Changed commit from e8bc5ca to 071779b

sagetrac-git · 2015-12-31T10:07:39Z

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

`071779b`	`one Ring to...`

dimpase · 2015-12-31T10:10:36Z

comment:36

OK, removed that 19777...

videlec · 2016-01-22T01:08:40Z

comment:37

Are we good?

nathanncohen · 2016-01-22T11:39:12Z

comment:38

You can switch the status yourself I guess: Dima is the one who merged it.

Nathann

vbraun · 2016-01-23T20:42:33Z

Changed branch from public/19778beta2 to 071779b

videlec added this to the sage-7.0 milestone Dec 24, 2015

videlec added c: combinatorial designs labels Dec 24, 2015

videlec added the s: needs review label Dec 24, 2015

nathanncohen mannequin added s: needs work and removed s: needs review labels Dec 25, 2015

videlec added s: needs review and removed s: needs work labels Dec 28, 2015

vbraun added s: needs work and removed s: positive review labels Dec 29, 2015

dimpase added s: needs review and removed s: needs work labels Dec 31, 2015

This comment has been minimized.

Sign in to view

videlec added s: positive review and removed s: needs review labels Jan 22, 2016

videlec modified the milestones: sage-7.0, sage-7.1 Jan 22, 2016

vbraun removed the s: positive review label Jan 23, 2016

vbraun closed this as completed in 50e8ada Jan 23, 2016

McFarland 1973 construction for difference sets #19778

McFarland 1973 construction for difference sets #19778

Comments

videlec commented Dec 24, 2015

videlec commented Dec 24, 2015

videlec commented Dec 24, 2015

videlec commented Dec 24, 2015

nathanncohen mannequin commented Dec 25, 2015

sagetrac-git mannequin commented Dec 28, 2015

sagetrac-git mannequin commented Dec 28, 2015

videlec commented Dec 28, 2015

nathanncohen mannequin commented Dec 28, 2015

videlec commented Dec 28, 2015

nathanncohen mannequin commented Dec 28, 2015

nathanncohen mannequin commented Dec 28, 2015

sagetrac-git mannequin commented Dec 28, 2015

sagetrac-git mannequin commented Dec 28, 2015

videlec commented Dec 28, 2015

nathanncohen mannequin commented Dec 28, 2015

nathanncohen mannequin commented Dec 28, 2015

nathanncohen mannequin commented Dec 28, 2015

nathanncohen mannequin commented Dec 28, 2015

sagetrac-git mannequin commented Dec 28, 2015

sagetrac-git mannequin commented Dec 28, 2015

videlec commented Dec 28, 2015

nathanncohen mannequin commented Dec 29, 2015

vbraun commented Dec 29, 2015

videlec commented Dec 29, 2015

nathanncohen mannequin commented Dec 30, 2015

dimpase commented Dec 31, 2015

nathanncohen mannequin commented Dec 31, 2015

dimpase commented Dec 31, 2015

dimpase commented Dec 31, 2015

dimpase commented Dec 31, 2015

dimpase commented Dec 31, 2015

nathanncohen mannequin commented Dec 31, 2015

This comment has been minimized.

dimpase commented Dec 31, 2015

dimpase commented Dec 31, 2015

sagetrac-git mannequin commented Dec 31, 2015

sagetrac-git mannequin commented Dec 31, 2015

dimpase commented Dec 31, 2015

videlec commented Jan 22, 2016

nathanncohen mannequin commented Jan 22, 2016

vbraun commented Jan 23, 2016