Symmetrical block plan

A symmetrical block plan (also called symmetrical block design ) is a block plan in finite geometry and combinatorics and thus a finite incidence structure in which the number of blocks is equal to the number of points . Symmetrical block plans are used, for example, in the planning of experiments or for the construction of codes . A symmetrical block diagram can be represented by a square (v × v) matrix that is filled with zeros and ones in such a way that the following two conditions are met:

• The number k of ones is the same in every row and column.
• Every two rows and two columns have a number λ of ones in common.

The rows of this matrix designate the blocks and the columns the points of the underlying incidence structure.

Although their properties are easy to understand, such symmetrical block diagrams cannot be constructed arbitrarily and only exist for certain combinations of the parameters v, k and λ. The existence of many symmetrical block plans has therefore not yet been clarified. The proof of the non-existence of a certain symmetrical block plan (the projective level of order 10 or the symmetrical (111,11,1) block plan) with the help of computer evidence therefore attracted great interest in 1991.

Definitions

Let B be a 2- (v, k, λ) block diagram. Furthermore, these conditions are met for B:

• B contains exactly v blocks
• B contains exactly v points
• every point of B lies on exactly k blocks
• each block of B goes through exactly k points
• every two different blocks of B intersect in exactly λ points
• two different points of B are connected by exactly λ blocks

Then B is referred to as a symmetrical 2- (v, k, λ) block plan or also as a (v, k, λ) block plan for short .

The order n of a symmetric (v, k, λ) block diagram is the difference n = k - λ.

A non-empty point set of a symmetrical block diagram with the property that no three points of this set are contained in a block is called an oval . Associated with this is a disjoint subdivision of the blocks of the block plan into:

• Secants (blocks containing exactly two points of the oval)
• Tangents (blocks that contain exactly one point of the oval)
• Passers-by (blocks that do not contain any points in the oval)

The number of points in an oval is called the order of the oval.

illustration

By definition, the (v, k, λ) block plan can be represented by an incidence matrix with v rows and v columns, which contains exactly k ones in each row and in each column (the remaining entries are zeros) and in which the scalar product of each two rows as well as that of two columns is exactly λ (ie every two rows or every two columns have a one in common at exactly λ positions). Here is z. B. a clear representation of the incidence matrix of the (7,3,1) block plan , where the ones are represented by circles and the zeros by dots in order to better recognize the structure:

O O O . . . .  ← diese Zeile repräsentiert den ersten Block. Er enthält die Punkte 1, 2 und 3
O . . O O . .
O . . . . O O
. O . O . O .  ← diese Zeile repräsentiert den vierten Block. Er enthält die Punkte 2, 4 und 6
. O . . O . O  ← diese Zeile repräsentiert den fünften Block. Er schneidet den vierten Block im Punkt 2
. . O O . . O
. . O . O O .
  ↑       ↑
  ↑       Diese Spalte repräsentiert den Punkt 6. Er liegt auf den Blöcken 3, 4 und 7 
  ↑
  Diese Spalte repräsentiert den Punkt 2. Er ist mit dem Punkt 6 durch den Block 4 verbunden 

Alternatively, the block diagram can also be displayed by listing its blocks, whereby the points contained in it are written down in one line for each block. Here again the example for the (7,3,1) block plan :

  1   2   3  ← diese Zeile repräsentiert den ersten Block. Er enthält die Punkte 1, 2 und 3
  1   4   5
  1   6   7
  2   4   6  ← diese Zeile repräsentiert den vierten Block. Er enthält die Punkte 2, 4 und 6
  2   5   7  ← diese Zeile repräsentiert den fünften Block. Er schneidet den vierten Block im Punkt 2
  3   4   7
  3   5   6

Conditions of existence

A central question is which symmetrical (v, k, λ) block plans actually exist. There are a number of necessary criteria for the existence of block plans, with which one can exclude many parameter combinations. Such criteria are provided, for example, by the generalized Fisher inequality (also called the Ray-Chaudhuri-Wilson theorem ) and the Bruck-Ryser-Chowla theorem . Two necessary conditions for the existence of a (v, k, λ) block plan that are easy to check are:

