Namespaces
Variants
Actions

Difference between revisions of "Net in finite geometry"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (Ivan moved page Net in finite geometry(2) to Net in finite geometry: no need for (2))
m (AUTOMATIC EDIT (latexlist): Replaced 48 formulas out of 48 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 48 formulas, 48 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|done}}
 
''(update)''
 
''(update)''
  
In the language of design theory (cf. [[Block design|Block design]] and the links given there), a net of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n1300501.png" />, degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n1300502.png" /> and index <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n1300503.png" /> (for short, an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n1300505.png" />-net) is the same as an affine resolvable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n1300506.png" />-design (see [[Tactical configuration|Tactical configuration]]; [[Affine design|Affine design]]). Thus, it is an incidence structure <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n1300507.png" /> for which the set of blocks <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n1300508.png" /> is partitioned into parallel classes each of which in turn partitions the point set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n1300509.png" />, and such that any two non-parallel blocks intersect in exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005010.png" /> points. Moreover, there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005011.png" /> parallel classes each consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005012.png" /> blocks; then each block has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005013.png" /> points. The dual of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005014.png" />-net is called a transversal design (denoted a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005015.png" />); in this setting, the parallel classes of blocks of a net become the point classes of the transversal design. In a more combinatorial language, a net is also equivalent to an [[Orthogonal array|orthogonal array]] of strength <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005016.png" />. For detailed studies of nets, transversal designs and orthogonal arrays, see [[#References|[a1]]] and [[#References|[a3]]].
+
In the language of design theory (cf. [[Block design|Block design]] and the links given there), a net of order $s$, degree $r$ and index $\mu$ (for short, an $( s , r , \mu )$-net) is the same as an affine resolvable $1 - ( s ^ { 2 } \mu , s \mu , r )$-design (see [[Tactical configuration|Tactical configuration]]; [[Affine design|Affine design]]). Thus, it is an incidence structure $\mathcal{D} = ( V , \mathcal{B} )$ for which the set of blocks $\mathcal{B}$ is partitioned into parallel classes each of which in turn partitions the point set $V$, and such that any two non-parallel blocks intersect in exactly $\mu$ points. Moreover, there are $r \geq 3$ parallel classes each consisting of $s$ blocks; then each block has $k = s \mu$ points. The dual of an $( s , r , \mu )$-net is called a transversal design (denoted a $\operatorname{TD} _ { \mu } [ r , s ]$); in this setting, the parallel classes of blocks of a net become the point classes of the transversal design. In a more combinatorial language, a net is also equivalent to an [[Orthogonal array|orthogonal array]] of strength $t = 2$. For detailed studies of nets, transversal designs and orthogonal arrays, see [[#References|[a1]]] and [[#References|[a3]]].
  
Any net <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005017.png" /> satisfies the inequality
+
Any net $\mathcal{D}$ satisfies the inequality
  
<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/n/n130/n130050/n13005018.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
\begin{equation} \tag{a1} r \leq \frac { s ^ { 2 } \mu - 1 } { \mu - 1 }, \end{equation}
  
and equality holds if and only the net is an (affine) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005019.png" />-design; then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005020.png" /> is also called a complete net. If the dual transversal design is also resolvable (that is, if  "not being joined"  induces an equivalence relation on the point set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005021.png" />), a stronger bound holds, namely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005022.png" />; in the case of equality (in which case the dual of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005023.png" /> is again an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005024.png" />-net), it is referred to as a symmetric net (or a symmetric transversal design). The classical examples for complete nets are the affine designs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005025.png" /> formed by the points and hyperplanes of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005026.png" />-dimensional finite affine spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005027.png" /> (cf. also [[Affine space|Affine space]]) over the [[Galois field|Galois field]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005028.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005029.png" /> (so <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005030.png" /> is a prime power here); and the classical symmetric nets can be obtained from the complete ones by omitting all hyperplanes parallel to some selected line.
+
and equality holds if and only the net is an (affine) $2$-design; then $\mathcal{D}$ is also called a complete net. If the dual transversal design is also resolvable (that is, if  "not being joined"  induces an equivalence relation on the point set of $\mathcal{D}$), a stronger bound holds, namely $r \leq s \mu$; in the case of equality (in which case the dual of $\mathcal{D}$ is again an $( s , s \mu ; \mu$-net), it is referred to as a symmetric net (or a symmetric transversal design). The classical examples for complete nets are the affine designs $A G _ { d -1}  ( d , q )$ formed by the points and hyperplanes of the $d$-dimensional finite affine spaces $A G ( d , q )$ (cf. also [[Affine space|Affine space]]) over the [[Galois field|Galois field]] $\operatorname {GF} ( q )$ of order $q$ (so $q$ is a prime power here); and the classical symmetric nets can be obtained from the complete ones by omitting all hyperplanes parallel to some selected line.
  
As of 2001, the outstanding problem in this area is the determination of the triples <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005031.png" /> for which an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005032.png" />-net exists. This problem is exceedingly difficult; for instance, it includes the famous problem of deciding whether or not a [[Projective plane|projective plane]] of order not a prime power exists, and, more generally, the existence problem for affine designs (cf. also [[Affine design|Affine design]]). Many constructions and a thorough discussion of the existence problem can be found in [[#References|[a1]]], and an extensive set of tables is given in [[#References|[a2]]].
+
As of 2001, the outstanding problem in this area is the determination of the triples $( s , r , \mu )$ for which an $( s , r , \mu )$-net exists. This problem is exceedingly difficult; for instance, it includes the famous problem of deciding whether or not a [[Projective plane|projective plane]] of order not a prime power exists, and, more generally, the existence problem for affine designs (cf. also [[Affine design|Affine design]]). Many constructions and a thorough discussion of the existence problem can be found in [[#References|[a1]]], and an extensive set of tables is given in [[#References|[a2]]].
  
In general, a net is not characterized just by its parameters. For instance, the number of non-isomorphic nets with the same parameters as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005033.png" /> grows exponentially with a growth rate of at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005034.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005035.png" />, and a similar assertion holds for symmetric nets. Hence, it is desirable to characterize the classical examples among the complete and symmetric nets. For instance, a symmetric net <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005036.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005037.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005038.png" /> in which every line (that is, the intersection of all blocks through two given points) has cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005039.png" /> is isomorphic to a classical example; see [[Affine design|Affine design]] for similar results in the complete case. There is also considerable interest in nets with  "nice"  automorphism groups, for instance in translation nets, a generalization of the well-known translation planes (cf. [[Plane|Plane]]). As a further example, any generalized Hadamard matrix (see [[Hadamard matrix|Hadamard matrix]]) is equivalent to a  "class-regular"  symmetric net. These topics are discussed in detail in [[#References|[a1]]], see also [[#References|[a4]]].
+
In general, a net is not characterized just by its parameters. For instance, the number of non-isomorphic nets with the same parameters as $A G _ { d -1}  ( d , q )$ grows exponentially with a growth rate of at least $e ^ { k .\operatorname { ln } k }$, where $k = q ^ { d - 1 }$, and a similar assertion holds for symmetric nets. Hence, it is desirable to characterize the classical examples among the complete and symmetric nets. For instance, a symmetric net $\mathcal{D}$ with $\mu &gt; 1$ and $s &gt; 2$ in which every line (that is, the intersection of all blocks through two given points) has cardinality $s$ is isomorphic to a classical example; see [[Affine design|Affine design]] for similar results in the complete case. There is also considerable interest in nets with  "nice"  automorphism groups, for instance in translation nets, a generalization of the well-known translation planes (cf. [[Plane|Plane]]). As a further example, any generalized Hadamard matrix (see [[Hadamard matrix|Hadamard matrix]]) is equivalent to a  "class-regular"  symmetric net. These topics are discussed in detail in [[#References|[a1]]], see also [[#References|[a4]]].
  
The case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005040.png" /> has received particular attention. An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005041.png" />-net is often called a Bruck net and is simply referred to as an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005043.png" />-net. Here the dual structure is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005044.png" /> (see also [[Transversal system|Transversal system]]) and the corresponding orthogonal arrays are equivalent to sets of mutually [[Orthogonal Latin squares|orthogonal Latin squares]]. The Bruck nets satisfying the bound (a1) with equality are precisely the affine planes of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005045.png" /> (see also [[Affine space|Affine space]]; [[Plane|Plane]]). An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005046.png" />-net is called maximal if it cannot be extended to an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005048.png" />-net by adding a new parallel class of lines. Any candidate for a new line necessarily is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005049.png" />-set of points which meets every existing line in a unique point; such a set is called a transversal. Many known constructions of maximal nets actually yield transversal-free nets. A related problem is deciding whether or not a given net is maximal, and to find conditions guaranteeing that nets may be extended to larger nets. There is also considerable interest in determining the spectrum of all pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005050.png" /> for which a maximal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n130/n130050/n13005051.png" />-net exists, a problem even harder than the existence problem discussed above and in [[Orthogonal Latin squares|Orthogonal Latin squares]]. See [[#References|[a1]]] for a detailed study of all these topics and [[#References|[a2]]] for an extensive set of tables. For a survey emphasizing the geometric properties of nets as well as their automorphism groups, see [[#References|[a4]]].
+
The case $\mu = 1$ has received particular attention. An $( s , r , 1 )$-net is often called a Bruck net and is simply referred to as an $( s , r )$-net. Here the dual structure is denoted by $\operatorname{TD} [ r , s ]$ (see also [[Transversal system|Transversal system]]) and the corresponding orthogonal arrays are equivalent to sets of mutually [[Orthogonal Latin squares|orthogonal Latin squares]]. The Bruck nets satisfying the bound (a1) with equality are precisely the affine planes of order $s$ (see also [[Affine space|Affine space]]; [[Plane|Plane]]). An $( s , r )$-net is called maximal if it cannot be extended to an $( s , r + 1 )$-net by adding a new parallel class of lines. Any candidate for a new line necessarily is an $s$-set of points which meets every existing line in a unique point; such a set is called a transversal. Many known constructions of maximal nets actually yield transversal-free nets. A related problem is deciding whether or not a given net is maximal, and to find conditions guaranteeing that nets may be extended to larger nets. There is also considerable interest in determining the spectrum of all pairs $( s , r )$ for which a maximal $( s , r )$-net exists, a problem even harder than the existence problem discussed above and in [[Orthogonal Latin squares|Orthogonal Latin squares]]. See [[#References|[a1]]] for a detailed study of all these topics and [[#References|[a2]]] for an extensive set of tables. For a survey emphasizing the geometric properties of nets as well as their automorphism groups, see [[#References|[a4]]].
  
 
====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">  A.S. Hedayat,  N.J.A. Sloane,  J. Stufken,  "Orthogonal arrays" , Springer  (1999)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D. Jungnickel,  "Latin squares, their geometries and their groups"  D.K. Ray-Chaudhuri (ed.) , ''Coding Theory and Design Theory Part II'' , Springer  (1990)  pp. 166–225</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">  A.S. Hedayat,  N.J.A. Sloane,  J. Stufken,  "Orthogonal arrays" , Springer  (1999)</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  D. Jungnickel,  "Latin squares, their geometries and their groups"  D.K. Ray-Chaudhuri (ed.) , ''Coding Theory and Design Theory Part II'' , Springer  (1990)  pp. 166–225</td></tr></table>

Latest revision as of 16:58, 1 July 2020

(update)

In the language of design theory (cf. Block design and the links given there), a net of order $s$, degree $r$ and index $\mu$ (for short, an $( s , r , \mu )$-net) is the same as an affine resolvable $1 - ( s ^ { 2 } \mu , s \mu , r )$-design (see Tactical configuration; Affine design). Thus, it is an incidence structure $\mathcal{D} = ( V , \mathcal{B} )$ for which the set of blocks $\mathcal{B}$ is partitioned into parallel classes each of which in turn partitions the point set $V$, and such that any two non-parallel blocks intersect in exactly $\mu$ points. Moreover, there are $r \geq 3$ parallel classes each consisting of $s$ blocks; then each block has $k = s \mu$ points. The dual of an $( s , r , \mu )$-net is called a transversal design (denoted a $\operatorname{TD} _ { \mu } [ r , s ]$); in this setting, the parallel classes of blocks of a net become the point classes of the transversal design. In a more combinatorial language, a net is also equivalent to an orthogonal array of strength $t = 2$. For detailed studies of nets, transversal designs and orthogonal arrays, see [a1] and [a3].

Any net $\mathcal{D}$ satisfies the inequality

\begin{equation} \tag{a1} r \leq \frac { s ^ { 2 } \mu - 1 } { \mu - 1 }, \end{equation}

and equality holds if and only the net is an (affine) $2$-design; then $\mathcal{D}$ is also called a complete net. If the dual transversal design is also resolvable (that is, if "not being joined" induces an equivalence relation on the point set of $\mathcal{D}$), a stronger bound holds, namely $r \leq s \mu$; in the case of equality (in which case the dual of $\mathcal{D}$ is again an $( s , s \mu ; \mu$-net), it is referred to as a symmetric net (or a symmetric transversal design). The classical examples for complete nets are the affine designs $A G _ { d -1} ( d , q )$ formed by the points and hyperplanes of the $d$-dimensional finite affine spaces $A G ( d , q )$ (cf. also Affine space) over the Galois field $\operatorname {GF} ( q )$ of order $q$ (so $q$ is a prime power here); and the classical symmetric nets can be obtained from the complete ones by omitting all hyperplanes parallel to some selected line.

As of 2001, the outstanding problem in this area is the determination of the triples $( s , r , \mu )$ for which an $( s , r , \mu )$-net exists. This problem is exceedingly difficult; for instance, it includes the famous problem of deciding whether or not a projective plane of order not a prime power exists, and, more generally, the existence problem for affine designs (cf. also Affine design). Many constructions and a thorough discussion of the existence problem can be found in [a1], and an extensive set of tables is given in [a2].

In general, a net is not characterized just by its parameters. For instance, the number of non-isomorphic nets with the same parameters as $A G _ { d -1} ( d , q )$ grows exponentially with a growth rate of at least $e ^ { k .\operatorname { ln } k }$, where $k = q ^ { d - 1 }$, and a similar assertion holds for symmetric nets. Hence, it is desirable to characterize the classical examples among the complete and symmetric nets. For instance, a symmetric net $\mathcal{D}$ with $\mu > 1$ and $s > 2$ in which every line (that is, the intersection of all blocks through two given points) has cardinality $s$ is isomorphic to a classical example; see Affine design for similar results in the complete case. There is also considerable interest in nets with "nice" automorphism groups, for instance in translation nets, a generalization of the well-known translation planes (cf. Plane). As a further example, any generalized Hadamard matrix (see Hadamard matrix) is equivalent to a "class-regular" symmetric net. These topics are discussed in detail in [a1], see also [a4].

The case $\mu = 1$ has received particular attention. An $( s , r , 1 )$-net is often called a Bruck net and is simply referred to as an $( s , r )$-net. Here the dual structure is denoted by $\operatorname{TD} [ r , s ]$ (see also Transversal system) and the corresponding orthogonal arrays are equivalent to sets of mutually orthogonal Latin squares. The Bruck nets satisfying the bound (a1) with equality are precisely the affine planes of order $s$ (see also Affine space; Plane). An $( s , r )$-net is called maximal if it cannot be extended to an $( s , r + 1 )$-net by adding a new parallel class of lines. Any candidate for a new line necessarily is an $s$-set of points which meets every existing line in a unique point; such a set is called a transversal. Many known constructions of maximal nets actually yield transversal-free nets. A related problem is deciding whether or not a given net is maximal, and to find conditions guaranteeing that nets may be extended to larger nets. There is also considerable interest in determining the spectrum of all pairs $( s , r )$ for which a maximal $( s , r )$-net exists, a problem even harder than the existence problem discussed above and in Orthogonal Latin squares. See [a1] for a detailed study of all these topics and [a2] for an extensive set of tables. For a survey emphasizing the geometric properties of nets as well as their automorphism groups, see [a4].

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] A.S. Hedayat, N.J.A. Sloane, J. Stufken, "Orthogonal arrays" , Springer (1999)
[a4] D. Jungnickel, "Latin squares, their geometries and their groups" D.K. Ray-Chaudhuri (ed.) , Coding Theory and Design Theory Part II , Springer (1990) pp. 166–225
How to Cite This Entry:
Net in finite geometry. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Net_in_finite_geometry&oldid=33898
This article was adapted from an original article by Dieter Jungnickel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article