Partial geometric designs from group actions

Jerod Michel, Qi Wang

TL;DR

This paper introduces a novel method for constructing "partial geometric designs" using group actions, specifically focusing on linear groups acting on subsets of finite fields. The authors demonstrate how this approach can generate infinite families of these designs and, by analyzing group stabilizers, also construct a new family of balanced incomplete block designs. This work offers a generalized framework for design construction, extending existing methods and providing new combinatorial structures with potential applications.

What Problem Does This Paper Address?

The paper tackles the challenge of constructing combinatorial designs, specifically "partial geometric designs" (also known as 1½-designs). These designs are of interest because their associated "concurrence matrices" have a specific eigenvalue structure (three eigenvalues, one of which is zero), offering partial solutions to open questions in design theory. While group actions are a classical tool for constructing designs, a key difficulty lies in computing the specific parameters of the resulting designs. This paper aims to provide a systematic and generalized method for constructing these designs, particularly partial geometric designs, by leveraging the power of group actions on finite fields.

Methods

The core of the paper's methodology lies in using group actions to construct combinatorial designs. Specifically, the authors investigate the actions of linear groups of degree two (like $SL_2(q)$ and $GL_2(q)$) on specific subsets of the finite field $\mathbb{F}_q^2$.

  • New Construction Method: A novel method for constructing partial geometric designs is introduced, which generalizes existing techniques based on difference sets and difference families, as well as the classical group action method for designs.
  • Group Action Analysis: The paper meticulously analyzes the orbits and stabilizers of specific subsets (like $D(q)$ and $D'(q)$) under the action of these linear groups. This involves detailed computations of setwise stabilizers and intersections of group-generated sets.
  • Parameter Computation: By computing these stabilizers and intersection properties, the authors are able to determine the parameters $(v, k, r; \alpha, \beta)$ of the resulting partial geometric designs.
  • Balanced Incomplete Block Designs (BIBDs): The computation of stabilizers also directly leads to the construction of a new infinite family of balanced incomplete block designs.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Unified Framework: The paper presents a powerful and unified approach to constructing partial geometric designs by framing it as a problem of group actions on specific subsets of finite fields. This generalizes and connects several existing construction methods.
  • Subsets of $\mathbb{F}_q^2$ as Building Blocks: The choice of specific subsets of $\mathbb{F}_q^2$, particularly those related to cyclotomy (like $D(q)$), proves to be a fruitful source for generating interesting designs.
  • Stabilizers are Key: The detailed analysis of stabilizers of these subsets under linear group actions is crucial for both constructing the designs and determining their parameters. This highlights the deep connection between group theory and combinatorial design theory.
  • New Families of Designs: The paper successfully constructs new infinite families of partial geometric designs and balanced incomplete block designs, expanding the known catalog of such structures.

Key Results

The paper establishes the following:

  • Infinite Families of Partial Geometric Designs: Using the action of $SL_2(q)$ on $F_q^2 \setminus \{0\}$ and subsets like $D(q)$, the authors construct infinite families of partial geometric designs. For instance, Theorem 2 shows that $(F_q^2 \setminus \{0\}, [D(q)]_{SL_2(q)})$ is a partial geometric design with specific parameters dependent on $q$.
  • New Family of Balanced Incomplete Block Designs (BIBDs): Theorem 4 demonstrates the construction of a new family of BIBDs by considering the action of the special affine group $SA_2(q)$ on $F_q^2$.
  • Explicit Parameter Calculations: The paper provides explicit formulas for the parameters of these designs, often in terms of the prime power $q$. For example, Theorem 2 gives parameters $(q^2-1, (q-1)^2, q(q-1)/2; \alpha, \beta)$ for a design derived from $SL_2(q)$ acting on $F_q^2 \setminus \{0\}$.

Limitations and Future Work

The authors acknowledge several avenues for future research:

  • Higher-Order Cyclotomies: Investigating the actions of degree-two linear groups on higher-order standard cyclotomies, which are more complex subsets of finite fields.
  • Triple Intersection Numbers: Computing the quantities $|S_1 \cap S_2|$ for specific subsets $S_1, S_2$ and group elements $g$ within $SL_2(q)$, which is noted as being difficult due to the unknown triple intersection numbers. This is crucial for understanding designs with repeated blocks.
  • Higher-Dimensional Groups: Exploring the actions of matrix groups of dimension higher than two on finite fields, which could lead to even more complex and varied designs.
  • Isomorphism Problems: The paper mentions that determining whether certain constructed designs are isomorphic (or non-isomorphic) to others is an open problem, particularly when comparing designs constructed via group actions to those built using multiset unions.

Summary updated

Abstract

In this paper, using group actions, we introduce a new method for constructing partial geometric designs (sometimes referred to as $$1\frac{1}{2}$$ 1 1 2 -designs). Using this new method, we construct several infinite families of partial geometric designs by investigating the actions of various linear groups of degree two on certain subsets of $${\mathbb {F}}_{q}^{2}$$ F q 2 . Moreover, by computing the stabilizers of such subsets in various linear groups of degree two, we are also able to construct a new infinite family of balanced incomplete block designs.
BibTeX
@inproceedings{michel2019partial,
  author = {Jerod Michel and Qi Wang},
  title = {{Partial geometric designs from group actions}},
  booktitle = {Des. Codes Cryptogr},
  year = {2019},
  url = {https://openreview.net/forum?id=5jV6IgGWKvH},
}
Figure