Symmetric design

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