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 |
|
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 |
|
Return a difference set associated to the set of hyperplanes in a projective space of dimension \(d\) over \(GF(q)\). |
|
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:
- 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 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(N)#
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.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.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
– 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)]]