# American Institute of Mathematical Sciences

doi: 10.3934/amc.2020136

## The lower bounds on the second-order nonlinearity of three classes of Boolean functions

 College of Mathematics and Computer Science, Key Laboratory of Information Security of Network Systems, Fuzhou University, Fuzhou 350108, China

* Corresponding author: Qian Liu

Received  October 2020 Revised  January 2021 Published  March 2021

Fund Project: This work was supported by Educational Research Projects of Young and Middle-aged Teachers in Fujian Province (No. JAT200033) and the Talent Fund project of Fuzhou University (No. 0030510858)

In this paper, by calculating the lower bounds on the nonlinearity of the derivatives of the following three classes of Boolean functions, we provide the tight lower bounds on the second-order nonlinearity of these Boolean functions: (1) $f_1(x) = Tr_1^n(x^{2^{r+1}+2^r+1})$, where $n = 2r+2$ with even $r$; (2) $f_2(x) = Tr_1^n(\lambda x^{2^{2r}+2^{r+1}+1})$, where $\lambda \in \mathbb{F}_{2^r}^*$ and $n = 4r$ with even $r$; (3) $f_3(x,y) = yTr_1^n(x^{2^r+1})+Tr_1^n(x^{2^r+3})$, where $(x, y)\in \mathbb{F}_{2^n}\times \mathbb{F}_2$, $n = 2r$ with odd $r$. The results show that our bounds are better than previously known lower bounds in some cases.

Citation: Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, doi: 10.3934/amc.2020136
##### References:

show all references

##### References:
The Walsh spectrum of $f$
 $W_f(\omega)$ Number of $\omega$ 0 $2^n-2^{n-k}$ $2^{\frac{n+k}{2}}$ $2^{n-k-1}+(-1)^{f(0)}2^{\frac{n-k-2}{2}}$ $-2^{\frac{n+k}{2}}$ $2^{n-k-1}-(-1)^{f(0)}2^{\frac{n-k-2}{2}}$
 $W_f(\omega)$ Number of $\omega$ 0 $2^n-2^{n-k}$ $2^{\frac{n+k}{2}}$ $2^{n-k-1}+(-1)^{f(0)}2^{\frac{n-k-2}{2}}$ $-2^{\frac{n+k}{2}}$ $2^{n-k-1}-(-1)^{f(0)}2^{\frac{n-k-2}{2}}$
Comparison of the lower bound on second-order nonlinearity with the known results
 $n$ bound in [19] bound in [9] bound in [11] bound in [15] Our new bound in Theorem 3.6 8 62 63 64 38 80 16 28615 24561 28672 26974 29815 24 8125467 7339906 8126464 8017875 8202293 32 2130690153 2013264900 2130706432 2123757059 2135604974 40 548681810337 532575936520 548682072064 548237313548 548996316833
 $n$ bound in [19] bound in [9] bound in [11] bound in [15] Our new bound in Theorem 3.6 8 62 63 64 38 80 16 28615 24561 28672 26974 29815 24 8125467 7339906 8126464 8017875 8202293 32 2130690153 2013264900 2130706432 2123757059 2135604974 40 548681810337 532575936520 548682072064 548237313548 548996316833
Comparison of the lower bound on second-order nonlinearity with the known results for odd $r$
 $r$ 1 3 5 7 9 11 13 bound in [4] 0 19 662 13487 238971 4008935 65625942 Our new bound in Theorem 3.9 1 32 763 14309 245641 4062737 66058274
 $r$ 1 3 5 7 9 11 13 bound in [4] 0 19 662 13487 238971 4008935 65625942 Our new bound in Theorem 3.9 1 32 763 14309 245641 4062737 66058274
 [1] Simone Fiori, Italo Cervigni, Mattia Ippoliti, Claudio Menotta. Synthetic nonlinear second-order oscillators on Riemannian manifolds and their numerical simulation. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021088 [2] Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184 [3] Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050 [4] Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709 [5] Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018 [6] Raimund Bürger, Christophe Chalons, Rafael Ordoñez, Luis Miguel Villada. A multiclass Lighthill-Whitham-Richards traffic model with a discontinuous velocity function. Networks & Heterogeneous Media, 2021, 16 (2) : 187-219. doi: 10.3934/nhm.2021004 [7] Anton Schiela, Julian Ortiz. Second order directional shape derivatives of integrals on submanifolds. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021017 [8] Huan Zhang, Jun Zhou. Asymptotic behaviors of solutions to a sixth-order Boussinesq equation with logarithmic nonlinearity. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021034 [9] Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2619-2633. doi: 10.3934/dcds.2020377 [10] Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247 [11] Dayalal Suthar, Sunil Dutt Purohit, Haile Habenom, Jagdev Singh. Class of integrals and applications of fractional kinetic equation with the generalized multi-index Bessel function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021019 [12] Davide La Torre, Simone Marsiglio, Franklin Mendivil, Fabio Privileggi. Public debt dynamics under ambiguity by means of iterated function systems on density functions. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021070 [13] Saima Rashid, Fahd Jarad, Zakia Hammouch. Some new bounds analogous to generalized proportional fractional integral operator with respect to another function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021020 [14] Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3651-3682. doi: 10.3934/dcds.2021011 [15] Akane Kawaharada. Singular function emerging from one-dimensional elementary cellular automaton Rule 150. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021125 [16] Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027 [17] Elimhan N. Mahmudov. Second order discrete time-varying and time-invariant linear continuous systems and Kalman type conditions. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021010 [18] Alberto Ibort, Alberto López-Yela. Quantum tomography and the quantum Radon transform. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021021 [19] Tomoyuki Tanaka, Kyouhei Wakasa. On the critical decay for the wave equation with a cubic convolution in 3D. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021048 [20] Ian Schindler, Kyril Tintarev. Mountain pass solutions to semilinear problems with critical nonlinearity. Conference Publications, 2007, 2007 (Special) : 912-919. doi: 10.3934/proc.2007.2007.912

2019 Impact Factor: 0.734

## Tools

Article outline

Figures and Tables