• ${\displaystyle \lambda \cdot (v-1)=k\cdot (k-1)}$, as derived in the article block plan
• k - λ is a square number if v is even ( Schützenberger's theorem ; also applies according to the Bruck-Ryser-Chowla theorem )

If a triple of parameters v, k, λ does not meet even one of these conditions, then there is no (v, k, λ) block diagram. On the other hand, these conditions are not sufficient: even if they are met, the (v, k, λ) block plan need not exist.

Classification

The symmetrical block plans can be divided into categories based on their parameters v, k, λ. The four most important are listed below:

Projective plane

→ Main article : Projective plane

All symmetrical block plans with are called projective planes . Your parameters are ${\displaystyle \lambda =1}$

${\displaystyle (v,k,\lambda )=\left(n^{2}+n+1,n+1,1\right)}$,

with as order of the projective plane. If this order is a prime number or a power of a prime number, the associated projective level with this order also exists. In no other case, however, is the existence of a projective plane known up to now. The existence of the two smallest cases of this kind (n = 2 · 3 and n = 2 · 5) has already been refuted. There is thus neither a (43,7,1) block plan (this would be the projective level of order 6) nor a (111,11,1) block plan (this would be the projective level of order 10, which has been sought in vain for a long time). The smallest order for which the existence of a projective plane has not yet been clarified is n = 12; the associated block diagram has the parameters (157,13,1). ${\displaystyle n}$ ${\displaystyle n}$

Biplane

All symmetrical block plans with hot biplanes , their parameters are ${\displaystyle \lambda =2}$

${\displaystyle (v,k,\lambda )=\left({\frac {n^{2}+3n+4}{2}},n+2,2\right)}$,

with as order of the biplane. So far only biplanes of order n = 3, 4, 7, 9 and 11 are known. ${\displaystyle n}$

Triplane

All symmetrical block plans with hot triplanes . You have the parameters ${\displaystyle \lambda =3}$

${\displaystyle (v,k,\lambda )=\left({\frac {n^{2}+5n+9}{3}},n+3,3\right)}$,

with the order of the triplane. So far only triplanes of order n = 4, 6, 7, 9 and 12 are known. ${\displaystyle n}$

Hadamard block plan

Every symmetrical block diagram is called a Hadamard block diagram (more precisely: Hadamard 2 block diagram ). The name comes from the fact that every normalized - Hadamard matrix can be assigned such a block diagram and vice versa. The first row and the first column of the Hadamard matrix H , which only contain entries 1 due to normalization, are deleted. The remaining matrix (with the entries 1 or −1) is used as the incidence structure of the Hadamard block diagram (by interpreting the entries −1 as 0). ${\displaystyle 2{\text{-}}(4n-1,2n-1,n-1)}$ ${\displaystyle 4n\times 4n}$ ${\displaystyle (n\geq 2)}$

All Hadamard 2 block plans are symmetrical block plans. They can be expanded into Hadamard 3 block plans (however, these no longer belong to the symmetrical block plans). The following applies:

Every Hadamard block plan can be expanded into a block plan . The extension looks like this: You agree with an additional point as a new point set and as a new block set for . Then is the 3 block plan. Apart from isomorphism, this extension is the only possible extension for the Hadamard 2 block plan , so that for a point x in the point set of applies and is a 3 block plan. is the derivative of at point x . Each block plan has a Hadamard 2 block plan as a derivation at each point. A 3-block plan is only highly resolvable if it is a Hadamard 3-block plan. ${\displaystyle 2{\text{-}}(4n-1,2n-1,n-1)}$ ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},\in )}$ ${\displaystyle 3{\text{-}}(4n,2n,n-1)}$ ${\displaystyle {\mathcal {E}}}$ ${\displaystyle {\mathfrak {p}}'={\mathfrak {p}}\cup \{\infty \}}$ ${\displaystyle \infty \not \in {\mathfrak {p}}}$ ${\displaystyle {\mathfrak {B}}'=\{X\cup \{\infty \}|X\in {\mathfrak {B}}\}\cup \{{\mathfrak {p}}\setminus X|X\in {\mathfrak {B}}\}}$ ${\displaystyle {\mathcal {E}}}$ ${\displaystyle {\mathcal {E}}=({\mathfrak {p}}',{\mathfrak {B}}',\in )}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {I}}={\mathcal {E}}_{x}}$ ${\displaystyle {\mathcal {E}}}$ ${\displaystyle {\mathcal {E}}}$ ${\displaystyle {\mathcal {E}}_{x}}$ ${\displaystyle {\mathcal {E}}}$ ${\displaystyle 3{\text{-}}(4n,2n,n-1)}$ ${\displaystyle {\mathcal {E}}}$ ${\displaystyle n\geq 2}$

