Difference set

For the set of elements in one set but not another, see Relative complement. For the set of differences of pairs of elements, see Minkowski difference.

In combinatorics, a $(v,k,\lambda )$ difference set is a subset $D$ of size $k$ of a group $G$ of order $v$ such that every non-identity element of $G$ can be expressed as a product $d_{1}d_{2}^{-1}$ of elements of $D$ in exactly $\lambda$ ways. A difference set $D$ is said to be cyclic, abelian, non-abelian, etc., if the group $G$ has the corresponding property. A difference set with $\lambda =1$ is sometimes called planar or simple. If $G$ is an abelian group written in additive notation, the defining condition is that every non-zero element of $G$ can be written as a difference of elements of $D$ in exactly $\lambda$ ways. The term "difference set" arises in this way.

Basic facts

• A simple counting argument shows that there are exactly $k^{2}-k$ pairs of elements from $D$ that will yield nonidentity elements, so every difference set must satisfy the equation $k^{2}-k=(v-1)\lambda .$
• The parameter $n=k-\lambda$ is called the order of the difference set.
• If $D$ is a difference set and $g\in G,$ then $gD=\{gd:d\in D\}$ is also a difference set, and is called a translate of $D$ ($D+g$ in additive notation).
• The complement of a $(v,k,\lambda )$-difference set is a $(v,v-k,v-2k+\lambda )$-difference set.
• The set of all translates of a difference set $D$ forms a symmetric block design, called the development of $D$ and denoted by $dev(D).$ In such a design there are $v$ elements (usually called points) and $v$ blocks (subsets). Each block of the design consists of $k$ points, each point is contained in $k$ blocks. Any two blocks have exactly $\lambda$ elements in common and any two points are simultaneously contained in exactly $\lambda$ blocks. The group $G$ acts as an automorphism group of the design. It is sharply transitive on both points and blocks.
  • In particular, if $\lambda =1$, then the difference set gives rise to a projective plane. An example of a (7,3,1) difference set in the group $\mathbb {Z} /7\mathbb {Z}$ is the subset $\{1,2,4\}$. The translates of this difference set form the Fano plane.
• Since every difference set gives a symmetric design, the parameter set must satisfy the Bruck–Ryser–Chowla theorem.
• Not every symmetric design gives a difference set.

Equivalent and isomorphic difference sets

Two difference sets $D_{1}$ in group $G_{1}$ and $D_{2}$ in group $G_{2}$ are equivalent if there is a group isomorphism $\psi$ between $G_{1}$ and $G_{2}$ such that $D_{1}^{\psi }=\{d^{\psi }\colon d\in D_{1}\}=gD_{2}$ for some $g\in G_{2}.$ The two difference sets are isomorphic if the designs $dev(D_{1})$ and $dev(D_{2})$ are isomorphic as block designs.

Equivalent difference sets are isomorphic, but there exist examples of isomorphic difference sets which are not equivalent. In the cyclic difference set case, all known isomorphic difference sets are equivalent.

Multipliers

A multiplier of a difference set $D$ in group $G$ is a group automorphism $\phi$ of $G$ such that $D^{\phi }=gD$ for some $g\in G.$ If $G$ is abelian and $\phi$ is the automorphism that maps $h\mapsto h^{t}$, then $t$ is called a numerical or Hall multiplier.

The multiplier conjecture predicts, in particular, that if p is a prime dividing $k-\lambda$ and not dividing v, then the automorphism $g\mapsto g^{p}$ is a multiplier. This is known when $p>\lambda$ and $G$ is abelian, a result called the First Multiplier Theorem. A more general result, the Second Multiplier Theorem, says that if $D$ is a $(v,k,\lambda )$-difference set in an abelian group $G$ of exponent $v^{*}$ (the least common multiple of the orders of its elements), and $t$ is an integer coprime to $v$, then the following condition is sufficient for $t$ to be a numerical multiplier: there is a divisor $m$ of $k-\lambda$ with $\gcd(m,v)=1$ and $m>\lambda$ such that, for every prime p dividing m, there is an integer i with $t\equiv p^{i}{\pmod {v^{*}}}$. Later work showed that the assumption $m>\lambda$ can be replaced by a weaker divisibility condition, but the full multiplier conjecture remains open.

For example, 2 is a multiplier of the (7,3,1)-difference set mentioned above.

It has been mentioned that a numerical multiplier of a difference set $D$ in an abelian group $G$ fixes a translate of $D$, but it can also be shown that there is a translate of $D$ which is fixed by all numerical multipliers of $D.$

