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

sage: G,F = designs.difference_family(13,4,1)                                       # needs sage.libs.pari sage.modules

Python

>>> from sage.all import *
>>> G,F = designs.difference_family(Integer(13),Integer(4),Integer(1))                                       # needs sage.libs.pari sage.modules

It defines the following functions:

`are_complementary_difference_sets()`	Check if `A` and `B` are complementary difference sets over the group `G`.
`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`.
`complementary_difference_sets()`	Compute complementary difference sets over a group of order \(n = 2m + 1\).
`complementary_difference_setsI()`	Construct complementary difference sets in a group of order \(n \cong 3 \mod 4\), \(n\) a prime power.
`complementary_difference_setsII()`	Construct complementary difference sets in a group of order \(n = p^t\), where \(p \cong 5 \mod 8\) and \(t \cong 1, 2, 3 \mod 4\).
`complementary_difference_setsIII()`	Construct complementary difference sets in a group of order \(n = 2m + 1\), where \(4m + 3\) is a prime power.
`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`.
`get_fixed_relative_difference_set()`	Construct an equivalent relative difference set fixed by the size of the set.
`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 whether `D` forms a difference family in the group `G`.
`is_fixed_relative_difference_set()`	Check if the relative difference set `R` is fixed by `q`.
`is_relative_difference_set()`	Check if `R` is a difference set of `G` relative to `H`, with the given parameters.
`is_supplementary_difference_set()`	Check that the sets in `Ks` are \(n-\{v; k_1, ..., k_n; \lambda \}\) supplementary difference sets over group `G` of order `v`.
`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`.
`relative_difference_set_from_homomorphism()`	Construct \(R((q^N-1)/(q-1), n, q^{N-1}, q^{N-2}d)\) where \(nd = q-1\).
`relative_difference_set_from_m_sequence()`	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\).
`singer_difference_set()`	Return a difference set associated to the set of hyperplanes in a projective space of dimension \(d\) over \(GF(q)\).
`skew_spin_goethals_seidel_difference_family()`	Construct skew spin type Goethals-Seidel difference family with parameters \((n; k_1, k_2, k_3, k_4; \lambda)\).
`skew_supplementary_difference_set()`	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\).
`skew_supplementary_difference_set_over_polynomial_ring()`	Construct skew supplementary difference sets over a polynomial ring of order `n`.
`skew_supplementary_difference_set_with_paley_todd()`	Construct \(4-\{n; n_1, n_2, n_3, n_4; \lambda\}\) skew supplementary difference sets where \(S_1\) is the Paley-Todd difference set.
`spin_goethals_seidel_difference_family()`	Construct a spin type Goethals-Seidel difference family with parameters \((n; k_1, k_2, k_3, k_4; \lambda)\).
`supplementary_difference_set()`	Construct \(4-\{2v; v, v+1, v, v; 2v\}\) supplementary difference sets where \(q=2v+1\).
`supplementary_difference_set_from_rel_diff_set()`	Construct \(4-\{2v; v, v+1, v, v; 2v\}\) supplementary difference sets where \(q=2v+1\).
`supplementary_difference_set_hadamard()`	Construct \(4-\{n; n_1, n_2, n_3, n_4; \lambda\}\) supplementary difference sets, where \(n_1 + n_2 + n_3 + n_4 = n+\lambda\).
`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_complementary_difference_sets(G, A, B, verbose=False)[source]¶

Check if A and B are complementary difference sets over the group G.

According to [Sze1971], two sets \(A\), \(B\) of size \(m\) are complementary difference sets over a group \(G\) of size \(2m+1\) if:

they are \(2-\{2m+1; m, m; m-1\}\) supplementary difference sets
\(A\) is skew, i.e. \(a \in A\) implies \(-a \not \in A\)

INPUT:

G – a group of odd order
A – set of elements of G
B – set of elements of G
verbose – boolean (default: False); if True the function will be verbose when the sets do not satisfy the contraints

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import are_complementary_difference_sets
sage: are_complementary_difference_sets(Zmod(7), [1, 2, 4], [1, 2, 4])
True

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import are_complementary_difference_sets
>>> are_complementary_difference_sets(Zmod(Integer(7)), [Integer(1), Integer(2), Integer(4)], [Integer(1), Integer(2), Integer(4)])
True

If verbose=True, the function will be verbose:

Sage

sage: are_complementary_difference_sets(Zmod(7), [1, 2, 5], [1, 2, 4], verbose=True)
The sets are not supplementary difference sets with lambda = 2
False

Python

>>> from sage.all import *
>>> are_complementary_difference_sets(Zmod(Integer(7)), [Integer(1), Integer(2), Integer(5)], [Integer(1), Integer(2), Integer(4)], verbose=True)
The sets are not supplementary difference sets with lambda = 2
False

See also

is_supplementary_difference_set()

sage.combinat.designs.difference_family.are_hadamard_difference_set_parameters(v, k, lmbda)[source]¶

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

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

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import are_hadamard_difference_set_parameters
>>> are_hadamard_difference_set_parameters(Integer(36), Integer(15), Integer(6))
True
>>> are_hadamard_difference_set_parameters(Integer(60), Integer(13), Integer(5))
False

sage.combinat.designs.difference_family.are_mcfarland_1973_parameters(v, k, lmbda, return_parameters=False)[source]¶

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

sage: # needs sage.rings.finite_rings
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):                                                   # needs sage.rings.finite_rings
....:     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

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> from sage.combinat.designs.difference_family import are_mcfarland_1973_parameters
>>> are_mcfarland_1973_parameters(Integer(64), Integer(28), Integer(12))
True
>>> are_mcfarland_1973_parameters(Integer(64), Integer(28), Integer(12), return_parameters=True)
(True, (2, 2))
>>> are_mcfarland_1973_parameters(Integer(60), Integer(13), Integer(5))
False
>>> are_mcfarland_1973_parameters(Integer(98125), Integer(19500), Integer(3875))
True
>>> are_mcfarland_1973_parameters(Integer(98125), Integer(19500), Integer(3875), True)
(True, (5, 3))

>>> from sage.combinat.designs.difference_family import are_mcfarland_1973_parameters
>>> for v in range(Integer(1), Integer(100)):                                                   # needs sage.rings.finite_rings
...     for k in range(Integer(1),Integer(30)):
...         for l in range(Integer(1),Integer(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)[source]¶

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

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]

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import block_stabilizer

>>> Z8 = Zmod(Integer(8))
>>> block_stabilizer(Z8, [Z8(Integer(0)),Z8(Integer(2)),Z8(Integer(4)),Z8(Integer(6))])
[0, 2, 4, 6]
>>> block_stabilizer(Z8, [Z8(Integer(0)),Z8(Integer(2))])
[0]

>>> C = cartesian_product([Zmod(Integer(4)),Zmod(Integer(3))])
>>> block_stabilizer(C, [C((Integer(0),Integer(0))),C((Integer(2),Integer(0))),C((Integer(0),Integer(1))),C((Integer(2),Integer(1)))])
[(0, 0), (2, 0)]

>>> b = list(map(Zmod(Integer(45)),[Integer(1), Integer(3), Integer(7), Integer(10), Integer(22), Integer(25), Integer(30), Integer(35), Integer(37), Integer(38), Integer(44)]))
>>> block_stabilizer(Zmod(Integer(45)),b)
[0]

sage.combinat.designs.difference_family.complementary_difference_sets(n, existence=False, check=True)[source]¶

Compute complementary difference sets over a group of order \(n = 2m + 1\).

According to [Sze1971], two sets \(A\), \(B\) of size \(m\) are complementary difference sets over a group \(G\) of size \(n = 2m + 1\) if:

they are \(2-\{2m+1; m, m; m-1\}\) supplementary difference sets
\(A\) is skew, i.e. \(a \in A\) implies \(-a \not \in A\)

This method tries to call complementary_difference_setsI(), complementary_difference_setsII() or complementary_difference_setsIII() if the parameter \(n\) satisfies the requirements of one of these functions.

