Coverage for local/lib/python2.7/site-packages/sage/combinat/designs/difference_family.py : 83%

# -*- coding: utf-8 -*- 

r""" 

Difference families 

This module gathers everything related to difference families. One can build a 

difference family (or check that it can be built) with :func:`difference_family`:: 

sage: G,F = designs.difference_family(13,4,1) 

It defines the following functions: 

{INDEX_OF_FUNCTIONS} 

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] \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] \R. M. Wilson "Cyclotomy and difference families in elementary Abelian 

groups", J. Number Theory, 4 (1972) 17--47. 

Functions 

--------- 

""" 

#***************************************************************************** 

# Copyright (C) 2014 Vincent Delecroix <20100.delecroix@gmail.com> 

# 

# Distributed under the terms of the GNU General Public License (GPL) 

# as published by the Free Software Foundation; either version 2 of 

# the License, or (at your option) any later version. 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

# python3 

from __future__ import division, print_function, absolute_import 

from builtins import zip 

import six 

from six import itervalues 

from six.moves import range 

from sage.misc.cachefunc import cached_method 

from sage.categories.sets_cat import EmptySetError 

import sage.arith.all as arith 

from sage.misc.unknown import Unknown 

from sage.rings.integer import Integer 

from sage.rings.integer_ring import ZZ 

def group_law(G): 

r""" 

Return a triple ``(identity, operation, inverse)`` that define the 

operations on the group ``G``. 

EXAMPLES:: 

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

sage: group_law(Zmod(3)) 

(0, <built-in function add>, <built-in function neg>) 

sage: group_law(SymmetricGroup(5)) 

((), <built-in function mul>, <built-in function inv>) 

sage: group_law(VectorSpace(QQ,3)) 

((0, 0, 0), <built-in function add>, <built-in function neg>) 

""" 

import operator 

from sage.categories.groups import Groups 

from sage.categories.additive_groups import AdditiveGroups 

if G in Groups(): # multiplicative groups 

return (G.one(), operator.mul, operator.inv) 

elif G in AdditiveGroups(): # additive groups 

return (G.zero(), operator.add, operator.neg) 

else: 

raise ValueError("%s does not seem to be a group"%G) 

def block_stabilizer(G, B): 

r""" 

Compute the left stabilizer of the block ``B`` under the action of ``G``. 

This function return the list of all `x\in G` such that `x\cdot B=B` (as a 

set). 

INPUT: 

- ``G`` -- a group (additive or multiplicative). 

- ``B`` -- a subset of ``G``. 

EXAMPLES:: 

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

sage: Z8 = Zmod(8) 

sage: block_stabilizer(Z8, [Z8(0),Z8(2),Z8(4),Z8(6)]) 

[0, 2, 4, 6] 

sage: block_stabilizer(Z8, [Z8(0),Z8(2)]) 

[0] 

sage: C = cartesian_product([Zmod(4),Zmod(3)]) 

sage: block_stabilizer(C, [C((0,0)),C((2,0)),C((0,1)),C((2,1))]) 

[(0, 0), (2, 0)] 

sage: b = list(map(Zmod(45),[1, 3, 7, 10, 22, 25, 30, 35, 37, 38, 44])) 

sage: block_stabilizer(Zmod(45),b) 

[0] 

""" 

if not B: 

return list(G) 

identity, op, inv = group_law(G) 

b0 = inv(B[0]) 

S = [] 

for b in B: 

# fun: if we replace +(-b) with -b it completely fails!! 

bb0 = op(b,b0) # bb0 = b-B[0] 

if all(op(bb0,c) in B for c in B): 

S.append(bb0) 

return S 

def is_difference_family(G, D, v=None, k=None, l=None, verbose=False): 

