Namespaces
Variants
Actions

Difference between revisions of "Difference set"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
 +
{{TEX|done}}
 
''complete difference set''
 
''complete difference set''
  
A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d0317601.png" /> consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d0317602.png" /> residues <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d0317603.png" /> modulo a certain natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d0317604.png" /> such that for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d0317605.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d0317606.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d0317607.png" />), there exist precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d0317608.png" /> ordered pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d0317609.png" /> of elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176010.png" /> for which
+
A set $D$ consisting of $k$ residues $d_1,\dots,d_k$ modulo a certain natural number $v$ such that for each $a\in D$, $a\not\equiv0$ ($\bmod\,v$), there exist precisely $\lambda$ ordered pairs $(d_i,d_j)$ of elements from $D$ for which
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176011.png" /></td> </tr></table>
+
$$a\equiv d_i-d_j\pmod v;$$
  
the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176012.png" /> are called the parameters of the difference set. For example, the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176013.png" /> of residues modulo 11 is a difference set with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176014.png" />.
+
the numbers $v,k,\lambda$ are called the parameters of the difference set. For example, the set $D=\{1,3,4,5,9\}$ of residues modulo 11 is a difference set with $\lambda=2$.
  
Difference sets are closely connected with block designs (cf. [[Block design|Block design]]), namely: The existence of a difference set is equivalent to the existence of a symmetric block design with parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176015.png" /> having a cyclic group of automorphisms of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176016.png" /> (the blocks of such a design are the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176018.png" />). The notion of a difference set can be generalized in the following way: A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176019.png" /> consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176020.png" /> distinct elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176021.png" /> of a group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176022.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176023.png" /> is called a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176025.png" />-difference set in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176026.png" /> if for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176027.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176028.png" />, there exist precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176029.png" /> ordered pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176031.png" />, such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176032.png" /> (or, what is the same, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176033.png" /> pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176034.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176035.png" />). In this case a difference set as defined above is called a cyclic difference set (since the group of residue classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176036.png" /> is a cyclic group). The existence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176037.png" />-difference sets in a group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176038.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176039.png" /> is equivalent to the existence of a symmetric block design with parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176040.png" /> admitting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176041.png" /> as a regular (that is, without fixed points) group of automorphisms (this design is obtained by identifying the elements of the block design with the elements of the group and the blocks with the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176042.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176043.png" /> runs over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176044.png" />).
+
Difference sets are closely connected with block designs (cf. [[Block design|Block design]]), namely: The existence of a difference set is equivalent to the existence of a symmetric block design with parameters $(v,k,\lambda)$ having a cyclic group of automorphisms of order $v$ (the blocks of such a design are the sets $\{d_1+i,\dots,d_k+i\}$, $i=0,\dots,v-1$). The notion of a difference set can be generalized in the following way: A set $D$ consisting of $k$ distinct elements $d_1,\dots,d_k$ of a group $G$ of order $v$ is called a $(v,k,\lambda)$-difference set in $G$ if for any $a\in G$, $a\neq1$, there exist precisely $\lambda$ ordered pairs $(d_i,d_j)$, $d_i,d_j\in G$, such that $d_id_j^{-1}=a$ (or, what is the same, $\lambda$ pairs $(d_i,d_j)$ with $d_i^{-1}d_j=a$). In this case a difference set as defined above is called a cyclic difference set (since the group of residue classes $\bmod\,v$ is a cyclic group). The existence of $(v,k,\lambda)$-difference sets in a group $G$ of order $v$ is equivalent to the existence of a symmetric block design with parameters $(v,k,\lambda)$ admitting $G$ as a regular (that is, without fixed points) group of automorphisms (this design is obtained by identifying the elements of the block design with the elements of the group and the blocks with the sets $\{d_1g,\dots,d_kg\}$, where $g$ runs over $G$).
  
The question of the existence and construction of a difference set with given parameters is fundamental in the theory of difference sets. For this question the concept of a multiplier of a difference set turns out to be useful: An automorphism of the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176045.png" /> is a multiplier of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176047.png" />-difference set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176048.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176049.png" /> if it is also an automorphism of the block design determined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176050.png" />. For a cyclic difference set a multiplier is a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176051.png" /> relatively prime with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176052.png" /> and with the property that
+
The question of the existence and construction of a difference set with given parameters is fundamental in the theory of difference sets. For this question the concept of a multiplier of a difference set turns out to be useful: An automorphism of the group $G$ is a multiplier of a $(v,k,\lambda)$-difference set $D$ in $G$ if it is also an automorphism of the block design determined by $D$. For a cyclic difference set a multiplier is a number $t$ relatively prime with $v$ and with the property that
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176053.png" /></td> </tr></table>
+
$$\{td_1,\dots,td_k\}=\{d_1+i,\dots,d_k+i\}$$
  
