% Copyright 2026 Ricardo Pinho. CC BY 4.0. \documentclass[11pt]{amsart} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage[margin=1in]{geometry} \usepackage{amsmath,amssymb} \usepackage[expansion=false]{microtype} \usepackage[hyphens]{url} \usepackage[hidelinks]{hyperref} \setlength{\emergencystretch}{2em} \newtheorem{theorem}{Theorem} \newcommand{\D}{\mathcal D} \title[Fourier certificates for relevant variables]{Fourier granularity and block sensitivity in the relevant-variable recurrence} \author{Ricardo Pinho} \address{Independent researcher} \thanks{ORCID: \href{https://orcid.org/0009-0006-2744-2599}{0009-0006-2744-2599}. Licensed under CC BY 4.0.} \date{30 October 2026; unrefereed preprint} \subjclass[2020]{06E30, 68Q25, 68R05} \keywords{Boolean functions, relevant variables, block sensitivity, Fourier granularity, rational certificates} \hypersetup{pdftitle={Fourier granularity and block sensitivity in the relevant-variable recurrence},pdfauthor={Ricardo Pinho}} \begin{document} \begin{abstract} Rational Fourier lattice certificates, inserted into the existing local-degree recurrence, give $C_{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 $B_4\le9$, $B_5\le14$ nor Fourier granularity is new. This note is unrefereed, with no independent human review or formalization. \end{abstract} \maketitle \section{Statement and scope} For a Boolean function $f$, write $r(f)$ for its number of relevant variables, $\deg f$ for its real multilinear degree, and $\operatorname{bs}(f)$ for its block sensitivity: the maximum, over inputs, of the number of disjoint coordinate sets whose individual flips change the output. Define \[ C_{44}=\sup_{\deg f\ge1}r(f)2^{-\deg f}. \] \begin{theorem} \[ C_{44}\le \frac{163310332697516761417555720251} {39614081257132168796771975168}<4.1225323803. \] \end{theorem} The contribution is the rational lattice criterion below and its finite certificates within the Chiarelli--Hatami--Saks/Wellens weighted method \cite{chs,wellens}. The final degree-31--40 certificates change numerical inputs to the same criterion; they require no further universal lemma. The released \textit{\'Epi} degree-48 certificates are unchanged \cite{epi}. Koshta's PR~283 already gives $B_4\le9$ after sensitive-block compression \cite{koshta}. Stepanovs's 2012 exclusion of a fully sensitive degree-five function on 15 inputs already implies $B_5\le14$ \cite{stepanovs}. Here $B_d$ denotes an upper bound for block sensitivity at degree at most $d$. The packet reproves these two inequalities. Granularity is standard, and Towell's conditional degree-five work already uses integer Fourier energy \cite{hatami,towell}. No broad priority or optimality claim is made. \section{The rational exclusion} Sensitive-block compression turns $\operatorname{bs}(f)\ge n$ into a sign Boolean function $g$ on $n$ bits with $g(0)=1$, $g(e_j)=-1$, and degree at most $d=\deg f$. Indeed, fix unused coordinates and substitute one bit, or its complement, for each coordinate in a block. Multilinear reduction cannot increase degree. Write $g=\sum_S a_S\chi_S$, with $\chi_S(x)=(-1)^{\sum_{i\in S}x_i}$. Put $M=2^{d-1}$. Then $a_S\in M^{-1}\mathbb Z$: the bit polynomial of $(1-g)/2$ has integer coefficients by inclusion--exclusion, and substitution $x_i=(1-\chi_{\{i\}})/2$ proves the assertion. Parseval gives $\sum_S a_S^2=1$. If $A_l=\sum_{|S|=l}a_S$, averaging over weight-$k$ inputs gives \[ q(k)=\sum_{l=0}^{\min(d,n)} A_l Q_l(k),\qquad Q_l(k)=\frac{\sum_j(-1)^j\binom{k}{j}\binom{n-k}{l-j}}{\binom nl}. \] Thus $q(0)=1$, $q(1)=-1$, and $|q(k)|\le1$. For rational $\alpha_0,\ldots,\alpha_n$, put \[ c_l=\sum_k\alpha_k Q_l(k),\quad L=\alpha_0-\alpha_1-\sum_{k=2}^n|\alpha_k|,\quad h(c)=\max_{z\in\mathbb Z}(cz-z^2). \] The two integers adjacent to $c/2$ suffice to evaluate $h(c)$ exactly. Since $a_S=z_S/M$ and $\sum_S z_S^2=M^2$, \[ L\le\sum_k\alpha_kq(k)=\sum_l c_l A_l \le M+\frac1M\sum_{l=0}^{\min(d,n)}\binom nl h(c_l). \] A strict reverse inequality is therefore a finite rational certificate that $\operatorname{bs}(f)\le n-1$. All multiplicities count the original Fourier subsets. No lattice assumption is made about the averaged function. \section{The potential, recurrence, and infinite tail} Let $d_i(f)$ be the largest monomial degree involving relevant coordinate $i$, and put $\D(f)=\sum_i2^{-d_i(f)}$. The standard support bound for a nonzero degree-$k$ multilinear polynomial is $2^{-k}$, by induction on a variable. Applied to each derivative, it gives $\D(f)\le I(f)/2\le\deg(f)/2$. The restriction inequality is \[ \D(f)\le\sum_{i\in H}2^{-d_i(f)}+ \mathbb E_\alpha\D(f_\alpha). \] For each coordinate outside $H$, survival in both branches cannot increase its local degree; survival in just one branch lowers its local degree by exactly one. Averaging and iterating proves the inequality. Take $H$ to be a maximum-degree monomial of size $d$. Its cost is $d2^{-d}$. For every outside assignment its full coefficient remains nonzero. Hence at a point witnessing a child's block sensitivity, an additional sensitive block inside $H$ is available. Thus $\operatorname{bs}(f_\alpha)\le\operatorname{bs}(f)-1$. With $U(0,d)=0$, define, for $1\le b\le B_d$, \[ U(b,d)=\min\left(c_d,\ d2^{-d}+\max_{1\le k\le d}U(b-1,k)\right), \qquad U(b,d)=U(B_d,d)\quad(b>B_d). \] Induction on $b$ bounds $\D(f)$ for degree exactly $d$ and block sensitivity at most $b$. Freezing is valid because the function class stops growing. Constants have potential zero. The caps are $c_3=5/4$, $c_4=31/16$, $c_7=447/128$, and $c_d=d/2$ otherwise. The complete inherited cap proofs are supplied in \texttt{fourier-granularity/baseline/PROOF.md}, Sections 1--8, in \cite{certificate} and the source archive. The cubic cap uses the published $R_3\le10$ theorem of Tarannikov--Kirienko, as stated by Krotov--Valyuzhenich \cite{cubic}. The other two caps follow from the strict influence equality exclusion proved there. They are sufficient caps, not asserted sharp values. For $B_d$ take the minimum of the lattice exclusions, the unchanged \'Epi bounds through degree 48, and the largest integer $b$ satisfying Wellens's theorem $3b(b-1)\le2(d^4-d^2)$ \cite{wellens}. For clarity, each \textit{\'Epi} certificate has positive integer nodes $x_0=1<\cdots0,\qquad w_0+\sum_{i\ge1:w_i<0}w_i>0. \] The compressed bit-valued symmetrization $p$ has $p(0)=0$, $p(1)=1$, $0\le p(k)\le1$; the displayed conditions force both $\sum_iw_ip(x_i)=0$ and $\sum_iw_ip(x_i)>0$. Thus $B_d\le x_d-1$. Wellens's inequality implies $\operatorname{bs}(f)\le d^2$. Above any horizon $H$, restriction of maximum-degree monomials therefore costs at most $e^3/2^e$ before degree $e$ drops. Consequently \[ \D(f)\le\max_{1\le d\le H}U(B_d,d) +\sum_{e>H}\frac{e^3}{2^e} =\max_{1\le d\le H}U(B_d,d) +\frac{H^3+6H^2+18H+26}{2^H}. \] The retained exact row-checker result at $H=96$ is the rational in the theorem; the column checker at $H=72$ proves the same printed decimal bound. Finally $r(f)2^{-\deg f}\le\D(f)$ proves the claim. \section{Finite evidence and review status} The exact public pointer is repository revision \texttt{0104c95dd218b6cb39625345a12cd7915dc14001}, directory \texttt{fourier-granularity} \cite{certificate}. Its \texttt{candidate.json} fixes the file \path{spectral_certificate_round3.json}, containing 37 rational functionals for degrees 4--40. The latter has SHA-256 \begin{center}\scriptsize \texttt{1020ed20d078ec1fece41c643007426bc452fc3aeafc81761901b32ded4495ed}. \end{center} \texttt{verify\_spectral.py}, \texttt{verify\_bound.py}, and \texttt{verify\_column.py} give the finite checks without search code. Stored receipts, rather than a new run for this note, supply the arithmetic results. The separate AI review covered the criterion and the earlier round-two endpoint $4.1225332506$; the final degree-31--40 extension is supported by its stored exact-checker results, not a claimed fresh review. This is an unrefereed preprint. There has been no independent human review and no formalization. The programs check finite arithmetic, not all prose or the cited external theorems. 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. \begin{thebibliography}{10} \bibitem{chs} J. Chiarelli, P. Hatami and M. Saks, An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function, \emph{Combinatorica} 40 (2020), 237--244; \url{https://arxiv.org/abs/1801.08564}. \bibitem{wellens} J. Wellens, Relationships between the number of inputs and other complexity measures of Boolean functions, \emph{Discrete Analysis} 2022:20; \url{https://discreteanalysisjournal.com/article/57741}. \bibitem{epi} BakeLab, \emph{\'Epi-results}, exact Wellens certificates; \url{https://github.com/BakeLab/Epi-results/tree/97fa6a420f417458e11723c8bceb70f1529e447a/mathematics/wellens}. \bibitem{koshta} D. Koshta, degree-four sensitivity certificate, PR 283; \url{https://github.com/teorth/optimizationproblems/pull/283}. \bibitem{stepanovs} I. Stepanovs, MSc thesis (2012), degree-five exclusion; \url{https://igors.org/theses/2012-boolean-deg-sens-gap-msc.pdf}. \bibitem{hatami} H. Hatami, Boolean function analysis, Theorem 6.4; \url{https://cs.mcgill.ca/~hatami/Boolean_function_analysis.pdf}. \bibitem{towell} Towell, conditional degree-five Fourier integer-energy work; \url{https://github.com/queelius/boolean-degree-sensitivity}. \bibitem{cubic} Yu. Tarannikov and D. Kirienko, \url{https://eprint.iacr.org/2000/050}; D. S. Krotov and A. Valyuzhenich, degree-three Boolean functions, Section 3; \url{https://arxiv.org/abs/2311.05566}. \bibitem{certificate} R. Pinho, \emph{C44 certificate}, revision 0104c95dd218b6cb39625345a12cd7915dc14001; \url{https://github.com/rpinho/c44-certificate/tree/0104c95dd218b6cb39625345a12cd7915dc14001/fourier-granularity}. \end{thebibliography} \end{document}