Namespaces
Variants
Actions

Difference between revisions of "Symmetric design"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (links)
Line 1: Line 1:
 
''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's inequality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120330/s1203302.png" /> (cf. also [[Block design|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 <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.
  
 
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 <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]]].
Line 9: Line 9:
 
<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>
 
<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>
  
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|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 <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.
  
 
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 <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.
  
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|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|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 <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.
  
 
====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,  "<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>

Revision as of 19:35, 4 January 2016

symmetric block design

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

The outstanding problem in this area (1998) is to characterize the possible parameter triples . A simple counting argument gives the equation , 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 -design, i.e. a projective plane of order , shows; see [a5].

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

(a1)

is equivalent to a regular Hadamard matrix of order , that is, a Hadamard matrix with constant row and column sums; these are conjectured to exist for all values of . Many examples are known, e.g. whenever is the product of a perfect square with an arbitrary number of the form . 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 grows exponentially with a growth rate of at least , where . Hence it is desirable to characterize the designs as well as other particularly interesting designs. For instance, the Dembowski–Wagner theorem states that a symmetric design with in which every line (that is, the intersection of all blocks through two given points) meets every block is isomorphic to some ; the same conclusion holds if 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 of a symmetric design has equally many orbits on points and blocks (cf. also Orbit). In particular, is transitive (cf. Transitive group) on points if and only if it is transitive on blocks. In this case, the permutation rank of on points agrees with that on blocks (cf. also Rank of a group). In the special case where has rank (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 and another series which has parameters of the form (a1), where is a power of ; the latter examples all admit a symplectic group as automorphism group. In addition, there are two sporadic examples, namely the Hadamard -design on points and a -design which admits the Higman–Sims group, one of the sporadic simple groups (cf. also Sporadic simple group). On the other end of the spectrum, there is the case of permutation rank , i.e. is regular (cf. Permutation group) on both points and blocks; such a group is called a Singer group of , generalizing the notion of a Singer cycle. In this case, is equivalent to a -difference set in (cf. also Difference set; Abelian difference set): Up to isomorphism, . 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 admitting a Singer group must be Desarguesian (cf. also Desargues geometry), at least in the cyclic case; but only for a few values of , this is actually proven. However, there is ample evidence for the validity of the weaker prime power conjecture, which asserts that the order of a finite projective plane admitting an Abelian Singer group must be a prime power; this is now known to hold whenever . 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, "-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