HEXAGONbeta

Derivative controls and Boolean completion in the relevant-variable recurrence

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Ricardo Pinho

Version 3 / Oct 31, 2026 / CC BY 4.0

Abstract

We give the unrefereed bound C44<2.0417086280C_{44}<2.0417086280 for the number of relevant variables of a Boolean function of real degree dd, r(f)≤C442dr(f)\le C_{44}2^d. The argument bounds the number of coordinates controlling a ternary derivative, exploits its dictator branches and Boolean completion, and propagates local-degree caps. The small-degree inputs are R4=22R_4=22, R5≤50R_5\le50, and R6≤109R_6\le109. The quartic proof uses an exact calculation on Rasoolzadeh's published cubic catalogue; the remaining finite arithmetic is rational. The lower bound remains 3/23/2. There has been no independent human review or formalization.

Provenance statement

Analysis and proof drafting by AI agents under my direction; I reviewed the results at summary level. AI agents also prepared certificates, checking software, and publication materials. No line-by-line human verification is claimed. AI is not an author.

References

  1. E. S. Barnes and G. E. Wall, Some extreme forms defined in terms of Abelian groups, J. Austral. Math. Soc. 1 (1959), 47--63; doi:10.1017/S1446788700025064 (https://doi.org/10.1017/S1446788700025064).DOI
  2. M. Broué and M. Enguehard, Une famille infinie de formes quadratiques entières; leurs groupes d'automorphismes, Ann. Sci. École Norm. Sup. (4) 6 (1973), 17--51; doi:10.24033/asens.1241 (https://doi.org/10.24033/asens.1241).DOI
  3. C. Carlet, Identifying codewords in general Reed--Muller codes and determining their weights, AIMS Mathematics 9 (2024), 10609--10637, Section 2; doi:10.3934/math.2024518 (https://doi.org/10.3934/math.2024518).DOI
  4. J. Chiarelli, P. Hatami and M. Saks, An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function, Combinatorica 40 (2020), 237--244; https://arxiv.org/abs/1801.08564.link
  5. T. Kasami and N. Tokura, On the weight structure of Reed--Muller codes, IEEE Trans. Inform. Theory 16 (1970), 752--759; doi:10.1109/TIT.1970.1054545 (https://doi.org/10.1109/TIT.1970.1054545). The below-two weight result is also credited to E. R. Berlekamp and N. J. A. Sloane.DOI
  6. D. S. Krotov and A. A. Valyuzhenich, On degree-33 and (n−4)(n-4)-correlation-immune perfect colorings of nn-cubes, Discrete Math. 347 (2024), 114138, Section 3 (crediting Yu. Tarannikov and D. Kirienko, Spectral analysis of high order correlation immune functions , ePrint 2000/050); https://arxiv.org/abs/2311.05566.link
  7. M. Masuda and T. E. Panov, Semifree circle actions, Bott towers and quasitoric manifolds, Sb. Math. 199 (2008), 1201--1223, Lemma 4.7; doi:10.1070/SM2008v199n08ABEH003959 (https://doi.org/10.1070/SM2008v199n08ABEH003959).DOI
  8. G. Nebe, The second minimum of Barnes--Wall lattices, preprint (2026), Theorems 2.5 and 3.3; https://arxiv.org/abs/2603.23133.link
  9. V. N. Potapov, On the number of relevant variables for discrete functions, Cryptogr. Commun. 17 (2025), 989--998; doi:10.1007/s12095-025-00797-4 (https://doi.org/10.1007/s12095-025-00797-4).DOI
  10. S. Rasoolzadeh, Classification of all tt-resilient Boolean functions with t+4t+4 variables, IACR Trans. Symmetric Cryptol. 2023(3), 213--226; doi:10.46586/tosc.v2023.i3.213-226 (https://doi.org/10.46586/tosc.v2023.i3.213-226).DOI
Show all 16 referencesShow fewer references
  1. A. Valyuzhenich, Optimal functions with spectral constraints in hypercubes, Discrete Math. 347 (2024), 113816, Theorem 2(2); https://arxiv.org/abs/2303.10995.link
  2. J. Wellens, Relationships between the number of inputs and other complexity measures of Boolean functions, Discrete Analysis 2022:20; https://discreteanalysisjournal.com/article/57741.link
  3. BakeLab, Épi-results , exact Wellens certificates, revision 97fa6a420f417458e11723c8bceb70f1529e447a ; Retained data at the pinned math-certificates revision (https://github.com/rpinho/math-certificates/tree/36325fade4b73afb787c37ee8cc4c90ae4adf856/c44/reed-muller-caps/baseline).link
  4. R. Pinho, Math certificates , revision 36325fade4b73afb787c37ee8cc4c90ae4adf856 , derivative-control base; c44/reed-muller-caps (https://github.com/rpinho/math-certificates/tree/36325fade4b73afb787c37ee8cc4c90ae4adf856/c44/reed-muller-caps).link
  5. R. Pinho, Math certificates , same revision, quartic proof and completion packet; c44/small-degree-classification (https://github.com/rpinho/math-certificates/tree/36325fade4b73afb787c37ee8cc4c90ae4adf856/c44/small-degree-classification).link
  6. R. Pinho, Tao optimization table, PR 294 (open, unrefereed; read 2 November 2026); https://github.com/teorth/optimizationproblems/pull/294.link

Version history

  1. v1Submitted by Ricardo PinhoInitial depositSupersededOct 30, 2026
  2. v2Submitted by Ricardo PinhoSubmitted as a new versionSupersededOct 31, 2026
  3. v3Submitted by Ricardo PinhoSubmitted as a new versionCurrentNov 03, 2026