Generalized Bent Functions Philippe Langevin

Abstract. In this paper, we compare the the binary bent functions and the generalized bent functions on the metric and degree points of view. We give an upperbound on the covering radius of the affine Reed-Muller codes defined over a finite and commutative ring. The paper ends by a bound on the degree of a generalized bent function.

1. Introduction

In his paper “On bent functions” [7], O. Rothaus studied the functions from 𝔽_{2}^{m} into 𝔽_{2} which the Fourier transform have constant magnitude. In fact, such functions exist if and only if m is an even integer. In this case, they are at maximal distance from the first order Reed-Muller code and it may be the reason why he called them the “bent functions”. Moreover, he proved that for any integer t within the range [2, \frac{m}{2}], there are bent functions of degree exactly t.

Later, the paper [4] of P. V. Kumar, R. A. Scholtz and L. R. Welch defined the generalized bent functions to be the maps from (Z/_{qZ})^{m} into Z/_{qZ} such that their Fourier transform with respect to an one-to-one character have also constant magnitude. As in the binary case, the non-degenerate quadratic forms provide a family of generalized bent functions. But the autors gave precise existence criterions and built some of them in all the existence cases.

Here, we want to compare the bent functions and the generalized bent functions on the metric point of view and on the algebraic point of view. Namely,

• Are the generalized bent functions really bent?

• What about the degree of generalized bent functions ?

2. Affine Reed-Muller Codes

Let A be a commutative and finite ring. The full space of maps from A^{m} into A is a metric space provided of

dist(f, g) = wt(f − g) (1)

where wt(h) = ♯{x ∈ A^{m} | f(x) ≠ 0}. The affine Reed-Muller code with m variables, denoted by RM_{A}(m), is the A-module of the affine maps from A^{m} into A. The covering radius of RM_{A}(m) is the smallest integer r such that an union of spheres centered arround some points of RM_{A}(m) cover the full space of functions, let us denote it by ρ_{A}(m) :

(2) ρ_{A}(m) = sup_{f} dist(f, RM_{A}(m)) = sup_{f} inf_{h∈RM_{A}(m)} dist(f, h).

3. Generalized Bent Functions

Let χ be an additive character of Z/_{qZ}. The Fourier transform of a map f from (Z/_{qZ})^{m} into Z/_{qZ} at the point z with respect to χ is

f̂_{χ}(z) = ∑_{x∈(Z/_{qZ})^{m}} χ(f(x) − z.x), (3)

where z.x is the usual dot product over (Z/_{qZ})^{m}. In fact, f̂_{χ}(z) must be seen as the Fourier transform of the function χ ∘ f (denoted by f_{χ}) at the character χ_{z}: x ↦ χ(z.x). A generalized bent function is a map such that

there exists a one-to-one character χ of (Z/_{qZ}, +) which satisfies :

∥f̂_{χ}(z)∥ = \sqrt{q^{m}}, ∀z ∈ (Z/_{qZ})^{m}. (4)

One can prove that does not depend on the choice of the one-to-one character χ. If f is a boolean bent function then it is a generalized bent function and there exists an another boolean function g such that :

f̂_{χ}(z) = χ(g(z))\sqrt{2^{m}} (5)

But in the general case, it is not true and we say that a generalized bent function f is regular at the point z if there exists g(z) ∈ (Z/_{qZ}) such that

f̂_{χ}(z) = χ(g(z))\sqrt{q^{m}}. (6)

A generalized bent function which is regular at every point of (Z/_{qZ})^{m} is said to be a regular generalized bent function.

4. Upper bound on ρ_{A}(m)

Let us suppose A is a finite and commutative ring with q elements. An additive character χ of A is said non-degenerate if the greatest ideal contained in its kernel is (0). For example, if A is a field then all the nontrivial characters are non-degenerate, and if A is the ring Z/_{qZ} then there are ϕ(q) non-degenerate characters. In what follows n(A) denotes the number of non-degenerate characters of A. If n(A) > 0 then A is a quasi-Fröbenius ring and, in this case, n(A) is equal to the number of invertible elements of A. Moreover, these characters satisfy :

Lemma 4.1. If χ is a non-degenerate character of A then

∑_{a∈A^{m}} |f̂_{χ}(a)|^{2} = q^{2m}.

Proof. Since χ is a non-degenerate character, a ↦ χ_{a} decribes the full set of characters of A^{m} when a runs over A^{m}. Hence, the lemma follows from the Parseval identity :

∑_{ψ∈Â^{m}} |f̂(ψ)|^{2} = q^{m} ∑_{x∈A^{m}} |f(x)|^{2} = q^{2m}.

For any map f from A^{m} into A, SF(f, a, b) denotes the sum :

