HEXAGONbeta

Fourier granularity and block sensitivity in the relevant-variable recurrence

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

Contributed by Ricardo Pinho ↗

Version 1 / Oct 31, 2026 / CC BY 4.0

Abstract

Rational Fourier lattice certificates, inserted into the existing local-degree recurrence, give C44≤4.1225323803C_{44}\le4.1225323803 for the number of relevant variables of a Boolean function. The finite packet contains 37 block-sensitivity exclusions through degree 40. We explain the certificate criterion and its passage to a bound valid in every degree, and identify the inherited analytic inputs. Neither the small-degree bounds B4≤9B_4\le9, B5≤14B_5\le14 nor Fourier granularity is new. This note is unrefereed, with 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. v1Submitted by Ricardo PinhoInitial depositCurrentOct 30, 2026