Ryser and Lander conjectures

Unsolved problem in mathematics

If an abelian group of order $v$ contains a difference set of order $n$, and a prime $p$ divides both $v$ and $n$, must the Sylow $p$-subgroup of the group be non-cyclic?

More unsolved problems in mathematics

In terms of the order $n=k-\lambda$, Ryser's cyclic difference-set conjecture states that a difference set in a cyclic group must satisfy $\gcd(v,n)=1$. For a Menon–Hadamard difference set with parameters $(4u^{2},2u^{2}-u,u^{2}-u)$, the order is $u^{2}$; consequently, the circulant Hadamard conjecture is a special case.

Lander's conjecture, proposed by Eric S. Lander in 1983, strengthens Ryser's conjecture. It states that if an abelian group $G$ of order $v$ contains a difference set of order $n$, and a prime $p$ divides both $v$ and $n$, then the Sylow $p$-subgroup of $G$ is not cyclic. Since every Sylow subgroup of a cyclic group is cyclic, Lander's conjecture implies Ryser's cyclic difference-set conjecture.

Lander's conjecture is unresolved in general. It has been proved when the order of the difference set is a power of a prime greater than 3, and for all difference sets in the McFarland, Spence, and Davis–Jedwab–Chen families. If the order is a power of 2 or 3 and the relevant Sylow subgroup is cyclic, then that subgroup must have order 2 or 3, respectively, and the parameters are restricted to a small number of exceptional forms. The conjecture is also known for all Hadamard difference sets of order at most 529.

Explicit small open cases are known. Baumert and Gordon settled the existence of cyclic $(v,k,\lambda )$-difference sets for all $k\leq 150$ except two parameter sets, and tabulated the undecided cases with $150<k\leq 300$. The smallest undecided cyclic parameter set with $\gcd(v,n)>1$ is $(465,145,45)$, of order $n=100$; here 5 divides both $v$ and $n$, so Ryser's conjecture, and hence Lander's, predicts that no such difference set exists.

Parameters

Some important infinite parameter families, considered up to complementation, are:

• $((q^{n+2}-1)/(q-1),(q^{n+1}-1)/(q-1),(q^{n}-1)/(q-1))$-difference set for some prime power $q$ and some positive integer $n$. These are known as the classical parameters and there are many constructions of difference sets having these parameters.
• $(4n-1,2n-1,n-1)$-difference set for some positive integer $n$. Difference sets with v = 4n − 1 are called Paley-type difference sets.
• $(4n^{2},2n^{2}-n,n^{2}-n)$-difference set for some positive integer $n$. A difference set with these parameters is called a Hadamard difference set or Menon difference set. The existence of such a difference set in a cyclic group is the subject of Ryser's conjecture on circulant Hadamard matrices, a well-known open problem.
• $(q^{n+1}(1+(q^{n+1}-1)/(q-1)),q^{n}(q^{n+1}-1)/(q-1),q^{n}(q^{n}-1)/(q-1))$-difference set for some prime power $q$ and some positive integer $n$. Known as the McFarland parameters.
• $(3^{n+1}(3^{n+1}-1)/2,3^{n}(3^{n+1}+1)/2,3^{n}(3^{n}+1)/2)$-difference set for some positive integer $n$. Known as the Spence parameters.
• $(4q^{2n}(q^{2n}-1)/(q-1),q^{2n-1}(1+2(q^{2n}-1)/(q+1)),q^{2n-1}(q^{2n-1}+1)(q-1)/(q+1))$-difference set for some prime power $q$ and some positive integer $n$. Difference sets with these parameters are called Davis–Jedwab–Chen difference sets.

Selected constructions

In many constructions of difference sets, the groups that are used are related to the additive and multiplicative groups of finite fields. The notation used to denote these fields differs according to discipline. In this section, ${\rm {GF}}(q)$ is the Galois field of order $q,$ where $q$ is a prime power. The group under addition is denoted by $G=({\rm {GF}}(q),+)$, while ${\rm {GF}}(q)^{*}$ is the multiplicative group of non-zero elements.

• Paley $(4n-1,2n-1,n-1)$-difference set:

Let $q=4n-1$ be a prime power. In the group $G=({\rm {GF}}(q),+)$, let $D$ be the set of all non-zero squares.

• Singer $((q^{n+2}-1)/(q-1),(q^{n+1}-1)/(q-1),(q^{n}-1)/(q-1))$-difference set:

