TL;DR
This paper introduces a new method for constructing strongly regular graphs (SRGs) using p-ary bent functions, generalizing previous work from ternary to p-ary cases. The authors demonstrate that these constructions can yield new SRGs, particularly of the "negative Latin square type," and provide a framework for exploring their properties and potential novelty.
What Problem Does This Paper Address?
The paper tackles the challenge of constructing strongly regular graphs (SRGs), which are fundamental objects in combinatorics with applications in areas like coding theory and experimental design. Specifically, the authors focus on a particular type of SRG known as "negative Latin square type." While constructions for "Latin square type" SRGs are abundant, those for the "negative Latin square type" are scarce. Previous work had shown that certain weakly regular ternary bent functions could be used to construct these SRGs. This paper aims to generalize this construction to p-ary bent functions (where p is an odd prime), thereby expanding the toolkit for creating these specific types of SRGs and potentially discovering new ones.
Methods
The core of the paper lies in generalizing a construction method for SRGs from ternary bent functions to p-ary bent functions. The authors leverage the properties of p-ary bent functions and their associated subsets (defined by the function's output values) to form partial difference sets (PDSs). These PDSs, in turn, are used to construct Cayley graphs, which are shown to be SRGs.
Key techniques include:
- Generalization of Bent Functions: Extending the concept of bent functions from characteristic 2 to finite fields of odd prime characteristic (p-ary).
- Partial Difference Sets (PDSs): Utilizing the subsets generated by the bent functions as PDSs. A PDS is a combinatorial object that, when used to generate a Cayley graph, results in an SRG.
- Group Ring Theory: Employing group ring theory and character theory as essential tools for analyzing the properties of PDSs and their relationship to SRGs.
- Condition A: Introducing a specific condition (Condition A) on the p-ary bent functions that is crucial for the construction of SRGs. This condition relates to the function's symmetry and its behavior under scalar multiplication.
- Computational Verification: Using computational tools like MAGMA to verify the novelty of the constructed SRGs for small parameters.
Datasets
Not discussed in the paper. The paper focuses on theoretical constructions rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Generalization is Possible: The paper successfully generalizes the construction of SRGs from ternary bent functions to the broader class of p-ary bent functions, opening up new avenues for research.
- New SRGs Emerge: The constructions, particularly using non-quadratic p-ary bent functions, can lead to new SRGs, especially of the "negative Latin square type," which are notoriously difficult to construct.
- Condition A is Key: The introduction and use of "Condition A" for p-ary bent functions are critical for ensuring the resulting subsets form PDSs and thus generate SRGs. This condition highlights the importance of specific symmetries and algebraic properties of the bent functions.
- Connection to Association Schemes: The paper establishes a link between these constructed SRGs and amorphic association schemes, further deepening their combinatorial significance.
- Computational Evidence for Novelty: While proving novelty in general is challenging, computational results for small parameters provide strong evidence that these constructions yield SRGs not previously known or easily constructible.
Key Results
The paper presents three main theorems that detail the construction of SRGs from p-ary bent functions satisfying Condition A:
- Theorem 1: Constructs a (v, d, λ₁, λ₂)-PDS (and thus an SRG) from the set of zeros of a bent function satisfying Condition A. The parameters are explicitly given in terms of p, k, and ε (where ε = ±1, related to the bent function's Walsh coefficients).
- Theorem 2: Constructs a (v, d, λ₁, λ₂)-PDS from the set of non-zero squares of the bent function's output. This theorem is a generalization of previous results for ternary bent functions.
- Theorem 3: Constructs a (v, d, λ₁, λ₂)-PDS from the set of squares of the bent function's output.
The paper also provides computational results for specific cases (p=3, 5, 7) that suggest the constructed SRGs are indeed new and not isomorphic to known "affine polar graphs" or SRGs from other constructions. For instance, for p=3 and a specific bent function, an SRG is found that is confirmed to be new by comparing its automorphism group and matrix rank to existing databases.
Limitations and Future Work
- Weakly Regular Condition: The paper emphasizes the necessity of the "weakly regular" condition for bent functions in their constructions. Remark 4 notes that non-weakly regular bent functions do not yield the same results, suggesting this condition is crucial.
- Proving Novelty in General: While computational evidence is strong for small parameters, proving that the constructed SRGs are always new and not isomorphic to existing ones (like affine polar graphs) for all p and k remains a significant challenge. The authors conjecture that the automorphism groups of their constructed SRGs are smaller than those of affine polar graphs, which could be a path to proving novelty.
- Exploration of Non-Quadratic Bent Functions: The paper highlights that using non-quadratic p-ary bent functions is key to generating new SRGs. Further exploration into the properties and constructions of such functions is a promising direction.
- Generalization to Other Types of SRGs: While the focus is on negative Latin square type SRGs, exploring if these constructions can yield other types of SRGs would be valuable.
- Applications: The paper focuses on the construction of SRGs. Investigating the practical applications of these newly constructed SRGs in fields like coding theory, cryptography, or experimental design would be a natural next step.
Summary updated