cs.CC — Computational Complexity

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

Contributed by YURAN XIU

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\geq2$, this maximum is exactly $\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.