Some observations on bent and planar functions
Robert S. Coulter, Steven Senger · 2025
Read Some observations on bent and planar functions by Robert S. Coulter, Steven Senger (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-17815.txt.
Introduction
Robert Coulter and Steven Senger report observations on bent and planar functions. These special functions over finite fields are valued in coding and cryptography because their differences spread out as evenly as possible. Bent functions are linked, in odd characteristic, to perfect nonlinear functions.
They show that the graph of a bent function forms a Salem set in a suitable sense. They also quantify repeated values among difference operators and prove, by elementary means, that two distinct planar functions must differ in at least two places. The results add clean structural facts about a heavily studied family.
Catalog record
| CREATOR | Robert S. Coulter, Steven Senger |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 15 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-17815
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Some observations on bent and planar functions Thanks: Orcid IDs: (R.S. Coulter) 0000-0002-1546-8779, (S. Senger) 0000-0003-2912-4464 Robert S. Coulter, Steven Senger Abstract . We show that the graph of a bent function is a Salem set in an appropriate sense. We also establish a simple result that quantifies redundancies in the difference operators of a function, which applies to bent functions over fields of odd characteristic via their equivalence to perfect non-linear functions in that setting. We end by demonstrating, by entirely elementary means, that the distance between two distinct planar functions must be at least two. 1. Motivation In this note we are interested in three related topics: bent functions, the inherent redundancy in the difference operators of a function, and the distance between two functions. We prove a result about each of these. While much is known about the Fourier properties of the graphs of various types of functions, we prove here that bent functions have graphs whose Fourier behavior is extremal in the sense that they are Salem sets. This result follows directly from the definition of bent functions. We next consider difference operators. These functions occur in the study of perfect non-linear and almost perfect non-linear functions. The former class of functions includes both planar and bent functions in odd characteristic. Here, we are interested in the inherent inter-dependence of the difference operators. We prove that all difference operators of a function can be completely determined by a small subset of them, effectively those difference operators defined by an appropriate basis. Finally, one major open problem in the study of many classes of functions is related to the minimum distance between two distinct functions within a given class. For example, it is not known if two APN functions can differ in exactly one output. Motivated by this, we use entirely elementary techniques to prove that if two planar functions differ in at least one output, then they must differ in more. A stronger result is known [ 3 ] , but not yet widely available. Our argument merely uses the definition of planarity, and so might give a different perspective for studying the minimum distance of other classes of functions. 1.1. Definitions and Notation Throughout, q=p^{\ell} for some prime p and \ell\in\mathbb{N} . We use {\mathbb{F}}_{q} to denote a finite field of q elements and {\mathbb{F}}_{q}^{\star} its non-zero elements. We also let \vec{0}_{d} denote the origin, or all zeros vector, of \mathbb{F}_{q}^{d} . Let f\in{\mathbb{F}}_{q}^{d}[x] . • For any a\in{\mathbb{F}}_{q}^{d} with a\neq\vec{0}_{d} , we define the difference or difference operator of f with respect to a, written \Delta_{f,a}:{\mathbb{F}}_{q}^{d}\rightarrow{\mathbb{F}}_{q} , by \Delta_{f,a}(x)=f(x+a)-f(x) . • f is called perfect non-linear (PN) if and only if for every a\neq\vec{0}_{d} , the difference operator \Delta_{f,a} is equidistributive on all of {\mathbb{F}}_{q}. That is, every element of {\mathbb{F}}_{q} has q^{d-1} pre-images under \Delta_{f,a} . When d=1 , f is also known as a planar function. • The Fourier transform of f at m\in\mathbb{F}_{q}^{d} is defined to be \widehat{f}(m):=q^{-d}\sum_{x\in\mathbb{F}_{q}^{d}}f(x)\chi(-x\cdot m), where \chi is a nontrivial additive character, and \cdot is the usual inner product. • f is called bent if and only if for all nontrivial additive characters \chi, we have that \left|\sum_{x\in\mathbb{F}_{q}^{d}}\chi(f(x)-x\cdot m)\right|=q^{\frac{d}{2}}. If p is odd, then f is bent if and only if it is PN, see [ 1 ] , [ 4 ] . For more general information see [ 8 ] . Following Iosevich and Rudnev in [ 6 ] , we say that a subset E\subseteq\mathbb{F}_{q}^{d} is called Salem if and only if for all m\in\mathbb{F}_{q}^{d}, with m\neq\vec{0}_{d}, we have that there must be some positive constant C independent of q so that \left|\widehat{E}(m)\right|\leq Cq^{-d}|E|^{\frac{1}{2}}, where E(x) denotes the indicator function of the set E. In this setting, we are typically interested in families of sets that can be defined as q grows large. For more on this definition, and its generalizations, see work by Fraser [ 5 ] . Given two functions f,g:A\rightarrow B, we say their Hamming distance or just distance is the number of images on which they differ. Specifically, we define it as |\{a\in A:f(a)\neq g(a)\}|. 2. Salem sets from graphs Salem sets of various kinds have been used to benchmark results in Fourier analysis, geometric measure theory, and other areas, as they exhibit many extreme behaviors. They are an object of study for their own sake, as well as for applications, as can be seen in the aforementioned [ 5 ] and the references contained therein. The important paper by Cheong, Ge, Koh, Pham, Tran, and Zhang [ 2 ] is a timely example of how central Salem sets are in geometric combinatorics over finite fields. By definition, pseudorandom sets are Salem, but deductive constructions are somewhat harder to come by. Moreover, while there are known families of Salem sets, what we prove here is that the graphs of bent functions are not only Salem, but they satisfy the definition with the constant C=1, while many constructions have bigger constants. This follows a theme with other functions widely used in cryptography. The paper by Mihaila and Thornburgh, [ 7 ] , and the references therein, have results where the graphs of various types of functions have similar Fourier properties. Theorem 1 . Given a bent polynomial f\in\mathbb{F}_{q}^{d-1}[x], its graph \left\{(x,f(x)):x\in\mathbb{F}_{q}^{d-1}\right\} is a Salem set in \mathbb{F}_{q}^{d}. Proof. Suppose f\in\mathbb{F}_{q}^{d-1}[x] is bent, and call its graph E , so E:=\left\{(x,f(x)):x\in\mathbb{F}_{q}^{d-1}\right\}\subseteq\mathbb{F}_{q}^{d}. By definition, |E|=q^{d-1} . For convenience, given an x\in\mathbb{F}_{q}^{d}, let x^{\prime} denote the first (d-1) coordinates, x^{\prime}:=(x_{1},x_{2},\dots,x_{d-1}). Now, pick an arbitrary m\in\mathbb{F}_{q}^{d}, with m\neq\vec{0}_{d}, and compute the Fourier transform of the indicator function \displaystyle\left|\widehat{E}(m)\right| \displaystyle=\left|q^{-d}\sum_{x\in\mathbb{F}_{q}^{d}}E(x)\chi(-x\cdot m)\right| \displaystyle=q^{-d}\left|\sum_{x^{\prime}\in\mathbb{F}_{q}^{d-1}}\chi(-x_{1}m_{1}-x_{2}m_{2}-\dots-x_{d-1}m_{d-1}-f(x^{\prime})m_{d})\right|, because the terms in the sum where x_{d}\neq f(x^{\prime}) are not in the set E , and therefore contribute zero to the sum. We now split into cases depending on whether m_{d}=0 or not. Case 1: If m_{d}=0, then m^{\prime}\neq\vec{0}_{d-1} because we know that m\neq\vec{0}_{d}. Continuing as above, we get \displaystyle\left|\widehat{E}(m)\right| \displaystyle=q^{-d}\left|\sum_{x^{\prime}\in\mathbb{F}_{q}^{d-1}}\chi(-x_{1}m_{1}-x_{2}m_{2}-\dots-x_{d-1}m_{d-1})\right| \displaystyle=q^{-d}\left|\sum_{x^{\prime}\in\mathbb{F}_{q}^{d-1}}\chi(-x^{\prime}\cdot m^{\prime})\right|, where the sum is zero by orthogonality, because m^{\prime}\neq\vec{0}_{d-1}. Therefore, the Salem bound holds when m_{d}=0. Case 2: If m_{d}\neq 0, then we can set m^{\prime\prime}:=\left(-m_{d}\right)^{-1}m^{\prime} , and compute \displaystyle\left|\widehat{E}(m)\right| \displaystyle=q^{-d}\left|\sum_{x^{\prime}\in\mathbb{F}_{q}^{d-1}}\chi\left(\frac{m_{d}}{m_{d}}\left(-x_{1}m_{1}-x_{2}m_{2}-\dots-x_{d-1}m_{d-1}-f(x^{\prime})m_{d}\right)\right)\right| \displaystyle=q^{-d}\left|\sum_{x^{\prime}\in\mathbb{F}_{q}^{d-1}}\chi\left(m_{d}\left(f(x^{\prime})+x^{\prime}\cdot m^{\prime\prime}\right)\right)\right|. Now, this is a sum in our original additive character \chi, but the factor of m_{d} in the argument of \chi can be thought of as changing this to a sum over a different additive character, \chi_{2} . Because m_{d}\neq 0, we know that \chi_{2} will not be a trivial additive character. Finally we set m^{\prime\prime\prime}=(-m^{\prime\prime}), and we see that we can apply the definition of bent functions as follows: \displaystyle\left|\widehat{E}(m)\right| \displaystyle=q^{-d}\left|\sum_{x^{\prime}\in\mathbb{F}_{q}^{d-1}}\chi\left(m_{d}\left(f(x^{\prime})+x^{\prime}\cdot m^{\prime\prime}\right)\right)\right| \displaystyle=q^{-d}\left|\sum_{x^{\prime}\in\mathbb{F}_{q}^{d-1}}\chi_{2}\left(f(x^{\prime})-x^{\prime}\cdot m^{\prime\prime\prime}\right)\right|=q^{-d}q^{\frac{d-1}{2}}=q^{-d}|E|^{\frac{1}{2}}. ∎ 3. What defines a bent function? We next make an observation concerning bent functions in odd characteristic, or more specifically about the redundancy in difference operators of a function, which has implications about what defines a bent function. We may view {\mathbb{F}}_{q}^{d} as a d\ell -dimensional vector space over {\mathbb{F}}_{p} . Let \{g_{1},g_{2},\ldots,g_{d\ell}\}\subseteq{\mathbb{F}}_{q}^{d} be an arbitrary but fixed basis of {\mathbb{F}}_{q}^{d} over {\mathbb{F}}_{p} . There are, of course, many such sets, but one obvious set is the set \{\beta_{i}e_{j}\} where \{\beta_{1},\ldots,\beta_{\ell}\} is basis for {\mathbb{F}}_{q} over {\mathbb{F}}_{p} and the \{e_{j}\} is the standard set of basis vectors for {\mathbb{F}}_{q}^{d} over {\mathbb{F}}_{q} with