Exponential bounds on the number of designs with affine parameters

It is well‐known that the number of designs with the parameters of a classical design having as blocks the hyperplanes in PG(n, q) or AG(n, q), n≥3, grows exponentially. This result was extended recently [D. Jungnickel, V. D. Tonchev, Des Codes Cryptogr, published online: 23 May, 2009] to designs having the same parameters as a projective geometry design whose blocks are the d‐subspaces of PG(n, q), for any 2≤d≤n−1. In this paper, exponential lower bounds are proved on the number of non‐isomorphic designs having the same parameters as an affine geometry design whose blocks are the d‐subspaces of AG(n, q), for any 2≤d≤n−1, as well as resolvable designs with these parameters. An exponential lower bound is also proved for the number of non‐isomorphic resolvable 3‐designs with the same parameters as an affine geometry design whose blocks are the d‐subspaces of AG(n, 2), for any 2≤d≤n−1. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 475–487, 2010     

Correction to: “Exponential bounds on the number of designs with affine parameters”

It is well known that the number of designs with the parameters of a classical design having as blocks the hyperplanes in PG(n, q) or AG(n, q), n?3, grows exponentially. This result was extended recently [5] to designs having the same parameters as a projective geometry design whose blocks are the d‐subspaces of PG(n, q), for any 2?d?n ? 1. In this paper, exponential lower bounds are proved on the number of non‐isomorphic designs having the same parameters as an affine geometry design whose blocks are the d‐subspaces of AG(n, q), for any 2≤d≤n ? 1. Exponential bounds are also proved for the number of resolvable designs with these parameters. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:156‐166, 2011     

A Hamada type characterization of the classical geometric designs

The dimension of a combinatorial design ${{\mathcal D}}$ over a finite field F = GF(q) was defined in (Tonchev, Des Codes Cryptogr 17:121–128, 1999) as the minimum dimension of a linear code over F that contains the blocks of ${{\mathcal D}}$ as supports of nonzero codewords. There it was proved that, for any prime power q and any integer n ≥ 2, the dimension over F of a design ${{\mathcal D}}$ that has the same parameters as the complement of a classical point-hyperplane design PG _n-1(n, q) or AG _n-1(n, q) is greater than or equal to n + 1, with equality if and only if ${{\mathcal D}}$ is isomorphic to the complement of the classical design. It is the aim of the present paper to generalize this Hamada type characterization of the classical point-hyperplane designs in terms of associated codes over F = GF(q) to a characterization of all classical geometric designs PG _d (n, q), where 1 ≤ d ≤ n ? 1, in terms of associated codes defined over some extension field E?=?GF(q ^t ) of F. In the affine case, we conjecture an analogous result and reduce this to a purely geometric conjecture concerning the embedding of simple designs with the parameters of AG _d (n, q) into PG(n, q). We settle this problem in the affirmative and thus obtain a Hamada type characterization of AG _d (n, q) for d = 1 and for d > (n ? 2)/2.     

The number of designs with geometric parameters grows exponentially

It is well-known that the number of 2-designs with the parameters of a classical point-hyperplane design PG _n-1(n, q) grows exponentially. Here we extend this result to the number of 2-designs with the parameters of PG _d (n, q), where 2 ≤ d ≤ n ? 1. We also establish a characterization of the classical geometric designs in terms of hyperplanes and, in the special case d = 2, also in terms of lines. Finally, we shall discuss some interesting configurations of hyperplanes arising in designs with geometric parameters.     

A generalization of a result of Dembowski and Wagner

The famous Dembowski-Wagner theorem gives various characterizations of the classical geometric 2-design PG _n-1(n, q) among all 2-designs with the same parameters. One of the characterizations requires that all lines have size q + 1. It was conjectured [2] that this is also true for the designs PG _d (n, q) with 2 ≤ d ≤  n − 1. We establish this conjecture, hereby improving various previous results.     

Affine geometry designs, polarities, and Hamada's conjecture

In a recent paper, two of the authors used polarities in PG(2d−1,p) (p?2 prime, d?2) to construct non-geometric designs having the same parameters and the same p-rank as the geometric design PGd(2d,p) having as blocks the d-subspaces in the projective space PG(2d,p), hence providing the first known infinite family of examples where projective geometry designs are not characterized by their p-rank, as it is the case in all known proven cases of Hamada's conjecture. In this paper, the construction based on polarities is extended to produce designs having the same parameters, intersection numbers, and 2-rank as the geometric design AGd+1(2d+1,2) of the (d+1)-subspaces in the binary affine geometry AG(2d+1,2). These designs generalize one of the four non-geometric self-orthogonal 3-(32,8,7) designs of 2-rank 16 (V.D. Tonchev, 1986 [12]), and provide the only known infinite family of examples where affine geometry designs are not characterized by their rank.     