Overview of the smallest symmetrical block plans

The following table lists the block plans according to λ and according to n - λ. Due to the delimitation n - λ> = 1, a limitation is ostensibly made here. However, it is equivalent to k <= v / 2, which means that each block may contain at most half of all points. The complementary block plans (k> v / 2) are not listed here. They arise from the block diagrams listed here by swapping 0 and 1 in the incidence matrices, their parameters are (v, vk, v-2k + λ).

If the necessary condition λ (v-1) = k (k-1) and the Bruck-Ryser-Chowla theorem are met, the corresponding table element contains the designation (v, k, λ) of the block plan, otherwise the corresponding cell remains empty because in this case no block plan can exist. Green colored cells mean that the corresponding block plan exists and link to the explicit representation of the block plan. Cells colored red mean that the corresponding block diagram does not exist. In the case of cells stained yellow, the existence of the block diagram is still uncertain.

In the row λ = 1 are the projective planes, in the row λ = 2 the biplanes, in the row λ = 3 the triplanes and in the column n - λ = 1 the Hadamard block plans. The smallest Hadamard block plan with the parameters (7,3,1) is also the projective plane of order 2, the next one with the parameters (11,5,2) is also the biplane of order 3 and the (15.7, 3) - Hadamard block plan is also the triplane of order 4.

	n - λ 1	2	3	4th	5	6th	7th	8th	9	10	11	12	13	14th	15th	16
λ 1	(7.3.1)	(13.4.1)	(21.5.1)	(31.6.1)	(43.7.1)	(57.8.1)	(73.9.1)	(91,10,1)	(111.11.1)	(133.12.1)	(157.13.1)	(183.14.1)	(211.15.1)	(241,16,1)	(273.17.1)	(307,18,1)
2	(11.5.2)	(16.6.2)		(29.8.2)	(37.9.2)		(56.11.2)	(67.12.2)	(79,13,2)			(121,16,2)	(137.17.2)	(154.18.2)		(191,20,2)
3	(15.7.3)		(25.9.3)	(31,10,3)		(45.12.3)			(71.15.3)	(81,16,3)			(115,19,3)			(155,22,3)
4th	(19,9,4)				(40,13,4)			(61,16,4)	(69.17.4)			(96,20,4)				(139,24,4)
5	(23.11.5)					(49,16,5)					(85.21.5)				(121.25.5)	(131.26.5)
6th	(27,13,6)		(36.15.6)	(41,16,6)					(71,21,6)	(78.22.6)			(101.25.6)			(127.28.6)
7th	(31.15.7)													(109.28.7)
8th	(35.17.8)							(70.24.8)
9	(39.19.9)								(79.27.9)	(85.28.9)
10	(43,21,10)				(61.25.10)	(66,26,10)									(120,35,10)	(127,36,10)
11	(47,23,11)										(97,33,11)	(103,34,11)
12	(51.25.12)			(64,28,12)									(112,37,12)			(131,40,12)
13	(55,27,13)													(121,40,13)
14th	(59,29,14)
15th	(63,31,15)					(85,36,15)				(105,40,15)						(139,46,15)
16	(67,33,16)

