Difference families#
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:
Check whether |
|
Test whether |
|
Compute the left stabilizer of the block |
|
Return a \((q,6,1)\)-difference family over the finite field \(K\). |
|
Return a ( |
|
Return a triple |
|
Make a product of two Hadamard difference sets. |
|
Check whether |
|
Check if \(R\) is a difference set of \(G\) relative to \(H\), with the given parameters. |
|
Check that the sets in |
|
Return a difference set. |
|
Given a subset |
|
Search for a radical difference family on |
|
Return a |
|
Return a difference set made of a cyclotomic coset in the finite field |
|
Construct \(R((q^N-1)/(q-1), n, q^{N-1}, q^{N-2}d)\) where \(nd = q-1\). |
|
Construct \(R((q^N-1)/(q-1), q-1, q^{N-1}, q^{N-2})\) where \(q\) is a prime power and \(N\ge 2\). |
|
Return a difference set associated to the set of hyperplanes in a projective space of dimension \(d\) over \(GF(q)\). |
|
Construct \(4-\{n; n_1, n_2, n_3, n_4; \lambda\}\) supplementary difference sets where \(S_1\) is skew and \(n_1+n_2+n_3+n_4= n+\lambda\). |
|
Construct \(4-\{2v; v, v+1, v, v; 2v\}\) supplementary difference sets where \(q=2v+1\). |
|
Return a difference set in either \(C_3 \times C_3 \times C_4\) or \(C_3 \times C_3 \times C_2 \times C_2\) with parameters \(v=36\), \(k=15\), \(\lambda=6\). |
|
Return a difference set on \(GF(p) \times GF(p+2)\). |
REFERENCES:
T. Beth, D. Jungnickel, H. Lenz “Design theory Vol. I.” Second edition. Encyclopedia of Mathematics and its Applications, 69. Cambridge University Press, (1999).
T. Beth, D. Jungnickel, H. Lenz “Design theory Vol. II.” Second edition. Encyclopedia of Mathematics and its Applications, 78. Cambridge University Press, (1999).
R. C. Bose, “On the construction of balanced incomplete block designs”, Ann. Eugenics, 9 (1939), 353–399.
M. Buratti “On simple radical difference families”, J. Combinatorial Designs, 3 (1995) 161–168.
R. J. Turyn “Character sum and difference sets” Pacific J. Math. 15 (1965) 319–346.
R. J. Turyn “A special class of Williamson matrices and difference sets” J. Combinatorial Theory (A) 36 (1984) 111–115.
Functions#
- sage.combinat.designs.difference_family.are_hadamard_difference_set_parameters(v, k, lmbda)#
Check whether
(v,k,lmbda)
is of the form(4N^2, 2N^2 - N, N^2 - N)
.INPUT:
(v,k,lmbda)
– parameters of a difference set
EXAMPLES:
sage: from sage.combinat.designs.difference_family import are_hadamard_difference_set_parameters sage: are_hadamard_difference_set_parameters(36, 15, 6) True sage: are_hadamard_difference_set_parameters(60, 13, 5) False
- sage.combinat.designs.difference_family.are_mcfarland_1973_parameters(v, k, lmbda, return_parameters=False)#
Test whether
(v,k,lmbda)
is a triple that can be obtained from the construction from [McF1973].See
mcfarland_1973_construction()
.INPUT:
v
,k
,lmbda
- (integers) parameters of the difference familyreturn_parameters
– (boolean, defaultFalse
) ifTrue
return a pair(True, (q, s))
so that(q,s)
can be used in the functionmcfarland_1973_construction()
to actually build a(v,k,lmbda)
-difference family. Or(False, None)
if the construction is not possible.
EXAMPLES:
sage: from sage.combinat.designs.difference_family import are_mcfarland_1973_parameters sage: are_mcfarland_1973_parameters(64, 28, 12) True sage: are_mcfarland_1973_parameters(64, 28, 12, return_parameters=True) (True, (2, 2)) sage: are_mcfarland_1973_parameters(60, 13, 5) False sage: are_mcfarland_1973_parameters(98125, 19500, 3875) True sage: are_mcfarland_1973_parameters(98125, 19500, 3875, True) (True, (5, 3)) sage: from sage.combinat.designs.difference_family import are_mcfarland_1973_parameters sage: for v in range(1, 100): ....: for k in range(1,30): ....: for l in range(1,15): ....: if are_mcfarland_1973_parameters(v,k,l): ....: answer, (q,s) = are_mcfarland_1973_parameters(v,k,l,return_parameters=True) ....: print("{} {} {} {} {}".format(v,k,l,q,s)) ....: assert answer is True ....: assert designs.difference_family(v,k,l,existence=True) is True ....: G,D = designs.difference_family(v,k,l) 16 6 2 2 1 45 12 3 3 1 64 28 12 2 2 96 20 4 4 1
- sage.combinat.designs.difference_family.block_stabilizer(G, B)#
Compute the left stabilizer of the block
B
under the action ofG
.This function return the list of all \(x\in G\) such that \(x\cdot B=B\) (as a set).
INPUT:
G
– a group (additive or multiplicative).B
– a subset ofG
.
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 = list(map(Zmod(45),[1, 3, 7, 10, 22, 25, 30, 35, 37, 38, 44])) sage: block_stabilizer(Zmod(45),b) [0]
- sage.combinat.designs.difference_family.df_q_6_1(K, existence=False, check=True)#
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 range(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) is True] sage: 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)
Todo
Do improvements due to Zhen and Wu 1999.
- sage.combinat.designs.difference_family.difference_family(v, k, l=1, existence=False, explain_construction=False, check=True)#
Return a (
k
,l
)-difference family on an Abelian group of cardinalityv
.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 momentNotImplementedError
is raised.INPUT:
v,k,l
– parameters of the difference family. Ifl
is not provided it is assumed to be1
.existence
– ifTrue
, then return eitherTrue
if Sage knows how to build such design,Unknown
if it does not andFalse
if it knows that the design does not exist.explain_construction
– instead of returning a difference family, returns a string that explains the construction used.check
– boolean (default:True
). IfTrue
then the result of the computation is checked before being returned. This should not be needed but ensures that the output is correct.
OUTPUT:
A pair
(G,D)
made of a group \(G\) and a difference family \(D\) on that group. Or, ifexistence
isTrue
a troolean or ifexplain_construction
isTrue
a string.EXAMPLES:
sage: G,D = designs.difference_family(73,4) sage: G Finite Field of size 73 sage: D [[0, 1, 5, 18], [0, 3, 15, 54], [0, 9, 45, 16], [0, 27, 62, 48], [0, 8, 40, 71], [0, 24, 47, 67]] sage: print(designs.difference_family(73, 4, explain_construction=True)) The database contains a (73,4)-evenly distributed set sage: G,D = designs.difference_family(15,7,3) sage: G Ring of integers modulo 15 sage: D [[0, 1, 2, 4, 5, 8, 10]] sage: print(designs.difference_family(15,7,3,explain_construction=True)) Singer difference set sage: print(designs.difference_family(91,10,1,explain_construction=True)) Singer difference set sage: print(designs.difference_family(64,28,12, explain_construction=True)) McFarland 1973 construction sage: print(designs.difference_family(576, 276, 132, explain_construction=True)) Hadamard difference set product from N1=2 and N2=3
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), int(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), int(60)): ....: l7[designs.difference_family(q,7,existence=True)].append(q) sage: l7[True] [169, 337, 379, 421, 463, 547, 631, 673, 757, 841, 883, 967, ..., 4621, 4957, 5167] sage: l7[Unknown] [43, 127, 211, 2017, 2143, 2269, 2311, 2437, 2521, 2647, ..., 4999, 5041, 5209] sage: l7[False] []
List available constructions:
sage: for v in range(2,100): ....: constructions = [] ....: for k in range(2,10): ....: for l in range(1,10): ....: ret = designs.difference_family(v,k,l,existence=True) ....: if ret is 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,1), (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), (7,1) 97: (2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (8,7), (9,3)
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)
- sage.combinat.designs.difference_family.group_law(G)#
Return a triple
(identity, operation, inverse)
that define the operations on the groupG
.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>)
- sage.combinat.designs.difference_family.hadamard_difference_set_product(G1, D1, G2, D2)#
Make a product of two Hadamard difference sets.
This product construction appears in [Tu1984].
INPUT:
G1,D1
,G2,D2
– two Hadamard difference sets
EXAMPLES:
sage: from sage.combinat.designs.difference_family import hadamard_difference_set_product sage: from sage.combinat.designs.difference_family import is_difference_family sage: G1,D1 = designs.difference_family(16,6,2) sage: G2,D2 = designs.difference_family(36,15,6) sage: G11,D11 = hadamard_difference_set_product(G1,D1,G1,D1) sage: assert is_difference_family(G11, D11, 256, 120, 56) sage: assert designs.difference_family(256, 120, 56, existence=True) is True sage: G12,D12 = hadamard_difference_set_product(G1,D1,G2,D2) sage: assert is_difference_family(G12, D12, 576, 276, 132) sage: assert designs.difference_family(576, 276, 132, existence=True) is True
- sage.combinat.designs.difference_family.hadamard_difference_set_product_parameters()#
Check whether a product construction is available for Hadamard difference set with parameter
N
.This function looks for two integers \(N_1\) and \(N_2`\) greater than \(1\) and so that \(N = 2 N_1 N_2\) and there exists Hadamard difference set with parameters \((4 N_i^2, 2N_i^2 - N_i, N_i^2 - N_i)\). If such pair exists, the output is the pair
(N_1, N_2)
otherwise it isNone
.INPUT:
N
– positive integer
EXAMPLES:
sage: from sage.combinat.designs.difference_family import hadamard_difference_set_product_parameters sage: hadamard_difference_set_product_parameters(8) (2, 2)
- sage.combinat.designs.difference_family.is_difference_family(G, D, v=None, k=None, l=None, verbose=False)#
Check whether
D
forms a difference family in the groupG
.INPUT:
G
– group of cardinalityv
D
– a set ofk
-subsets ofG
v
,k
andl
– optional parameters of the difference familyverbose
- whether to print additional information
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)
- sage.combinat.designs.difference_family.is_relative_difference_set(R, G, H, params, verbose=False)#
Check if \(R\) is a difference set of \(G\) relative to \(H\), with the given parameters.
This function checks that \(G\), \(H\) and \(R\) have the orders specified in the parameters, and that \(R\) satisfies the definition of relative difference set (from [EB1966]): the collection of differences \(r-s\), \(r,s \in R\), \(r \neq s\) contains only elements of \(G\) which are not in \(H\), and contains every such element exactly \(d\) times.
INPUT:
R
– list, the relative diffeence set of length \(k\).G
– an additive abelian group of order \(mn\).H
– a submodule ofG
of order \(n\).params
– a tuple in the form \((m, n, k, d)\).verbose
– boolean (default False). If true the function will be verbose when the sequences do not satisfy the contraints.
EXAMPLES:
sage: from sage.combinat.designs.difference_family import _get_submodule_of_order, relative_difference_set_from_m_sequence, is_relative_difference_set sage: q, N = 5, 2 sage: G = AdditiveAbelianGroup([q^N-1]) sage: H = _get_submodule_of_order(G, q-1) sage: params = ((q^N-1)//(q-1), q-1, q^(N-1), q^(N-2)) sage: R = relative_difference_set_from_m_sequence(q, N) sage: is_relative_difference_set(R, G, H, params) True
If we pass the
verbose
argument, the function will explain why it failed:sage: R2 = [G[1], G[2], G[3], G[5], G[6]] sage: is_relative_difference_set(R2, G, H, params, verbose=True) There is a value in the difference set which is not repeated d times False
- sage.combinat.designs.difference_family.is_supplementary_difference_set(Ks, v, lmbda)#
Check that the sets in
Ks
are \(n-\{v; k_1,...,k_n; \lambda \}\) supplementary difference sets.From the definition in [Spe1975]: let \(S_1, S_2, ..., S_n\) be \(n\) subsets of an additive abelian group \(G\) of order \(v\) such that \(|S_i|= k_i\). If, for each \(g\in G\), \(g \neq 0\), the total number of solutions of \(a_i-a'_i = g\), with \(a_i,a'_i \in S_i\) is \(\lambda\), then \(S_1, S_2, ..., S_n\) are \(n-\{v; k_1,...,k_n;\lambda\}\) supplementary difference sets.
INPUT:
Ks
– a list of sets to be checked.v
– integer, the parameter \(v\) of the supplementary difference sets.lmbda
– integer, the parameter \(\lambda\) of the supplementary difference sets.
EXAMPLES:
sage: from sage.combinat.designs.difference_family import supplementary_difference_set, is_supplementary_difference_set sage: S1, S2, S3, S4 = supplementary_difference_set(17) sage: is_supplementary_difference_set([S1, S2, S3, S4], 16, 16) True sage: is_supplementary_difference_set([S1, S2, S3, S4], 16, 14) False sage: is_supplementary_difference_set([S1, S2, S3, S4], 20, 16) False
See also
- sage.combinat.designs.difference_family.mcfarland_1973_construction(q, s)#
Return a difference set.
The difference set returned has the following parameters
\[v = \frac{q^{s+1}(q^{s+1}+q-2)}{q-1}, k = \frac{q^s (q^{s+1}-1)}{q-1}, \lambda = \frac{q^s(q^s-1)}{q-1}\]This construction is due to [McF1973].
INPUT:
q
,s
- (integers) parameters for the difference set (see the above formulas for the expression ofv
,k
,l
in terms ofq
ands
)
See also
The function
are_mcfarland_1973_parameters()
makes the translation between the parameters \((q,s)\) corresponding to a given triple \((v,k,\lambda)\).REFERENCES:
[McF1973] (1,2,3)Robert L. McFarland “A family of difference sets in non-cyclic groups” J. Combinatorial Theory (A) 15 (1973) 1–10. doi:10.1016/0097-3165(73)90031-9
EXAMPLES:
sage: from sage.combinat.designs.difference_family import ( ....: mcfarland_1973_construction, is_difference_family) sage: G,D = mcfarland_1973_construction(3, 1) sage: assert is_difference_family(G, D, 45, 12, 3) sage: G,D = mcfarland_1973_construction(2, 2) sage: assert is_difference_family(G, D, 64, 28, 12)
- sage.combinat.designs.difference_family.one_cyclic_tiling(A, n)#
Given a subset
A
of the cyclic additive group \(G = Z / nZ\) return another subset \(B\) so that \(A + B = G\) and \(|A| |B| = n\) (i.e. any element of \(G\) is uniquely expressed as a sum \(a+b\) with \(a\) in \(A\) and \(b\) in \(B\)).EXAMPLES:
sage: from sage.combinat.designs.difference_family import one_cyclic_tiling sage: tile = [0,2,4] sage: m = one_cyclic_tiling(tile,6); m [0, 3] sage: sorted((i+j)%6 for i in tile for j in m) [0, 1, 2, 3, 4, 5] sage: def print_tiling(tile, translat, n): ....: for x in translat: ....: print(''.join('X' if (i-x)%n in tile else '.' for i in range(n))) sage: tile = [0, 1, 2, 7] sage: m = one_cyclic_tiling(tile, 12) sage: print_tiling(tile, m, 12) XXX....X.... ....XXX....X ...X....XXX. sage: tile = [0, 1, 5] sage: m = one_cyclic_tiling(tile, 12) sage: print_tiling(tile, m, 12) XX...X...... ...XX...X... ......XX...X ..X......XX. sage: tile = [0, 2] sage: m = one_cyclic_tiling(tile, 8) sage: print_tiling(tile, m, 8) X.X..... ....X.X. .X.X.... .....X.X
ALGORITHM:
Uses dancing links
sage.combinat.dlx
- sage.combinat.designs.difference_family.one_radical_difference_family(K, k)#
Search for a radical difference family on
K
using dancing links algorithm.For the definition of radical difference family, see
radical_difference_family()
. Here, we consider only radical difference family with \(\lambda = 1\).INPUT:
K
– a finite field of cardinality \(q\).k
– a positive integer so that \(k(k-1)\) divides \(q-1\).
OUTPUT:
Either a difference family or
None
if it does not exist.ALGORITHM:
The existence of a radical difference family is equivalent to a one dimensional tiling (or packing) problem in a cyclic group. This subsequent problem is solved by a call to the function
one_cyclic_tiling()
.Let \(K^*\) be the multiplicative group of the finite field \(K\). A radical family has the form \(\mathcal B = \{x_1 B, \ldots, x_k B\}\), where \(B=\{x:x^{k}=1\}\) (for \(k\) odd) or \(B=\{x:x^{k-1}=1\}\cup \{0\}\) (for \(k\) even). Equivalently, \(K^*\) decomposes as:
\[K^* = \Delta (x_1 B) \cup \cdots \cup \Delta (x_k B) = x_1 \Delta B \cup \cdots \cup x_k \Delta B.\]We observe that \(C=B\backslash 0\) is a subgroup of the (cyclic) group \(K^*\), that can thus be generated by some element \(r\). Furthermore, we observe that \(\Delta B\) is always a union of cosets of \(\pm C\) (which is twice larger than \(C\)).
\[\begin{split}\begin{array}{llll} (k\text{ odd} ) & \Delta B &= \{r^i-r^j:r^i\neq r^j\} &= \pm C\cdot \{r^i-1: 0 < i \leq m\}\\ (k\text{ even}) & \Delta B &= \{r^i-r^j:r^i\neq r^j\}\cup C &= \pm C\cdot \{r^i-1: 0 < i < m\}\cup \pm C \end{array}\end{split}\]where
\[(k\text{ odd})\ m = (k-1)/2 \quad \text{and} \quad (k\text{ even})\ m = k/2.\]Consequently, \(\mathcal B = \{x_1 B, \ldots, x_k B\}\) is a radical difference family if and only if \(\{x_1 (\Delta B/(\pm C)), \ldots, x_k (\Delta B/(\pm C))\}\) is a partition of the cyclic group \(K^*/(\pm C)\).
EXAMPLES:
sage: from sage.combinat.designs.difference_family import ( ....: one_radical_difference_family, ....: is_difference_family) sage: one_radical_difference_family(GF(13),4) [[0, 1, 3, 9]]
The parameters that appear in [Bu95]:
sage: df = one_radical_difference_family(GF(449), 8); df [[0, 1, 18, 25, 176, 324, 359, 444], [0, 9, 88, 162, 222, 225, 237, 404], [0, 11, 140, 198, 275, 357, 394, 421], [0, 40, 102, 249, 271, 305, 388, 441], [0, 49, 80, 93, 161, 204, 327, 433], [0, 70, 99, 197, 230, 362, 403, 435], [0, 121, 141, 193, 293, 331, 335, 382], [0, 191, 285, 295, 321, 371, 390, 392]] sage: is_difference_family(GF(449), df, 449, 8, 1) True
- sage.combinat.designs.difference_family.radical_difference_family(K, k, l=1, existence=False, check=True)#
Return a
(v,k,l)
-radical difference family.Let fix an integer \(k\) and a prime power \(q = t k(k-1) + 1\). Let \(K\) be a field of cardinality \(q\). A \((q,k,1)\)-difference family is radical if its base blocks are either: a coset of the \(k\)-th root of unity for \(k\) odd or a coset of \(k-1\)-th root of unity and \(0\) if \(k\) is even (the number \(t\) is the number of blocks of that difference family).
The terminology comes from M. Buratti article [Bu95] but the first constructions go back to R. Wilson [Wi72].
INPUT:
K
- a finite fieldk
– positive integer, the size of the blocksl
– the \(\lambda\) parameter (default to \(1\))existence
– ifTrue
, then return eitherTrue
if Sage knows how to build such design,Unknown
if it does not andFalse
if it knows that the design does not exist.check
– boolean (default:True
). IfTrue
then the result of the computation is checked before being returned. This should not be needed but ensures that the output is correct.
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]] sage: for k in range(5,10): ....: print("k = {}".format(k)) ....: list_q = [] ....: for q in range(k*(k-1)+1, 2000, k*(k-1)): ....: if is_prime_power(q): ....: K = GF(q,'a') ....: if radical_difference_family(K, k, existence=True) is True: ....: list_q.append(q) ....: _ = radical_difference_family(K,k) ....: print(" ".join(str(p) for p in list_q)) k = 5 41 61 81 241 281 401 421 601 641 661 701 761 821 881 1181 1201 1301 1321 1361 1381 1481 1601 1681 1801 1901 k = 6 181 211 241 631 691 1531 1831 1861 k = 7 337 421 463 883 1723 k = 8 449 1009 k = 9 73 1153 1873
- sage.combinat.designs.difference_family.radical_difference_set(K, k, l=1, existence=False, check=True)#
Return a difference set made of a cyclotomic coset in the finite field
K
and with parametersk
andl
.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 k in range(2,50): ....: for l in reversed(divisors(k*(k-1))): ....: v = k*(k-1)//l + 1 ....: if is_prime_power(v) and radical_difference_set(GF(v,'a'),k,l,existence=True) is True: ....: _ = radical_difference_set(GF(v,'a'),k,l) ....: print("{:3} {:3} {:3}".format(v,k,l)) 3 2 1 4 3 2 7 3 1 5 4 3 7 4 2 13 4 1 11 5 2 7 6 5 11 6 3 16 6 2 8 7 6 9 8 7 19 9 4 37 9 2 73 9 1 11 10 9 19 10 5 23 11 5 13 12 11 23 12 6 27 13 6 27 14 7 16 15 14 31 15 7 ... 41 40 39 79 40 20 83 41 20 43 42 41 83 42 21 47 46 45 49 48 47 197 49 12
- sage.combinat.designs.difference_family.relative_difference_set_from_homomorphism(q, N, d, check=True)#
Construct \(R((q^N-1)/(q-1), n, q^{N-1}, q^{N-2}d)\) where \(nd = q-1\).
Given a prime power \(q\), a number \(N \ge 2\) and integers \(d\) such that \(d | q-1\) we create the relative difference set using the construction from Corollary 5.1.1 of [EB1966].
INPUT:
q
– a prime power.N
– an integer greater than 1.d
– an integer which divides \(q-1\).check
– boolean (default True). If true, check that the result is a relative difference set before returning it.
EXAMPLES:
sage: from sage.combinat.designs.difference_family import relative_difference_set_from_homomorphism sage: relative_difference_set_from_homomorphism(7, 2, 3) #random [(0), (3), (4), (2), (13), (7), (14)] sage: relative_difference_set_from_homomorphism(9, 2, 4, check=False) #random [(0), (4), (6), (13), (7), (12), (15), (8), (9)] sage: relative_difference_set_from_homomorphism(9, 2, 5) Traceback (most recent call last): ... ValueError: q-1 must be a multiple of d
- sage.combinat.designs.difference_family.relative_difference_set_from_m_sequence(q, N, check=True)#
Construct \(R((q^N-1)/(q-1), q-1, q^{N-1}, q^{N-2})\) where \(q\) is a prime power and \(N\ge 2\).
The relative difference set is constructed over the set of additive integers modulo \(q^N-1\), as described in Theorem 5.1 of [EB1966]. Given an m-sequence \((a_i)\) of period \(q^N-1\), the set is: \(R=\{i | 0 \le i \le q^{N-1}, a_i=1\}\).
INPUT:
q
– a prime power.N
– a nonnegative number.check
– boolean (default True). If true, check that the result is a relative difference set before returning it.
EXAMPLES:
sage: from sage.combinat.designs.difference_family import relative_difference_set_from_m_sequence sage: relative_difference_set_from_m_sequence(2, 4) #random [(0), (4), (5), (6), (7), (9), (11), (12)] sage: relative_difference_set_from_m_sequence(8, 2, check=False) #random [(0), (6), (30), (40), (41), (44), (56), (61)] sage: relative_difference_set_from_m_sequence(6, 2) Traceback (most recent call last): ... ValueError: q must be a prime power
- sage.combinat.designs.difference_family.singer_difference_set(q, d)#
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:
\[v = \frac{q^{d+1}-1}{q-1}, \quad k = \frac{q^d-1}{q-1}, \quad \lambda = \frac{q^{d-1}-1}{q-1}.\]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
- sage.combinat.designs.difference_family.skew_supplementary_difference_set(n, existence=False, check=True)#
Construct \(4-\{n; n_1, n_2, n_3, n_4; \lambda\}\) supplementary difference sets where \(S_1\) is skew and \(n_1+n_2+n_3+n_4= n+\lambda\).
These sets are constructed from available data, as described in [Djo1994]. The set \(S_1 \subset G\) is always skew, i.e. \(S_1 \cap (-S_1) = \emptyset\) and \(S_1 \cup (-S_1) = G\setminus\{0\}\).
The data for \(n = 103, 151\) is taken from [Djo1994] and the data for \(n = 67, 113, 127, 157, 163, 181, 241\) is taken from [Djo1992].
INPUT:
n
– integer, the parameter of the supplementary difference set.existence
– boolean (dafault False). If true, only check whether the supplementary difference sets can be constructed.check
– boolean (default True). If true, check that the sets are supplementary difference sets with \(S_1\) skew before returning them. Setting this parameter to False may speed up the computation considerably.
OUTPUT:
If
existence
is false, the function returns the 4 sets (containing integers modulo \(n\)), or raises an error if data for the givenn
is not available. Ifexistence
is true, the function returns a boolean representing whether skew supplementary difference sets can be constructed.EXAMPLES:
sage: from sage.combinat.designs.difference_family import skew_supplementary_difference_set sage: S1, S2, S3, S4 = skew_supplementary_difference_set(103)
If existence is
True
, the function returns a booleansage: skew_supplementary_difference_set(103, existence=True) True sage: skew_supplementary_difference_set(17, existence=True) False
- sage.combinat.designs.difference_family.supplementary_difference_set(q, existence=False, check=True)#
Construct \(4-\{2v; v, v+1, v, v; 2v\}\) supplementary difference sets where \(q=2v+1\).
The sets are created from relative difference sets as detailed in Theorem 3.3 of [Spe1975]. this construction requires that \(q\) is an odd prime power and that there exists \(s \ge 0\) such that \((q-(2^{s+1}+1))/2^{s+1}\) is an odd prime power.
Note that the construction from [Spe1975] states that the resulting sets are \(4-\{2v; v+1, v, v, v; 2v\}\) supplementary difference sets. However, the implementation of that construction returns \(4-\{2v; v, v+1, v, v; 2v\}\) supplementary difference sets. This is not important, since the supplementary difference sets are not ordered.
INPUT:
q
– an odd prime power.existence
– boolean (dafault False). If true, only check whether the supplementary difference sets can be constructed.check
– boolean (default True). If true, check that the sets are supplementary difference sets before returning them.
OUTPUT:
If
existence
is false, the function returns the 4 sets (containing integers), or raises an error ifq
does not satify the constraints. Ifexistence
is true, the function returns a boolean representing whether supplementary difference sets can be constructed.EXAMPLES:
sage: from sage.combinat.designs.difference_family import supplementary_difference_set sage: supplementary_difference_set(17) #random ([0, 2, 5, 6, 8, 10, 13, 14], [0, 1, 2, 6, 7, 9, 10, 14, 15], [0, 1, 2, 6, 11, 12, 13, 15], [0, 2, 6, 9, 11, 12, 13, 15])
If existence is
True
, the function returns a boolean:sage: supplementary_difference_set(7, existence=True) False sage: supplementary_difference_set(17, existence=True) True
See also
- sage.combinat.designs.difference_family.turyn_1965_3x3xK(k=4)#
Return a difference set in either \(C_3 \times C_3 \times C_4\) or \(C_3 \times C_3 \times C_2 \times C_2\) with parameters \(v=36\), \(k=15\), \(\lambda=6\).
This example appears in [Tu1965].
INPUT:
k
– either2
(to get a difference set in \(C_3 \times C_3 \times C_2 \times C_2\)) or4
(to get a difference set in \(C_3 \times C_3 \times C_3 \times C_4\)).
EXAMPLES:
sage: from sage.combinat.designs.difference_family import turyn_1965_3x3xK sage: from sage.combinat.designs.difference_family import is_difference_family sage: G,D = turyn_1965_3x3xK(4) sage: assert is_difference_family(G, D, 36, 15, 6) sage: G,D = turyn_1965_3x3xK(2) sage: assert is_difference_family(G, D, 36, 15, 6)
- sage.combinat.designs.difference_family.twin_prime_powers_difference_set(p, check=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)\):
\((x,0)\) with any \(x\)
\((x,y)\) with \(x\) and \(y\) squares
\((x,y)\) with \(x\) and \(y\) non-squares
For more information see Wikipedia article Difference_set.
INPUT:
check
– boolean (default:True
). IfTrue
then the result of the computation is checked before being returned. This should not be needed but ensures that the output is correct.
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)]]