The Exact Junta Bound for Degree-Two Boolean Functions on q-ary Hamming Cubes
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00301
curl -X POST /api/v1/records/hexagon/2610.00301/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00301/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'