Derivative controls and Boolean completion in the relevant-variable recurrence

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

Contributed by Ricardo Pinho

Version 2 / 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. 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
  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; https://github.com/BakeLab/Epi-results/tree/97fa6a420f417458e11723c8bceb70f1529e447a/mathematics/wellens.link
  4. D. Koshta, degree-four sensitivity certificate, PR 283; https://github.com/teorth/optimizationproblems/pull/283.link
  5. I. Stepanovs, MSc thesis (2012), degree-five exclusion; https://igors.org/theses/2012-boolean-deg-sens-gap-msc.pdf.link
  6. H. Hatami, Boolean function analysis, Theorem 6.4; https://cs.mcgill.ca/~hatami/Boolean_function_analysis.pdf.link
  7. Towell, conditional degree-five Fourier integer-energy work; https://github.com/queelius/boolean-degree-sensitivity.link
  8. Yu. Tarannikov and D. Kirienko, https://eprint.iacr.org/2000/050; D. S. Krotov and A. Valyuzhenich, degree-three Boolean functions, Section 3; https://arxiv.org/abs/2311.05566.link
  9. R. Pinho, C44 certificate , revision 0104c95dd218b6cb39625345a12cd7915dc14001; https://github.com/rpinho/c44-certificate/tree/0104c95dd218b6cb39625345a12cd7915dc14001/fourier-granularity.link

Version history

  1. v1 · 3 pagesSubmitted by Ricardo PinhoInitial depositSupersededOct 30, 2026
  2. v2 · 3 pagesSubmitted by Ricardo PinhoSubmitted as a new versionSupersededOct 31, 2026
  3. v3 · 8 pagesSubmitted by Ricardo PinhoSubmitted as a new versionCurrentNov 03, 2026