Abstract
We exhibit a new, surprisingly tight, connection between incidence structures, linear codes, and Galois geometry. To this end, we introduce new invariants for finite simple incidence structures \({\mathcal{D}}\), which admit both an algebraic and a geometric description. More precisely, we will associate one invariant for the isomorphism class of \({\mathcal{D}}\) with each prime power q. On the one hand, we consider incidence matrices M with entries from GF(q t) for the complementary incidence structure \({\mathcal{D}^*}\), where t may be any positive integer; the associated codes C = C(M) spanned by M over GF(q t); and the corresponding trace codes Tr(C(M)) over GF(q). The new invariant, namely the q-dimension \({{\rm dim}_q(\mathcal{D}^*)}\) of \({\mathcal{D}^*}\), is defined to be the smallest dimension over all trace codes which may be obtained in this manner. This modifies and generalizes the q-dimension of a design as introduced in Tonchev (Des Codes Cryptogr 17:121–128, 1999). On the other hand, we consider embeddings of \({\mathcal{D}}\) into projective geometries \({\Pi = PG(n, q)}\), where an embedding means identifying the points of \({\mathcal{D}}\) with a point set V in \({\Pi}\) in such a way that every block of \({\mathcal{D}}\) is induced as the intersection of V with a suitable subspace of \({\Pi}\). Our main result shows that the q-dimension of \({\mathcal{D}^*}\) always coincides with the smallest value of N for which \({\mathcal{D}}\) may be embedded into the (N − 1)-dimensional projective geometry PG(N − 1, q). We also give a necessary and sufficient condition when actually an embedding into the affine geometry AG(N − 1, q) is possible. Several examples and applications will be discussed: designs with classical parameters, some Steiner designs, and some configurations.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abdul-Elah M.S., Al-Dhahir M.W., Jungnickel D.: 83 in PG(2, q). Arch. Math. 49, 141–150 (1987)
Beth T., Jungnickel D., Lenz H.: Design Theory, 2nd edn. Cambridge University Press, Cambridge (1999)
Beutelspacher A., Rosenbaum U.: Projective Geometry, 2nd edn. Cambridge University Press, Cambridge (2004)
Bierbrauer J.: Introduction to Coding Theory. CRC, Boca Raton (2005)
Calderbank R., Kantor W.M.: The geometry of two-weight codes. Bull. Lond. Math. Soc. 18, 97–122 (1986)
Clark D., Jungnickel D., Tonchev V.D.: Affine geometry designs, polarities, and Hamada’s conjecture. J. Comb. Theory A. 118, 231–239 (2011a)
Clark D., Jungnickel D., Tonchev V.D.: Correction to: “Exponential bounds on the number of designs with affine parameters”. J. Comb. Des. 19, 156–166 (2011b)
Colbourn C.J., Dinitz J.H.: Handbook of Combinatorial Designs, 2nd edn. CRC Press, Boca Raton (2007)
Coxeter H.S.M.: Twelve points in PG(5, 3) with 95040 self-transformations. Philos. Trans. R. Soc. Lond. A. 247, 279–293 (1958)
Delsarte P.: Weights of linear codes and strongly regular normed spaces. Discret. Math. 3, 47–64 (1972)
Dembowski P.: Finite Geometries. Springer, Berlin (1968)
Doyen J., Hubaut X., Vandensavel M.: Ranks of incidence matrices of Steiner triple systems. Math. Z. 163, 251–259 (1978)
Ghinelli D., Jungnickel D., Metsch K.: Remarks on polarity designs (Submitted).
Giorgetti M., Previtali A.: Galois invariance, trace codes and subfield subcodes. Finite Fields Appl. 16, 96–99 (2010)
Goethals J.M., Delsarte P.: On a class of majority-logic decodable cyclic codes. IEEE Trans. Inf. Theory 14, 182–188 (1968)
Grünbaum B.: Configurations of points and lines. Graduate Studies in Mathematics 103. American Mathematical Society, Providence (2009).
Hamada N.: On the p-rank of the incidence matrix of a balanced or partially balanced incomplete block design and its application to error correcting codes. Hiroshima Math. J. 3, 154–226 (1973)
Hamada N., Ohmori H.: On the BIB-design having the minimum p-rank. J. Comb. Theory A. 18, 131–140 (1975)
Harada M., Lam C.W.H., Tonchev V.D.: Symmetric (4,4)-nets and generalized Hadamard matrices over groups of order 4. Des. Codes Cryptogr. 34, 71–87 (2005)
Hirschfeld J.W.P.H.: Projective spaces of square size. Simon Stevin 65, 319–329 (1991)
Jungnickel D.: Recent results on designs with classical parameters. J. Geom. 101, 137–155 (2011)
Jungnickel D., Tonchev V.D.: Polarities, quasi-symmetric designs, and Hamada’s conjecture. Des. Codes Cryptogr. 51, 131–140 (2009)
Jungnickel D., Tonchev V.D.: The number of designs with geometric parameters grows exponentially. Des. Codes Cryptogr. 55, 131–140 (2010)
Jungnickel D., Tonchev V.D.: A Hamada type characterization of the classical geometric designs. Des. Codes Cryptogr. doi:10.1007/s10623-011-9580-3 (2011).
Jurrius R.: Weight enumeration of codes from finite spaces. Des. Codes Cryptogr. doi:10.1007/s10623-011-9557-2 (2011).
MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1977).
Rigby J.F.: Affine subplanes of finite projective planes. Can. J. Math. 17, 977–1009 (1965)
Tallini G.: On caps of kind s in a Galois r-dimensional space. Acta Arith. 7, 19–28 (1961)
Teirlinck L.: On projective and affine hyperplanes. J. Comb. Theory A. 28, 290–306 (1980)
Tonchev V.D.: Quasi-symmetric 2-(31, 7, 7)-designs and a revision of Hamada’s conjecture. J. Comb. Theory A. 42, 104–110 (1986)
Tonchev V.D.: Linear perfect codes and a characterization of the classical designs. Des. Codes Cryptogr. 17, 121–128 (1999)
Tonchev V.D.: A note on MDS codes, n-arcs and complete designs. Des. Codes Cryptogr. 29, 247–250 (2003)
Tonchev V.D.: Finite geometry, designs, codes, and Hamada’s conjecture. In: Crnković, D., Tonchev, V. (eds.) Information Security, Coding Theory and Related Combinatorics, pp. 437–448. IOS Press, Amsterdam (2011)
Author information
Authors and Affiliations
Corresponding author
Additional information
This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Finite Geometries”.
Rights and permissions
About this article
Cite this article
Jungnickel, D., Tonchev, V.D. New invariants for incidence structures. Des. Codes Cryptogr. 68, 163–177 (2013). https://doi.org/10.1007/s10623-012-9636-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-012-9636-z