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:

are_hadamard_difference_set_parameters() Check whether (v,k,lmbda) is of the form (4N^2, 2N^2 - N, N^2 - N).
are_mcfarland_1973_parameters() Test whether (v,k,lmbda) is a triple that can be obtained from the construction from [McF1973].
block_stabilizer() Compute the left stabilizer of the block B under the action of G.
df_q_6_1() Return a \((q,6,1)\)-difference family over the finite field \(K\).
difference_family() Return a (k, l)-difference family on an Abelian group of cardinality v.
group_law() Return a triple (identity, operation, inverse) that define the operations on the group G.
hadamard_difference_set_product() Make a product of two Hadamard difference sets.
is_difference_family() Check wether D forms a difference family in the group G.
mcfarland_1973_construction() Return a difference set.
one_cyclic_tiling() 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\)).
one_radical_difference_family() Search for a radical difference family on K using dancing links algorithm.
radical_difference_family() Return a (v,k,l)-radical difference family.
radical_difference_set() Return a difference set made of a cyclotomic coset in the finite field K and with parameters k and l.
singer_difference_set() Return a difference set associated to the set of hyperplanes in a projective space of dimension \(d\) over \(GF(q)\).
turyn_1965_3x3xK() 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\).
twin_prime_powers_difference_set() Return a difference set on \(GF(p) \times GF(p+2)\).

REFERENCES:

[BJL99-1]T. Beth, D. Jungnickel, H. Lenz “Design theory Vol. I.” Second edition. Encyclopedia of Mathematics and its Applications, 69. Cambridge University Press, (1999).
[BLJ99-2]T. Beth, D. Jungnickel, H. Lenz “Design theory Vol. II.” Second edition. Encyclopedia of Mathematics and its Applications, 78. Cambridge University Press, (1999).
[Bo39]R. C. Bose, “On the construction of balanced incomplete block designs”, Ann. Eugenics, 9 (1939), 353–399.
[Bu95](1, 2) M. Buratti “On simple radical difference families”, J. Combinatorial Designs, 3 (1995) 161–168.
[Tu1965]R. J. Turyn “Character sum and difference sets” Pacific J. Math. 15 (1965) 319–346.
[Tu1984]R. J. Turyn “A special class of Williamson matrices and difference sets” J. Combinatorial Theory (A) 36 (1984) 111–115.
[Wi72](1, 2) R. M. Wilson “Cyclotomy and difference families in elementary Abelian groups”, J. Number Theory, 4 (1972) 17–47.

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 family
  • return_parameters – (boolean, default False) if True return a pair (True, (q, s)) so that (q,s) can be used in the function mcfarland_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 of G.

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 of G.

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)]
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 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:

  • v,k,l – parameters of the difference family. If l is not provided it is assumed to be 1.
  • existence – if True, then return either True if Sage knows how to build such design, Unknown if it does not and False 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). If True 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, 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, 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), 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]
[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):
....:             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,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 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>)
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)

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)
sage.combinat.designs.difference_family.hadamard_difference_set_product_parameters

A decorator that creates a cached version of an instance method of a class.

Note

For proper behavior, the method must be a pure function (no side effects). Arguments to the method must be hashable or transformed into something hashable using key or they must define sage.structure.sage_object.SageObject._cache_key().

EXAMPLES:

sage: class Foo(object):
....:     @cached_method
....:     def f(self, t, x=2):
....:         print('computing')
....:         return t**x
sage: a = Foo()

The example shows that the actual computation takes place only once, and that the result is identical for equivalent input:

sage: res = a.f(3, 2); res
computing
9
sage: a.f(t = 3, x = 2) is res
True
sage: a.f(3) is res
True

Note, however, that the CachedMethod is replaced by a CachedMethodCaller or CachedMethodCallerNoArgs as soon as it is bound to an instance or class:

sage: P.<a,b,c,d> = QQ[]
sage: I = P*[a,b]
sage: type(I.__class__.gens)
<type 'sage.misc.cachefunc.CachedMethodCallerNoArgs'>

So, you would hardly ever see an instance of this class alive.

The parameter key can be used to pass a function which creates a custom cache key for inputs. In the following example, this parameter is used to ignore the algorithm keyword for caching:

sage: class A(object):
....:     def _f_normalize(self, x, algorithm): return x
....:     @cached_method(key=_f_normalize)
....:     def f(self, x, algorithm='default'): return x
sage: a = A()
sage: a.f(1, algorithm="default") is a.f(1) is a.f(1, algorithm="algorithm")
True

The parameter do_pickle can be used to enable pickling of the cache. Usually the cache is not stored when pickling:

sage: class A(object):
....:     @cached_method
....:     def f(self, x): return None
sage: import __main__
sage: __main__.A = A
sage: a = A()
sage: a.f(1)
sage: len(a.f.cache)
1
sage: b = loads(dumps(a))
sage: len(b.f.cache)
0

When do_pickle is set, the pickle contains the contents of the cache:

sage: class A(object):
....:     @cached_method(do_pickle=True)
....:     def f(self, x): return None
sage: __main__.A = A
sage: a = A()
sage: a.f(1)
sage: len(a.f.cache)
1
sage: b = loads(dumps(a))
sage: len(b.f.cache)
1

Cached methods can not be copied like usual methods, see trac ticket #12603. Copying them can lead to very surprising results:

sage: class A:
....:     @cached_method
....:     def f(self):
....:         return 1
sage: class B:
....:     g=A.f
....:     def f(self):
....:         return 2

sage: b=B()
sage: b.f()
2
sage: b.g()
1
sage: b.f()
1
sage.combinat.designs.difference_family.is_difference_family(G, D, v=None, k=None, l=None, verbose=False)

Check wether D forms a difference family in the group G.

INPUT:

  • G - group of cardinality v
  • D - a set of k-subsets of G
  • v, k and l - optional parameters of the difference family
  • verbose - whether to print additional information

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.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 of v, k, l in terms of q and s)

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. http://dx.doi.org/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 ... \cup \Delta (x_k B) = x_1 \Delta B \cup ... \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 field
  • k – positive integer, the size of the blocks
  • l – the \(\lambda\) parameter (default to \(1\))
  • existence – if True, then return either True if Sage knows how to build such design, Unknown if it does not and False if it knows that the design does not exist.
  • check – boolean (default: True). If True 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):
....:                  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 parameters 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 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):
....:             _ = 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.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.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 – either 2 (to get a difference set in \(C_3 \times C_3 \times C_2 \times C_2\)) or 4 (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). If True 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)]]