Three basic questions on Boolean functions

In a first part of this paper, we investigate those Boolean functions satisfying two apparently related, but in fact distinct conditions concerning the algebraic degree:

1. we study those Boolean functions $f$ whose restrictions to all affine hyperplanes have the same algebraic degree (equal to $deg(f)$ , the algebraic degree of $f$ ),

2. we study those functions whose derivatives $D_af(x)=f(x)+ f(x+a)$ , $a≠ 0$ , have all the same (optimal) algebraic degree $deg(f)-1$ .

For determining to which extent these two questions are related, we find three classes of Boolean functions: the first class satisfies both conditions, the second class satisfies the first condition but not the second and the third class satisfies the second condition but not the first. We also give for any fixed positive integer $k$ and for all integers $n$ , $p$ , $s$ such that $p≥q k+1$ , $s≥q k+1$ and $n≥q ps$ , a class (denoted by $C_{n,p,s}$ ) of functions whose restrictions to all $k$ -codimensional affine subspaces of ${\Bbb F}_2^n$ have the same algebraic degree as the function.

In a second part of the paper, we introduce the notion of second-order-bent function, whose second order derivatives $D_aD_bf(x)=f(x)+f(x+a)+f(x+b)+f(x+a+b)$ , $a≠ 0, b≠ 0, a≠ b$ , are all balanced. We exhibit an example in 3 variables and we prove that second-order-bent functions cannot exist if $n$ is not congruent with 3 mod 4. We characterize second-order-bent functions by the Walsh transform, state some of their properties and prove the non existence of such functions for algebraic degree 3 when $n>3$ . We leave open the question whether second-order-bent functions can exist for $n$ larger than $3$ .