HEXAGONbeta

The Exact Junta Bound for Degree-Two Boolean Functions on q-ary Hamming Cubes

Primarily AI-generated textHuman understanding: no partscs.CC — Computational Complexity

Contributed by YURAN XIU ↗

Version 1 / Oct 17, 2026 / CC BY 4.0

Abstract

We determine the maximum number of relevant variables of a Boolean function of degree at most two on a finite alphabet. For every integer q≥2q\geq2, this maximum is exactly max⁡{4,q+1}\max\{4,q+1\}. Here degree means Hamming, or junta, degree: the function is a sum of real-valued functions, each depending on at most two coordinates. We also prove that any such function with more than four relevant variables has a selector coordinate: after that coordinate is fixed, the function depends on at most one other coordinate. The proof combines saturation on a binary four-dimensional restriction with a rigidity argument that applies to every symbol of the original alphabet. Two disjoint interactions force a four-junta; a function with more than four relevant variables has a star of interactions. The exact bound and selector theorem have been formalized in Lean 4, with transitive dependencies using only the standard axioms of Lean and mathlib.

References

  1. Yuval Filmus. Quadratic Boolean functions on the cube. Manuscript, 27 March 2022. https://yuvalfilmus.cs.technion.ac.il/Manuscripts/Degree2.pdf.link
  2. Ivan Mogilnykh and Alexandr Valyuzhenich. Equitable 2-partitions of the Hamming graphs with the second eigenvalue. Discrete Mathematics , 343(11):112039, 2020. doi:10.1016/j.disc.2020.112039 (https://doi.org/10.1016/j.disc.2020.112039). Preprint: arXiv:1903.12333 (https://arxiv.org/abs/1903.12333).arXivDOI
  3. Alexandr Valyuzhenich. An upper bound on the number of relevant variables for Boolean functions on the Hamming graph. Discrete Mathematics , 349(2):114745, 2026. doi:10.1016/j.disc.2025.114745 (https://doi.org/10.1016/j.disc.2025.114745). Preprint: arXiv:2404.10418v1 (https://arxiv.org/abs/2404.10418v1), 2024.arXivDOI
  4. Alexandr Valyuzhenich. An upper bound on the number of relevant variables in a bounded degree Boolean function on the Hamming graph. arXiv:2609.12540v1 (https://arxiv.org/abs/2609.12540v1), 2026.arXiv

Version history

  1. v1Submitted by YURAN XIUInitial depositCurrentOct 17, 2026