for a certain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176054.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176055.png" />. The multipliers of a cyclic difference set form a group. The following assertion is true: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176056.png" /> is a cyclic <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176057.png" />-difference set and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176058.png" /> is a prime number dividing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176059.png" /> and such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176060.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176061.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176062.png" /> is a multiplier of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176063.png" /> (the multiplier theorem for difference sets). The following result is useful when constructing difference sets: For any multiplier of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176064.png" />-difference set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176065.png" /> in an Abelian group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176066.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176067.png" /> there exists a block in the block design determined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176068.png" /> which is fixed by this multiplier; when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176069.png" /> there exists a block fixed by any multiplier.
+
for a certain $i$, $0\leq i\leq v-1$. The multipliers of a cyclic difference set form a group. The following assertion is true: If $D$ is a cyclic $(v,k,\lambda)$-difference set and if $p$ is a prime number dividing $k-\lambda$ and such that $(p,v)=1$ and $p>\lambda$, then $p$ is a multiplier of $D$ (the multiplier theorem for difference sets). The following result is useful when constructing difference sets: For any multiplier of a $(v,k,\lambda)$-difference set $D$ in an Abelian group $G$ of order $v$ there exists a block in the block design determined by $D$ which is fixed by this multiplier; when $(v,k)=1$ there exists a block fixed by any multiplier.
  
Difference sets are usually constructed by direct methods, using the properties of finite fields and cyclotomic fields (see [[Cyclotomic field|Cyclotomic field]]) as well as finite geometries. Several infinite families of difference sets are known, for example the following types <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176070.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176071.png" />.
+
Difference sets are usually constructed by direct methods, using the properties of finite fields and cyclotomic fields (see [[Cyclotomic field|Cyclotomic field]]) as well as finite geometries. Several infinite families of difference sets are known, for example the following types $S$ and $Q$.
  
Type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176073.png" /> (Singer difference sets): These are hyperplanes in an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176074.png" />-dimensional projective geometry over a field of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176075.png" /> elements. The parameters are:
+
Type $S$ (Singer difference sets): These are hyperplanes in an $n$-dimensional projective geometry over a field of $q$ elements. The parameters are:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176076.png" /></td> </tr></table>
+
$$v=\frac{q^{n+1}-1}{q-1},\quad k=\frac{q^n-1}{q-1},\quad\lambda=\frac{q^{n-1}-1}{q-1}.$$
  