Let $G={\rm {GF}}(q^{n+2})^{*}/{\rm {GF}}(q)^{*}$. Then the set $D=\{x\in G~|~{\rm {Tr}}_{q^{n+2}/q}(x)=0\}$ is a $((q^{n+2}-1)/(q-1),(q^{n+1}-1)/(q-1),(q^{n}-1)/(q-1))$-difference set, where ${\rm {Tr}}_{q^{n+2}/q}:{\rm {GF}}(q^{n+2})\rightarrow {\rm {GF}}(q)$ is the trace function ${\rm {{Tr}_{q^{n+2}/q}(x)=x+x^{q}+\cdots +x^{q^{n+1}}.}}$

• Twin prime power $\left(q^{2}+2q,{\frac {q^{2}+2q-1}{2}},{\frac {q^{2}+2q-3}{4}}\right)$-difference set when $q$ and $q+2$ are both prime powers:

In the group $G=({\rm {GF}}(q),+)\oplus ({\rm {GF}}(q+2),+)$, let $D=\{(x,y)\colon y=0{\text{ or }}x{\text{ and }}y{\text{ are non-zero and both are squares or both are non-squares}}\}.$

History

The systematic use of cyclic difference sets and methods for the construction of symmetric block designs dates back to R. C. Bose and a seminal paper of his in 1939. However, various examples appeared earlier than this, such as the "Paley Difference Sets" which date back to 1933. The generalization of the cyclic difference set concept to more general groups is due to R.H. Bruck in 1955. Multipliers were introduced by Marshall Hall Jr. in 1947.

Application

Xia, Zhou and Giannakis used difference sets to construct complex vector codebooks that attain the Welch lower bound on maximum cross-correlation amplitude in certain cases.

Generalisations

A $(v,k,\lambda ,s)$ difference family is a set of subsets $B=\{B_{1},\ldots ,B_{s}\}$ of a group $G$ such that the order of $G$ is $v$, the size of $B_{i}$ is $k$ for all $i$, and every non-identity element of $G$ can be expressed as a product $d_{1}d_{2}^{-1}$ of elements of $B_{i}$ for some $i$ (i.e. both $d_{1},d_{2}$ come from the same $B_{i}$) in exactly $\lambda$ ways.

A difference set is a difference family with $s=1.$ The parameter equation above generalises to $s(k^{2}-k)=(v-1)\lambda .$ The development $dev(B)=\{B_{i}+g:i=1,\ldots ,s,g\in G\}$ of a difference family is a 2-design. Every 2-design with a regular automorphism group is $dev(B)$ for some difference family $B.$

See also

• Combinatorial design
• Ryser's conjecture on circulant Hadamard matrices

References

• Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1986), Design Theory, Cambridge: Cambridge University Press, ISBN 0-521-33334-2, Zbl 0602.05001
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs, Discrete Mathematics and its Applications (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 978-1-58488-506-1, Zbl 1101.05001
• van Lint, J.H.; Wilson, R.M. (1992), A Course in Combinatorics, Cambridge: Cambridge University Press, ISBN 0-521-42260-4, Zbl 0769.05001
• Wallis, W.D. (1988). Combinatorial Designs. Marcel Dekker. ISBN 0-8247-7942-8. Zbl 0637.05004.

Further reading

• Moore, EH; Pollastek, HSK (2013). Difference Sets: Connecting Algebra, Combinatorics, and Geometry. AMS. ISBN 978-0-8218-9176-6.
• Storer, Thomas (1967). Cyclotomy and difference sets. Chicago: Markham Publishing Company. Zbl 0157.03301.
• Xia, Pengfei; Zhou, Shengli; Giannakis, Georgios B. (2005). "Achieving the Welch Bound with Difference Sets" (PDF). IEEE Transactions on Information Theory. 51 (5): 1900–1907. doi:10.1109/TIT.2005.846411. ISSN 0018-9448. S2CID 8916926. Zbl 1237.94007..

Xia, Pengfei; Zhou, Shengli; Giannakis, Georgios B. (2006). "Correction to Achieving the Welch bound with difference sets". IEEE Trans. Inf. Theory. 52 (7): 3359. doi:10.1109/tit.2006.876214. Zbl 1237.94008.

• Zwillinger, Daniel (2003). CRC Standard Mathematical Tables and Formulae. CRC Press. p. 246. ISBN 1-58488-291-3.