Maximal number of relevant variables in degree-$d$ Boolean functions
Description of constant
Let \(f:\{0,1\}^n\to\{0,1\}\) be a Boolean function. Let $\deg(f)$ denote the degree of the unique multilinear polynomial over $\mathbb{R}$ that agrees with $f$ on {0,1}^n.
A variable $x_i$ is relevant if $f$ depends on it (equivalently: $x_i$ appears in some monomial with nonzero coefficient in the multilinear representation of $f$).
For integers $1\le d\le n$, define $R_{d,n}$ as the maximum possible number of relevant variables among Boolean functions \(f:\{0,1\}^n\to\{0,1\}\) of degree at most $d$. Let $R_d := \sup_{n\ge d} R_{d,n}$, and set $C_{44} := \sup_{d\ge 1} \frac{R_d}{2^d}.$
Equivalently, $C_{44}$ is the smallest constant $C$ such that every Boolean function $f$ has at most $C\ 2^{\deg(f)}$ relevant variables.
The finiteness of $C_{44}$ (i.e. existence of a universal constant $C$) follows from the work of Chiarelli–Hatami–Saks.
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $26$ | [CHS2020] | First explicit universal constant bound. |
| $6.614$ | [CHS2020] | Optimized constant in the same framework. |
| $4.416$ | [Wel2019] | Refines the CHS restriction/induction method. |
| $4.394$ | [Wel2022] | Best published bound found (Theorem 1.1). |
| $4.3654674227$* | [Epi2026] | BakeLab/Épi: exact rational degree-48 certificates with Wellens’s recurrence and tail; reviewed 11 September 2026. |
| $4.3576549226$* | [P2026] | Degree-three weighted cap $5/4$ inserted into Wellens’s recurrence, retaining Épi’s exact degree-48 data. At horizon 96 the exact upper bound is $172624496193406565421448533795/39614081257132168796771975168$; the gain over the reproduced preceding bound is exactly $1/128$. Two exact checkers by the same AI agent pass at horizons 96 and 72. Unrefereed, without independent human review or formalization; no optimality claimed. |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $1$ | [CHS2020] | A complete read-once decision tree of depth $d$ has degree $d$ and uses $2^d-1$ distinct variables, so $R_d\ge 2^d-1$. |
| $3/2$ | [CHS2020] | Construction with $R_d \ge 3\cdot 2^{d-1}-2$, hence $\sup_d R_d/2^d \ge 3/2$. (Also observed by Shinkar and Tal.) |
Additional comments
- Best currently-known interval: $\frac{3}{2}\le C_{44}\le 4.3576549226$ (upper bound unrefereed; marked *).
- For monotone Boolean functions, Wellens proves a smaller constant ($1.325$) multiplying $2^{\deg(f)}$.
- $R_3 = 10$. Tarannikov–Kirienko [TK2000] prove $p’(4)=p(4)=10$ in resilient-function language; via the standard translation $R_d = p(d+1)$ (cf. [KV2024]), this is $R_3 = 10$, attained by the CHS function $\Xi_3$.
- [Wel2019], Table 2, gives $R_8 \le 1008$ (from the bound $W(f) \le 3.9375$ at degree $8$, hence $R_8 \le 256 \cdot 3.9375 = 1008 < 8 \cdot 2^7$).
References
- [NS1994] Nisan, N. and Szegedy, M. On the degree of Boolean functions as real polynomials. Computational Complexity 4 (1994), 301–313. DOI: 10.1007/BF01263419.
- [TK2000] Tarannikov, Y. and Kirienko, D. Spectral analysis of high order correlation immune functions. IACR ePrint 2000/050. https://eprint.iacr.org/2000/050
- [CHS2020] Chiarelli, J.; Hatami, P.; Saks, M. An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean Function. Combinatorica 40 (2020), 237–244. Preprint: https://arxiv.org/abs/1801.08564
- [Wel2019] Wellens, J. A tighter bound on the number of relevant variables in a bounded degree Boolean function. Preprint: https://arxiv.org/abs/1903.08214
- [Wel2022] Wellens, J. Relationships between the number of inputs and other complexity measures of Boolean functions. Discrete Analysis 2022:19. Preprint: https://arxiv.org/abs/2005.00566
-
[KV2024] Krotov, D. S. and Valyuzhenich, A. On degree-3 and $(n-4)$-correlation-immune perfect colorings of $n$-cubes. Discrete Mathematics 347 (2024), 114138. Preprint: https://arxiv.org/abs/2311.05566
- [Epi2026] BakeLab, Épi-results: Wellens’ Boolean-function bound, reviewed 11 September 2026. Exact certificate and result; Huang et al., Épi: Towards a Persistent, Self-Improving Agent for Autonomous Research, Appendix A.1, https://arxiv.org/abs/2610.24944.
- [P2026] Ricardo Pinho, A degree-three local-weight cap and an improved relevant-variable bound, 23 October 2026, unrefereed preprint. Paper, exact certificate and both checkers. AI-assisted analysis and proof drafting under the author’s direction; author review at summary level.