INPUT:

n – integer; the order of the group over which the sets are constructed
existence – boolean (default: False); if True, only check whether the supplementary difference sets can be constructed
check – boolean (default: True); if True, check that the sets are complementary difference sets before returning them; setting this to False might speed up the computation for large values of n

OUTPUT:

If existence=False, the function returns group G and two complementary difference sets, or raises an error if data for the given n is not available. If existence=True, the function returns a boolean representing whether complementary difference sets can be constructed for the given n.

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import complementary_difference_sets
sage: complementary_difference_sets(15)                                         # needs sage.libs.pari
(Ring of integers modulo 15, [1, 2, 4, 6, 7, 10, 12], [0, 1, 2, 6, 9, 13, 14])

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import complementary_difference_sets
>>> complementary_difference_sets(Integer(15))                                         # needs sage.libs.pari
(Ring of integers modulo 15, [1, 2, 4, 6, 7, 10, 12], [0, 1, 2, 6, 9, 13, 14])

If existence=True, the function returns a boolean:

Sage

sage: complementary_difference_sets(15, existence=True)                         # needs sage.libs.pari
True
sage: complementary_difference_sets(16, existence=True)
False

Python

>>> from sage.all import *
>>> complementary_difference_sets(Integer(15), existence=True)                         # needs sage.libs.pari
True
>>> complementary_difference_sets(Integer(16), existence=True)
False

See also

are_complementary_difference_sets()

sage.combinat.designs.difference_family.complementary_difference_setsI(n, check=True)[source]¶

Construct complementary difference sets in a group of order \(n \cong 3 \mod 4\), \(n\) a prime power.

Let \(G\) be a Galois Field of order \(n\), where \(n\) satisfies the requirements above. Let \(A\) be the set of nonzero quadratic elements in \(G\), and \(B = A\). Then \(A\) and \(B\) are complementary difference sets over a group of order \(n\). This construction is described in [Sze1971].

INPUT:

n – integer; the order of the group \(G\)
check – boolean (default: True); if True, check that the sets are complementary difference sets before returning them

OUTPUT:

The function returns the Galois field of order n and the two sets, or raises an error if n does not satisfy the requirements of this construction.

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import complementary_difference_setsI
sage: complementary_difference_setsI(19)
(Finite Field of size 19,
 [1, 4, 5, 6, 7, 9, 11, 16, 17],
 [1, 4, 5, 6, 7, 9, 11, 16, 17])

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import complementary_difference_setsI
>>> complementary_difference_setsI(Integer(19))
(Finite Field of size 19,
 [1, 4, 5, 6, 7, 9, 11, 16, 17],
 [1, 4, 5, 6, 7, 9, 11, 16, 17])

sage.combinat.designs.difference_family.complementary_difference_setsII(n, check=True)[source]¶

Construct complementary difference sets in a group of order \(n = p^t\), where \(p \cong 5 \mod 8\) and \(t \cong 1, 2, 3 \mod 4\).

Consider a finite field \(G\) of order \(n\) and let \(\rho\) be the generator of the corresponding multiplicative group. Then, there are two different constructions, depending on whether \(t\) is even or odd.

If \(t \cong 2 \mod 4\), let \(C_0\) be the set of nonzero octic residues in \(G\), and let \(C_i = \rho^i C_0\) for \(1 \le i \le 7\). Then, \(A = C_0 \cup C_1 \cup C_2 \cup C_3\) and \(B = C_0 \cup C_1 \cup C_6 \cup C_7\).

If \(t\) is odd, let \(C_0\) be the set of nonzero fourth powers in \(G\), and let \(C_i = \rho^i C_0\) for \(1 \le i \le 3\). Then, \(A = C_0 \cup C_1\) and \(B = C_0 \cup C_3\).

For more details on this construction, see [Sze1971].

INPUT:

n – integer; the order of the group \(G\)
check – boolean (default: True); if True, check that the sets are complementary difference sets before returning them; setting this to False might speed up the computation for large values of n

OUTPUT:

The function returns the Galois field of order n and the two sets, or raises an error if n does not satisfy the requirements of this construction.

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import complementary_difference_setsII
sage: complementary_difference_setsII(5)                                        # needs sage.libs.pari
(Finite Field of size 5, [1, 2], [1, 3])

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import complementary_difference_setsII
>>> complementary_difference_setsII(Integer(5))                                        # needs sage.libs.pari
(Finite Field of size 5, [1, 2], [1, 3])

sage.combinat.designs.difference_family.complementary_difference_setsIII(n, check=True)[source]¶

Construct complementary difference sets in a group of order \(n = 2m + 1\), where \(4m + 3\) is a prime power.

Consider a finite field \(G\) of order \(n\) and let \(\rho\) be a primite element of this group. Now let \(Q\) be the set of nonzero quadratic residues in \(G\), and let \(A = \{ a | \rho^{2a} - 1 \in Q\}\), \(B' = \{ b | -(\rho^{2b} + 1) \in Q\}\). Then \(A\) and \(B = Q \setminus B'\) are complementary difference sets over the ring of integers modulo \(n\). For more details, see [Sz1969].

INPUT:

n – integer; the order of the group over which the sets are constructed
check – boolean (default: True); if True, check that the sets are complementary difference sets before returning them; setting this to False might speed up the computation for large values of n

OUTPUT:

The function returns the Galois field of order n and the two sets, or raises an error if n does not satisfy the requirements of this construction.

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import complementary_difference_setsIII
sage: complementary_difference_setsIII(11)                                      # needs sage.libs.pari
(Ring of integers modulo 11, [1, 2, 5, 7, 8], [0, 1, 3, 8, 10])

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import complementary_difference_setsIII
>>> complementary_difference_setsIII(Integer(11))                                      # needs sage.libs.pari
(Ring of integers modulo 11, [1, 2, 5, 7, 8], [0, 1, 3, 8, 10])

sage.combinat.designs.difference_family.df_q_6_1(K, existence=False, check=True)[source]¶

Return a \((q,6,1)\)-difference family over the finite field \(K\).

