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 $de g (f)$ denote the degree of the unique multilinear polynomial over $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 \leq d \leq 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 \geq d} R_{d, n}$ , and set $C_{44} := sup_{d \geq 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^{d e g (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).

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} \geq 2^{d} - 1$ .
$3/2$	[CHS2020]	Construction with $R_{d} \geq 3 \cdot 2^{d - 1} - 2$ , hence $sup_{d} R_{d} / 2^{d} \geq 3/2$ . (Also observed by Shinkar and Tal.)

Additional comments

Best currently-known interval: $\frac{3}{2} \leq C_{44} \leq 4.394.$
For monotone Boolean functions, Wellens proves a smaller constant ( $1.325$ ) multiplying $2^{d e g (f)}$ .
$R_{3} = 10$ . Tarannikov–Kirienko [[TK2000](#TK2000)] prove $p^{'} (4) = p (4) = 10$ in resilient-function language; via the standard translation $R_{d} = p (d + 1)$ (cf. [[KV2024](#KV2024)]), this is $R_{3} = 10$ , attained by the CHS function $Ξ_{3}$ .
[Wel2019], Table 2, gives $R_{8} \leq 1008$ (from the bound $W (f) \leq 3.9375$ at degree $8$ , hence $R_{8} \leq 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

What counts as progress

A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
A formal proof (Lean) of a known bound, or a precise error in a claimed one.
New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.