Depending on the parity of n and the regularity of a bent function f from \({{\mathbb F}_{p}^{n}}\) to \({\mathbb F}_{p}\), f can be affine on a subspace of dimension at most n/2, (n − 1)/2 or n/2 − 1. We point out that many p-ary bent functions take on this bound, and it seems not easy to find examples for which one can show a different behaviour. This resembles the situation for Boolean bent functions of which many are (weakly) n/2-normal, i.e. affine on a n/2-dimensional subspace. However applying an algorithm by Canteaut et.al., some Boolean bent functions were shown to be not n/2-normal. We develop an algorithm for testing normality for functions from \({{\mathbb F}_{p}^{n}}\) to \({\mathbb F}_{p}\). Applying the algorithm, for some bent functions in small dimension we show that they do not take on the bound on normality. Applying direct sum of functions this yields bent functions with this property in infinitely many dimensions.
Hinweise
This article is part of the Topical Collection on Special Issue on Sequences and Their Applications
1 Introduction
Let p be a prime, and let f be a function from an n-dimensional vector space \(\mathbb {V}_{n}\) over \({\mathbb F}_{p}\) to \({\mathbb F}_{p}\). The Walsh transform of f is the complex valued function
where 〈u, x〉 is a (nondegenerate) inner product in \(\mathbb {V}_{n}\). The classical frameworks are \(\mathbb {V}_{n} = {{\mathbb F}_{p}^{n}}\), in which case we take the conventional dot product as inner product, and \(\mathbb {V}_{n} = {\mathbb F}_{p^{n}}\), for which the standard inner product is 〈u, x〉 = Trn(ux), where Trn(z) is the absolute trace of z in \({\mathbb F}_{p^{n}}\).
The function f is called a bent function if \(|\widehat {f}(b)| = p^{n/2}\) for all \(b\in \mathbb {V}_{n}\). For Boolean bent functions we have \(\widehat {f}(b) = (-1)^{f^{*}(b)}2^{n/2}\) for a Boolean function f∗, called the dual of f. When p is odd, then a bent function f satisfies (cf. [10])
for a function f∗ from \(\mathbb {V}_{n}\) to \({\mathbb F}_{p}\). Accordingly f is called regular if \(p^{-n/2}\widehat {f}(b) =\epsilon _{p}^{f^{*}(b)}\) for all \(b \in \mathbb {V}_{n}\), which for a Boolean bent function always holds. If \(p^{-n/2}\widehat {f}(b) =\zeta \ \epsilon _{p}^{f^{*}(b)}\) for some ζ ∈{± 1,±i}, independent from b, we call fweakly regular, otherwise f is called non-weakly regular. Note that regular implies weakly regular. Weakly regular bent functions always come in pairs, since the dual is bent as well. This does in general not hold for non-weakly regular bent functions, see [6, 8]. Note that Boolean bent functions only exist for even n, which is different when p is odd, where bent functions exist in even and in odd dimension.
Anzeige
Bent functions are interesting objects due to applications in cryptography and coding, and due to rich connections to objects in combinatorics and geometry. In particular, bent functions define relative difference sets in the elementary abelian p-group. Many constructions and infinite classes of bent functions are known, hence research focuses on the nature and properties of bent functions, rather than on discovering new formulas for bent functions. In this article we investigate normality for p-ary bent functions, which then also describes a feature of the corresponding relative difference set.
We start by recalling the relevant definitions as given in the literature, see [2, 3, 9, 14] or [17, pp.81], [18, pp.155]. A function \(f:\mathbb {V}_{n}\rightarrow {\mathbb F}_{p}\) is called k-normal if there exists a k-dimensional affine subspace of \(\mathbb {V}_{n}\) restricted to which f is constant. If f is affine on a k-dimensional affine subspace of \(\mathbb {V}_{n}\), then f is called weakly-k-normal. When n is even and k = n/2, then f is called (weakly)-normal. We emphasize that a weakly-k-normal function can be transformed into a k-normal function by adding an affine function. As bentness is invariant under addition of affine functions, the distinction between normality and weak normality is not relevant for describing the properties of a bent function.
Many classical constructions of Boolean bent functions like Maiorana-McFarland and PS+ yield normal functions. This is very different for random Boolean functions, which are not likely to be constant (affine) on an affine subspace with “large” dimension [3]. The question if there exist non-(weakly)-normal Boolean bent functions was open for several years. In [2] it was shown that the Kasami bent function in dimension 14 is non-weakly-normal. Non-weakly-normal bent functions in dimension 10 (and 12) were presented in [14]. By [2, Lemma 25] this guarantees the existence of non-weakly-normal Boolean bent functions in (even) dimension n ≥ 10.
k-normality may also be of cryptographic significance. As pointed out in [3], k-normality is a quite natural complexity criterion, since any affine function is constant on an affine hyperplane. Moreover there is a relation between normality and nonlinearity for Boolean functions, see [3, Proposition 2]. As also mentioned in [3], the k-normality was not yet related to explicit attacks on ciphers, however the situation was the same for nonlinearity when it was introduced. In fact, meanwhile the attack on the stream cipher Grain-128 in [16] is based on the 5-normality of the 9-variable filter function (which can be seen as a modification of the standard quadratic bent function in 8 variables), used in the sequence generation.
Anzeige
The situation for bent functions from \(\mathbb {V}_{n}\) to \({\mathbb F}_{p}\), p odd, is somewhat different from the Boolean case. In [7] it is pointed out that a weakly regular but not regular bent function in even dimension n cannot be normal. However some results indicate that also for odd p, bent functions exhibit a typical normality behaviour. It may not be easy to find bent functions for which one can prove a different behaviour.
In this paper, we first present a p-ary equivalent of a result of Carlet in [3] showing that - as one would expect - an arbitrary p-ary function is with high probability not (weakly)-k-normal for any not very small value of k. We then show the p-ary equivalent of a relation between nonlinearity and normality for Boolean functions, [3, 9]. We summarize some known results on normality for p-ary bent functions, which indicate that many have a “typical” behaviour with respect to normality, similar as it was observed in the Boolean case: Many p-ary bent functions are k-normal, where k is as large as it is theoretically possible for a bent function.
In Section 3 we present an algorithm for testing (weak)-k-normality for p-ary functions. Our algorithm is not a straightforward generalization of the algorithm in [2], which was used to find non-weakly-normal Boolean bent functions in dimension 14 [2], and 10 and 12 [14]. Applying this algorithm we find the first examples of p-ary bent functions (in small dimensions) which do not possess k-normality with maximal possible k. Generalizing Lemma 25 of [2] we then can obtain bent functions with this property in every larger dimension of the same parity.
2 Normality results
One target in this paper is to pave the way for a systematic analysis of the behaviour of p-ary bent functions with respect to normality. We hence start with showing some p-ary equivalents of results on the normality behaviour of Boolean (bent) functions. Our first proposition, is the p-ary version of Theorem 3 and Proposition 1 in [3]. The proof resembles the proof in [3].
Proposition 1
Letknbe a sequence of integers such that\(\lim _{n\rightarrow \infty }\frac {p^{k_{n}}}{nk_{n}} = \infty \). The density of the functions which are weakly-kn-normalin the set of functions from\(\mathbb {V}_{n}\)to\({\mathbb F}_{p}\),tends to 0 if n tends to infinity.
Letlnbe a sequence of positive integers such that\(l_{n}/\sqrt {n}\)tends to infinity if n tends to infinity. The density of the set of weaklyln-normalfunctions from\(\mathbb {V}_{n}\)to\({\mathbb F}_{p}\)of degree at most 3 in the set of all functions of degree at most 3, tends to 0 if n tends to infinity.
Proof
For the proof we may identify \(\mathbb {V}_{n}\) with \({{\mathbb F}_{p}^{n}}\). The number of linear subspaces of \({{\mathbb F}_{p}^{n}}\) of dimension kn is
hence the number of kn-dimensional affine subspaces of \({{\mathbb F}_{p}^{n}}\) is
$$\lambda_{n} = p^{n-k_{n}}\left[ \begin{array}{c} n \\ k_{n} \end{array} \right]. $$
Let μn be the number of functions from \({{\mathbb F}_{p}^{n}}\) to \({\mathbb F}_{p}\) which are affine on a fixed kn-dimensional affine subspace A (which does not depend on the choice of A). To determine μn, we choose \(A={\mathbb F}_{2}^{k_{n}} \times \{(0,\ldots ,0)\}\). Observe that the restriction of a p-ary function to A is affine if and only if its ANF contains no monomial of degree at least 2 which only contains variables in \(\{x_{1},x_{2},\ldots ,x_{k_{n}}\}\). The number of such functions is \(p^{p^{n}-p^{k_{n}}+k_{n}+ 1}\), hence the number \(\omega _{k_{n}}\) of weakly- kn-normal functions is at most
Since \(\frac {p^{k_{n}}}{nk_{n}}\) tends to infinity when n tends to ∞, the exponent \(n(k_{n}+ 1)-p^{k_{n}}\) tends to −∞. As a consequence, \(\lim _{n\rightarrow \infty }\frac {\omega _{k_{n}}}{p^{p^{n}}} = 0\).
Let νn be the number of functions from \({{\mathbb F}_{p}^{n}}\) to \({\mathbb F}_{p}\) of degree at most 3 which are affine on \(A={\mathbb F}_{2}^{l_{n}} \times \{(0,\ldots ,0)\}\). Similarly as above we see that \(\nu _{n} = p^{1+n+{n\choose 2}+{n\choose 3}-{l_{n}\choose 2}-{l_{n}\choose 3}}\), and the number of weakly- ln-normal functions of degree at most 3 is at most \(p^{n(l_{n}+ 1)-{l_{n}^{2}}+ 1+n+{n\choose 2}+{n\choose 3}-{l_{n}\choose 2}-{l_{n}\choose 3}}\). The density of this set in the set of p-ary functions of degree at most 3 is therefore upper bounded by
We remark that the proof of Proposition 1 also shows that the existence of a not weakly k-normal function from \(\mathbb {V}_{n}\) to \({\mathbb F}_{p}\) is guaranteed whenever \(\frac {p^{n(k + 1)-k^{2}+k + 1-p^{k}}}{(p-1)^{k}} < 1\). For instance, there are not (weakly) normal functions for p =3 and n = 6, and for p = 5 and n = 4.
For Boolean functions, in [3, 9] relations between normality and Walsh coefficients have been explored. We next generalize these results to p-ary functions. Some identities for Boolean functions which play a role in the analysis can straightforwardly be generalized to odd p, hence we omit the proof. Let
V be a k-dimensional subspace of \(\mathbb {V}_{n}\), and let W be a complement of V in \(\mathbb {V}_{n}\),
fa be defined on W by fa(x) = f(a + x), x ∈ W, for a function \(f:\mathbb {V}_{n}\rightarrow {\mathbb F}_{p}\) and \(a \in \mathbb {V}_{n}\),
Dbf(x) = f(x) − f(x + b) the derivative of f in direction b.
Then
(a) \(\widehat {D_{b}f}(0) = {\sum }_{a\in V}\widehat {D_{b}f_{a}}(0)\) for any b ∈ W,
for all a ∈ V. We may apply the same arguments to the function \(\tilde {f}(x) = f(x) + \langle v, x\rangle \) for some \(v\in \mathbb {V}_{n}\) (which has the same Walsh spectrum as f, hence \(\max _{u\in \mathbb {V}_{n}}|\widehat {\tilde {f}}(u)| = \max _{u\in \mathbb {V}_{n}}|\widehat {f}(u)|\)). Then (2) converts to
for all a ∈ V, and the claim of the lemma follows. □
With Lemma 2 we get the relation between normality and Walsh coefficient more general for functions from \(\mathbb {V}_{n}\) to \({\mathbb F}_{p}\) for arbitrary primes p.
Corollary 1
Let fbe a function from\(\mathbb {V}_{n}\)to\({\mathbb F}_{p}\). Iff is (weakly)k-normal, then\(p^{k} \le \max _{u\in \mathbb {V}_{n}}|\widehat {f}(u)|\).
Proof
Suppose that f is weakly k-normal, i.e. f(x) = 〈v, x〉 + c, for some \(v\in \mathbb {V}_{n}\), \(c\in {\mathbb F}_{p}\), and all x ∈ a + W for some k-dimensional subspace W of \(\mathbb {V}_{n}\) and some a in a complement V of W . Then, using Lemma 2 we have
For a bent function \(f:\mathbb {V}_{n}\rightarrow {\mathbb F}_{p}\), Corollary 1 implies that f can be at most ⌊n/2⌋-normal. Moreover, for bent functions in even dimension which are weakly regular but not regular the following result has been shown in [7, Theorem 6(i)]:
Proposition 2
Let nbe even, pan odd prime, and\(f:{{\mathbb F}_{p}^{n}}\rightarrow {\mathbb F}_{p}\)be a bent function. If fis weakly regular but not regular, then fis not (weakly)normal.
Hence, a weakly regular but not regular bent function in even dimension can be at most (n/2 − 1)-normal. However, whereas an arbitrary p-ary function is with high probability “highly non-normal” (see Proposition 1), many bent functions in odd characteristic are (weakly) k-normal with k as large as the theory allows. That is, many p-ary bent functions in even dimension are weakly normal, except from those which are weakly regular but not regular, of which many are n/2 − 1-normal, many p-ary bent functions in odd dimension are weakly- (n − 1)/2-normal. The following results on normality of p-ary bent functions support this observation. Note that the large classes of completed Maiorana-McFarland and PS+ bent functions (all of which members are regular bent functions in even dimension) are normal by their definition.
A quadratic bent function \(Q:\mathbb {V}_{n}\rightarrow {\mathbb F}_{p}\), p odd, is normal if n is even and Q is regular, (n/2 − 1)-normal if n is even and Q is weakly regular but not regular, and (n − 1)/2-normal if n is odd, see [7].
[13, Proposition 5] A regular bent function of the form
is normal. (For the bentness conditions see [13, Theorem 1].)
[7, Theorem 7] The regular Coulter-Matthews bent functions are normal.
The secondary construction of non-weakly regular bent functions \(f:\mathbb {V}_{n}\rightarrow {\mathbb F}_{p}\) in [4, 5], yields (weakly) normal bent functions when n is even and (weakly) (n − 1)/2-normal bent functions when n is odd.
[7, Example 1] \(f:{\mathbb F}_{3^{4}}\rightarrow {\mathbb F}_{3}\), f(x) = Tr4(ω10x22 + x4), ω primitive element of \({\mathbb F}_{3^{4}}\), is normal.
The last example presented in [11], was one of the first known examples for a non-weakly regular bent function. As pointed out in [7], the function does not have a bent dual. One may expect that this in some sense not smooth bent function exhibits a more chaotic behaviour, which however does not apply with regard to normality in this case. We here remark that differently to Boolean functions in dimension 4 (see [3]), functions from \({\mathbb F}_{3^{4}}\) to \({\mathbb F}_{3}\) which are not weakly normal do exist. Examples are the quadratic bent functions from \({\mathbb F}_{3^{4}}\) to \({\mathbb F}_{3}\) which are weakly regular but not regular, and then by Proposition 2 not weakly normal.
In general it seems not to be easy to find p-ary bent functions which do not exhibit this “typical” behaviour with regard to normality as described above. This resembles the situation for Boolean bent functions of which most standard examples are (weakly) normal. However, it has been shown that there are not (weakly) normal Boolean bent functions in every (even) dimension n ≥ 10, see [2, 14], which shows that normality is not a feature of Boolean bent functions.
We attempt to prove a different than the described behaviour with respect to normality for some p-ary bent functions. Candidates for non-weakly normal bent functions may be sporadic examples of non-weakly regular bent functions (other than the last example in the list above):
1.
\(g_{1}:{\mathbb F}_{3^{6}}\rightarrow {\mathbb F}_{3}\) with g1(x) = Tr6(ξ7x98), where ξ is a primitive element of \({\mathbb F}_{3^{6}}\), [10],
2.
\(g_{2}:{\mathbb F}_{3^{6}}\rightarrow {\mathbb F}_{3}\) with g2(x) = Tr6(ξ7x14 + ξ35x70), where ξ is a primitive element of \({\mathbb F}_{3^{6}}\), [12].
Recently, the first construction of non-weakly regular bent functions for which the dual is not bent was presented, see [8]. This construction may also provide candidates for non-weakly normal bent functions:
Let \(1,\alpha ,\beta \in {\mathbb F}_{p^{n}}\) be linearly independent over \({\mathbb F}_{p}\), and let f(x) = Trn(x2), h1(x) = Trn(αx2), h2(x) = Trn(βx2). Then the bent function \(F:{\mathbb F}_{p^{n}}{\times {\mathbb F}_{p}^{2}}\rightarrow {\mathbb F}_{p}\)
is in general non-weakly regular. As pointed out in the next section, the sporadic examples g1, g2 given as above are in fact not weakly-normal, and the construction in [8] potentially yields not weakly-normal bent functions.
3 Testing normality
It is not easy to show (weak) normality for a given function, and it is even harder to disprove (weak) normality. There is no approach known, how to prove non-weak-normality by hand. In [2, 14], to show the non-weak-normality of some Boolean bent function in dimension 10,12,14, a computer algorithm is used, see [2]. In this section, based on the principles of the algorithm for Boolean functions in [2], we develop an algorithm for p-ary functions.
Similarly as in [2] for Boolean functions, the strategy is to combine cosets of a subspace U of dimension s on which f is a fixed constant c to an affine subspace of dimension s + 1 on which f is constant c. Differently to the Boolean case, where the union of two cosets of a linear subspace U is always an affine subspace, the union of p cosets of a subspace U of \({{\mathbb F}_{p}^{n}}\) is in general not an affine subspace. Hence the algorithm in [2] does not transfer straightforward to p-ary functions. To generate a complete list of the cosets of a subspace U (without repetitions) we fix a complement Uc of U. We then get a partition of \({{\mathbb F}_{p}^{n}}\) into cosets of U as {a + U : a ∈ Uc}. We will use the following two simple lemmas for which we include the proof for the convenience of the reader.
Lemma 3
Let Ube a linear subspace of\(\mathbb {V}_{n}={{\mathbb F}_{p}^{n}}\)of dimensions < n, letUcbe a complementofU and leta1, a2,…,apbedistinct elements ofUc. Then the union
$$\bigcup_{i = 1}^{p}(a_{i}+U) $$
is an affine subspacea1 + U′of dimensions + 1, if and only if {a1, a2,…,ap} is an affine subspace {a1 + (a2 − a1)t : 0 ≤ t ≤ p − 1} ofUc. Then
$$a_{1}+U^{\prime} = a_{1} + \langle a_{2}-a_{1}\rangle + U. $$
In particular, forp = 3, \(\bigcup _{i = 1}^{p}(a_{i}+U)\)is an affine subspace if and only ifa1 + a2 + a3 = 0.
Proof
First assume that {a1, a2,…,ap} is an affine subspace which w.l.o.g. we can write as a1 + 〈a0〉 with a0 = a2 − a1. Then
Since 0≠a0 = a2 − a1 ∈ Uc implies a0∉U, the dimension of U′ := 〈a0〉 + U is s + 1.
Conversely, let the union \(\bigcup _{i = 1}^{p}(a_{i}+U) = a_{1}+U^{\prime }\) be an affine subspace for some pairwise distinct a1,…,ap ∈ Uc. Again we have a0 = a2 − a1∉U, but a2 − a1 ∈ U′. Hence we can write U′ as 〈a0〉 + U. For 1 < s ≤ p we can write the element as − a1 of U′ as as − a1 = u + ta0 for some \(t\in {\mathbb F}_{p}\) and u ∈ U. Hence γ = as − a1 − ta0 = u ∈ U. Since γ ∈ Uc we must have γ = u = 0, and hence as = a1 + ta0. □
Lemma 4
Let fbe a function from\(\mathbb {V}_{n}\)to\({\mathbb F}_{p}\)andA = a1 + U′be an affine subspace of dimensions + 1 ≤ nof\(\mathbb {V}_{n}\). Then the restriction off to Ais affine but nonconstant if and only ifU′ = 〈a0〉 + Usuch that f is constant on each coset (a1 + ta0) + Uof U, and affine (but nonconstant) ona1 + 〈a0〉.
Remark 1
The function f is then constant on the cosets a1 + ta0 + U of U, 0 ≤ t ≤ p − 1, with pairwise distinct constants for pairwise distinct 0 ≤ t1, t2 ≤ p − 1. For the special case that p =3, the condition in Lemma 4 simplifies: The function f is affine (but not constant) on a + U if and only if a + U is the union of three affine subspaces a1 + U′, a2 + U′, a3 + U′ for a subspace U′ of \({{\mathbb F}_{3}^{m}}\) of dimension s −1, such that \(f_{|(a_{1}+U^{\prime })}=c\), \(f_{|(a_{2}+U^{\prime })}=c + 1\) and f|(a3+U′) = c + 2.
Proof of the Lemma
Let f be affine on A, i.e. there exists a linear function L such that f(a1 + u′) = L(u′) + f(a1) for u′∈ U′. Since we suppose that f is not constant on A, the linear function L is not the zero-function on U′, hence has an s-dimensional kernel U in U′. We can write U′ as U′ = 〈a0〉 + U for some a0 ∈ U′∖ U, and observe that for all \(t\in {\mathbb F}_{p}\) and u ∈ U,
In particular, f is affine on a1 + 〈a0〉, and constant tL(a0) + f(a1) on a1 + ta0 + U for every fixed t.
Conversely let A = a1 + 〈a0〉 + U, and suppose that f is constant on (a1 + ta0) + U for every fixed 0 ≤ t ≤ p − 1, and affine on a1 + 〈a0〉. Then for some linear function L we have
Hence f is affine on a1 + U′. (Note that U is in the kernel of L). □
Lemma 3 and Lemma 4 suggest the following procedure to construct an affine subspace of dimension s + 1 on which \(f:{{\mathbb F}_{p}^{n}}\rightarrow {\mathbb F}_{p}\) is constant, from such affine subspaces of dimension s. For a linear subspace U of dimension s fix a complement Uc and find a1,…,ap ∈ Uc such that f is constant with the same c on all affine subspaces a1 + U,…,ap + U. If {a1,…ap} form a one-dimensional affine subspace, then take the union of those cosets. Note that this union then equals a1 + U′ with U′ = 〈U, a2 − a1〉. (In the following we use the term 1-flat for a one-dimensional affine subspace.)
×
We applied our algorithm to several known bent functions, and observed that many of them are in fact weakly k-normal with k as large as the theory allows. But we also found examples with a different behaviour. We collect some of the experimental results, which we find interesting in the following. For the first two examples we choose bent functions which have maximal possible normality. The other functions we present below do not meet the upper bound on k-normality.
I The weakly regular and not regular Coulter-Matthews bent function \(\text {Tr}_{6}(\xi ^{3} x^{{(3^{7}+ 1)/2)}})\) from \({\mathbb F}_{3^{6}}\) to \({\mathbb F}_{3}\), where ξ is a primitive element of \({\mathbb F}_{3^{6}}\), is 2-normal.
II The regular bent function in dimension 4, Tr4(ξ138x24 + ξ184x336), from \({\mathbb F}_{5^{4}}\) to \({\mathbb F}_{5}\),where ξ is a primitive element of \({\mathbb F}_{5^{4}}\), is 2-normal (Ex.7.1 in [15]).
III The weakly regular Coulter-Matthews bent function in odd dimension 7, \(\text {Tr}_{7}(\xi ^{6} x^{(3^{9}+ 1)/2)})\), where ξ is a primitive element of \({\mathbb F}_{3^{7}}\), is 2-normal but not (weakly) 3-normal.
IV The weakly regular Coulter-Matthews bent function in odd dimension 9, \(\text {Tr}_{9}(\xi ^{5} x^{(3^{11}+ 1)/2)})\), where ξ is a primitive element of \({\mathbb F}_{3^{9}}\), is 3-normal but not (weakly) 4-normal.
V The non-weakly regular bent function \(g_{1}:{\mathbb F}_{3^{6}}\rightarrow {\mathbb F}_{3}\) with g1(x) = Tr6(ξ7x98) where ξ is a primitive element of \({\mathbb F}_{3^{6}}\), is not (weakly) normal.
VI The non-weakly regular bent function \(g_{2}:{\mathbb F}_{3^{6}}\rightarrow {\mathbb F}_{3}\) with g2(x) = Tr6(ξ7x14 + ξ35x70), where ξ is a primitive element of \({\mathbb F}_{3^{6}}\), is not (weakly) normal.
VII The non-weakly regular bent function \(F:{\mathbb F}_{3^{4}}{\times {\mathbb F}_{3}^{2}}\rightarrow {\mathbb F}_{3}\) with F(x, y1, y2) = Tr4(x2) + (y1 +Tr4(ξ73x2))(y2 +Tr4(ξ76x2)), where ξ is a primitive element of \({\mathbb F}_{3^{4}}\), is not (weakly) normal.
Examples III and IV are both bent functions in odd dimension, which are not (weakly) (n − 1)/2-normal. As our experimental results indicate, being solely ((n − 1)/2 − 1)-normal seems to be the typical behaviour of Coulter-Matthews bent functions in odd dimension. To the best of our knowledge, the last three examples are the first (non-binary) examples of bent functions in even dimension (not in the class of weakly regular but not regular bent functions) which are shown to be not (weakly) normal. Though we do not see a causal relationship between bent functions without a bent dual and non-normality, we note that all functions in V,VI,VII are non-weakly regular bent functions for which the dual is not bent, see [6, 8].
Once a bent function in dimension n is known which is not (weakly) k-normal for some k, we can construct bent functions in any dimension N = n + 2s, s ≥ 1, that is not (weakly) (k + s)-normal, applying the following lemma which is a generalization of Lemma 25 in [2] for Boolean functions in dimension n and k = n/2. In particular we can construct not weakly normal (not weakly (N − 1)/2, N/2 − 1-normal) bent functions in dimension N, starting from such bent functions in dimension n.
Lemma 5
For ap-ary function\(f:{{\mathbb F}_{p}^{n}}\rightarrow {\mathbb F}_{p}\)the following properties are equivalent.
In particular,f is (weakly) normal if and only ifg is weakly normal (n even).
Proof
First suppose that f is (weakly) k-normal, and E is a k-dimensional affine subspace restricted to which f is constant (affine). Then g is constant (affine) on the (k + 1)-dimensional affine subspace \(E^{\prime } = \{(x,y,0) \,:\,x\in E, y\in {\mathbb F}_{p}\}\) of \({{\mathbb F}_{p}^{n}}{\times {\mathbb F}_{p}^{2}}\).
Conversely suppose that g is weakly (k + 1)-normal, and let E′ = w + U′, w = (w1, w2, w3), be a (k + 1)-dimensional affine subspace of \({{\mathbb F}_{p}^{n}}{\times {\mathbb F}_{p}^{2}}\) restricted to which g is constant or affine. Then for (x, y, z) ∈ E′ we have
$$ g(x,y,z) = \langle\gamma,x\rangle + \alpha y + \beta z + c $$
(4)
for some \(\gamma {\in {\mathbb F}_{p}^{n}}\), \(\alpha ,\beta ,c\in {\mathbb F}_{p}\). For \(a,b\in {\mathbb F}_{p}\) define
If \(\bar {x}\in E_{a,b}\), then \(E_{a,b} = \bar {x} + U\), where U is the subspace of \({{\mathbb F}_{p}^{n}}\) given by \(U = \{x{\in {\mathbb F}_{p}^{n}}\,:\, (x,0,0) \in U^{\prime }\}\) (straightforward). Observe that restricted to Ea, b, the function
$$ f(x)-\langle\gamma,x\rangle = \alpha a + \beta b + c - ab $$
(6)
is constant. If U has dimension k we are done. Suppose that dim(U) < k. Since E′ is the union \(\bigcup _{a,b}\{(x,a,b)\,:\,x\in E_{a,b}\}\) (some Ea, b may be the same, some the empty set), we have \(p^{k + 1} = |E^{\prime }| \le {\sum }_{a,b}|E_{a,b}|\). As we assume that dim(U) < k, this implies that dim(U) = k − 1, i.e. |Ea, b| = pk− 1 for all \((a,b){\in {\mathbb F}_{p}^{2}}\) and all Ea, b are distinct. We then define E as the disjoint union
for an element \(\bar {x}\in E\), where \(\bar {U} = \{x{\in {\mathbb F}_{p}^{n}}\,:\,(x,a,0)\in E^{\prime }\;\text {for some}\;a \in {\mathbb F}_{p}\}\), and observe that f(x) −〈γ, x〉 = βα + c is constant on this k-dimensional affine subspace. □
Combining our sporadic examples in low dimension with Lemma 5 we get the following result.
Theorem 1
There are not (weakly) normal ternary bent functions,which do not belong to the class of bent functions whichare weakly regular but not regular, in every even dimensionn ≥ 6.
We remark that since our sporadic examples, Examples V, VI, VII, are non-weakly regular bent functions for which the dual is not bent, by [8, Theorem 2] all bent functions obtained from these functions with Lemma 5 also have this property. To the best of our knowledge, no example for a regular p-ary bent function which is not (weakly) normal is known.
4 Perspectives
In this article we contribute to the analysis of k-normality for p-ary bent functions. Depending on the regularity of a bent function f from \(\mathbb {V}_{n}\) to \({\mathbb F}_{p}\) and the parity of n, many bent functions seem to be (weakly) normal, (n/2 − 1)-normal or (n − 1)/2-normal, which is drastically different from the average behaviour of a p-ary function. It seems not easy to find bent functions for which one can show a different behaviour. This resembles the situation for Boolean bent functions. We develop an algorithm for testing normality for p-ary functions. Applying this algorithm we verify that some ternary non-weakly regular bent functions in even dimension n are not weakly normal. For odd dimension n we found examples in the class of Coulter-Matthews bent functions which are not weakly (n − 1)/2-normal. With Lemma 5 we then can construct from such functions in dimension n, bent functions with the same property in any dimension n + 2s, s ≥ 1.
There are many interesting open questions on normality for p-ary bent functions. We close with a collection of some of them, which can now be attacked using our presented algorithm.
Find regular p-ary bent functions in even dimension which are not normal.
Find weakly regular but not regular p-ary bent functions in even dimension which are not (n/2 − 1)-normal.
To the best of our knowledge there are no such examples known.
Show that the weakly regular but not regular Coulter-Matthews bent functions in even dimension are (n/2 − 1)-normal or find counter-examples.
The question on the average behaviour of Boolean and p-ary bent functions with respect to normality seems not easy to be answered. Are (most) bent functions affine on affine subspaces of large dimension, or do they behave like arbitrary Boolean and p-ary functions, normal, (n/2 − 1)-normal, ((n − 1)/2)-normal bent functions are only easier to find?
Acknowledgements
Open access funding provided by Johannes Kepler University Linz. Wilfried Meidl is supported by the Austrian Science Fund (FWF) Project no. M1767-N26.
Ísabel Pirsic is supported by the Austrian Science Fund (FWF) Project no. P27351-N26.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
