Nondegenerate functions and permutations (Q674920)

A Boolean function \(f(x_1, \dots, x_n)\) is called degenerate if for all \(x_i, \dots, x_n\in \{0,1\}^n\) \[ f(x_1, \dots, x_i, \dots, x_n) =f(x_1, \dots, x_i+1, \dots, x_n); \] otherwise \(f\) is said to be nondegenerate. The author proves that nondegeneracy in Boolean function can be verified in linear time on average. If for a Boolean function \(f(x_1, \dots, x_n)\) the equation \(|\{X: f(X) =1\), \(X\in \{0,1\}^n\} |= 2^{n-1}\) holds than the author proves that, on average, at least \(n-\lceil \log n \rceil- 2\) variables must be held constant before a degenerate subfunction is induced. A function \(F:\{0,1\}^n \to\{0,1\}^n\) is called an \((n,n)\)-bit function, and is nondegenerate if for all \(i\) the \(i\)-th bit of \(F\) is realized by the nondegenerate Boolean function. Let \(N^{n,n}\) be the set of invertible nondegenerate \((n,n)\)-bit function, the author derives bounds \(L_n\), \(U_n \in 0(1)\) such that \(1-L_n <{|N^{n,n} |\over 2^n!} <1-L_n+ U_n\).