r""" 

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

INPUT: 

- ``G`` - group of cardinality ``v`` 

- ``D`` - a set of ``k``-subsets of ``G`` 

- ``v``, ``k`` and ``l`` - optional parameters of the difference family 

- ``verbose`` - whether to print additional information 

.. SEEALSO:: 

:func:`difference_family` 

EXAMPLES:: 

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

sage: G = Zmod(21) 

sage: D = [[0,1,4,14,16]] 

sage: is_difference_family(G, D, 21, 5) 

True 

sage: G = Zmod(41) 

sage: D = [[0,1,4,11,29],[0,2,8,17,21]] 

sage: is_difference_family(G, D, verbose=True) 

Too few: 

5 is obtained 0 times in blocks [] 

14 is obtained 0 times in blocks [] 

27 is obtained 0 times in blocks [] 

36 is obtained 0 times in blocks [] 

Too much: 

4 is obtained 2 times in blocks [0, 1] 

13 is obtained 2 times in blocks [0, 1] 

28 is obtained 2 times in blocks [0, 1] 

37 is obtained 2 times in blocks [0, 1] 

False 

sage: D = [[0,1,4,11,29],[0,2,8,17,22]] 

sage: is_difference_family(G, D) 

True 

sage: G = Zmod(61) 

sage: D = [[0,1,3,13,34],[0,4,9,23,45],[0,6,17,24,32]] 

sage: is_difference_family(G, D) 

True 

sage: G = AdditiveAbelianGroup([3]*4) 

sage: a,b,c,d = G.gens() 

sage: D = [[d, -a+d, -c+d, a-b-d, b+c+d], 

....: [c, a+b-d, -b+c, a-b+d, a+b+c], 

....: [-a-b+c+d, a-b-c-d, -a+c-d, b-c+d, a+b], 

....: [-b-d, a+b+d, a-b+c-d, a-b+c, -b+c+d]] 

sage: is_difference_family(G, D) 

True 

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

sage: G = Zmod(15) 

sage: D = [[0,1,4],[0,2,9],[0,5,10]] 

sage: is_difference_family(G,D,verbose=True) 

It is a (15,3,1)-difference family 

True 

The function also supports multiplicative groups (non necessarily Abelian):: 

sage: G = DihedralGroup(8) 

sage: x,y = G.gens() 

sage: i = G.one() 

sage: D1 = [[i,x,x^4], [i,x^2, y*x], [i,x^5,y], [i,x^6,y*x^2], [i,x^7,y*x^5]] 

sage: is_difference_family(G, D1, 16, 3, 2) 

True 

sage: from sage.combinat.designs.bibd import BIBD_from_difference_family 

sage: bibd = BIBD_from_difference_family(G,D1,lambd=2) 

TESTS:: 

sage: K = GF(3^2,'z') 

sage: z = K.gen() 

sage: D = [[1,z+1,2]] 

sage: _ = is_difference_family(K, D, verbose=True) 

the number of differences (=6) must be a multiple of v-1=8 

sage: _ 

False 

""" 

import operator 

identity, mul, inv = group_law(G) 

Glist = list(G) 

D = [[G(_) for _ in d] for d in D] 

# Check v (and define it if needed) 

if v is None: 

v = len(Glist) 

else: 

if len(Glist) != v: 

if verbose: 

print("G must have cardinality v (=%d)" % int(v)) 

return False 

# Check k (and define it if needed) 

if k is None: 

k = len(D[0]) 

else: 

k = int(k) 

for d in D: 

if len(d) != k: 

if verbose: 

print("the block {} does not have length {}".format(d, k)) 

return False 

# Check l (and define it if needed) 

# 

# - nb_diff: the number of pairs (with multiplicity) covered by the BIBD 

# generated by the DF. 

# 

# - stab: the stabilizer of each set. 

nb_diff = 0 

stab = [] 

for d in D: 

s = block_stabilizer(G,d) 

stab.append(s) 

nb_diff += k*(k-1) // len(s) 

if l is None: 

if nb_diff % (v-1) != 0: 

if verbose: 

print("the number of differences (={}) must be a multiple of v-1={}".format(nb_diff, v-1)) 

return False 

l = nb_diff // (v-1) 

else: 

if nb_diff != l*(v-1): 

if verbose: 

print("the number of differences (={}) is not equal to l*(v-1) = {}".format(nb_diff, l*(v-1))) 