Characterization of symmetrical block plans

If there are several non-isomorphic solutions for a symmetric (v, k, λ) block plan , the question arises as to how they can be distinguished from one another. One possibility is to search for special properties of the block plan, which are invariant under isomorphism. This means that this property is retained after any row or column permutations have been carried out on the incidence matrix of the block diagram. If two block plans differ in this regard, they are non-isomorphic solutions. The reverse, however, does not apply: two block diagrams that do not differ in this property may or may not be isomorphic.

Ovals

The number of ovals of maximum order in a block diagram is such an invariant. If two solutions of a block plan have a different number of ovals of the same order or if one block plan has ovals of a larger order than the other, these block plans are non-isomorphic.

Example : There are exactly three non-isomorphic solutions of the (16,6,2) block plan . All three have ovals of the order 4, but in different numbers:

• Solution 1 contains 60 ovals of the 4th order
• Solution 2 contains 28 ovals of order 4
• Solution 3 contains 12 ovals of order 4

Thus these three solutions are pairwise non-isomorphic.

λ-chains

For biplanes (symmetrical block plans with λ = 2), λ-chains can be used as a distinguishing feature.

You choose a block of the biplane and call it an index block. Every other block of the biplane can be identified by the pair of points which this block has in common with the index block. Now every point P of the biplane which is not on the index block corresponds to a permutation of the points of the index block. In this permutation, two points are adjacent if and only if a block containing the point P is characterized by precisely this pair of points. The resulting permutation cycles are called λ-chains. This calculation is carried out for each index block and each point not incident with it and the resulting cycle lengths are counted. The λ-chains are shown in the form with the numbers and the cycle lengths . ${\displaystyle a_{1}\cdot l_{1},a_{2}\cdot l_{2},\dotsc }$ ${\displaystyle a_{1},a_{2},\dotsc }$ ${\displaystyle l_{1},l_{2},\dotsc }$

Example : In this (16,6,2) block plan , a block is marked as an index block and each point is marked '9'. The composite identification point pairs result in the cycle (2,7,12,6,15,8). This λ-chain thus has the length 6.

blocks							Labelling
1	2	3	5	10	15th		2	15th
2	3	4th	6th	11	16		2	6th
3	4th	5	7th	9	12		7th	12
4th	5	6th	8th	10	13		6th	8th
1	5	6th	7th	11	14th		6th	7th
2	6th	7th	8th	12	15th	Index block
1	3	7th	8th	13	16		7th	8th
1	2	4th	8th	9	14th		2	8th
2	7th	9	10	11	13		2	7th
3	8th	10	11	12	14th		8th	12
1	4th	11	12	13	15th		12	15th
2	5	12	13	14th	16		2	12
3	6th	9	13	14th	15th		6th	15th
4th	7th	10	14th	15th	16		7th	15th
5	8th	9	11	15th	16		8th	15th
1	6th	9	10	12	16		6th	12

The three non-isomorphic solutions of the (16,6,2) block plan have these λ-chains:

• Solution 1 has the λ-chains 320 * 3 (i.e. 320 λ-chains of length 3)
• Solution 2 has the λ-chains 192 * 3, 64 * 6 (i.e. 192 λ-chains of length 3 and 64 λ-chains of length 6)
• Solution 3 has the λ-chains 128 * 3, 96 * 6 (i.e. 128 λ-chains of length 3 and 96 λ-chains of length 6)

Thus these three solutions are pairwise non-isomorphic.

signature

In many cases, a very effective differentiation aid is the creation of a signature. For this purpose, four different blocks are marked: an index block and three further blocks . Let be the number of all points which are incised with more than one of the 4 blocks. Let the frequency of the smallest when iterates through all possible combinations. If the index block now also runs through all possibilities, the signature is displayed in the form with the numbers and the determined ones. ${\displaystyle I}$ ${\displaystyle A,B,C}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle A,B,C}$ ${\displaystyle {\tbinom {v-1}{3}}}$ ${\displaystyle I}$ ${\displaystyle v}$ ${\displaystyle a_{1}\cdot q_{1},a_{2}\cdot q_{2},\dotsc }$ ${\displaystyle a_{1},a_{2},\dotsc }$ ${\displaystyle q_{1},q_{2},\dotsc }$

