Introduction
In the fields of cryptography and coding theory, bent functions are highly valued for their "perfect nonlinearity." This property ensures that the functions are as far from linear as possible, providing maximum resistance to linear cryptanalysis. Consequently, they serve as fundamental building blocks for S-boxes in block ciphers and spreading sequences in Code Division Multiple Access (CDMA) communications.
While standard Boolean bent functions (mapping bits to bits) are well-documented, $(m, n)$-generalized bent functions (GBFs)—which map a vector of $n$ bits to an integer modulo $m$—remain more mysterious. While researchers have identified specific cases where they do exist (such as when $m$ is a power of 2), the "forbidden zones" where they cannot exist have historically been poorly mapped. This research establishes new boundaries for these functions, specifically focusing on cases where $m$ is odd or twice an odd number.
Theoretical Framework: Group Rings and Character Theory
To address the existence problem, the authors move away from traditional functional analysis and instead employ Algebraic Group Theory and Character Theory. The methodology relies on three primary pillars:
- Group Rings: The authors represent the GBF as an element within a group ring $\mathbb{Z}[C_m][G]$. This transformation allows the "bentness" property to be expressed as a structural equation, making it susceptible to algebraic analysis.
- Vanishing Sums of Roots of Unity: A central challenge in this field is determining when a sum of complex roots of unity equals zero. The authors utilize the concepts of "minimal relations" and "c-exponents" to analyze these sums and identify structural impossibilities.
- The Reduction Principle: A key strategic move is the development of a reduction approach. The authors prove that if a prime factor of $m$ is sufficiently large, it does not contribute to the existence of the function, allowing complex values of $m$ to be simplified into smaller, more manageable cases.
Key Insights and Structural Constraints
The "Large Prime" Filter
One of the most significant insights presented (Proposition 3.1) is that if $m$ has a prime factor $p > 2^n$, the existence of an $(m, n)$-GBF implies the existence of an $(m/p, n)$-GBF. This allows researchers to effectively "ignore" very large prime factors when searching for nonexistence, as the problem reduces to the smaller factor $m/p$.
Constraints on Odd Moduli
The paper demonstrates that for odd $m$, the requirements for existence are quite strict. Theorem 3.4 establishes that if an $(m, n)$-GBF exists for an odd $m = \prod p_i^{\alpha_i}$, then $m$ must have at least two distinct prime factors ($s \ge 2$) and those factors must satisfy a specific inequality relative to the dimension $n$:
$$3p_1 + p_2 \le 2^n$$
This significantly narrows the search space for these functions in the odd-modulus domain.
The n=3 Breakthrough
By combining these new tools, the authors provide a definitive answer for the case where $n=3$. They prove that no $(m, 3)$-GBF exists for any $m$ that is odd or $m \equiv 2 \pmod 4$. This settles a specific case that had remained an open question in previous literature, providing a complete nonexistence proof for these parameters.
Results for Even Moduli
For the case where $m = 2p^\alpha$ and $n$ is odd, the authors show that $p$ must be relatively small ($p < 2^{n-3}$) unless $p$ is a specific type of Mersenne prime. This further constrains the possible parameters for GBFs when the modulus is twice a prime power.
Conclusion and Future Work
This research significantly improves upon previous work by refining the conditions under which generalized bent functions can exist. By establishing these new nonexistence criteria, the authors provide a clearer map of the mathematical landscape of perfect nonlinearity.
While the paper focuses on the "negative" side—proving where functions cannot exist—this work is vital for narrowing the search for new constructions. Future research may apply these group ring techniques to higher dimensions ($n > 3$) or explore different group structures, such as non-Abelian groups, to see if similar nonexistence patterns emerge.
Summary updated