Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 4 min ago
PreprintCC BY 4.0arXiv

The Maximum Nonlinearity of 8-variable Balanced Boolean Functions is 116

  • Yueying Lou
  • Youle Xu
  • Qichun Wang
Open at sourcePDFDOICite

Abstract

Does there exist an 8-variable balanced Boolean function with nonlinearity 118? This is a famous and long-standing open problem in Boolean functions. In this paper, we give a negative answer to this open problem, and prove that the maximum nonlinearity of balanced Boolean functions in 8 variables is 116, establishing the 8-variable instance of Dobbertin's conjectured recursion for the minimum Walsh peak of balanced functions. Equivalently, the covering radius of the Reed--Muller code RM(1,8) in 0-resilient Boolean functions is 116. We deduce the result by obtaining a quadratic form of polar rank 6, and reducing the problem to the existence of a 6-variable Boolean function with nonlinearity greater than 26 whose Hamming distance to a bent function is between 4 and 6.

Related

  1. On balanced subfamilies of maximum complement-free families in the middle layer of the Boolean lattice
    Sa'ul A. Blanco
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Bi-balanced shifts and variable specification
    Soonjo Hong, Minkyu Kim
    arXivPreprintCC BY 4.0Full textDynamical systemsarXiv
  3. CRANDALL-PAZY RIGIDITY FOR LOWER SEMICONTINUOUS CONVEX FUNCTIONS: A BALANCED MEDIAN-FLOW ARGUMENT
    Julien Bernis
    HALPreprintPublisher termsFull textOptimisation & controlHAL
  4. On the Fourier Entropy-Influence Conjecture for Boolean Plateaued Functions
    Vladimir N. Potapov
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Tameness of transitive Boolean functions
    Xinyu Long
    arXivPreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{lou2026maximum,
  title = {{The Maximum Nonlinearity of 8-variable Balanced Boolean Functions is 116}},
  author = {Yueying Lou and Youle Xu and Qichun Wang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.17897},
  eprint = {2610.17897},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.17897},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The Maximum Nonlinearity of 8-variable Balanced Boolean Functions is 116
AU  - Yueying Lou
AU  - Youle Xu
AU  - Qichun Wang
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2610.17897
UR  - https://arxiv.org/abs/2610.17897
AB  - Does there exist an 8-variable balanced Boolean function with nonlinearity 118? This is a famous and long-standing open problem in Boolean functions. In this paper, we give a negative answer to this open problem, and prove that the maximum nonlinearity of balanced Boolean functions in 8 variables is 116, establishing the 8-variable instance of Dobbertin's conjectured recursion for the minimum Walsh peak of balanced functions. Equivalently, the covering radius of the Reed--Muller code RM(1,8) in 0-resilient Boolean functions is 116. We deduce the result by obtaining a quadratic form of polar rank 6, and reducing the problem to the existence of a 6-variable Boolean function with nonlinearity greater than 26 whose Hamming distance to a bent function is between 4 and 6.
ER  -