If it is necessary for a clear distinction , the next larger value is included in the creation of the signature in addition to the smallest . Then it is represented in the form . ${\displaystyle p}$ ${\displaystyle a_{1}\cdot q_{1a}/q_{1b},\dotsc }$

Example : In this (16,6,2) block plan , an index block and three blocks are marked: ${\displaystyle I}$ ${\displaystyle A,B,C}$

blocks
1	2	3	5	10	15th
2	3	4th	6th	11	16	Block A
3	4th	5	7th	9	12
4th	5	6th	8th	10	13
1	5	6th	7th	11	14th
2	6th	7th	8th	12	15th	Index block I
1	3	7th	8th	13	16
1	2	4th	8th	9	14th
2	7th	9	10	11	13
3	8th	10	11	12	14th
1	4th	11	12	13	15th	Block B
2	5	12	13	14th	16	Block C
3	6th	9	13	14th	15th
4th	7th	10	14th	15th	16
5	8th	9	11	15th	16
1	6th	9	10	12	16

In this constellation, the points 2, 4, 6, 11, 12, 13, 15 and 16 occur in more than one of the four blocks. So here = 8. If you run through all possible combinations with the blocks , you get the following frequencies: 12 * 4, 32 * 6, 60 * 7, 312 * 8, 32 * 10, 7 * 12. This means = 12. If you now run the index block over all 16 blocks, you get the same value for each time in this example and the signature is therefore 16 * 12. ${\displaystyle p}$ ${\displaystyle A,B,C}$ ${\displaystyle {\tbinom {15}{3}}}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle q}$

The three non-isomorphic solutions of the (16,6,2) block plan have these signatures:

• Solution 1 has the signature 16 * 20
• Solution 2 has the signature 16 * 12
• Solution 3 has the signature 16 * 8

Thus these three solutions are pairwise non-isomorphic.

literature

• Thomas Beth , Dieter Jungnickel , Hanfried Lenz : Design Theory . 2nd Edition. BI Wissenschaftsverlag, London / New York / New Rochelle / Melbourne / Sidney 1999, ISBN 0-521-33334-2 (first edition: 1986).
• Albrecht Beutelspacher : Introduction to Finite Geometry . I. Block plans. BI Wissenschaftsverlag, Mannheim / Vienna / Zurich 1982, ISBN 3-411-01632-9 .

References and comments

1. ↑ Beutelspacher, p. 43
2. ^ Clement WH Lam : The Search for a Finite Projective Plane of Order 10 . In: The American Mathematical Monthly , vol. 98, 1991, pp. 305-318
3. ↑ Beth, Jungnickel, Lenz: 2.3
4. ↑ Beth, Jungnickel, Lenz (1986, 1999), Appendex-Table B.
5. ^ Sanja Rukavina: Some new triplanes of order twelve. Glass. Mat. Vol 36 (2001) 105-125
6. ↑ Beth, Jungnickel, Lenz (1986, 1999), I.9 Hadamard designs
7. ↑ Beth, Jungnickel, Lenz (1986, 1999), Lemma I.9.3
8. ↑ Beth, Jungnickel, Lenz (1986, 1999), Theorem I.9.9
9. ↑ The blocks of can be understood as sets of points, since Hadamard block plans are simple . ${\displaystyle {\mathcal {I}}}$
10. ↑ Beth, Jungnickel, Lenz (1986, 1999), Theorem II.8.10, Corollary II.8.11
11. ↑ Chester J. Salwach, Joseph A. Mezzaroba: The four known biplanes with k = 11 . In: Internat. J. Math. & Math. Sci. , Vol. 2 No. 2, 1979, p. 253