New invariants for incidence structures

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 D , which admit both an algebraic and a geometric description. More precisely, we will associate one invariant for the isomorphism class of 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 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 dimq(D∗) of 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 D into projective geometries Π=PG(n,q) , where an embedding means identifying the points of D with a point set V in Π in such a way that every block of D is induced as the intersection of V with a suitable subspace of Π . Our main result shows that the q-dimension of D∗ always coincides with the smallest value of N for which 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