The construction uses Theorem 11 of [Wi72].

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
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)

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> from sage.combinat.designs.difference_family import is_difference_family, df_q_6_1
>>> prime_powers = [v for v in range(Integer(31),Integer(500),Integer(30)) if is_prime_power(v)]
>>> parameters = [v for v in prime_powers
...               if df_q_6_1(GF(v,'a'), existence=True) is True]
>>> parameters
[31, 151, 181, 211, 241, 271, 331, 361, 421]
>>> for v in parameters:
...     K = GF(v, 'a')
...     df = df_q_6_1(K, check=True)
...     assert is_difference_family(K, df, v, Integer(6), Integer(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)[source]¶

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.

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=True a troolean or if explain_construction=True a string.

EXAMPLES:

Sage

sage: G,D = designs.difference_family(73,4)                                     # needs sage.libs.pari
sage: G                                                                         # needs sage.libs.pari
Finite Field of size 73
sage: D                                                                         # needs sage.libs.pari
[[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: # needs sage.libs.pari
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: # needs sage.libs.pari
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

Python

>>> from sage.all import *
>>> G,D = designs.difference_family(Integer(73),Integer(4))                                     # needs sage.libs.pari
>>> G                                                                         # needs sage.libs.pari
Finite Field of size 73
>>> D                                                                         # needs sage.libs.pari
[[0, 1, 5, 18],
 [0, 3, 15, 54],
 [0, 9, 45, 16],
 [0, 27, 62, 48],
 [0, 8, 40, 71],
 [0, 24, 47, 67]]

>>> print(designs.difference_family(Integer(73), Integer(4), explain_construction=True))
The database contains a (73,4)-evenly distributed set

>>> # needs sage.libs.pari
>>> G,D = designs.difference_family(Integer(15),Integer(7),Integer(3))
>>> G
Ring of integers modulo 15
>>> D
[[0, 1, 2, 4, 5, 8, 10]]
>>> print(designs.difference_family(Integer(15),Integer(7),Integer(3),explain_construction=True))
Singer difference set

>>> # needs sage.libs.pari
>>> print(designs.difference_family(Integer(91),Integer(10),Integer(1),explain_construction=True))
Singer difference set
>>> print(designs.difference_family(Integer(64),Integer(28),Integer(12), explain_construction=True))
McFarland 1973 construction
>>> print(designs.difference_family(Integer(576), Integer(276), Integer(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

sage: def prime_power_mod(r, m):
....:     k = m+r
....:     while True:
....:         if is_prime_power(k):
....:             yield k
....:         k += m

sage: # needs sage.libs.pari
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: # needs sage.libs.pari
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]
[]

Python

>>> from sage.all import *
>>> def prime_power_mod(r, m):
...     k = m+r
...     while True:
...         if is_prime_power(k):
...             yield k
...         k += m

>>> # needs sage.libs.pari
>>> from itertools import islice
>>> l6 = {True: [], False: [], Unknown: []}
>>> for q in islice(prime_power_mod(Integer(1),Integer(30)), int(Integer(60))):
...     l6[designs.difference_family(q,Integer(6),existence=True)].append(q)
>>> l6[True]
[31, 121, 151, 181, 211, ...,  3061, 3121, 3181]
>>> l6[Unknown]
[61]
>>> l6[False]
[]

>>> # needs sage.libs.pari
>>> l7 = {True: [], False: [], Unknown: []}
>>> for q in islice(prime_power_mod(Integer(1),Integer(42)), int(Integer(60))):
...     l7[designs.difference_family(q,Integer(7),existence=True)].append(q)
>>> l7[True]
[169, 337, 379, 421, 463, 547, 631, 673, 757, 841, 883, 967, ...,  4621, 4957, 5167]
>>> l7[Unknown]
[43, 127, 211, 2017, 2143, 2269, 2311, 2437, 2521, 2647, ..., 4999, 5041, 5209]
>>> l7[False]
[]

List available constructions:

Sage

sage: for v in range(2,100):                                                    # needs sage.libs.pari
....:     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)))
(2,1)
(3,2)
(2,1), (4,3)
(5,4)
(2,1), (3,1), (3,2), (4,2), (6,5)
(7,6)
(2,1), (4,3), (8,7)
(9,8)
(2,1), (4,6), (5,2), (5,4), (6,3)
(2,1), (3,1), (3,2), (4,1), (4,3), (5,5), (6,5)
(3,1), (4,6), (5,6), (7,3), (7,6)
(3,2), (5,4), (6,2)
(2,1), (4,3), (5,5), (8,7)
(2,1), (3,1), (3,2), (4,2), (6,5), (9,4), (9,8)
(3,1), (4,3), (5,1), (6,3), (6,5)
(4,2), (6,5), (7,4), (8,8)
(2,1)
(2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (7,7), (8,7)
(2,1), (3,1)
(3,2), (6,5)
(2,1), (4,3), (7,3), (7,6), (8,4), (8,6)
(2,1), (3,1), (3,2), (4,2), (5,2), (5,4), (6,1), (6,5)
(3,1), (5,5), (6,5)
(4,2)
(5,2)
(2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (9,2), (9,8)
(3,1), (6,5)
(3,2), (4,1)
(2,1), (4,3), (5,1), (5,4), (6,3), (8,7)
(2,1), (3,1), (3,2), (4,2), (6,5), (7,2), (7,3), (7,6), (8,4)
(3,1), (5,1)
(4,2), (6,2)
(2,1)
(2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (8,7), (9,3)
(3,1), (5,2), (6,3)
(4,1)
(2,1), (4,3)
(3,1), (9,4)
(3,1), (7,3), (8,1)
(2,1)
(2,1), (3,1), (3,2), (4,1), (4,3), (5,1), (5,4), (6,2), (6,3), (6,5)
(3,1)
(3,2), (4,1), (7,2), (7,6), (9,8)
(5,1)
(2,1), (3,1), (3,2), (6,5)
(3,1)
(2,1), (5,2), (5,4), (7,3), (7,6), (8,4)
(2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (8,7), (9,1), (9,8)
(3,1), (5,2)
(4,1)
(2,1), (3,1), (3,2), (6,5)
(2,1), (3,1), (4,3), (5,1), (5,4), (8,7)
(2,1)
(4,1), (7,2), (7,3), (8,2)
(2,1), (4,3), (8,7)
(6,1), (7,1)
(2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (8,7), (9,3)

Python

>>> from sage.all import *
>>> for v in range(Integer(2),Integer(100)):                                                    # needs sage.libs.pari
...     constructions = []
...     for k in range(Integer(2),Integer(10)):
...         for l in range(Integer(1),Integer(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)))
(2,1)
(3,2)
(2,1), (4,3)
(5,4)
(2,1), (3,1), (3,2), (4,2), (6,5)
(7,6)
(2,1), (4,3), (8,7)
(9,8)
(2,1), (4,6), (5,2), (5,4), (6,3)
(2,1), (3,1), (3,2), (4,1), (4,3), (5,5), (6,5)
(3,1), (4,6), (5,6), (7,3), (7,6)
(3,2), (5,4), (6,2)
(2,1), (4,3), (5,5), (8,7)
(2,1), (3,1), (3,2), (4,2), (6,5), (9,4), (9,8)
(3,1), (4,3), (5,1), (6,3), (6,5)
(4,2), (6,5), (7,4), (8,8)
(2,1)
(2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (7,7), (8,7)
(2,1), (3,1)
(3,2), (6,5)
(2,1), (4,3), (7,3), (7,6), (8,4), (8,6)
(2,1), (3,1), (3,2), (4,2), (5,2), (5,4), (6,1), (6,5)
(3,1), (5,5), (6,5)
(4,2)
(5,2)
(2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (9,2), (9,8)
(3,1), (6,5)
(3,2), (4,1)
(2,1), (4,3), (5,1), (5,4), (6,3), (8,7)
(2,1), (3,1), (3,2), (4,2), (6,5), (7,2), (7,3), (7,6), (8,4)
(3,1), (5,1)
(4,2), (6,2)
(2,1)
(2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (8,7), (9,3)
(3,1), (5,2), (6,3)
(4,1)
(2,1), (4,3)
(3,1), (9,4)
(3,1), (7,3), (8,1)
(2,1)
(2,1), (3,1), (3,2), (4,1), (4,3), (5,1), (5,4), (6,2), (6,3), (6,5)
(3,1)
(3,2), (4,1), (7,2), (7,6), (9,8)
(5,1)
(2,1), (3,1), (3,2), (6,5)
(3,1)
(2,1), (5,2), (5,4), (7,3), (7,6), (8,4)
(2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (8,7), (9,1), (9,8)
(3,1), (5,2)
(4,1)
(2,1), (3,1), (3,2), (6,5)
(2,1), (3,1), (4,3), (5,1), (5,4), (8,7)
(2,1)
(4,1), (7,2), (7,3), (8,2)
(2,1), (4,3), (8,7)
(6,1), (7,1)
(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.get_fixed_relative_difference_set(G, rel_diff_set, as_elements=False)[source]¶

Construct an equivalent relative difference set fixed by the size of the set.

Given a relative difference set \(R(q+1, q-1, q, 1)\), it is possible to find a translation of this set fixed by \(q\) (see Section 3 of [Spe1975]). We say that a set is fixed by \(t\) if \(\{td | d\in R\}= R\).

In addition, the set returned by this function will contain the element \(0\). This is needed in the construction of supplementary difference sets (see supplementary_difference_set_from_rel_diff_set()).

INPUT:

G – a group, of which rel_diff_set is a subset
rel_diff_set – the relative difference set
as_elements – boolean (default: False); if True, the list returned will contain elements of the abelian group (this may slow down the computation considerably)

OUTPUT:

By default, this function returns the set as a list of integers. However, if as_elements=True it will return the set as a list containing elements of the abelian group. If no such set can be found, the function will raise an error.

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import relative_difference_set_from_m_sequence, get_fixed_relative_difference_set
sage: G, s1 = relative_difference_set_from_m_sequence(5, 2, return_group=True)  # needs sage.libs.pari sage.modules
sage: get_fixed_relative_difference_set(G, s1)  # random                        # needs sage.libs.pari sage.modules
[2, 10, 19, 23, 0]

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import relative_difference_set_from_m_sequence, get_fixed_relative_difference_set
>>> G, s1 = relative_difference_set_from_m_sequence(Integer(5), Integer(2), return_group=True)  # needs sage.libs.pari sage.modules
>>> get_fixed_relative_difference_set(G, s1)  # random                        # needs sage.libs.pari sage.modules
[2, 10, 19, 23, 0]

If as_elements=True, the result will contain elements of the group:

Sage

sage: get_fixed_relative_difference_set(G, s1, as_elements=True)  # random      # needs sage.libs.pari sage.modules
[(2), (10), (19), (23), (0)]

Python

>>> from sage.all import *
>>> get_fixed_relative_difference_set(G, s1, as_elements=True)  # random      # needs sage.libs.pari sage.modules
[(2), (10), (19), (23), (0)]

sage.combinat.designs.difference_family.group_law(G)[source]¶

Return a triple (identity, operation, inverse) that define the operations on the group G.

EXAMPLES:

Sage

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))                                              # needs sage.groups
((), <built-in function mul>, <built-in function inv>)
sage: group_law(VectorSpace(QQ, 3))                                             # needs sage.modules
((0, 0, 0), <built-in function add>, <built-in function neg>)

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import group_law
>>> group_law(Zmod(Integer(3)))
(0, <built-in function add>, <built-in function neg>)
>>> group_law(SymmetricGroup(Integer(5)))                                              # needs sage.groups
((), <built-in function mul>, <built-in function inv>)
>>> group_law(VectorSpace(QQ, Integer(3)))                                             # needs sage.modules
((0, 0, 0), <built-in function add>, <built-in function neg>)

sage.combinat.designs.difference_family.hadamard_difference_set_product(G1, D1, G2, D2)[source]¶

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

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)                                 # needs sage.rings.finite_rings
sage: G2,D2 = designs.difference_family(36,15,6)                                # needs sage.rings.finite_rings

sage: G11,D11 = hadamard_difference_set_product(G1,D1,G1,D1)                    # needs sage.rings.finite_rings
sage: assert is_difference_family(G11, D11, 256, 120, 56)                       # needs sage.rings.finite_rings
sage: assert designs.difference_family(256, 120, 56, existence=True) is True    # needs sage.rings.finite_rings

sage: G12,D12 = hadamard_difference_set_product(G1,D1,G2,D2)                    # needs sage.rings.finite_rings
sage: assert is_difference_family(G12, D12, 576, 276, 132)                      # needs sage.rings.finite_rings
sage: assert designs.difference_family(576, 276, 132, existence=True) is True   # needs sage.rings.finite_rings

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import hadamard_difference_set_product
>>> from sage.combinat.designs.difference_family import is_difference_family

>>> G1,D1 = designs.difference_family(Integer(16),Integer(6),Integer(2))                                 # needs sage.rings.finite_rings
>>> G2,D2 = designs.difference_family(Integer(36),Integer(15),Integer(6))                                # needs sage.rings.finite_rings

>>> G11,D11 = hadamard_difference_set_product(G1,D1,G1,D1)                    # needs sage.rings.finite_rings
>>> assert is_difference_family(G11, D11, Integer(256), Integer(120), Integer(56))                       # needs sage.rings.finite_rings
>>> assert designs.difference_family(Integer(256), Integer(120), Integer(56), existence=True) is True    # needs sage.rings.finite_rings

>>> G12,D12 = hadamard_difference_set_product(G1,D1,G2,D2)                    # needs sage.rings.finite_rings
>>> assert is_difference_family(G12, D12, Integer(576), Integer(276), Integer(132))                      # needs sage.rings.finite_rings
>>> assert designs.difference_family(Integer(576), Integer(276), Integer(132), existence=True) is True   # needs sage.rings.finite_rings

sage.combinat.designs.difference_family.hadamard_difference_set_product_parameters()[source]¶

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 is None.

INPUT:

N – positive integer

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import hadamard_difference_set_product_parameters
sage: hadamard_difference_set_product_parameters(8)                             # needs sage.rings.finite_rings
(2, 2)

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import hadamard_difference_set_product_parameters
>>> hadamard_difference_set_product_parameters(Integer(8))                             # needs sage.rings.finite_rings
(2, 2)

sage.combinat.designs.difference_family.is_difference_family(G, D, v=None, k=None, l=None, verbose=False)[source]¶

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

INPUT:

G – group of cardinality v
D – set of k-subsets of G
v, k, l – (optional) parameters of the difference family
verbose – boolean (default: False); whether to print additional information

See also

difference_family()

EXAMPLES:

Sage

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: # needs sage.modules
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

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import is_difference_family
>>> G = Zmod(Integer(21))
>>> D = [[Integer(0),Integer(1),Integer(4),Integer(14),Integer(16)]]
>>> is_difference_family(G, D, Integer(21), Integer(5))
True

>>> G = Zmod(Integer(41))
>>> D = [[Integer(0),Integer(1),Integer(4),Integer(11),Integer(29)],[Integer(0),Integer(2),Integer(8),Integer(17),Integer(21)]]
>>> 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
>>> D = [[Integer(0),Integer(1),Integer(4),Integer(11),Integer(29)],[Integer(0),Integer(2),Integer(8),Integer(17),Integer(22)]]
>>> is_difference_family(G, D)
True

>>> G = Zmod(Integer(61))
>>> D = [[Integer(0),Integer(1),Integer(3),Integer(13),Integer(34)],[Integer(0),Integer(4),Integer(9),Integer(23),Integer(45)],[Integer(0),Integer(6),Integer(17),Integer(24),Integer(32)]]
>>> is_difference_family(G, D)
True

>>> # needs sage.modules
>>> G = AdditiveAbelianGroup([Integer(3)]*Integer(4))
>>> a,b,c,d = G.gens()
>>> 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]]
>>> is_difference_family(G, D)
True

The following example has a third block with a non-trivial stabilizer:

Sage

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

Python

>>> from sage.all import *
>>> G = Zmod(Integer(15))
>>> D = [[Integer(0),Integer(1),Integer(4)],[Integer(0),Integer(2),Integer(9)],[Integer(0),Integer(5),Integer(10)]]
>>> 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

sage: # needs sage.groups
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)

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> G = DihedralGroup(Integer(8))
>>> x,y = G.gens()
>>> i = G.one()
>>> D1 = [[i,x,x**Integer(4)], [i,x**Integer(2), y*x], [i,x**Integer(5),y], [i,x**Integer(6),y*x**Integer(2)], [i,x**Integer(7),y*x**Integer(5)]]
>>> is_difference_family(G, D1, Integer(16), Integer(3), Integer(2))
True
>>> from sage.combinat.designs.bibd import BIBD_from_difference_family
>>> bibd = BIBD_from_difference_family(G, D1, lambd=Integer(2))

sage.combinat.designs.difference_family.is_fixed_relative_difference_set(R, q)[source]¶

Check if the relative difference set R is fixed by q.

A relative difference set \(R\) is fixed by \(q\) if \(\{qd | d \in R\}= R\) (see Section 3 of [Spe1975]).

INPUT:

R – list containing elements of an abelian group; the relative difference set
q – integer

EXAMPLES:

Sage

sage: # needs sage.modules
sage: from sage.combinat.designs.difference_family import relative_difference_set_from_m_sequence, get_fixed_relative_difference_set, is_fixed_relative_difference_set
sage: G, s1 = relative_difference_set_from_m_sequence(7, 2, return_group=True)  # needs sage.libs.pari
sage: s2 = get_fixed_relative_difference_set(G, s1, as_elements=True)           # needs sage.libs.pari
sage: is_fixed_relative_difference_set(s2, len(s2))                             # needs sage.libs.pari
True
sage: G = AdditiveAbelianGroup([15])
sage: s3 = [G[1], G[2], G[3], G[4]]
sage: is_fixed_relative_difference_set(s3, len(s3))
False

Python

>>> from sage.all import *
>>> # needs sage.modules
>>> from sage.combinat.designs.difference_family import relative_difference_set_from_m_sequence, get_fixed_relative_difference_set, is_fixed_relative_difference_set
>>> G, s1 = relative_difference_set_from_m_sequence(Integer(7), Integer(2), return_group=True)  # needs sage.libs.pari
>>> s2 = get_fixed_relative_difference_set(G, s1, as_elements=True)           # needs sage.libs.pari
>>> is_fixed_relative_difference_set(s2, len(s2))                             # needs sage.libs.pari
True
>>> G = AdditiveAbelianGroup([Integer(15)])
>>> s3 = [G[Integer(1)], G[Integer(2)], G[Integer(3)], G[Integer(4)]]
>>> is_fixed_relative_difference_set(s3, len(s3))
False

If the relative difference set does not contain elements of the group, the method returns false:

Sage

sage: G, s1 = relative_difference_set_from_m_sequence(7, 2, return_group=True)  # needs sage.libs.pari sage.modules
sage: s2 = get_fixed_relative_difference_set(G, s1, as_elements=False)          # needs sage.libs.pari sage.modules
sage: is_fixed_relative_difference_set(s2, len(s2))                             # needs sage.libs.pari sage.modules
False

Python

>>> from sage.all import *
>>> G, s1 = relative_difference_set_from_m_sequence(Integer(7), Integer(2), return_group=True)  # needs sage.libs.pari sage.modules
>>> s2 = get_fixed_relative_difference_set(G, s1, as_elements=False)          # needs sage.libs.pari sage.modules
>>> is_fixed_relative_difference_set(s2, len(s2))                             # needs sage.libs.pari sage.modules
False

sage.combinat.designs.difference_family.is_relative_difference_set(R, G, H, params, verbose=False)[source]¶

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 – list; a submodule of G of order \(n\)
params – 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

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: params = ((q^N-1) // (q-1), q - 1, q^(N-1), q^(N-2))
sage: G, R = relative_difference_set_from_m_sequence(q, N, return_group=True)   # needs sage.libs.pari sage.modules
sage: H = _get_submodule_of_order(G, q - 1)                                     # needs sage.libs.pari sage.modules
sage: is_relative_difference_set(R, G, H, params)                               # needs sage.libs.pari sage.modules
True

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import _get_submodule_of_order, relative_difference_set_from_m_sequence, is_relative_difference_set
>>> q, N = Integer(5), Integer(2)
>>> params = ((q**N-Integer(1)) // (q-Integer(1)), q - Integer(1), q**(N-Integer(1)), q**(N-Integer(2)))
>>> G, R = relative_difference_set_from_m_sequence(q, N, return_group=True)   # needs sage.libs.pari sage.modules
>>> H = _get_submodule_of_order(G, q - Integer(1))                                     # needs sage.libs.pari sage.modules
>>> is_relative_difference_set(R, G, H, params)                               # needs sage.libs.pari sage.modules
True

If we pass the verbose argument, the function will explain why it failed:

Sage

sage: R2 = [G[1], G[2], G[3], G[5], G[6]]                                       # needs sage.libs.pari sage.modules
sage: is_relative_difference_set(R2, G, H, params, verbose=True)                # needs sage.libs.pari sage.modules
There is a value in the difference set which is not repeated d times
False

Python

>>> from sage.all import *
>>> R2 = [G[Integer(1)], G[Integer(2)], G[Integer(3)], G[Integer(5)], G[Integer(6)]]                                       # needs sage.libs.pari sage.modules
>>> is_relative_difference_set(R2, G, H, params, verbose=True)                # needs sage.libs.pari sage.modules
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=None, lmbda=None, G=None, verbose=False)[source]¶

Check that the sets in Ks are \(n-\{v; k_1, ..., k_n; \lambda \}\) supplementary difference sets over group G of order v.

From the definition in [Spe1975]: let \(S_1, S_2, ..., S_n\) be \(n\) subsets of a 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.

One of the parameters v or G must always be specified. If G is not given, the function will use an AdditiveAbelianGroup of order v.

INPUT:

Ks – 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
G – a group of order \(v\)
verbose – boolean (default: False); if True, the function will be verbose when the sets do not satisfy the contraints

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import supplementary_difference_set_from_rel_diff_set, is_supplementary_difference_set
sage: G, [S1, S2, S3, S4] = supplementary_difference_set_from_rel_diff_set(17)  # needs sage.modules sage.rings.finite_rings
sage: is_supplementary_difference_set([S1, S2, S3, S4], lmbda=16, G=G)          # needs sage.modules sage.rings.finite_rings
True

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import supplementary_difference_set_from_rel_diff_set, is_supplementary_difference_set
>>> G, [S1, S2, S3, S4] = supplementary_difference_set_from_rel_diff_set(Integer(17))  # needs sage.modules sage.rings.finite_rings
>>> is_supplementary_difference_set([S1, S2, S3, S4], lmbda=Integer(16), G=G)          # needs sage.modules sage.rings.finite_rings
True

The parameter v can be given instead of G:

Sage

sage: is_supplementary_difference_set([S1, S2, S3, S4], v=16, lmbda=16)         # needs sage.modules sage.rings.finite_rings
True
sage: is_supplementary_difference_set([S1, S2, S3, S4], v=20, lmbda=16)         # needs sage.modules sage.rings.finite_rings
False

Python

>>> from sage.all import *
>>> is_supplementary_difference_set([S1, S2, S3, S4], v=Integer(16), lmbda=Integer(16))         # needs sage.modules sage.rings.finite_rings
True
>>> is_supplementary_difference_set([S1, S2, S3, S4], v=Integer(20), lmbda=Integer(16))         # needs sage.modules sage.rings.finite_rings
False

If verbose=True, the function will be verbose:

Sage

sage: is_supplementary_difference_set([S1, S2, S3, S4], lmbda=14, G=G,          # needs sage.modules sage.rings.finite_rings
....:                                 verbose=True)
Number of pairs with difference (1) is 16, but lambda is 14
False

Python

>>> from sage.all import *
>>> is_supplementary_difference_set([S1, S2, S3, S4], lmbda=Integer(14), G=G,          # needs sage.modules sage.rings.finite_rings
...                                 verbose=True)
Number of pairs with difference (1) is 16, but lambda is 14
False

sage.combinat.designs.difference_family.mcfarland_1973_construction(q, s)[source]¶

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. doi:10.1016/0097-3165(73)90031-9

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import (
....:    mcfarland_1973_construction, is_difference_family)

sage: G,D = mcfarland_1973_construction(3, 1)                                   # needs sage.modules
sage: assert is_difference_family(G, D, 45, 12, 3)                              # needs sage.modules

sage: G,D = mcfarland_1973_construction(2, 2)                                   # needs sage.modules
sage: assert is_difference_family(G, D, 64, 28, 12)                             # needs sage.modules

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import (
...    mcfarland_1973_construction, is_difference_family)

>>> G,D = mcfarland_1973_construction(Integer(3), Integer(1))                                   # needs sage.modules
>>> assert is_difference_family(G, D, Integer(45), Integer(12), Integer(3))                              # needs sage.modules

>>> G,D = mcfarland_1973_construction(Integer(2), Integer(2))                                   # needs sage.modules
>>> assert is_difference_family(G, D, Integer(64), Integer(28), Integer(12))                             # needs sage.modules

sage.combinat.designs.difference_family.one_cyclic_tiling(A, n)[source]¶

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

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

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import one_cyclic_tiling
>>> tile = [Integer(0),Integer(2),Integer(4)]
>>> m = one_cyclic_tiling(tile,Integer(6)); m
[0, 3]
>>> sorted((i+j)%Integer(6) for i in tile for j in m)
[0, 1, 2, 3, 4, 5]

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

>>> tile = [Integer(0), Integer(1), Integer(2), Integer(7)]
>>> m = one_cyclic_tiling(tile, Integer(12))
>>> print_tiling(tile, m, Integer(12))
XXX....X....
....XXX....X
...X....XXX.

>>> tile = [Integer(0), Integer(1), Integer(5)]
>>> m = one_cyclic_tiling(tile, Integer(12))
>>> print_tiling(tile, m, Integer(12))
XX...X......
...XX...X...
......XX...X
..X......XX.

>>> tile = [Integer(0), Integer(2)]
>>> m = one_cyclic_tiling(tile, Integer(8))
>>> print_tiling(tile, m, Integer(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)[source]¶

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 – 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

sage: from sage.combinat.designs.difference_family import (
....:    one_radical_difference_family,
....:    is_difference_family)

sage: one_radical_difference_family(GF(13),4)                                   # needs sage.rings.finite_rings
[[0, 1, 3, 9]]

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import (
...    one_radical_difference_family,
...    is_difference_family)

>>> one_radical_difference_family(GF(Integer(13)),Integer(4))                                   # needs sage.rings.finite_rings
[[0, 1, 3, 9]]

The parameters that appear in [Bu95]:

Sage

sage: df = one_radical_difference_family(GF(449), 8); df                        # needs sage.rings.finite_rings
[[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)                              # needs sage.rings.finite_rings
True

Python

>>> from sage.all import *
>>> df = one_radical_difference_family(GF(Integer(449)), Integer(8)); df                        # needs sage.rings.finite_rings
[[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]]
>>> is_difference_family(GF(Integer(449)), df, Integer(449), Integer(8), Integer(1))                              # needs sage.rings.finite_rings
True

sage.combinat.designs.difference_family.radical_difference_family(K, k, l=1, existence=False, check=True)[source]¶

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 – integer (default: \(1\)); the \(\lambda\) parameter
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

sage: from sage.combinat.designs.difference_family import radical_difference_family

sage: radical_difference_family(GF(73), 9)                                      # needs sage.rings.finite_rings
[[1, 2, 4, 8, 16, 32, 37, 55, 64]]

sage: radical_difference_family(GF(281), 5)                                     # needs sage.rings.finite_rings
[[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):                                                     # needs sage.rings.finite_rings
....:     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

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import radical_difference_family

>>> radical_difference_family(GF(Integer(73)), Integer(9))                                      # needs sage.rings.finite_rings
[[1, 2, 4, 8, 16, 32, 37, 55, 64]]

>>> radical_difference_family(GF(Integer(281)), Integer(5))                                     # needs sage.rings.finite_rings
[[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]]

>>> for k in range(Integer(5),Integer(10)):                                                     # needs sage.rings.finite_rings
...     print("k = {}".format(k))
...     list_q = []
...     for q in range(k*(k-Integer(1))+Integer(1), Integer(2000), k*(k-Integer(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)[source]¶

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

sage: from sage.combinat.designs.difference_family import radical_difference_set

sage: D = radical_difference_set(GF(7), 3, 1); D                                # needs sage.rings.finite_rings
[[1, 2, 4]]
sage: sorted(x-y for x in D[0] for y in D[0] if x != y)                         # needs sage.rings.finite_rings
[1, 2, 3, 4, 5, 6]

sage: D = radical_difference_set(GF(16,'a'), 6, 2)                              # needs sage.rings.finite_rings
sage: sorted(x-y for x in D[0] for y in D[0] if x != y)                         # needs sage.rings.finite_rings
[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):                                                     # needs sage.rings.finite_rings
....:     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

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import radical_difference_set

>>> D = radical_difference_set(GF(Integer(7)), Integer(3), Integer(1)); D                                # needs sage.rings.finite_rings
[[1, 2, 4]]
>>> sorted(x-y for x in D[Integer(0)] for y in D[Integer(0)] if x != y)                         # needs sage.rings.finite_rings
[1, 2, 3, 4, 5, 6]

>>> D = radical_difference_set(GF(Integer(16),'a'), Integer(6), Integer(2))                              # needs sage.rings.finite_rings
>>> sorted(x-y for x in D[Integer(0)] for y in D[Integer(0)] if x != y)                         # needs sage.rings.finite_rings
[1,
 1,
 a,
 a,
 a + 1,
 a + 1,
 a^2,
 a^2,
 ...
 a^3 + a^2 + a + 1,
 a^3 + a^2 + a + 1]

>>> for k in range(Integer(2),Integer(50)):                                                     # needs sage.rings.finite_rings
...     for l in reversed(divisors(k*(k-Integer(1)))):
...         v = k*(k-Integer(1))//l + Integer(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, return_group=False)[source]¶

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 – integer greater than 1
d – integer which divides \(q-1\)
check – boolean (default: True); if True, check that the result is a relative difference set before returning it
return_group – boolean (default: False); if True, the function will also return the group from which the set is created

OUTPUT:

If return_group=False, the function return only the relative difference set. Otherwise, it returns a tuple containing the group and the set.

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import relative_difference_set_from_homomorphism
sage: relative_difference_set_from_homomorphism(7, 2, 3)        # random        # needs sage.modules sage.rings.finite_rings
[(0), (3), (4), (2), (13), (7), (14)]
sage: relative_difference_set_from_homomorphism(9, 2, 4,        # random        # needs sage.modules sage.rings.finite_rings
....:                                           check=False, return_group=True)
(Additive abelian group isomorphic to Z/80,
 [(0), (4), (6), (13), (7), (12), (15), (8), (9)])
sage: relative_difference_set_from_homomorphism(9, 2, 5)                        # needs sage.modules sage.rings.finite_rings
Traceback (most recent call last):
...
ValueError: q-1 must be a multiple of d

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import relative_difference_set_from_homomorphism
>>> relative_difference_set_from_homomorphism(Integer(7), Integer(2), Integer(3))        # random        # needs sage.modules sage.rings.finite_rings
[(0), (3), (4), (2), (13), (7), (14)]
>>> relative_difference_set_from_homomorphism(Integer(9), Integer(2), Integer(4),        # random        # needs sage.modules sage.rings.finite_rings
...                                           check=False, return_group=True)
(Additive abelian group isomorphic to Z/80,
 [(0), (4), (6), (13), (7), (12), (15), (8), (9)])
>>> relative_difference_set_from_homomorphism(Integer(9), Integer(2), Integer(5))                        # needs sage.modules sage.rings.finite_rings
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, return_group=False)[source]¶

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
return_group – boolean (default: False); if True, the function will also return the group from which the set is created

OUTPUT:

If return_group=False, the function return only the relative difference set. Otherwise, it returns a tuple containing the group and the set.

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import relative_difference_set_from_m_sequence
sage: relative_difference_set_from_m_sequence(2, 4,               # random      # needs sage.modules sage.rings.finite_rings
....:                                         return_group=True)
(Additive abelian group isomorphic to Z/15,
 [(0), (4), (5), (6), (7), (9), (11), (12)])
sage: relative_difference_set_from_m_sequence(8, 2, check=False)  # random      # needs sage.modules sage.rings.finite_rings
[(0), (6), (30), (40), (41), (44), (56), (61)]
sage: relative_difference_set_from_m_sequence(6, 2)                             # needs sage.modules
Traceback (most recent call last):
...
ValueError: q must be a prime power

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import relative_difference_set_from_m_sequence
>>> relative_difference_set_from_m_sequence(Integer(2), Integer(4),               # random      # needs sage.modules sage.rings.finite_rings
...                                         return_group=True)
(Additive abelian group isomorphic to Z/15,
 [(0), (4), (5), (6), (7), (9), (11), (12)])
>>> relative_difference_set_from_m_sequence(Integer(8), Integer(2), check=False)  # random      # needs sage.modules sage.rings.finite_rings
[(0), (6), (30), (40), (41), (44), (56), (61)]
>>> relative_difference_set_from_m_sequence(Integer(6), Integer(2))                             # needs sage.modules
Traceback (most recent call last):
...
ValueError: q must be a prime power

sage.combinat.designs.difference_family.singer_difference_set(q, d)[source]¶

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

sage: from sage.combinat.designs.difference_family import singer_difference_set, is_difference_family
sage: G,D = singer_difference_set(3,2)                                          # needs sage.rings.finite_rings
sage: is_difference_family(G, D, verbose=True)                                  # needs sage.rings.finite_rings
It is a (13,4,1)-difference family
True

sage: G,D = singer_difference_set(4,2)                                          # needs sage.rings.finite_rings
sage: is_difference_family(G, D, verbose=True)                                  # needs sage.rings.finite_rings
It is a (21,5,1)-difference family
True

sage: G,D = singer_difference_set(3,3)                                          # needs sage.rings.finite_rings
sage: is_difference_family(G, D, verbose=True)                                  # needs sage.rings.finite_rings
It is a (40,13,4)-difference family
True

sage: G,D = singer_difference_set(9,3)                                          # needs sage.rings.finite_rings
sage: is_difference_family(G, D, verbose=True)                                  # needs sage.rings.finite_rings
It is a (820,91,10)-difference family
True

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import singer_difference_set, is_difference_family
>>> G,D = singer_difference_set(Integer(3),Integer(2))                                          # needs sage.rings.finite_rings
>>> is_difference_family(G, D, verbose=True)                                  # needs sage.rings.finite_rings
It is a (13,4,1)-difference family
True

>>> G,D = singer_difference_set(Integer(4),Integer(2))                                          # needs sage.rings.finite_rings
>>> is_difference_family(G, D, verbose=True)                                  # needs sage.rings.finite_rings
It is a (21,5,1)-difference family
True

>>> G,D = singer_difference_set(Integer(3),Integer(3))                                          # needs sage.rings.finite_rings
>>> is_difference_family(G, D, verbose=True)                                  # needs sage.rings.finite_rings
It is a (40,13,4)-difference family
True

>>> G,D = singer_difference_set(Integer(9),Integer(3))                                          # needs sage.rings.finite_rings
>>> is_difference_family(G, D, verbose=True)                                  # needs sage.rings.finite_rings
It is a (820,91,10)-difference family
True

sage.combinat.designs.difference_family.skew_spin_goethals_seidel_difference_family(n, existence=False, check=True)[source]¶

Construct skew spin type Goethals-Seidel difference family with parameters \((n; k_1, k_2, k_3, k_4; \lambda)\).

This data is used to construct the difference family using the functions _construct_gs_difference_family_from_full() and _construct_gs_difference_family_from_compact().

INPUT:

n – integer; the parameter of the GS difference family
existence – boolean (default: False); if True, only check whether the skew difference family can be constructed
check – boolean (default: True); if True, check that the sets are a skew difference family before returning them; setting this parameter to False may speed up the computation considerably

OUTPUT:

If existence=False, the function returns the group G of integers modulo n and a list containing 4 sets, or raises an error if data for the given n is not available. If existence=True, the function returns a boolean representing whether the skew difference family can be constructed.

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import skew_spin_goethals_seidel_difference_family
sage: G, [S1, S2, S3, S4] = skew_spin_goethals_seidel_difference_family(61)

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import skew_spin_goethals_seidel_difference_family
>>> G, [S1, S2, S3, S4] = skew_spin_goethals_seidel_difference_family(Integer(61))

If existence is True, the function returns a boolean:

Sage

sage: skew_spin_goethals_seidel_difference_family(61, existence=True)
True
sage: skew_spin_goethals_seidel_difference_family(5, existence=True)
False

Python

>>> from sage.all import *
>>> skew_spin_goethals_seidel_difference_family(Integer(61), existence=True)
True
>>> skew_spin_goethals_seidel_difference_family(Integer(5), existence=True)
False

sage.combinat.designs.difference_family.skew_supplementary_difference_set(n, existence=False, check=True, return_group=False)[source]¶

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 [Djo1994a]. 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 is taken from:

\(n = 103, 151\): [Djo1994a]
\(n = 67, 113, 127, 157, 163, 181, 241\): [Djo1992a]
\(n = 37, 43\): [Djo1992b]
\(n = 39, 49, 65, 93, 121, 129, 133, 217, 219, 267\): [Djo1992c]
\(n = 97\): [Djo2008a]
\(n = 109, 145, 247\): [Djo2008b]
\(n = 73\): [Djo2023b]
\(n = 213, 631\): [DGK2014]
\(n = 331\): [DK2016]

Additional skew Supplementary difference sets are built using the function skew_supplementary_difference_set_over_polynomial_ring(), and skew_supplementary_difference_set_with_paley_todd().

INPUT:

n – integer; the parameter of the supplementary difference set
existence – boolean (default: 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
return_group – boolean (default: False); if True, the function will also return the group from which the sets are created

OUTPUT:

If existence=False, the function returns a list containing 4 sets, or raises an error if data for the given n is not available. If return_group=True the function will additionally return the group from which the sets are created. If existence=True, the function returns a boolean representing whether skew supplementary difference sets can be constructed.

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import skew_supplementary_difference_set
sage: [S1, S2, S3, S4] = skew_supplementary_difference_set(39)

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import skew_supplementary_difference_set
>>> [S1, S2, S3, S4] = skew_supplementary_difference_set(Integer(39))

If return_group=True, the function will also return the group:

Sage

sage: G, [S1, S2, S3, S4] = skew_supplementary_difference_set(103, return_group=True)

Python

>>> from sage.all import *
>>> G, [S1, S2, S3, S4] = skew_supplementary_difference_set(Integer(103), return_group=True)

If existence=True, the function returns a boolean:

Sage

sage: skew_supplementary_difference_set(103, existence=True)
True
sage: skew_supplementary_difference_set(17, existence=True)
False

Python

>>> from sage.all import *
>>> skew_supplementary_difference_set(Integer(103), existence=True)
True
>>> skew_supplementary_difference_set(Integer(17), existence=True)
False

Note

The data for \(n=247\) in [Djo2008b] contains a typo: the set \(\alpha_2\) should contain \(223\) instead of \(233\). This can be verified by checking the resulting sets, which are given explicitly in the paper.

sage.combinat.designs.difference_family.skew_supplementary_difference_set_over_polynomial_ring(n, existence=False, check=True)[source]¶

Construct skew supplementary difference sets over a polynomial ring of order n.

The skew supplementary difference sets for \(n=81, 169\) are taken from [Djo1994a].

INPUT:

n – integer; the parameter of the supplementary difference sets
existence – boolean (default: 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=False, the function returns a Polynomial Ring of order n and a list containing 4 sets, or raises an error if data for the given n is not available. If existence=True, the function returns a boolean representing whether skew supplementary difference sets can be constructed.

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import skew_supplementary_difference_set_over_polynomial_ring
sage: G, [S1, S2, S3, S4] = skew_supplementary_difference_set_over_polynomial_ring(81)      # needs sage.libs.pari

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import skew_supplementary_difference_set_over_polynomial_ring
>>> G, [S1, S2, S3, S4] = skew_supplementary_difference_set_over_polynomial_ring(Integer(81))      # needs sage.libs.pari

If existence=True, the function returns a boolean:

Sage

sage: skew_supplementary_difference_set_over_polynomial_ring(81, existence=True)
True
sage: skew_supplementary_difference_set_over_polynomial_ring(17, existence=True)
False

Python

>>> from sage.all import *
>>> skew_supplementary_difference_set_over_polynomial_ring(Integer(81), existence=True)
True
>>> skew_supplementary_difference_set_over_polynomial_ring(Integer(17), existence=True)
False

sage.combinat.designs.difference_family.skew_supplementary_difference_set_with_paley_todd(n, existence=False, check=True)[source]¶

Construct \(4-\{n; n_1, n_2, n_3, n_4; \lambda\}\) skew supplementary difference sets where \(S_1\) is the Paley-Todd difference set.

The skew SDS returned have the property that \(n_1 + n_2 + n_3 + n_4 = n + \lambda\).

This construction is described in [DK2016]. The function contains, for each value of \(n\), a set \(H\) containing integers modulo \(n\), and four sets \(J, K, L\). Then, these are used to construct \((n; k_2, k_3, k_4; \lambda_2)\) difference family, with \(\lambda_2 = k_2 + k_3 + k_4 + (3n - 1) / 4\). Finally, these sets together with the Paley-Todd difference set form a skew supplementary difference set.

INPUT:

n – integer; the parameter of the supplementary difference set
existence – boolean (default: 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:

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import skew_supplementary_difference_set_with_paley_todd
sage: G, [S1, S2, S3, S4] = skew_supplementary_difference_set_with_paley_todd(239)

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import skew_supplementary_difference_set_with_paley_todd
>>> G, [S1, S2, S3, S4] = skew_supplementary_difference_set_with_paley_todd(Integer(239))

If existence is True, the function returns a boolean:

Sage

sage: skew_supplementary_difference_set_with_paley_todd(239, existence=True)
True
sage: skew_supplementary_difference_set_with_paley_todd(17, existence=True)
False

Python

>>> from sage.all import *
>>> skew_supplementary_difference_set_with_paley_todd(Integer(239), existence=True)
True
>>> skew_supplementary_difference_set_with_paley_todd(Integer(17), existence=True)
False

sage.combinat.designs.difference_family.spin_goethals_seidel_difference_family(n, existence=False, check=True)[source]¶

Construct a spin type Goethals-Seidel difference family with parameters \((n; k_1, k_2, k_3, k_4; \lambda)\).

The construction is described in [Djo2024]. This function contains, for each value of \(n\), either a full representation of \(S_1, S_2\) together with the multiplier \(\mu\), or a subgroup \(H\), two sets of representatives, and the multiplier. This data is used to construct the difference family using the functions _construct_gs_difference_family_from_full() and _construct_gs_difference_family_from_compact().

Additionally, this function also checks if a (skew) difference family can be constructed using skew_spin_goethals_seidel_difference_family().

INPUT:

n – integer; the parameter of the GS difference family
existence – boolean (default: False); if True, only check whether the difference family can be constructed
check – boolean (default: True); if True, check that the sets are a difference family before returning them; setting this parameter to False may speed up the computation considerably

OUTPUT:

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import spin_goethals_seidel_difference_family
sage: G, [S1, S2, S3, S4] = spin_goethals_seidel_difference_family(73)

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import spin_goethals_seidel_difference_family
>>> G, [S1, S2, S3, S4] = spin_goethals_seidel_difference_family(Integer(73))

If existence is True, the function returns a boolean:

Sage

sage: spin_goethals_seidel_difference_family(73, existence=True)
True
sage: spin_goethals_seidel_difference_family(5, existence=True)
False

Python

>>> from sage.all import *
>>> spin_goethals_seidel_difference_family(Integer(73), existence=True)
True
>>> spin_goethals_seidel_difference_family(Integer(5), existence=True)
False

sage.combinat.designs.difference_family.supplementary_difference_set(q, existence=False, check=True)[source]¶

Construct \(4-\{2v; v, v+1, v, v; 2v\}\) supplementary difference sets where \(q=2v+1\).

This is a deprecated version of supplementary_difference_set_from_rel_diff_set(), please use that instead.

sage.combinat.designs.difference_family.supplementary_difference_set_from_rel_diff_set(q, existence=False, check=True)[source]¶

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 (default: 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=False, the function returns the 4 sets (containing integers), or raises an error if q does not satify the constraints. If existence=True, the function returns a boolean representing whether supplementary difference sets can be constructed.

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import supplementary_difference_set_from_rel_diff_set
sage: supplementary_difference_set_from_rel_diff_set(17)  #random               # needs sage.libs.pari
(Additive abelian group isomorphic to Z/16,
 [[(1), (5), (6), (7), (9), (13), (14), (15)],
  [(0), (2), (3), (5), (6), (10), (11), (13), (14)],
  [(0), (1), (2), (3), (5), (6), (7), (12)],
  [(0), (2), (3), (5), (6), (7), (9), (12)]])

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import supplementary_difference_set_from_rel_diff_set
>>> supplementary_difference_set_from_rel_diff_set(Integer(17))  #random               # needs sage.libs.pari
(Additive abelian group isomorphic to Z/16,
 [[(1), (5), (6), (7), (9), (13), (14), (15)],
  [(0), (2), (3), (5), (6), (10), (11), (13), (14)],
  [(0), (1), (2), (3), (5), (6), (7), (12)],
  [(0), (2), (3), (5), (6), (7), (9), (12)]])

If existence=True, the function returns a boolean:

Sage

sage: supplementary_difference_set_from_rel_diff_set(7, existence=True)
False
sage: supplementary_difference_set_from_rel_diff_set(17, existence=True)
True

Python

>>> from sage.all import *
>>> supplementary_difference_set_from_rel_diff_set(Integer(7), existence=True)
False
>>> supplementary_difference_set_from_rel_diff_set(Integer(17), existence=True)
True

See also

is_supplementary_difference_set()

sage.combinat.designs.difference_family.supplementary_difference_set_hadamard(n, existence=False, check=True)[source]¶

Construct \(4-\{n; n_1, n_2, n_3, n_4; \lambda\}\) supplementary difference sets, where \(n_1 + n_2 + n_3 + n_4 = n+\lambda\).

These sets are constructed from available data, as described in [Djo1994a]. The data is taken from:

\(n = 191\): [Djo2008c]
\(n = 239\): [Djo1994b]
\(n = 251\): [DGK2014]

Additional SDS are constructed using skew_supplementary_difference_set().

INPUT:

n – integer; the parameter of the supplementary difference set
existence – boolean (default: 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; Setting this parameter to False may speed up the computation considerably

OUTPUT:

If existence=False, the function returns the ring of integers modulo n and a list containing the 4 sets, or raises an error if data for the given n is not available. If existence=True, the function returns a boolean representing whether skew supplementary difference sets can be constructed.

EXAMPLES:

Sage

sage: from sage.combinat.designs.difference_family import supplementary_difference_set_hadamard
sage: G, [S1, S2, S3, S4] = supplementary_difference_set_hadamard(191)

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import supplementary_difference_set_hadamard
>>> G, [S1, S2, S3, S4] = supplementary_difference_set_hadamard(Integer(191))

If existence=True, the function returns a boolean:

Sage

sage: supplementary_difference_set_hadamard(191, existence=True)
True
sage: supplementary_difference_set_hadamard(17, existence=True)
False

Python

>>> from sage.all import *
>>> supplementary_difference_set_hadamard(Integer(191), existence=True)
True
>>> supplementary_difference_set_hadamard(Integer(17), existence=True)
False

sage.combinat.designs.difference_family.turyn_1965_3x3xK(k=4)[source]¶

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

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)

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import turyn_1965_3x3xK
>>> from sage.combinat.designs.difference_family import is_difference_family
>>> G,D = turyn_1965_3x3xK(Integer(4))
>>> assert is_difference_family(G, D, Integer(36), Integer(15), Integer(6))
>>> G,D = turyn_1965_3x3xK(Integer(2))
>>> assert is_difference_family(G, D, Integer(36), Integer(15), Integer(6))

sage.combinat.designs.difference_family.twin_prime_powers_difference_set(p, check=True)[source]¶

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

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

Python

>>> from sage.all import *
>>> from sage.combinat.designs.difference_family import twin_prime_powers_difference_set
>>> G, D = twin_prime_powers_difference_set(Integer(3))
>>> G
The Cartesian product of (Finite Field of size 3, Finite Field of size 5)
>>> D
[[(1, 1), (1, 4), (2, 2), (2, 3), (0, 0), (1, 0), (2, 0)]]