SF(f, a, b) = ∑_{χ≠1} f̂_{χ}(a)χ̄(b).

It is easy to prove that these exponentials sums have the properties :

∑_{b∈A} SF(f, a, b) = 0 (7)

the distance between f and the affine map a.x + b is equal to

(q − 1)q^{m−1} − \frac{1}{q}SF(f, a, b). (8)

which is useful to show :

4. UPPER BOUND ON ρ_{A}(m) 5

Theorem 4.1. The covering radius of the affine Reed-Muller code with m variables over the ring A satisfies the inequality

ρ_{A}(m) ≤ (q − 1)q^{m−1} − \frac{\sqrt{n(A)}}{q(q − 1)}q^{\frac{m}{2}}

Where n(A) is the number of non-degenerated characters of A : the order of A^{×} if A is quasi-Fröbenius and 0 otherwise.

Here we want to point out that this upperbound deals with the ring structure of A. On one hand, the additive characters involves the additive structure and on the other hand the notion of non degenerate characters involves the multiplicative structure.

Proof. Let us consider the sum Σ(f) defined by :

Σ(f) = ∑_{b∈A,a∈A^{m}} ∥S(f, a, b)∥^{2}. (9)

one has :

Σ(f) = ∑_{a∈A^{m}} ∑_{χ≠1,ψ≠1} f̂_{χ}(a)f̂ψ̄(a) ∑_{b∈A} χ(b)ψ̄(b)

= q ∑_{χ≠1} ∑_{a∈A^{m}} ∥f̂_{χ}(a)∥^{2}

and by Lemma (4.1) we get :

Σ(f) ≥ q n(A) q^{2m}

looking at the average of the terms of this sum, we deduce that there exists an ordered pair (a, b) ∈ A^{m} × A such that :

|S(f, a, b)| ≥ \sqrt{n(A)}q^{m/2}.

(i) If S(f, a, b) ≥ 0 then :

d(f, ax + b) ≤ (q − 1)q^{m−1} − \frac{\sqrt{n(A)}}{q}q^{m/2}.

(ii) Otherwise, we use the property (7) to get :

∑_{c≠b} S(f, a, b) ≥ \sqrt{n(A)}q^{m/2}

Once time more, there is a term of the LHS greater or equal to the average and so, there exists c ∈ A such that :

S(f, a, c) ≥ \frac{\sqrt{n(A)}}{(q − 1)}q^{m/2}.

that is :

d(f, ax + b) ≤ (q − 1)q^{m−1} − \frac{\sqrt{n(A)}}{q(q − 1)}q^{m/2}.

The two equalities (i) and (ii) lead to the result.

Proposition 4.1. Let f be a perfect non-linear function, that is :

f_{χ} × f_{χ}(z) = ∑_{x∈A^{m}} f_{χ}(x)fχ̄(x + z) = 0, ∀z ∈ A^{m} − 0.

Then :

d(f, RM_{A}(m)) ≤ (q − 1)q^{m−1} − \frac{1}{q}\sqrt{q − 1}q^{m/2}.

Proof. We have

Σ(f) = q(q − 1)q^{2m}

and the proof follows as in the preceding theorem.

Open problems :

• What are the values-distributions of the generalized bent functions ?

• Find a good minoration of the distance from a generalized bent func-

tions to the affine Reed-Muller codes. A good answer for one of these two problems is a alternative way to solve the existence questions of the Hadamard circulant matrix. Indeed, with any such a matrix we can associate a generalized bent function (of dimension 1) satisfying :

(1) f_{χ} takes only the two values −1 and +1, and that is probably not enougth for a bent function.

(2) the distance between f and the affine Reed-Muller code is at most \frac{q}{2}, and that is probably too small.

5. Distance from a bent function to RM_{F_{p}}(m)

From now on, we suppose that p is prime number, p ≠ 2. In her paper [6], K. Nyberg calculated the distance from a generalized bent function to the affine Reed-Muller code over F_{p}. Here, we propose to show the usefulness of the property (8) to caltulate the distance between a generalized bent function and any hyperplan. The method is very pleasant but the results have to be seen as a slight precision of [6]. Let f be a generalized bent

function over F_{p}. First, from the property (8) the distance from f to the affine map x ↦ x.u + b is

d(f, u.x + b) = (p − 1)p^{m−1} − \frac{1}{p}SF(f, u, b)

but here, SF(f, u, b) takes the wonderful form

SF(f, u, b) = ∑_{ψ≠1} f̂_{ψ}(u)ψ̄(b) = tr_{Q(ζ_{p})/Q}(f̂_{χ}(u)χ̄(b)) (10)

where χ is a non-trivial character and ζ_{p} is a primitive (p − 1)th root of unity. Because the automorphism z ↦ z̄ is in the decomposition group of p in Q(ζ_{p}), it follows from [4] that :

