Submit progress

on Maximal number of relevant variables in Boolean functions of degree $d$ ($C_{44}$)

The statement

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.

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.