Answers are grounded in this paper and cite their sources.
Investigation of Gowers U3 norms in vectorial Boolean functions reveals critical differences among power permutations.
Vectorial Boolean functions from F 2 n to F 2 m are fundamental objects in theoretical computer science and mathematics. Understanding their structure, particularly how well they can be approximated by low-degree functions, is crucial in various applications, including pseudorandomness, property testing, and cryptography. The Gowers uniformity norm, introduced in additive combinatorics, provides a powerful measure for these purposes, serving as a key indicator of the approximation and has significant applications in mathematics and theoretical computer science. While the Gowers U 2 norm is well-understood, the analysis of higher-order structures, particularly the Gowers U k norm for k ≥ 3 , poses significant challenges. Indeed, the computation of the Gowers U 3 norm is intrinsically linked to the second-order differential spectrum of a function. However, determining this spectrum is a notoriously difficult problem, and to date, it has only been solved for a few specific cases, such as the inverse function over F 2 n for n = 6 , 8 and the APN permutation over F 2 6 . In this paper, we investigate the Gowers U 3 norms of vectorial Boolean functions, with specific focus on five classes of cubic highly nonlinear power permutations over finite fields. We provide a comprehensive analysis of the Gowers U 3 norm for the Welch function, the Modified Welch function, the cubic Kasami function, the Bracken-Leander function, and the Cusick-Dobbertin function. By characterizing the distribution of solutions for all second-order derivatives of these functions, we derive exact expressions for their Gowers U 3 norms. Our results reveal quantitative differences in higher-order uniformity among these functions, with the Modified Welch function exhibiting a smaller Gowers U 3 norm compared to the Welch and cubic Kasami functions. And the Bracken-Leander function and the Cusick-Dobbertin function are shown to possess larger Gowers U 3 norm compared to the inverse function. These findings contribute to a deeper understanding of these highly nonlinear power permutations.
No takes yet. Share an insight, caveat, or question.
Li et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: