A Note on a Conjecture for Balanced Elementary Symmetric Boolean Functions

DOI10.1109/TIT.2012.2215576zbMATH Open1364.94807arXiv1203.1418WikidataQ123247486 ScholiaQ123247486MaRDI QIDQ2989494FDOQ2989494

Authors: Wei Su, Xiaohu Tang, Alexander Pott 

Publication date: 8 June 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: In 2008, Cusick {it et al.} conjectured that certain elementary symmetric Boolean functions of the form $sigm{a}_{2^{t+1}l-1,2^t}$ are the only nonlinear balanced ones, where $t$, $l$ are any positive integers, and $$ for positive integers $n$, $1ledlen$. In this note, by analyzing the weight of $sigm{a}_{n,2^t}$ and $sigm{a}_{n,d}$, we prove that $mwt(sigm{a}_{n,d})<2^{n-1}$ holds in most cases, and so does the conjecture. According to the remainder of modulo 4, we also consider the weight of $sigm{a}_{n,d}$ from two aspects: $nequiv3(mmod4)$ and $notequiv3(mmod4)$. Thus, we can simplify the conjecture. In particular, our results cover the most known results. In order to fully solve the conjecture, we also consider the weight of $sigm{a}_{n,2^t+2^s}$ and give some experiment results on it.

Full work available at URL: https://arxiv.org/abs/1203.1418

Mathematics Subject Classification ID

Cited In (11)

• Asymptotic behavior of perturbations of symmetric functions
• One sufficient and necessary condition on balanced Boolean functions with \(\sigma_{f} = 2^{2n} + 2^{n+3}\) \((n \geq 3)\)
• Hamming weights of symmetric Boolean functions
• Sensitivities and block sensitivities of elementary symmetric Boolean functions
• A divisibility approach to the open boundary cases of Cusick-Li-Stǎnicǎ's conjecture
• New families of balanced symmetric functions and a generalization of Cusick, Li and Stǎnicǎ's conjecture
• Exact 2-divisibility of exponential sums associated to Boolean functions
• The Degree of Balanced Elementary Symmetric Boolean Functions of <formula formulatype="inline"> <tex Notation="TeX">${{\bf 4k}+{\bf 3}}$</tex> </formula> Variables
• Certificate complexity of elementary symmetric Boolean functions
• Modular periodicity of exponential sums of symmetric Boolean functions
• Generalized exponential sums and the power of computers

This page was built for publication: A Note on a Conjecture for Balanced Elementary Symmetric Boolean Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989494)