This module gathers everything related to difference families. One can build a difference family (or check that it can be built) with difference_family():
sage: G,F = designs.difference_family(13,4,1)
It defines the following functions:
is_difference_family() | Check if the input is a (k, l)-difference family. |
difference_family() | Return a (k, l)-difference family on an Abelian group of size v. |
singer_difference_set() | Return a difference set associated to hyperplanes in a projective space. |
df_q_6_1() | Return a difference set with parameter \(k=6\) on a finite field. |
radical_difference_set() | Return a radical difference set |
radical_difference_family() | Return a radical difference family |
twin_prime_powers_difference_set() | Return a twin prime powers difference family. |
wilson_1972_difference_family() | Return a radical difference family on a finite field following a construction of Wilson. |
REFERENCES:
[Bu95] | M. Buratti “On simple radical difference families”, J. of Combinatorial Designs, vol. 3, no. 2 (1995) |
[Wi72] | (1, 2, 3, 4) R. M. Wilson “Cyclotomy and difference families in elementary Abelian groups”, J. of Num. Th., 4 (1972), pp. 17-47. |
Compute the left stabilizer of the block B under the action of G.
This function return the list of all \(x\in G\) such that \(x\cdot B=B\) (as a set).
INPUT:
EXAMPLES:
sage: from sage.combinat.designs.difference_family import block_stabilizer
sage: Z8 = Zmod(8)
sage: block_stabilizer(Z8, [Z8(0),Z8(2),Z8(4),Z8(6)])
[0, 2, 4, 6]
sage: block_stabilizer(Z8, [Z8(0),Z8(2)])
[0]
sage: C = cartesian_product([Zmod(4),Zmod(3)])
sage: block_stabilizer(C, [C((0,0)),C((2,0)),C((0,1)),C((2,1))])
[(0, 0), (2, 0)]
sage: b = map(Zmod(45),[1, 3, 7, 10, 22, 25, 30, 35, 37, 38, 44])
sage: block_stabilizer(Zmod(45),b)
[0]
Return a \((q,6,1)\)-difference family over the finite field \(K\).
The construction uses Theorem 11 of [Wi72].
EXAMPLES:
sage: from sage.combinat.designs.difference_family import is_difference_family, df_q_6_1
sage: prime_powers = [v for v in xrange(31,500,30) if is_prime_power(v)]
sage: parameters = [v for v in prime_powers if df_q_6_1(GF(v,'a'), existence=True)]
sage: print parameters
[31, 151, 181, 211, 241, 271, 331, 361, 421]
sage: for v in parameters:
....: K = GF(v, 'a')
....: df = df_q_6_1(K, check=True)
....: assert is_difference_family(K, df, v, 6, 1)
Return a (k, l)-difference family on an Abelian group of cardinality v.
Let \(G\) be a finite Abelian group. For a given subset \(D\) of \(G\), we define \(\Delta D\) to be the multi-set of differences \(\Delta D = \{x - y; x \in D, y \in D, x \not= y\}\). A \((G,k,\lambda)\)-difference family is a collection of \(k\)-subsets of \(G\), \(D = \{D_1, D_2, \ldots, D_b\}\) such that the union of the difference sets \(\Delta D_i\) for \(i=1,...b\), seen as a multi-set, contains each element of \(G \backslash \{0\}\) exactly \(\lambda\)-times.
When there is only one block, i.e. \(\lambda(v - 1) = k(k-1)\), then a \((G,k,\lambda)\)-difference family is also called a difference set.
See also Wikipedia article Difference_set.
If there is no such difference family, an EmptySetError is raised and if there is no construction at the moment NotImplementedError is raised.
INPUT:
OUTPUT:
A pair (G,D) made of a group \(G\) and a difference family \(D\) on that group. Or, if existence is True a troolean or if explain_construction is True a string.
EXAMPLES:
sage: G,D = designs.difference_family(73,4)
sage: G
Finite Field of size 73
sage: D
[[0, 1, 8, 64],
[0, 2, 16, 55],
[0, 3, 24, 46],
[0, 25, 54, 67],
[0, 35, 50, 61],
[0, 36, 41, 69]]
sage: print designs.difference_family(73, 4, explain_construction=True)
Radical difference family on a finite field
sage: G,D = designs.difference_family(15,7,3)
sage: G
The cartesian product of (Finite Field of size 3, Finite Field of size 5)
sage: D
[[(1, 1), (1, 4), (2, 2), (2, 3), (0, 0), (1, 0), (2, 0)]]
sage: print designs.difference_family(15,7,3,explain_construction=True)
Twin prime powers difference family
sage: print designs.difference_family(91,10,1,explain_construction=True)
Singer difference set
For \(k=6,7\) we look at the set of small prime powers for which a construction is available:
sage: def prime_power_mod(r,m):
....: k = m+r
....: while True:
....: if is_prime_power(k):
....: yield k
....: k += m
sage: from itertools import islice
sage: l6 = {True:[], False: [], Unknown: []}
sage: for q in islice(prime_power_mod(1,30), 60):
....: l6[designs.difference_family(q,6,existence=True)].append(q)
sage: l6[True]
[31, 121, 151, 181, 211, ..., 3061, 3121, 3181]
sage: l6[Unknown]
[61]
sage: l6[False]
[]
sage: l7 = {True: [], False: [], Unknown: []}
sage: for q in islice(prime_power_mod(1,42), 60):
....: l7[designs.difference_family(q,7,existence=True)].append(q)
sage: l7[True]
[337, 421, 463, 883, 1723, 3067, 3319, 3529, 3823, 3907, 4621, 4957, 5167]
sage: l7[Unknown]
[43, 127, 169, 211, ..., 4999, 5041, 5209]
sage: l7[False]
[]
List available constructions:
sage: for v in xrange(2,100):
....: constructions = []
....: for k in xrange(2,10):
....: for l in xrange(1,10):
....: if designs.difference_family(v,k,l,existence=True):
....: constructions.append((k,l))
....: _ = designs.difference_family(v,k,l)
....: if constructions:
....: print "%2d: %s"%(v, ', '.join('(%d,%d)'%(k,l) for k,l in constructions))
3: (2,1)
4: (3,2)
5: (2,1), (4,3)
6: (5,4)
7: (2,1), (3,1), (3,2), (4,2), (6,5)
8: (7,6)
9: (2,1), (4,3), (8,7)
10: (9,8)
11: (2,1), (4,6), (5,2), (5,4), (6,3)
13: (2,1), (3,1), (3,2), (4,1), (4,3), (5,5), (6,5)
15: (3,1), (4,6), (5,6), (7,3)
16: (3,2), (5,4), (6,2)
17: (2,1), (4,3), (5,5), (8,7)
19: (2,1), (3,1), (3,2), (4,2), (6,5), (9,4), (9,8)
21: (3,1), (4,3), (5,1), (6,3), (6,5)
22: (4,2), (6,5), (7,4), (8,8)
23: (2,1)
25: (2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (7,7), (8,7)
27: (2,1), (3,1)
28: (3,2), (6,5)
29: (2,1), (4,3), (7,3), (7,6), (8,4), (8,6)
31: (2,1), (3,1), (3,2), (4,2), (5,2), (5,4), (6,1), (6,5)
33: (3,1), (5,5), (6,5)
34: (4,2)
35: (5,2)
37: (2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (9,2), (9,8)
39: (3,1), (6,5)
40: (3,2), (4,1)
41: (2,1), (4,3), (5,1), (5,4), (6,3), (8,7)
43: (2,1), (3,1), (3,2), (4,2), (6,5), (7,2), (7,3), (7,6), (8,4)
45: (3,1), (5,1)
46: (4,2), (6,2)
47: (2,1)
49: (2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (8,7), (9,3)
51: (3,1), (5,2), (6,3)
52: (4,1)
53: (2,1), (4,3)
55: (3,1), (9,4)
57: (3,1), (7,3), (8,1)
59: (2,1)
61: (2,1), (3,1), (3,2), (4,3), (5,1), (5,4), (6,2), (6,3), (6,5)
63: (3,1)
64: (3,2), (4,1), (7,2), (7,6), (9,8)
65: (5,1)
67: (2,1), (3,1), (3,2), (6,5)
69: (3,1)
71: (2,1), (5,2), (5,4), (7,3), (7,6), (8,4)
73: (2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (8,7), (9,1), (9,8)
75: (3,1), (5,2)
76: (4,1)
79: (2,1), (3,1), (3,2), (6,5)
81: (2,1), (3,1), (4,3), (5,1), (5,4), (8,7)
83: (2,1)
85: (4,1), (7,2), (7,3), (8,2)
89: (2,1), (4,3), (8,7)
91: (6,1)
97: (2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (8,7), (9,3)
TESTS:
Check more of the Wilson constructions from [Wi72]:
sage: Q5 = [241, 281,421,601,641, 661, 701, 821,881]
sage: Q9 = [73, 1153, 1873, 2017]
sage: Q15 = [76231]
sage: Q4 = [13, 73, 97, 109, 181, 229, 241, 277, 337, 409, 421, 457]
sage: Q8 = [1009, 3137, 3697]
sage: for Q,k in [(Q4,4),(Q5,5),(Q8,8),(Q9,9),(Q15,15)]:
....: for q in Q:
....: assert designs.difference_family(q,k,1,existence=True) is True
....: _ = designs.difference_family(q,k,1)
Check Singer difference sets:
sage: sgp = lambda q,d: ((q**(d+1)-1)//(q-1), (q**d-1)//(q-1), (q**(d-1)-1)//(q-1))
sage: for q in range(2,10):
....: if is_prime_power(q):
....: for d in [2,3,4]:
....: v,k,l = sgp(q,d)
....: assert designs.difference_family(v,k,l,existence=True) is True
....: _ = designs.difference_family(v,k,l)
Check twin primes difference sets:
sage: for p in [3,5,7,9,11]:
....: v = p*(p+2); k = (v-1)/2; lmbda = (k-1)/2
....: G,D = designs.difference_family(v,k,lmbda)
Check the database:
sage: from sage.combinat.designs.database import DF sage: for v,k,l in DF: ....: df = designs.difference_family(v,k,l,check=True)
Check a failing construction (trac ticket #17528):
sage: designs.difference_family(9,3) Traceback (most recent call last): ... NotImplementedError: No construction available for (9,3,1)-difference family
Todo
Implement recursive constructions from Buratti “Recursive for difference matrices and relative difference families” (1998) and Jungnickel “Composition theorems for difference families and regular planes” (1978)
Return a triple (identity, operation, inverse) that define the operations on the group G.
EXAMPLES:
sage: from sage.combinat.designs.difference_family import group_law
sage: group_law(Zmod(3))
(0, <built-in function add>, <built-in function neg>)
sage: group_law(SymmetricGroup(5))
((), <built-in function mul>, <built-in function inv>)
sage: group_law(VectorSpace(QQ,3))
((0, 0, 0), <built-in function add>, <built-in function neg>)
Check wether D forms a difference family in the group G.
INPUT:
See also
EXAMPLES:
sage: from sage.combinat.designs.difference_family import is_difference_family
sage: G = Zmod(21)
sage: D = [[0,1,4,14,16]]
sage: is_difference_family(G, D, 21, 5)
True
sage: G = Zmod(41)
sage: D = [[0,1,4,11,29],[0,2,8,17,21]]
sage: is_difference_family(G, D, verbose=True)
Too few:
5 is obtained 0 times in blocks []
14 is obtained 0 times in blocks []
27 is obtained 0 times in blocks []
36 is obtained 0 times in blocks []
Too much:
4 is obtained 2 times in blocks [0, 1]
13 is obtained 2 times in blocks [0, 1]
28 is obtained 2 times in blocks [0, 1]
37 is obtained 2 times in blocks [0, 1]
False
sage: D = [[0,1,4,11,29],[0,2,8,17,22]]
sage: is_difference_family(G, D)
True
sage: G = Zmod(61)
sage: D = [[0,1,3,13,34],[0,4,9,23,45],[0,6,17,24,32]]
sage: is_difference_family(G, D)
True
sage: G = AdditiveAbelianGroup([3]*4)
sage: a,b,c,d = G.gens()
sage: D = [[d, -a+d, -c+d, a-b-d, b+c+d],
....: [c, a+b-d, -b+c, a-b+d, a+b+c],
....: [-a-b+c+d, a-b-c-d, -a+c-d, b-c+d, a+b],
....: [-b-d, a+b+d, a-b+c-d, a-b+c, -b+c+d]]
sage: is_difference_family(G, D)
True
The following example has a third block with a non-trivial stabilizer:
sage: G = Zmod(15)
sage: D = [[0,1,4],[0,2,9],[0,5,10]]
sage: is_difference_family(G,D,verbose=True)
It is a (15,3,1)-difference family
True
The function also supports multiplicative groups (non necessarily Abelian):
sage: G = DihedralGroup(8)
sage: x,y = G.gens()
sage: i = G.one()
sage: D1 = [[i,x,x^4], [i,x^2, y*x], [i,x^5,y], [i,x^6,y*x^2], [i,x^7,y*x^5]]
sage: is_difference_family(G, D1, 16, 3, 2)
True
sage: from sage.combinat.designs.bibd import BIBD_from_difference_family
sage: bibd = BIBD_from_difference_family(G,D1,lambd=2)
TESTS:
sage: K = GF(3^2,'z')
sage: z = K.gen()
sage: D = [[1,z+1,2]]
sage: _ = is_difference_family(K, D, verbose=True)
the number of differences (=6) must be a multiple of v-1=8
sage: _
False
Return a (v,k,l)-radical difference family.
Let \(K\) be a finite field. A radical difference family is a difference family on \(K\) whose blocks are made of either cyclotomic cosets or cyclotomic cosets together with \(0\). The terminology comes from M. Buratti article [Bu95] but the constructions go back to R. Wilson [Wi72].
EXAMPLES:
sage: from sage.combinat.designs.difference_family import radical_difference_family
sage: radical_difference_family(GF(73),9)
[[1, 2, 4, 8, 16, 32, 37, 55, 64]]
sage: radical_difference_family(GF(281),5)
[[1, 86, 90, 153, 232],
[4, 50, 63, 79, 85],
[5, 36, 149, 169, 203],
[7, 40, 68, 219, 228],
[9, 121, 212, 248, 253],
[29, 81, 222, 246, 265],
[31, 137, 167, 247, 261],
[32, 70, 118, 119, 223],
[39, 56, 66, 138, 263],
[43, 45, 116, 141, 217],
[98, 101, 109, 256, 279],
[106, 124, 145, 201, 267],
[111, 123, 155, 181, 273],
[156, 209, 224, 264, 271]]
Return a difference set made of a cyclotomic coset in the finite field K and with paramters k and l.
Most of these difference sets appear in chapter VI.18.48 of the Handbook of combinatorial designs.
EXAMPLES:
sage: from sage.combinat.designs.difference_family import radical_difference_set
sage: D = radical_difference_set(GF(7), 3, 1); D
[[1, 2, 4]]
sage: sorted(x-y for x in D[0] for y in D[0] if x != y)
[1, 2, 3, 4, 5, 6]
sage: D = radical_difference_set(GF(16,'a'), 6, 2)
sage: sorted(x-y for x in D[0] for y in D[0] if x != y)
[1,
1,
a,
a,
a + 1,
a + 1,
a^2,
a^2,
...
a^3 + a^2 + a + 1,
a^3 + a^2 + a + 1]
sage: for (v,k,l) in [(3,2,1), (7,3,1), (7,4,2), (11,5,2), (11,6,3),
....: (13,4,1), (16,6,2), (19,9,4), (19,10,5)]:
....:
....: assert radical_difference_set(GF(v,'a'), k, l, existence=True), "pb with v={} k={} l={}".format(v,k,l)
Return a difference set associated to the set of hyperplanes in a projective space of dimension \(d\) over \(GF(q)\).
A Singer difference set has parameters:
The idea of the construction is as follows. One consider the finite field \(GF(q^{d+1})\) as a vector space of dimension \(d+1\) over \(GF(q)\). The set of \(GF(q)\)-lines in \(GF(q^{d+1})\) is a projective plane and its set of hyperplanes form a balanced incomplete block design.
Now, considering a multiplicative generator \(z\) of \(GF(q^{d+1})\), we get a transitive action of a cyclic group on our projective plane from which it is possible to build a difference set.
The construction is given in details in [Stinson2004], section 3.3.
EXAMPLES:
sage: from sage.combinat.designs.difference_family import singer_difference_set, is_difference_family
sage: G,D = singer_difference_set(3,2)
sage: is_difference_family(G,D,verbose=True)
It is a (13,4,1)-difference family
True
sage: G,D = singer_difference_set(4,2)
sage: is_difference_family(G,D,verbose=True)
It is a (21,5,1)-difference family
True
sage: G,D = singer_difference_set(3,3)
sage: is_difference_family(G,D,verbose=True)
It is a (40,13,4)-difference family
True
sage: G,D = singer_difference_set(9,3)
sage: is_difference_family(G,D,verbose=True)
It is a (820,91,10)-difference family
True
Return a difference set on \(GF(p) \times GF(p+2)\).
The difference set is built from the following element of the cartesian product of finite fields \(GF(p) \times GF(p+2)\):
For more information see Wikipedia article Difference_set.
INPUT:
EXAMPLES:
sage: from sage.combinat.designs.difference_family import twin_prime_powers_difference_set
sage: G,D = twin_prime_powers_difference_set(3)
sage: G
The cartesian product of (Finite Field of size 3, Finite Field of size 5)
sage: D
[[(1, 1), (1, 4), (2, 2), (2, 3), (0, 0), (1, 0), (2, 0)]]
Wilson construction of difference families on finite field.
The construction appears in [Wi72].
INPUT:
EXAMPLES:
sage: from sage.combinat.designs.difference_family import wilson_1972_difference_family
sage: wilson_1972_difference_family(GF(13),4)
[[0, 1, 3, 9]]
sage: wilson_1972_difference_family(GF(337), 7, existence=True)
True
sage: from itertools import ifilter, count
sage: ppap = lambda k,r: ifilter(is_prime_power, (k*i+r for i in count(1)))
sage: it4 = ppap(4*3,1)
sage: for _ in range(7):
....: v = next(it4)
....: existence = wilson_1972_difference_family(GF(v,'a'), 4, existence=True)
....: print "v = {}: {}".format(v, existence)
v = 13: True
v = 25: True
v = 37: False
v = 49: True
v = 61: False
v = 73: True
v = 97: True
sage: it5 = ppap(5*4,1)
sage: for _ in range(7):
....: v = next(it5)
....: existence = wilson_1972_difference_family(GF(v,'a'), 5, existence=True)
....: print "v = {:3}: {}".format(v, existence)
v = 41: True
v = 61: True
v = 81: False
v = 101: False
v = 121: False
v = 181: False
v = 241: True
sage: it6 = ppap(6*5,1)
sage: for _ in range(7):
....: v = next(it6)
....: existence = wilson_1972_difference_family(GF(v,'a'), 6, existence=True)
....: print "v = {:3}: {}".format(v, existence)
v = 31: False
v = 61: False
v = 121: False
v = 151: False
v = 181: True
v = 211: True
v = 241: True
sage: it7 = ppap(7*6,1)
sage: for _ in range(7):
....: v = next(it7)
....: existence = wilson_1972_difference_family(GF(v,'a'), 7, existence=True)
....: print "v = {:3}: {}".format(v, existence)
v = 43: False
v = 127: False
v = 169: False
v = 211: False
v = 337: True
v = 379: False
v = 421: True