Sidon sets, thin sets, and the nonlinearity of vectorial Boolean functions
Gábor P. Nagy · Journal of Combinatorial Theory Series A · 2024
The vectorial nonlinearity of a vector-valued function is its distance from the set of affine functions. In 2017, Liu, Mesnager, and Chen conjectured a general upper bound for the vectorial linearity. Recently, Carlet established a lower bound in terms of differential uniformity. In this paper, we improve Carlet's lower bound. Our approach is based on the fact that the level sets of a vectorial Boolean function are thin sets. In particular, level sets of APN functions are Sidon sets, hence the Liu-Mesnager-Chen conjecture predicts that in F 2 n , there should be Sidon sets of size at least 2 n / 2 + 1 for all n . This paper provides an overview of the known large Sidon sets in F 2 n , and examines the completeness of the large Sidon sets derived from hyperbolas and ellipses of the finite affine plane.