This paper, titled "Strongly Regular Graphs Constructed from $p$-ary Bent Functions," bridges the gap between algebraic cryptography and combinatorial graph theory. It provides a generalized framework for building highly symmetric graphs using a special class of mathematical functions.
TL;DR
The authors generalize a method for constructing Strongly Regular Graphs (SRGs) from ternary ($p=3$) bent functions to any odd prime $p$. By applying specific "weakly regular" $p$-ary bent functions, they produce new families of SRGs and amorphic association schemes that were previously unknown for certain small parameters.
What Problem Does This Paper Address?
Strongly Regular Graphs (SRGs) are a central object of study in algebraic combinatorics because of their intense internal symmetry. An SRG is defined by four parameters $(v, k, \lambda, \mu)$: it has $v$ vertices, each with $k$ neighbors; any two adjacent vertices share $\lambda$ common neighbors, and any two non-adjacent vertices share $\mu$ common neighbors.
Finding new families of SRGs is notoriously difficult. Most known constructions rely on quadratic forms (geometry over finite fields). Recently, researchers found a link between "bent functions"—functions used in cryptography because they are as far from linear as possible—and SRGs, but this was largely limited to the case where the base field was ternary ($p=3$). This paper tackles the challenge of generalizing this construction to all odd primes $p$, potentially uncovering new graph structures that quadratic forms cannot produce.
Methods
The authors utilize $p$-ary bent functions mapping from a finite field $\mathbb{F}_{p^n}$ to $\mathbb{F}_p$. Their approach involves several key steps:
- Condition A: They define a specific requirement for the bent functions used, involving a homogeneity-like property ($f(\alpha x) = \alpha^l f(x)$) and "weak regularity" (a property of the function's Walsh transform).
- Partial Difference Sets (PDS): The core of the proof involves showing that specific subsets of the finite field—defined by the values of the bent function and whether those values are quadratic residues (squares)—form Partial Difference Sets.
- Cayley Graph Construction: Once a PDS is identified, it can be used to generate a Cayley graph, which is guaranteed to be an SRG.
- Character Theory: The authors use complex character theory and group rings to calculate the eigenvalues of these graphs and prove they satisfy the SRG requirements.
Datasets
As a theoretical mathematics paper, it does not use traditional "datasets." Instead, it uses:
- Mathematical Objects: Finite fields $\mathbb{F}_{p^n}$ and specific bent function families (e.g., the non-quadratic function discovered by Helleseth and Kholosha).
- Computational Verification: The authors used the MAGMA computational algebra system to verify the properties of the resulting graphs for small parameters (e.g., $p=3, 5, 7$) and compared them against Brouwer’s online database of SRGs to confirm if the graphs were truly "new."
Key Insights and Ideas
- Generalization Beyond Ternary: The most significant insight is that the link between bent functions and SRGs isn't a fluke of $p=3$; it is a fundamental property of weakly regular bent functions across all odd primes.
- Negative Latin Square Type: The constructions specifically produce "negative Latin square type" SRGs. While "Latin square type" SRGs are common, the "negative" variety is much rarer and harder to construct.
- Non-Quadratic Advantage: By using bent functions that are not quadratic polynomials, the authors can generate graphs that are not isomorphic to standard "affine polar graphs," which are the typical source of SRGs in these parameter ranges.
- Amorphic Association Schemes: They proved that the sets they constructed don't just form individual graphs, but fit together into a larger algebraic structure called an amorphic association scheme.
Key Results
- Theorems 1, 2, and 3: These provide explicit algebraic formulas for the $(v, k, \lambda, \mu)$ parameters of three distinct types of SRGs based on different subsets of the bent function's range.
- Discovery of New Graphs:
- For $p=3, n=8$, they found a new SRG with parameters $(6561, 2214, 729, 756)$.
- For $p=5, n=4$, they produced new SRGs with parameters $(625, 260, 105, 110)$ and $(625, 364, 213, 210)$.
- Automorphism Groups: Using MAGMA, they showed that the automorphism groups of their new graphs have different orders than those of known graphs with the same parameters, proving their "newness."
Limitations and Future Work
- Restriction to Condition A: The construction relies on "Condition A." The authors demonstrate (via a counter-example in Remark 4) that if a function is not weakly regular, the construction fails. This limits the pool of usable bent functions.
- The "Newness" Gap: While the authors found new graphs for small parameters, they acknowledge that for $p \ge 5$, many known bent functions still result in graphs isomorphic to existing affine polar graphs.
- Future Direction: The authors suggest that the search for more "non-quadratic" weakly regular bent functions is the key to finding even more exotic families of strongly regular graphs. There is also an open question regarding whether similar constructions exist for the prime $p=2$ (Boolean bent functions) in a way that yields SRGs.
Summary updated