On the continuation to bent functions and upper bounds on their number

S. V. Agievich

Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 18-21

Résumé

A Boolean bent function $f$ of $n$ variables is a continuation of a Boolean function $g$ of $k$ variables if $g$ is a restriction of $f$ to a fixed affine plane of dimension $k$. We prove that a continuation always exists if $k\leq n/2$. We obtain an upper bound for the number of continuations. The bound is strengthened in the case $k=n-1$, when $g$ is a near-bent function. As a result, we improve the known upper bounds for the number of bent functions. More precisely, we show that for even $n\geq 6$ there are no more than $$ c_n 2^{2^{n-2}-n/2+5/2} \left(\frac{B(n/2,n-1)-B(n/2-1,n-1)}{2^{2^{n/2}-n/2-1}} +B(n/2-1,n-1)\right) $$ bent functions of $n$ variables. Here $c_n=\exp(-1/2+23/(18\cdot 2^{n-2}))/\sqrt{\pi}$ and $B(d,n)=2^{\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{d}}$.

Détail

Keywords: bent function, number of bent functions, near-bent function, affine plane.