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 exactly $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).

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

References