The characterization problem for designs with the parameters of AG<Subscript>d</Subscript>(<Emphasis Type="Italic">n</Emphasis>, <Emphasis Type="Italic">q</Emphasis>)

We start a new characterization of the geometric 2-design AG _d (n,q) among all simple 2-designs with the same parameters by handling the cases d ∈ {1,2,3,n — 2}. For d ≠ 1, our characterization is in terms of line sizes, and for d = 1 in terms of the number of affine hyperplanes. We also show that the number of non-isomorphic resolvable designs with the parameters of AG₁(n,q) grows exponentially with linear growth of n.     

Designs having the parameters of projective and affine spaces

Two constructions are described that yield an improved lower bound for the number of 2-designs with the parameters of PG _d (n, q), and a lower bound for the number of resolved 2-designs with the parameters of AG _d (n, q).     

Automorphisms and Isomorphisms of Symmetric and Affine Designs

Given a finite group G, for all sufficiently large d and for each q > 3 there are symmetric designs and affine designs having the same parameters as PG(d, q) and AG(d, q), respectively, and having full automorphism group isomorphic to G.     

Characterizing geometric designs, II

We provide a characterization of the classical point-line designs PG₁(n,q), where n?3, among all non-symmetric 2-(v,k,1)-designs as those with the maximal number of hyperplanes. As an application of this result, we characterize the classical quasi-symmetric designs PGn−2(n,q), where n?4, among all (not necessarily quasi-symmetric) designs with the same parameters as those having line size q+1 and all intersection numbers at least qn−4+?+q+1. Finally, we also give an explicit lower bound for the number of non-isomorphic designs having the same parameters as PG₁(n,q); in particular, we obtain a new proof for the known fact that this number grows exponentially for any fixed value of q.     

A characterization of projective subspaces of codimension two as quasi-symmetric designs with good blocks

Consider an incidence structure whose points are the points of a PG_n(n+2,q) and whose block are the subspaces of codimension two, where n?2. Since every two subspaces of codimension two intersect in a subspace of codimension three or codimension four, it is easily seen that this incidence structure is a quasi-symmetric design. The aim of this paper is to prove a characterization of such designs (that are constructed using projective geometries) among the class of all the quasi-symmetric designs with correct parameters and with every block a good block. The paper also improves an earlier result for the special case of n=2 and obtains a Dembowski-Wagner-type result for the class of all such quasi-symmetric designs.     

On affine designs and Hadamard designs with line spreads

Rahilly [On the line structure of designs, Discrete Math. 92 (1991) 291-303] described a construction that relates any Hadamard design H on 4^m-1 points with a line spread to an affine design having the same parameters as the classical design of points and hyperplanes in AG(m,4). Here it is proved that the affine design is the classical design of points and hyperplanes in AG(m,4) if, and only if, H is the classical design of points and hyperplanes in PG(2m-1,2) and the line spread is of a special type. Computational results about line spreads in PG(5,2) are given. One of the affine designs obtained has the same 2-rank as the design of points and planes in AG(3,4), and provides a counter-example to a conjecture of Hamada [On the p-rank of the incidence matrix of a balanced or partially balanced incomplete block design and its applications to error-correcting codes, Hiroshima Math. J. 3 (1973) 153-226].     

The packing problem for projective geometries over GF(3) with dimension greater than five

An (n, d) set in the projective geometry PG(r, q) is a set of n points, no d of which are dependent. The packing problem is that of finding n(r, q, d), the largest size of an (n, d) set in PG(r, q). The packing problem for PG(r, 3) is considered. All of the values of n(r, 3, d) for r ? 5 are known. New results for r = 6 are n(6, 3, 5) = 14 and 20 ? n(6, 3, 4) ? 31. In general, upper bounds on n(r, q, d) are determined using a slightly improved sphere-packing bound, the linear programming approach of coding theory, and an orthogonal (n, d) set with the known extremal values of n(r, q, d)—values when r and d are close to each other. The BCH constructions and computer searches are used to give lower bounds. The current situation for the packing problem for PG(r, 3) with r ? 15 is summarized in a final table.     

Ambient Spaces of Dimensional Dual Arcs

