Namespaces
Variants
Actions

Difference between revisions of "Symmetric design"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (links)
m (AUTOMATIC EDIT (latexlist): Replaced 62 formulas out of 62 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
 
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 62 formulas, 62 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|done}}
 
''symmetric block design''
 
''symmetric block design''
  
A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s1203301.png" />-design (or [[balanced incomplete block design]], BIBD) which satisfies [[Fisher inequality|Fisher's inequality]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s1203302.png" /> (cf. also [[Block design]]) with equality. More precisely, a symmetric <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s1203304.png" />-design is an incidence structure consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s1203305.png" /> points and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s1203306.png" /> blocks (cf. also [[Block design|Block design]]) of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s1203307.png" /> (that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s1203308.png" />-subsets of the point set), such that any two distinct points are on precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s1203309.png" /> common blocks. It can be shown that then also any two distinct blocks intersect in precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033010.png" /> points, see [[#References|[a1]]], § II.3.
+
A $2$-design (or [[balanced incomplete block design]], BIBD) which satisfies [[Fisher inequality|Fisher's inequality]] $b \geq v$ (cf. also [[Block design]]) with equality. More precisely, a symmetric $( v , k , \lambda )$-design is an incidence structure consisting of $v$ points and $b = v$ blocks (cf. also [[Block design|Block design]]) of size $k$ (that is, $k$-subsets of the point set), such that any two distinct points are on precisely $\lambda$ common blocks. It can be shown that then also any two distinct blocks intersect in precisely $\lambda$ points, see [[#References|[a1]]], § II.3.
  
The outstanding problem in this area (1998) is to characterize the possible parameter triples <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033011.png" />. A simple counting argument gives the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033012.png" />, which provides a trivial necessary existence condition. A non-trivial restriction is the Bruck–Ryser–Chowla theorem, see [[Block design|Block design]]. This condition is not sufficient, as the non-existence of a symmetric <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033013.png" />-design, i.e. a [[Projective plane|projective plane]] of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033014.png" />, shows; see [[#References|[a5]]].
+
The outstanding problem in this area (1998) is to characterize the possible parameter triples $( v , k , \lambda )$. A simple counting argument gives the equation $\lambda ( v - 1 ) = k ( k - 1 )$, which provides a trivial necessary existence condition. A non-trivial restriction is the Bruck–Ryser–Chowla theorem, see [[Block design|Block design]]. This condition is not sufficient, as the non-existence of a symmetric $( 111,11,1 )$-design, i.e. a [[Projective plane|projective plane]] of order $10$, shows; see [[#References|[a5]]].
  
There are more than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033015.png" /> known infinite series of symmetric designs (as of 1998). The most classical examples are the symmetric designs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033016.png" /> formed by the points and hyperplanes of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033017.png" />-dimensional finite projective space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033018.png" /> over the [[Galois field|Galois field]] of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033019.png" /> (so <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033020.png" /> is a prime power here) and the Hadamard <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033022.png" />-designs (or Hadamard configurations) with parameters of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033023.png" />; such a design is equivalent to a [[Hadamard matrix|Hadamard matrix]] of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033024.png" />, which is conjectured to exist for all values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033025.png" />. Similarly, a symmetric design with parameters of the form
+
There are more than $20$ known infinite series of symmetric designs (as of 1998). The most classical examples are the symmetric designs $P G _ { d -1} ( d , q )$ formed by the points and hyperplanes of the $d$-dimensional finite projective space $P G ( d , q )$ over the [[Galois field|Galois field]] of order $q$ (so $q$ is a prime power here) and the Hadamard $2$-designs (or Hadamard configurations) with parameters of the form $( 4 n - 1,2 n - 1 , n - 1 )$; such a design is equivalent to a [[Hadamard matrix|Hadamard matrix]] of order $4 n$, which is conjectured to exist for all values of $n$. Similarly, a symmetric design with parameters of the form
  
<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/s/s120/s120330/s12033026.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
\begin{equation} \tag{a1} ( 4 u ^ { 2 } , 2 u ^ { 2 } - u , u ^ { 2 } - u ) \end{equation}
  
is equivalent to a regular Hadamard matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033027.png" />, that is, a Hadamard matrix with constant row and column sums; these are conjectured to exist for all values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033028.png" />. Many examples are known, e.g. whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033029.png" /> is the product of a perfect square with an arbitrary number of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033030.png" />. An important recent (1998) construction method for symmetric designs which combines Abelian difference sets (cf. [[Abelian difference set]]; [[Difference set|Difference set]]; [[Difference set|Difference set]] (update)) with so-called balanced generalized weighing matrices yields seven infinite families; this is due to Y.J. Ionin [[#References|[a3]]]. See [[#References|[a1]]], [[#References|[a2]]] for lists of the known (1998) infinite series, tables of small symmetric designs and some constructions.
+
is equivalent to a regular Hadamard matrix of order $4 u ^ { 2 }$, that is, a Hadamard matrix with constant row and column sums; these are conjectured to exist for all values of $u$. Many examples are known, e.g. whenever $u$ is the product of a perfect square with an arbitrary number of the form $2 ^ { a } 3 ^ { b }$. An important recent (1998) construction method for symmetric designs which combines Abelian difference sets (cf. [[Abelian difference set]]; [[Difference set|Difference set]]; [[Difference set|Difference set]] (update)) with so-called balanced generalized weighing matrices yields seven infinite families; this is due to Y.J. Ionin [[#References|[a3]]]. See [[#References|[a1]]], [[#References|[a2]]] for lists of the known (1998) infinite series, tables of small symmetric designs and some constructions.
  
In general, a symmetric design cannot be characterized just by its parameters. For instance, the number of non-isomorphic designs with the same parameters as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033031.png" /> grows exponentially with a growth rate of at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033032.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033033.png" />. Hence it is desirable to characterize the designs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033034.png" /> as well as other particularly interesting designs. For instance, the Dembowski–Wagner theorem states that a symmetric design <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033035.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033036.png" /> in which every line (that is, the intersection of all blocks through two given points) meets every block is isomorphic to some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033037.png" />; the same conclusion holds if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033038.png" /> admits an automorphism group which is transitive on ordered triples of non-collinear points. See [[#References|[a1]]], § XII.2, for proofs and further characterizations.
+
In general, a symmetric design cannot be characterized just by its parameters. For instance, the number of non-isomorphic designs with the same parameters as $P G _ { d -1} ( d , q )$ grows exponentially with a growth rate of at least $e ^ { k .\operatorname { ln } k }$, where $k = q ^ { d - 1 } + \ldots + q + 1$. Hence it is desirable to characterize the designs $P G _ { d -1} ( d , q )$ as well as other particularly interesting designs. For instance, the Dembowski–Wagner theorem states that a symmetric design $\mathcal{D}$ with $\lambda &gt; 1$ in which every line (that is, the intersection of all blocks through two given points) meets every block is isomorphic to some $P G _ { d -1} ( d , q )$; the same conclusion holds if $\mathcal{D}$ admits an automorphism group which is transitive on ordered triples of non-collinear points. See [[#References|[a1]]], § XII.2, for proofs and further characterizations.
  
Symmetric designs with a  "nice"  automorphism group are of particular interest. The orbit theorem states that any automorphism group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033039.png" /> of a symmetric design <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033040.png" /> has equally many orbits on points and blocks (cf. also [[Orbit|Orbit]]). In particular, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033041.png" /> is transitive (cf. [[Transitive group]]) on points if and only if it is transitive on blocks. In this case, the permutation rank of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033042.png" /> on points agrees with that on blocks (cf. also [[Rank of a group|Rank of a group]]). In the special case where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033043.png" /> has rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033044.png" /> (and thus is doubly transitive on both points and blocks), a complete classification was given by W.M. Kantor [[#References|[a4]]]: There are two infinite series, namely the classical designs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033045.png" /> and another series which has parameters of the form (a1), where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033046.png" /> is a power of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033047.png" />; the latter examples all admit a [[symplectic group]] as automorphism group. In addition, there are two sporadic examples, namely the Hadamard <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033050.png" />-design on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033051.png" /> points and a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033052.png" />-design which admits the Higman–Sims group, one of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033053.png" /> sporadic simple groups (cf. also [[Sporadic simple group|Sporadic simple group]]). On the other end of the spectrum, there is the case of permutation rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033054.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033055.png" /> is regular (cf. [[Permutation group|Permutation group]]) on both points and blocks; such a group is called a Singer group of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033056.png" />, generalizing the notion of a Singer cycle. In this case, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033057.png" /> is equivalent to a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033058.png" />-difference set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033059.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033060.png" /> (cf. also [[Difference set|Difference set]]; [[Abelian difference set|Abelian difference set]]): Up to isomorphism, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033061.png" />. A complete classification is yet (1998) out of reach, even in the Abelian case. For instance, it is widely conjectured that a projective plane of finite order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033062.png" /> admitting a Singer group must be Desarguesian (cf. also [[Desargues geometry|Desargues geometry]]), at least in the cyclic case; but only for a few values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033063.png" />, this is actually proven. However, there is ample evidence for the validity of the weaker prime power conjecture, which asserts that the order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033064.png" /> of a finite projective plane admitting an Abelian Singer group must be a prime power; this is now known to hold whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033065.png" />. See [[#References|[a1]]], § VI.7, where this topic is studied in the language of planar difference sets.
+
Symmetric designs with a  "nice"  automorphism group are of particular interest. The orbit theorem states that any automorphism group $G$ of a symmetric design $\mathcal{D}$ has equally many orbits on points and blocks (cf. also [[Orbit|Orbit]]). In particular, $G$ is transitive (cf. [[Transitive group]]) on points if and only if it is transitive on blocks. In this case, the permutation rank of $G$ on points agrees with that on blocks (cf. also [[Rank of a group|Rank of a group]]). In the special case where $G$ has rank $2$ (and thus is doubly transitive on both points and blocks), a complete classification was given by W.M. Kantor [[#References|[a4]]]: There are two infinite series, namely the classical designs $P G _ { d -1} ( d , q )$ and another series which has parameters of the form (a1), where $u$ is a power of $2$; the latter examples all admit a [[symplectic group]] as automorphism group. In addition, there are two sporadic examples, namely the Hadamard $2$-design on $11$ points and a $( 176,50,14 )$-design which admits the Higman–Sims group, one of the $26$ sporadic simple groups (cf. also [[Sporadic simple group|Sporadic simple group]]). On the other end of the spectrum, there is the case of permutation rank $v$, i.e. $G$ is regular (cf. [[Permutation group|Permutation group]]) on both points and blocks; such a group is called a Singer group of $\mathcal{D}$, generalizing the notion of a Singer cycle. In this case, $\mathcal{D}$ is equivalent to a $( v , k , \lambda )$-difference set $\mathcal{D}$ in $G$ (cf. also [[Difference set|Difference set]]; [[Abelian difference set|Abelian difference set]]): Up to isomorphism, ${\cal D} = ( G , \{ D g : g \in G \} , \in )$. A complete classification is yet (1998) out of reach, even in the Abelian case. For instance, it is widely conjectured that a projective plane of finite order $n$ admitting a Singer group must be Desarguesian (cf. also [[Desargues geometry|Desargues geometry]]), at least in the cyclic case; but only for a few values of $\leq 100$, this is actually proven. However, there is ample evidence for the validity of the weaker prime power conjecture, which asserts that the order $n$ of a finite projective plane admitting an Abelian Singer group must be a prime power; this is now known to hold whenever $n \leq 2,000,000$. See [[#References|[a1]]], § VI.7, where this topic is studied in the language of planar difference sets.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  T. Beth,  D. Jungnickel,  H. Lenz,  "Design theory" , Cambridge Univ. Press  (1999)  (Edition: Second)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  C.J. Colbourn,  J.H. Dinitz,  "The CRC Handbook of combinatorial designs" , CRC  (1996)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  Y.J. Ionin,  "Building symmetric designs with building sets"  ''Designs, Codes and Cryptography'' , '''17'''  (1999)  pp. 159–175</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  W.M. Kantor,  "<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s12033066.png" />-transitive symmetric designs"  ''Graphs Combin.'' , '''1'''  (1985)  pp. 165–166</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  C.W.H. Lam,  L.H. Thiel,  S. Swiercz,  "The non-existence of finite projective planes of order 10"  ''Canad. J. Math.'' , '''41'''  (1989)  pp. 1117–1123</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  T. Beth,  D. Jungnickel,  H. Lenz,  "Design theory" , Cambridge Univ. Press  (1999)  (Edition: Second)</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  C.J. Colbourn,  J.H. Dinitz,  "The CRC Handbook of combinatorial designs" , CRC  (1996)</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  Y.J. Ionin,  "Building symmetric designs with building sets"  ''Designs, Codes and Cryptography'' , '''17'''  (1999)  pp. 159–175</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  W.M. Kantor,  "$2$-transitive symmetric designs"  ''Graphs Combin.'' , '''1'''  (1985)  pp. 165–166</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  C.W.H. Lam,  L.H. Thiel,  S. Swiercz,  "The non-existence of finite projective planes of order 10"  ''Canad. J. Math.'' , '''41'''  (1989)  pp. 1117–1123</td></tr></table>

Latest revision as of 16:45, 1 July 2020

symmetric block design

A $2$-design (or balanced incomplete block design, BIBD) which satisfies Fisher's inequality $b \geq v$ (cf. also Block design) with equality. More precisely, a symmetric $( v , k , \lambda )$-design is an incidence structure consisting of $v$ points and $b = v$ blocks (cf. also Block design) of size $k$ (that is, $k$-subsets of the point set), such that any two distinct points are on precisely $\lambda$ common blocks. It can be shown that then also any two distinct blocks intersect in precisely $\lambda$ points, see [a1], § II.3.

The outstanding problem in this area (1998) is to characterize the possible parameter triples $( v , k , \lambda )$. A simple counting argument gives the equation $\lambda ( v - 1 ) = k ( k - 1 )$, which provides a trivial necessary existence condition. A non-trivial restriction is the Bruck–Ryser–Chowla theorem, see Block design. This condition is not sufficient, as the non-existence of a symmetric $( 111,11,1 )$-design, i.e. a projective plane of order $10$, shows; see [a5].

There are more than $20$ known infinite series of symmetric designs (as of 1998). The most classical examples are the symmetric designs $P G _ { d -1} ( d , q )$ formed by the points and hyperplanes of the $d$-dimensional finite projective space $P G ( d , q )$ over the Galois field of order $q$ (so $q$ is a prime power here) and the Hadamard $2$-designs (or Hadamard configurations) with parameters of the form $( 4 n - 1,2 n - 1 , n - 1 )$; such a design is equivalent to a Hadamard matrix of order $4 n$, which is conjectured to exist for all values of $n$. Similarly, a symmetric design with parameters of the form

\begin{equation} \tag{a1} ( 4 u ^ { 2 } , 2 u ^ { 2 } - u , u ^ { 2 } - u ) \end{equation}

is equivalent to a regular Hadamard matrix of order $4 u ^ { 2 }$, that is, a Hadamard matrix with constant row and column sums; these are conjectured to exist for all values of $u$. Many examples are known, e.g. whenever $u$ is the product of a perfect square with an arbitrary number of the form $2 ^ { a } 3 ^ { b }$. An important recent (1998) construction method for symmetric designs which combines Abelian difference sets (cf. Abelian difference set; Difference set; Difference set (update)) with so-called balanced generalized weighing matrices yields seven infinite families; this is due to Y.J. Ionin [a3]. See [a1], [a2] for lists of the known (1998) infinite series, tables of small symmetric designs and some constructions.

In general, a symmetric design cannot be characterized just by its parameters. For instance, the number of non-isomorphic designs with the same parameters as $P G _ { d -1} ( d , q )$ grows exponentially with a growth rate of at least $e ^ { k .\operatorname { ln } k }$, where $k = q ^ { d - 1 } + \ldots + q + 1$. Hence it is desirable to characterize the designs $P G _ { d -1} ( d , q )$ as well as other particularly interesting designs. For instance, the Dembowski–Wagner theorem states that a symmetric design $\mathcal{D}$ with $\lambda > 1$ in which every line (that is, the intersection of all blocks through two given points) meets every block is isomorphic to some $P G _ { d -1} ( d , q )$; the same conclusion holds if $\mathcal{D}$ admits an automorphism group which is transitive on ordered triples of non-collinear points. See [a1], § XII.2, for proofs and further characterizations.

Symmetric designs with a "nice" automorphism group are of particular interest. The orbit theorem states that any automorphism group $G$ of a symmetric design $\mathcal{D}$ has equally many orbits on points and blocks (cf. also Orbit). In particular, $G$ is transitive (cf. Transitive group) on points if and only if it is transitive on blocks. In this case, the permutation rank of $G$ on points agrees with that on blocks (cf. also Rank of a group). In the special case where $G$ has rank $2$ (and thus is doubly transitive on both points and blocks), a complete classification was given by W.M. Kantor [a4]: There are two infinite series, namely the classical designs $P G _ { d -1} ( d , q )$ and another series which has parameters of the form (a1), where $u$ is a power of $2$; the latter examples all admit a symplectic group as automorphism group. In addition, there are two sporadic examples, namely the Hadamard $2$-design on $11$ points and a $( 176,50,14 )$-design which admits the Higman–Sims group, one of the $26$ sporadic simple groups (cf. also Sporadic simple group). On the other end of the spectrum, there is the case of permutation rank $v$, i.e. $G$ is regular (cf. Permutation group) on both points and blocks; such a group is called a Singer group of $\mathcal{D}$, generalizing the notion of a Singer cycle. In this case, $\mathcal{D}$ is equivalent to a $( v , k , \lambda )$-difference set $\mathcal{D}$ in $G$ (cf. also Difference set; Abelian difference set): Up to isomorphism, ${\cal D} = ( G , \{ D g : g \in G \} , \in )$. A complete classification is yet (1998) out of reach, even in the Abelian case. For instance, it is widely conjectured that a projective plane of finite order $n$ admitting a Singer group must be Desarguesian (cf. also Desargues geometry), at least in the cyclic case; but only for a few values of $\leq 100$, this is actually proven. However, there is ample evidence for the validity of the weaker prime power conjecture, which asserts that the order $n$ of a finite projective plane admitting an Abelian Singer group must be a prime power; this is now known to hold whenever $n \leq 2,000,000$. See [a1], § VI.7, where this topic is studied in the language of planar difference sets.

References

[a1] T. Beth, D. Jungnickel, H. Lenz, "Design theory" , Cambridge Univ. Press (1999) (Edition: Second)
[a2] C.J. Colbourn, J.H. Dinitz, "The CRC Handbook of combinatorial designs" , CRC (1996)
[a3] Y.J. Ionin, "Building symmetric designs with building sets" Designs, Codes and Cryptography , 17 (1999) pp. 159–175
[a4] W.M. Kantor, "$2$-transitive symmetric designs" Graphs Combin. , 1 (1985) pp. 165–166
[a5] C.W.H. Lam, L.H. Thiel, S. Swiercz, "The non-existence of finite projective planes of order 10" Canad. J. Math. , 41 (1989) pp. 1117–1123
How to Cite This Entry:
Symmetric design. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Symmetric_design&oldid=37362
This article was adapted from an original article by D. Jungnickel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article