f̂_{χ}(u) = λ(u)\sqrt{p}^{m}

5. DISTANCE FROM A BENT FUNCTION TO RM_{F_{p}}(m) 7

where λ(u) is a root of unity. When m is even λ(u) is Q(ζ_{p}) and when m is odd, the Gauss’s quadratic sum

∑_{k=0}^{p−1} ζ_{p}^{k^{2}} = θ\sqrt{p}

where

θ = \begin{cases}1, & if p ≡ 1[4]; \\ i, & if p ≡ 3[4]; \end{cases}

shows that \frac{λ(u)}{θ} is a root of unity in Q(ζ_{p}). Now, we are able to evaluate the trace (10), and we get the complete distances distribution between a generalized bent function and the set of hyperplanes.

Proposition 5.1. Suppose that m is even. When b runs over F_{p} then

SF(f, u, b) = \begin{cases}−p^{\frac{m}{2}} , & p − 1 times; \\ (p − 1)p^{\frac{m}{2}} , & 1 time. \end{cases}

If f is regular at u.

SF(f, u, b) = \begin{cases}p^{\frac{m}{2}} , & p − 1 times; \\ −(p − 1)p^{\frac{m}{2}} , & 1 time. \end{cases}

If f is not regular at u.

Proof. We have to evaluate (10) :

SF(f, u, b) = tr_{Q(ζ_{p})/Q}(f̂_{χ}(u)χ̄(b))
= p^{\frac{m}{2}} tr_{Q(ζ_{p})/Q}(λ(u)ζ_{p}^{−b})

• If f is regular at u there exists one and only one b such that

λ(u) = ζ_{p}^{b}

and we get

tr_{Q(ζ_{p})/Q}(λ(u)ζ_{p}^{−b}) = \begin{cases}p − 1, & if λ(u) = ζ_{p}^{b}; \\ −1, & otherwise. \end{cases}

• If f is not regular at u there exists one and only one b such that

−λ(u) = ζ_{p}^{b}

and we get

tr_{Q(ζ_{p})/Q}(λ(u)ζ_{p}^{−b}) = \begin{cases}1 − p, & if λ(u) = −ζ_{p}^{b}; \\ 1, & otherwise. \end{cases}

Proposition 5.2. Suppose that m is odd. When b runs over F_{p} then

SF(f, u, b) = \begin{cases}−p^{\frac{m+1}{2}} , & \frac{p−1}{2} times; \\ 0, & 1 time; \\ p^{\frac{m+1}{2}} , & \frac{p−1}{2} times; \end{cases}

Proof. Denote by K the field Q(θ\sqrt{p}) and by L the field Q(ζ_{p}). We know the following inclusions of fields

Q ⊆ K ⊆ L

Let R and N be respectively the sets of squares and not squares in F_{p}^{∗}, and let us set :

R = ∑_{s∈R} ζ_{p}^{s} N = ∑_{s∈N} ζ_{p}^{s}

From the Gauss’s quadratic sum we deduce that :

R = θ\sqrt{p} − \frac{1}{2} N = −θ\sqrt{p} − \frac{1}{2}

Moreover the galois group of L/K is the set of automorphisms σ_{s}, s ∈ R and thus :

tr_{L/K}(ζ_{p}^{s}) = \begin{cases}R, & if s ∈ R; \\ p − \frac{1}{2}, & if s = 0; \\ N, & if s ∈ N. \end{cases}

Now, we are able to calculate SF(f, u, b) :

SF(f, u, b) = p^{[ \frac{m}{2} ]}tr_{L/Q}(λ(u)\sqrt{p}ζ_{p}^{−b})

= p^{[ \frac{m}{2} ]}tr_{K/Q}(θ\sqrt{p}tr_{L/K}(\frac{λ(u)}{θ}ζ_{p}^{−b}))

Let ϵ = 1 or −1 according whether to \frac{λ(u)}{θ} is or is not a p-root of unity. • There are exactely \frac{p−1}{2} b’s such that

ϵ\frac{λ(u)}{θ}ζ_{p}^{−b} ∈ ζ_{p}^{R}

For which :

SF(f, u, b) = ϵθ^{2}p^{[ \frac{m}{2} ]+1}.
• There are exactely \frac{p−1}{2} b’s such that

ϵ\frac{λ(u)}{θ}ζ_{p}^{−b} ∈ ζ_{p}^{N}

For which :

SF(f, u, b) = −ϵθ^{2}p^{[ \frac{m}{2} ]+1}.

• There is one and only one b such that

ϵ\frac{λ(u)}{θ}ζ_{p}^{−b} = 1

For which :

SF(f, u, b) = 0.