Type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176078.png" />: Quadratic residues in the field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176079.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176080.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176081.png" />) (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176082.png" /> is a prime number). The parameters are:
+
Type $Q$: Quadratic residues in the field $\operatorname{GF}(p^r)$ when $p^r\equiv3$ ($\bmod\,4$) ($p$ is a prime number). The parameters are:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176083.png" /></td> </tr></table>
+
$$v=p^r=4t-1,\quad k=2t-1,\quad\lambda=t-1.$$
  
For other infinite families of difference sets see [[#References|[1]]]–[[#References|[3]]]. Besides these difference sets, generalized difference sets are often considered. They are also called difference families and are sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176084.png" /> consisting of residues <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176085.png" /> such that for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176086.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176087.png" />) there exist precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176088.png" /> ordered pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176089.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176090.png" />, with
+
For other infinite families of difference sets see [[#References|[1]]]–[[#References|[3]]]. Besides these difference sets, generalized difference sets are often considered. They are also called difference families and are sets $D_1,\dots,D_r$ consisting of residues $\bmod\,v$ such that for any $a\not\equiv0$ ($\bmod\,v$) there exist precisely $\lambda$ ordered pairs $(d_i,d_j)$, $d_i,d_j\in D_k$, with
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176091.png" /></td> </tr></table>
+
$$a\equiv d_i-d_j\pmod v$$
  
for a certain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176092.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031760/d03176093.png" />.
+
for a certain $k$, $1\leq k\leq r$.
  
 
There are also other generalizations of difference sets.
 
There are also other generalizations of difference sets.

Latest revision as of 10:37, 15 November 2014

complete difference set

A set $D$ consisting of $k$ residues $d_1,\dots,d_k$ modulo a certain natural number $v$ such that for each $a\in D$, $a\not\equiv0$ ($\bmod\,v$), there exist precisely $\lambda$ ordered pairs $(d_i,d_j)$ of elements from $D$ for which

$$a\equiv d_i-d_j\pmod v;$$

the numbers $v,k,\lambda$ are called the parameters of the difference set. For example, the set $D=\{1,3,4,5,9\}$ of residues modulo 11 is a difference set with $\lambda=2$.

Difference sets are closely connected with block designs (cf. Block design), namely: The existence of a difference set is equivalent to the existence of a symmetric block design with parameters $(v,k,\lambda)$ having a cyclic group of automorphisms of order $v$ (the blocks of such a design are the sets $\{d_1+i,\dots,d_k+i\}$, $i=0,\dots,v-1$). The notion of a difference set can be generalized in the following way: A set $D$ consisting of $k$ distinct elements $d_1,\dots,d_k$ of a group $G$ of order $v$ is called a $(v,k,\lambda)$-difference set in $G$ if for any $a\in G$, $a\neq1$, there exist precisely $\lambda$ ordered pairs $(d_i,d_j)$, $d_i,d_j\in G$, such that $d_id_j^{-1}=a$ (or, what is the same, $\lambda$ pairs $(d_i,d_j)$ with $d_i^{-1}d_j=a$). In this case a difference set as defined above is called a cyclic difference set (since the group of residue classes $\bmod\,v$ is a cyclic group). The existence of $(v,k,\lambda)$-difference sets in a group $G$ of order $v$ is equivalent to the existence of a symmetric block design with parameters $(v,k,\lambda)$ admitting $G$ as a regular (that is, without fixed points) group of automorphisms (this design is obtained by identifying the elements of the block design with the elements of the group and the blocks with the sets $\{d_1g,\dots,d_kg\}$, where $g$ runs over $G$).

The question of the existence and construction of a difference set with given parameters is fundamental in the theory of difference sets. For this question the concept of a multiplier of a difference set turns out to be useful: An automorphism of the group $G$ is a multiplier of a $(v,k,\lambda)$-difference set $D$ in $G$ if it is also an automorphism of the block design determined by $D$. For a cyclic difference set a multiplier is a number $t$ relatively prime with $v$ and with the property that

$$\{td_1,\dots,td_k\}=\{d_1+i,\dots,d_k+i\}$$

for a certain $i$, $0\leq i\leq v-1$. The multipliers of a cyclic difference set form a group. The following assertion is true: If $D$ is a cyclic $(v,k,\lambda)$-difference set and if $p$ is a prime number dividing $k-\lambda$ and such that $(p,v)=1$ and $p>\lambda$, then $p$ is a multiplier of $D$ (the multiplier theorem for difference sets). The following result is useful when constructing difference sets: For any multiplier of a $(v,k,\lambda)$-difference set $D$ in an Abelian group $G$ of order $v$ there exists a block in the block design determined by $D$ which is fixed by this multiplier; when $(v,k)=1$ there exists a block fixed by any multiplier.

Difference sets are usually constructed by direct methods, using the properties of finite fields and cyclotomic fields (see Cyclotomic field) as well as finite geometries. Several infinite families of difference sets are known, for example the following types $S$ and $Q$.

Type $S$ (Singer difference sets): These are hyperplanes in an $n$-dimensional projective geometry over a field of $q$ elements. The parameters are:

$$v=\frac{q^{n+1}-1}{q-1},\quad k=\frac{q^n-1}{q-1},\quad\lambda=\frac{q^{n-1}-1}{q-1}.$$

Type $Q$: Quadratic residues in the field $\operatorname{GF}(p^r)$ when $p^r\equiv3$ ($\bmod\,4$) ($p$ is a prime number). The parameters are:

$$v=p^r=4t-1,\quad k=2t-1,\quad\lambda=t-1.$$

For other infinite families of difference sets see [1][3]. Besides these difference sets, generalized difference sets are often considered. They are also called difference families and are sets $D_1,\dots,D_r$ consisting of residues $\bmod\,v$ such that for any $a\not\equiv0$ ($\bmod\,v$) there exist precisely $\lambda$ ordered pairs $(d_i,d_j)$, $d_i,d_j\in D_k$, with

$$a\equiv d_i-d_j\pmod v$$

for a certain $k$, $1\leq k\leq r$.

There are also other generalizations of difference sets.

References

[1] M. Hall, "Combinatorial theory" , Blaisdell (1967)
[2] L.D. Baumert, "Cyclic difference sets" , Springer (1971)
[3] M. Hall, "Difference sets" , Combinatorics. 3 Combinatorial group theory. Proc. NATO, Breukelen , Math. Centre Tracts , 57 , CWI (1974) pp. 1–26
How to Cite This Entry:
Difference set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Difference_set&oldid=14897
This article was adapted from an original article by V.E. Tarakanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article