return False 

# Check that every x \in G-{0},occurs exactly l times as a difference 

counter = {g: 0 for g in Glist} 

where = {g: set() for g in Glist} 

del counter[identity] 

for i,d in enumerate(D): 

tmp_counter = {} 

for b in d: 

for c in d: 

if b == c: 

continue 

gg = mul(b,inv(c)) # = b-c or bc^{-1} 

if gg not in tmp_counter: 

tmp_counter[gg] = 0 

where[gg].add(i) 

tmp_counter[gg] += 1 

if sum(itervalues(tmp_counter)) != k * (k - 1): 

if verbose: 

print("repeated element in the {}-th block {}".format(i,d)) 

return False 

# Normalized number of occurrences added to counter 

stabi = len(stab[i]) 

for gg in tmp_counter: 

counter[gg] += tmp_counter[gg]//stabi 

# Check the counter and report any error 

too_few = [] 

too_much = [] 

for g in Glist: 

if g == identity: 

continue 

if counter[g] < l: 

if verbose: 

too_few.append(g) 

else: 

return False 

if counter[g] > l: 

if verbose: 

too_much.append(g) 

else: 

return False 

if too_few: 

print("Too few:") 

for g in too_few: 

print(" {} is obtained {} times in blocks {}".format( 

g, counter[g], sorted(where[g]))) 

if too_much: 

print("Too much:") 

for g in too_much: 

print(" {} is obtained {} times in blocks {}".format( 

g, counter[g], sorted(where[g]))) 

if too_few or too_much: 

return False 

if verbose: 

print("It is a ({},{},{})-difference family".format(v, k, l)) 

return True 

def singer_difference_set(q,d): 

r""" 

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: 

.. MATH:: 

v = \frac{q^{d+1}-1}{q-1}, \quad 

k = \frac{q^d-1}{q-1}, \quad 

\lambda = \frac{q^{d-1}-1}{q-1}. 

The idea of the construction is as follows. One consider the finite field 

`GF(q^{d+1})` as a vector space of dimension `d+1` over `GF(q)`. The set of 

`GF(q)`-lines in `GF(q^{d+1})` is a projective plane and its set of 

hyperplanes form a balanced incomplete block design. 

Now, considering a multiplicative generator `z` of `GF(q^{d+1})`, we get a 

transitive action of a cyclic group on our projective plane from which it is 

possible to build a difference set. 

The construction is given in details in [Stinson2004]_, section 3.3. 

EXAMPLES:: 

sage: from sage.combinat.designs.difference_family import singer_difference_set, is_difference_family 

sage: G,D = singer_difference_set(3,2) 

sage: is_difference_family(G,D,verbose=True) 

It is a (13,4,1)-difference family 

True 

sage: G,D = singer_difference_set(4,2) 

sage: is_difference_family(G,D,verbose=True) 

It is a (21,5,1)-difference family 

True 

sage: G,D = singer_difference_set(3,3) 

sage: is_difference_family(G,D,verbose=True) 

It is a (40,13,4)-difference family 

True 

sage: G,D = singer_difference_set(9,3) 

sage: is_difference_family(G,D,verbose=True) 

It is a (820,91,10)-difference family 

True 

""" 

q = Integer(q) 

assert q.is_prime_power() 

assert d >= 2 

from sage.rings.finite_rings.finite_field_constructor import GF 

from sage.rings.finite_rings.conway_polynomials import conway_polynomial 

from sage.rings.finite_rings.integer_mod_ring import Zmod 

# build a polynomial c over GF(q) such that GF(q)[x] / (c(x)) is a 

# GF(q**(d+1)) and such that x is a multiplicative generator. 

p,e = q.factor()[0] 

c = conway_polynomial(p,e*(d+1)) 

if e != 1: # i.e. q is not a prime, so we factorize c over GF(q) and pick 

# one of its factor 

K = GF(q,'z') 

c = c.change_ring(K).factor()[0][0] 

else: 

K = GF(q) 

z = c.parent().gen() 