Theorem 5.1. The covering radius of the affine Reed-Muller code with m variables over the prime field F_{p} satisfies the inequalities

(p − 1)p^{m−1} − p^{[ \frac{m−1}{2} ]} ≤ ρ_{F_{p}}(m) ≤ (p − 1)p^{m−1} − \frac{1}{1\sqrt{p − 1}}p^{\frac{m}{2} −1}

Proof. The RHS is a straightforward application of the section 4. The lower bound is obtained building generalized bent functions that are not regular, for example :

f(x_{1}, x_{2}, …, x_{m}) = sx_{1}^{2} + x_{2}^{2} + … + x_{m}^{2},

where s is not a square of F_{p}.

This permit us to answer partly to the first question. A generalized bent function over a prime field is at maximal distance from the affine Reed-Muller codes RM_{F_{p}}(m) when m = 1 and when m = 2 provided it is not regular.

6. Degree of generalized bent functions

Once more, we work with the prime case. A good reason for is that we do not know if the generalized bent functions over Z/_{qZ} are polynomial or not. Let S be a subset of F_{p}^{m}. We denote by 1_{S} the indicating function of

S. That is the map with codomain F_{p} defined by :

1_{S}(x) = \begin{cases}1, & if x ∈ P; \\ 0, & otherwise. \end{cases}

Proposition 6.1. Let f be a generalized bent function and let S be an affine subspace of dimension k, k ≥ \frac{m}{2} + 2, then f is orthogonal with 1_{S}.

Proof. Let b ∈ F_{p}, and denote by n(b) the number of s ∈ S which satisfy f(x) = b.

as usual, n(b) evaluate by means of characters :

p n(b) = ∑_{s∈S} ∑_{χ∈F̂_{p}} χ(f(s) − b)

so

n(b) = p^{k−1} − \frac{1}{p} ∑_{χ≠1} χ(f(s) − b)

and the Poisson formula gives :

∑_{s∈S} χ(f(s)) = p^{k−m} ∑_{t∈S^{⊥}} f̂_{χ}(t)

The ideal decomposition of (p) is in Z(ζ_{p})p is (p) = P^{(p−1)} where P is the prime principal ideal (1 − ζ_{p}). Since the automorphism z ↦ z̄ is in the decomposition group of P, the P -adic valuation of f̂_{χ}(s) is :

ν_{P} (f̂_{χ}(s)) = (p − 1)\frac{m}{2}

and

ν_{P} (p^{k−m−1} ∑_{t∈S^{⊥}} f̂_{χ}(t)χ̄(b)) ≥ (k − m − 1)(p − 1) + (p − 1)\frac{m}{2}

≥ (p − 1)(k − \frac{m}{2} − 1)

and because the dimension of S is great enougth :

> (p − 1)

Therefore, the integer n(b) has a positive p-adic valuation. On an other hand,

f.1_{S} = ∑_{b∈F_{p}} n(b) = 0 [p]

and the vectors f and 1_{S} are orthogonal each other.

This combined with the proposition of P. Delsarte [1] which states that the indicating functions of affine spaces of dimension k spans the Reed-Muller code of order (p − 1)(m − k), give :

Corollary 6.1. If f is a generalized bent function then

deg(f) ≤ (p − 1)(t + 1)

Proof. Let r be the smallest integer than \frac{m}{2} + 1. Assume m = 2t + 1 or m = 2t, then r = t + 1.The function f lies in the dual of the space spaned by the indicating functions of the affine spaces of dimensions r :

f ∈ RM_{F_{p}}((p − 1)(m − r), m)^{⊥}

But the dual of RM_{F_{p}}((p − 1)r, m) is RM_{F_{p}}((p − 1)r − 1, m) (see [5]) and thus

deg(f) ≤ (p − 1)t + 2p − 3.

Bibliography

[1] Delsarte P., Goethals J. M. ,Mac Williams F. J. . On generalized Reed-Muller Codes and their relatives. Information and Control, 16:403–443, 1970.

[2] Hua L. K. Introduction to number theory. Springer-Verlag, 1982.

[3] Ireland L., Rosen M. A Classical Introduction to Modern Number Theory, volume 84 of Graduate Texts in Mathematics. Springer-Verlag.

[4] Kumar P.V., Scholtz R.A., Welch L.R. Generalized bent functions and their properties. Journal of Combinatorial Theory (A), 40:90–107, 1985.

[5] MacWilliams F. J., Sloane N. J. A. The Theory of Error-Correcting Codes, volume 16 of Mathematical Library. North-Holland, 1977.

[6] Nyberg K. Constructions of bent functions and differerence sets. 1989.

[7] Rothaus O. S. On bent functions. Journal of Combinatorial Theory (A), 20:300–305, 1976.