Combinatorial designs and configurations

It was not until the 20th century that combinatorial design theory was studied as a formal subject. This field has many applications, for example in statistical experimental design, coding theory, authentication codes, and cryptography. Major approaches to the problem of discovering new t-designs rely on (i) the construction of large sets of t designs, (ii) using prescribed automorphism groups, (iii) recursive construction methods. In 2017 and 2018, Tran Van Trung introduced new recursive techniques to construct t – (v, k, λ) designs. These methods are of purely combinatorial nature and require using "ingredient" t-designs or resolutions whose parameters satisfy a system of non-linear equations. Even after restricting the range of parameters in this new method, the task is computationally intractable. In this work, we enhance Tran Van Trung's "Basic Construction" by a robust and efficient hybrid computational apparatus which enables us to construct hundreds of thousands of new t – (v, k, Λ) designs from previously known ingredient designs. Towards the end of the dissertation we also create a new family of 2-resolutions, which will be infinite if there are infinitely many Sophie Germain primes.

With the publication of Shor's quantum algorithm for solving discrete logarithms in
finite cyclic groups, a need for new cryptographic primitives arose; namely, for more secure
primitives that would prevail in the post-quantum era.
The aim of this dissertation is to exploit some hard problems arising from group theory
for use in cryptography. Over the years, there have been many such proposals. We first look
at two recently proposed schemes based on some form of a generalization of the discrete
logari thm problem (DLP), identify their weaknesses, and cryptanalyze them.
By applying the exper tise gained from the above cryptanalyses, we define our own
generalization of the DLP to arbitrary finite groups. We show that such a definition leads
to the design of signature schemes and pseudo-random number generators with provable
security under a security assumption based on a group theoretic problem. In particular,
our security assumption is based on the hardness of factorizing elements of the projective
special linear group over a finite field in some representations. We construct a one-way
function based on this group theoretic assumption and provide a security proof.

Every transitive permutation representation of a finite group is the representation of the group in its action on the cosets of a particular subgroup of the group. The group has a certain rank for each of these representations. We first find almost all rank-3 and rank-4 transitive representations of the projective special linear group P SL(2, q) where q = pm and p is an odd prime. We also determine the rank of P SL (2, p) in terms of p on the cosets of particular given subgroups. We then investigate the construction of rank-3 transitive and primitive extensions of a simple group, such that the extension group formed is also simple. In the latter context we present a new, group theoretic construction of the famous Hoffman-Singleton graph as a rank-3 graph.

In this dissertation, we study some open problems concerning the existence or non-existence of some combinatorial designs. We give the construction or proof of non-existence of some Steiner systems, large sets of designs, and graph designs, with prescribed automorphism groups.

This work was motivated by the well-known question: "Does there exist a nondesarguesian projective plane of prime order?" For a prime p < 11, there is only the pappian plane of order p. Hence, such planes are indeed desarguesian. Thus, it is of interest to examine whether there are non-desarguesian planes of order 11. A suggestion by Ascher Wagner in 1985 was made to Spyros S. Magliveras: "Begin with a non-desarguesian plane of order pk, k > 1, determine all subplanes of order p up to collineations, and check whether one of these is non-desarguesian." In this manuscript we use a group-theoretic methodology to determine the subplane structures of some non-desarguesian planes. In particular, we determine orbit representatives of all proper Q-subplanes both of a Veblen-Wedderburn (VW) plane of order 121 and of the Hughes plane of order 121, under their full collineation groups. In PI, there are 13 orbits of Baer subplanes, all of which are desarguesian, and approximately 3000 orbits of Fano subplanes. In Sigma , there are 8 orbits of Baer subplanes, all of which are desarguesian, 2 orbits of subplanes of order 3, and at most 408; 075 distinct Fano subplanes. In addition to the above results, we also study the subplane structures of some non-desarguesian planes, such as the Hall plane of order 25, the Hughes planes of order 25 and 49, and the Figueora planes of order 27 and 125. A surprising discovery by L. Puccio and M. J. de Resmini was the existence of a plane of order 3 in the Hughes plane of order 25. We generalize this result, showing that there are subplanes of order 3 in the Hughes planes of order q2, where q is a prime power and q 5 (mod 6). Furthermore, we analyze the structure of the full collineation groups of certain Veblen- Wedderburn (VW) planes of orders 25, 49 and 121, and discuss how to recover the planes from their collineation groups.