A d-dimensional dual arc in PG(n, q) is a higher dimensional analogue of a dual arc in a projective plane. For every prime power q other than 2, the existence of a d-dimensional dual arc (d 2) in PG(n, q) of a certain size implies n d(d + 3)/2 (Theorem 1). This is best possible, because of the recent construction of d-dimensional dual arcs in PG(d(d + 3)/2, q) of size ^d–1 _i=0 q ⁱ, using the Veronesean, observed first by Thas and van Maldeghem (Proposition 7). Another construction using caps is given as well (Proposition 10).     

Parameters for which the Griesmer bound is not sharp

We prove for a large class of parameters t and r that a multiset of at most tθ_d-k+rθ_d-k-2 points in PG(d,q) that blocks every k-dimensional subspace at least t times must contain a sum of t subspaces of codimension k.We use our results to identify a class of parameters for linear codes for which the Griesmer bound is not sharp. Our theorem generalizes the non-existence results from Maruta [On the achievement of the Griesmer bound, Des. Codes Cryptogr. 12 (1997) 83-87] and Klein [On codes meeting the Griesmer bound, Discrete Math. 274 (2004) 289-297].     

Classes of optical orthogonal codes from arcs in root subspaces

We present new constructions for (n,w,λ) optical orthogonal codes (OOC) using techniques from finite projective geometry. In one case codewords correspond to (q-1)-arcs contained in Baer subspaces (and, in general, kth-root subspaces) of a projective space. In the other construction, we use sublines isomorphic to PG(2,q) lying in a projective plane isomorphic to PG(2,q^k), k>1. Our construction yields for each λ>1 an infinite family of OOCs which, in many cases, are asymptotically optimal with respect to the Johnson bound.     

Some Characterizations of Finite Hermitian Veroneseans

We characterize the finite Veronesean of all Hermitian varieties of PG(n,q²) as the unique representation of PG(n,q²) in PG(d,q), d n(n+2), where points and lines of PG(n,q²) are represented by points and ovoids of solids, respectively, of PG(d,q), with the only condition that the point set of PG(d,q) corresponding to the point set of PG(n,q²) generates PG(d,q). Using this result for n=2, we show that is characterized by the following properties: (1) ; (2) each hyperplane of PG(8,q) meets in q²+1, q³+1 or q³+q²+1 points; (3) each solid of PG(8,q) having at least q+3 points in common with shares exactly q²+1 points with it.51E24     

Sets of even type in PG(3, 4), alias the binary (85, 24) projective geometry code

To characterize Hermitian varieties in projective space PG(d, q) of d dimensions over the Galois field GF(q), it is necessary to find those subsets K for which there exists a fixed integer n satisfying (i) 3 ? n ? q ? 1, (ii) every line meets K in 1, n or q + 1 points. K is called singular or non-singular as there does or does not exist a point P for which every line through P meets K in 1 or q + 1 points. For q odd, a non-singular K is a non-singular Hermitian variety (M. Tallini Scafati “Caratterizzazione grafica delle forme hermitiane di un S_{r, q}” Rend. Mat. Appl.26 (1967), 273–303). For q even, q > 4 and d = 3, a non-singular K is a Hermitian surface or “looks like” the projection of a non-singular quadric in PG(4, q) (J.W.P. Hirschfeld and J.A. Thas “Sets of type (1, n, q + 1) in PG(d, q)” to appear). The case q = 4 is quite exceptional, since the complements of these sets K form a projective geometry code, a (21, 11) code for d = 2 and an (85, 24) code for d = 3. The full list of these sets is given.     

2-Spreads and Transitive and Orthogonal 2-Parallelisms of PG(5, 2)

A 2-spread is a set of two-dimensional subspaces of PG(d, q), which partition the point set. We establish that up to equivalence there exists only one 2-spread of PG(5, 2). The order of the automorphism group preserving it is 10584. A 2-parallelism is a partition of the set of two-dimensional subspaces by 2-spreads. There is a one-to-one correspondence between the 2-parallelisms of PG(5, 2) and the resolutions of the 2-(63,7,15) design of the points and two-dimensional subspaces. Sarmiento (Graphs and Combinatorics 18(3):621–632, 2002) has classified 2-parallelisms of PG(5, 2), which are invariant under a point transitive cyclic group of order 63. We classify 2-parallelisms with automorphisms of order 31. Among them there are 92 2-parallelisms with full automorphism group of order 155, which is transitive on their 2-spreads. Johnson and Montinaro (Results Math 52(1–2):75–89, 2008) point out that no transitive t-parallelisms of PG(d, q) have been constructed for t > 1. The 92 transitive 2-parallelisms of PG(5, 2) are then the first known examples. We also check them for mutual orthogonality and present a set of ten mutually orthogonal resolutions of the geometric 2-(63,7,15) design.