# Now we consider the GF(q)-subspace V spanned by (1,z,z^2,...,z^(d-1)) inside 

# GF(q^(d+1)). The multiplication by z is an automorphism of the 

# GF(q)-projective space built from GF(q^(d+1)). The difference family is 

# obtained by taking the integers i such that z^i belong to V. 

powers = [0] 

i = 1 

x = z 

k = (q**d-1)//(q-1) 

while len(powers) < k: 

if x.degree() <= (d-1): 

powers.append(i) 

x = (x*z).mod(c) 

i += 1 

return Zmod((q**(d+1)-1)//(q-1)), [powers] 

def df_q_6_1(K, existence=False, check=True): 

r""" 

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

The construction uses Theorem 11 of [Wi72]_. 

EXAMPLES:: 

sage: from sage.combinat.designs.difference_family import is_difference_family, df_q_6_1 

sage: prime_powers = [v for v in range(31,500,30) if is_prime_power(v)] 

sage: parameters = [v for v in prime_powers if df_q_6_1(GF(v,'a'), existence=True)] 

sage: parameters 

[31, 151, 181, 211, 241, 271, 331, 361, 421] 

sage: for v in parameters: 

....: K = GF(v, 'a') 

....: df = df_q_6_1(K, check=True) 

....: assert is_difference_family(K, df, v, 6, 1) 

.. TODO:: 

Do improvements due to Zhen and Wu 1999. 

""" 

v = K.cardinality() 

x = K.multiplicative_generator() 

one = K.one() 

if v % 30 != 1: 

if existence: 

return False 

raise EmptySetError("k(k-1)=30 should divide (v-1)") 

t = (v-1) // 30 # number of blocks 

r = x**((v-1)//3) # primitive cube root of unity 

r2 = r*r # the other primitive cube root 

# we now compute the cosets of x**i 

xx = x**5 

to_coset = {x**i * xx**j: i for i in range(5) for j in range((v-1)/5)} 

for c in to_coset: # the loop runs through all nonzero elements of K 

if c == one or c == r or c == r2: 

continue 

if len(set(to_coset[elt] for elt in (r-one, c*(r-one), c-one, c-r, c-r**2))) == 5: 

if existence: 

return True 

B = [one,r,r2,c,c*r,c*r2] 

D = [[xx**i * b for b in B] for i in range(t)] 

break 

else: 

if existence: 

return Unknown 

raise NotImplementedError("Wilson construction failed for v={}".format(v)) 

if check and not is_difference_family(K, D, v, 6, 1): 

raise RuntimeError("Wilson 1972 construction failed! Please e-mail sage-devel@googlegroups.com") 

return D 

def radical_difference_set(K, k, l=1, existence=False, check=True): 

r""" 

Return a difference set made of a cyclotomic coset in the finite field 

``K`` and with parameters ``k`` and ``l``. 

Most of these difference sets appear in chapter VI.18.48 of the Handbook of 

combinatorial designs. 

EXAMPLES:: 

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

sage: D = radical_difference_set(GF(7), 3, 1); D 

[[1, 2, 4]] 

sage: sorted(x-y for x in D[0] for y in D[0] if x != y) 

[1, 2, 3, 4, 5, 6] 

sage: D = radical_difference_set(GF(16,'a'), 6, 2) 

sage: sorted(x-y for x in D[0] for y in D[0] if x != y) 

[1, 

1, 

a, 

a, 

a + 1, 

a + 1, 

a^2, 

a^2, 

... 

a^3 + a^2 + a + 1, 

a^3 + a^2 + a + 1] 

sage: for k in range(2,50): 

....: for l in reversed(divisors(k*(k-1))): 

....: v = k*(k-1)//l + 1 

....: if is_prime_power(v) and radical_difference_set(GF(v,'a'),k,l,existence=True): 

....: _ = radical_difference_set(GF(v,'a'),k,l) 

....: print("{:3} {:3} {:3}".format(v,k,l)) 

3 2 1 

4 3 2 

7 3 1 

5 4 3 

7 4 2 

13 4 1 

11 5 2 

7 6 5 

11 6 3 

16 6 2 

8 7 6 

9 8 7 

19 9 4 

37 9 2 

73 9 1 

11 10 9 

19 10 5 

23 11 5 

13 12 11 

23 12 6 

27 13 6 

27 14 7 

16 15 14 

31 15 7 

... 

41 40 39 

79 40 20 

83 41 20 

43 42 41 

83 42 21 

47 46 45 

49 48 47 

197 49 12 

""" 

v = K.cardinality() 

if l*(v-1) != k*(k-1): 

if existence: 

return False 

raise EmptySetError("l*(v-1) is not equal to k*(k-1)") 

# trivial case 

if (v-1) == k: 

if existence: 

return True 

add_zero = False 

# q = 3 mod 4 

elif v%4 == 3 and k == (v-1)//2: 

if existence: 

return True 

add_zero = False 

# q = 3 mod 4 

elif v%4 == 3 and k == (v+1)//2: 

if existence: 

return True 

add_zero = True 

# q = 4t^2 + 1, t odd 

elif v%8 == 5 and k == (v-1)//4 and arith.is_square((v-1)//4): 

if existence: 

return True 

add_zero = False 

# q = 4t^2 + 9, t odd 

elif v%8 == 5 and k == (v+3)//4 and arith.is_square((v-9)//4): 

if existence: 

return True 

add_zero = True 

# exceptional case 1 

elif (v,k,l) == (16,6,2): 

if existence: 

return True 

add_zero = True 

# exceptional case 2 

elif (v,k,l) == (73,9,1): 

if existence: 

return True 

add_zero = False 

# are there more ?? 

else: 

x = K.multiplicative_generator() 

D = K.cyclotomic_cosets(x**((v-1)//k), [K.one()]) 

if is_difference_family(K, D, v, k, l): 

print("** You found a new example of radical difference set **\n"\ 

"** for the parameters (v,k,l)=({},{},{}). **\n"\ 

"** Please contact sage-devel@googlegroups.com **\n".format(v, k, l)) 

if existence: 

return True 

add_zero = False 

else: 

D = K.cyclotomic_cosets(x**((v-1)//(k-1)), [K.one()]) 

D[0].insert(0,K.zero()) 

if is_difference_family(K, D, v, k, l): 

print("** You found a new example of radical difference set **\n"\ 

"** for the parameters (v,k,l)=({},{},{}). **\n"\ 

"** Please contact sage-devel@googlegroups.com **\n".format(v, k, l)) 

if existence: 

return True 

add_zero = True 

elif existence: 

return False 

else: 

raise EmptySetError("no radical difference set exist " 

"for the parameters (v,k,l) = ({},{},{}".format(v,k,l)) 

x = K.multiplicative_generator() 

if add_zero: 

r = x**((v-1)//(k-1)) 

D = K.cyclotomic_cosets(r, [K.one()]) 

D[0].insert(0, K.zero()) 

else: 

r = x**((v-1)//k) 

D = K.cyclotomic_cosets(r, [K.one()]) 

if check and not is_difference_family(K, D, v, k, l): 

raise RuntimeError("Sage tried to build a radical difference set with " 

"parameters ({},{},{}) but it seems that it failed! Please " 

"e-mail sage-devel@googlegroups.com".format(v,k,l)) 

return D 

def one_cyclic_tiling(A,n): 

r""" 

Given a subset ``A`` of the cyclic additive group `G = Z / nZ` return 

another subset `B` so that `A + B = G` and `|A| |B| = n` (i.e. any element 

of `G` is uniquely expressed as a sum `a+b` with `a` in `A` and `b` in `B`). 

EXAMPLES:: 

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

sage: tile = [0,2,4] 

sage: m = one_cyclic_tiling(tile,6); m 

[0, 3] 

sage: sorted((i+j)%6 for i in tile for j in m) 

[0, 1, 2, 3, 4, 5] 

sage: def print_tiling(tile, translat, n): 

....: for x in translat: 

....: print(''.join('X' if (i-x)%n in tile else '.' for i in range(n))) 

sage: tile = [0, 1, 2, 7] 

sage: m = one_cyclic_tiling(tile, 12) 

sage: print_tiling(tile, m, 12) 

XXX....X.... 

....XXX....X 

...X....XXX. 

sage: tile = [0, 1, 5] 

sage: m = one_cyclic_tiling(tile, 12) 

sage: print_tiling(tile, m, 12) 

XX...X...... 

...XX...X... 

......XX...X 

..X......XX. 

sage: tile = [0, 2] 

sage: m = one_cyclic_tiling(tile, 8) 

sage: print_tiling(tile, m, 8) 

X.X..... 

....X.X. 

.X.X.... 

.....X.X 

ALGORITHM: 

Uses dancing links :mod:`sage.combinat.dlx` 

""" 

# we first try a naive approach which correspond to what Wilson used in his 

# 1972 article 

n = int(n) 

d = len(A) 

if len(set(a%d for a in A)) == d: 

return [i*d for i in range(n//d)] 

# next, we consider an exhaustive search 

from sage.combinat.dlx import DLXMatrix 

rows = [] 

for i in range(n): 

rows.append([i+1, [(i+a)%n+1 for a in A]]) 

M = DLXMatrix(rows) 

for c in M: 

return [i-1 for i in c] 

def one_radical_difference_family(K, k): 

r""" 

Search for a radical difference family on ``K`` using dancing links 

algorithm. 

For the definition of radical difference family, see 

:func:`radical_difference_family`. Here, we consider only radical difference 

family with `\lambda = 1`. 

INPUT: 

- ``K`` -- a finite field of cardinality `q`. 

- ``k`` -- a positive integer so that `k(k-1)` divides `q-1`. 

OUTPUT: 

Either a difference family or ``None`` if it does not exist. 

ALGORITHM: 

The existence of a radical difference family is equivalent to a one 

dimensional tiling (or packing) problem in a cyclic group. This subsequent 

problem is solved by a call to the function :func:`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: 

.. MATH:: 

K^* = \Delta (x_1 B) \cup ... \cup \Delta (x_k B) = x_1 \Delta B \cup ... \cup x_k \Delta B 

We observe that `C=B\backslash 0` is a subgroup of the (cyclic) group 

`K^*`, that can thus be generated by some element `r`. Furthermore, we 

observe that `\Delta B` is always a union of cosets of `\pm C` (which is 

twice larger than `C`). 

.. MATH:: 

\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} 

where 

.. MATH:: 

(k\text{ odd})\ m = (k-1)/2 \quad \text{and} \quad (k\text{ even})\ m = k/2. 

Consequently, `\mathcal B = \{x_1 B, \ldots, x_k B\}` is a radical 

difference family if and only if `\{x_1 (\Delta B/(\pm C)), \ldots, x_k 

(\Delta B/(\pm C))\}` is a partition of the cyclic group `K^*/(\pm C)`. 

EXAMPLES:: 

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

....: one_radical_difference_family, 

....: is_difference_family) 

sage: one_radical_difference_family(GF(13),4) 

[[0, 1, 3, 9]] 

The parameters that appear in [Bu95]_:: 

sage: df = one_radical_difference_family(GF(449), 8); df 

[[0, 1, 18, 25, 176, 324, 359, 444], 

[0, 9, 88, 162, 222, 225, 237, 404], 

[0, 11, 140, 198, 275, 357, 394, 421], 

[0, 40, 102, 249, 271, 305, 388, 441], 

[0, 49, 80, 93, 161, 204, 327, 433], 

[0, 70, 99, 197, 230, 362, 403, 435], 

[0, 121, 141, 193, 293, 331, 335, 382], 

[0, 191, 285, 295, 321, 371, 390, 392]] 

sage: is_difference_family(GF(449), df, 449, 8, 1) 

True 

""" 

q = K.cardinality() 

x = K.multiplicative_generator() 

e = k*(k-1) 

if q%e != 1: 

raise ValueError("q%e is not 1") 

# We define A by (see the function's documentation): 

# ΔB = C.A 

if k%2 == 1: 

m = (k-1) // 2 

r = x ** ((q-1) // k) # k-th root of unity 

A = [r**i - 1 for i in range(1,m+1)] 

else: 

m = k // 2 

r = x ** ((q-1) // (k-1)) # (k-1)-th root of unity 

A = [r**i - 1 for i in range(1,m)] 

A.append(K.one()) 

# instead of the complicated multiplicative group K^*/(±C) we use the 

# discrete logarithm to convert everything into the additive group Z/cZ 

c = m * (q-1) // e # cardinal of ±C 

from sage.groups.generic import discrete_log 

logA = [discrete_log(a,x)%c for a in A] 

# if two elments of A are equal modulo c then no tiling is possible 

if len(set(logA)) != m: 

return None 

# brute force 

tiling = one_cyclic_tiling(logA, c) 

if tiling is None: 

return None 

D = K.cyclotomic_cosets(r, [x**i for i in tiling]) 

if k%2 == 0: 

for d in D: 

d.insert(K.zero(),0) 

return D 

def radical_difference_family(K, k, l=1, existence=False, check=True): 

r""" 

Return a ``(v,k,l)``-radical difference family. 

Let fix an integer `k` and a prime power `q = t k(k-1) + 1`. Let `K` be a 

field of cardinality `q`. A `(q,k,1)`-difference family is *radical* if 

its base blocks are either: a coset of the `k`-th root of unity for `k` odd 

or a coset of `k-1`-th root of unity and `0` if `k` is even (the number `t` 

is the number of blocks of that difference family). 

The terminology comes from M. Buratti article [Bu95]_ but the first 

constructions go back to R. Wilson [Wi72]_. 

INPUT: 

- ``K`` - a finite field 

- ``k`` -- positive integer, the size of the blocks 

- ``l`` -- the `\lambda` parameter (default to `1`) 

- ``existence`` -- if ``True``, then return either ``True`` if Sage knows 

how to build such design, ``Unknown`` if it does not and ``False`` if it 

knows that the design does not exist. 

- ``check`` -- boolean (default: ``True``). If ``True`` then the result of 

the computation is checked before being returned. This should not be 

needed but ensures that the output is correct. 

EXAMPLES:: 

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

sage: radical_difference_family(GF(73),9) 

[[1, 2, 4, 8, 16, 32, 37, 55, 64]] 

sage: radical_difference_family(GF(281),5) 

[[1, 86, 90, 153, 232], 

[4, 50, 63, 79, 85], 

[5, 36, 149, 169, 203], 

[7, 40, 68, 219, 228], 

[9, 121, 212, 248, 253], 

[29, 81, 222, 246, 265], 

[31, 137, 167, 247, 261], 

[32, 70, 118, 119, 223], 

[39, 56, 66, 138, 263], 

[43, 45, 116, 141, 217], 

[98, 101, 109, 256, 279], 

[106, 124, 145, 201, 267], 

[111, 123, 155, 181, 273], 

[156, 209, 224, 264, 271]] 

sage: for k in range(5,10): 

....: print("k = {}".format(k)) 

....: list_q = [] 

....: for q in range(k*(k-1)+1, 2000, k*(k-1)): 

....: if is_prime_power(q): 

....: K = GF(q,'a') 

....: if radical_difference_family(K, k, existence=True): 

....: list_q.append(q) 

....: _ = radical_difference_family(K,k) 

....: print(" ".join([str(p) for p in list_q])) 

k = 5 

41 61 81 241 281 401 421 601 641 661 701 761 821 881 1181 1201 1301 1321 

1361 1381 1481 1601 1681 1801 1901 

k = 6 

181 211 241 631 691 1531 1831 1861 

k = 7 

337 421 463 883 1723 

k = 8 

449 1009 

k = 9 

73 1153 1873 

""" 

v = K.cardinality() 

x = K.multiplicative_generator() 

one = K.one() 

e = k*(k-1) 

if (l*(v-1)) % e: