On Boolean Functions with Low Polynomial Degree and Higher Order Sensitivity

NEW

Problem: Reconstructed formalization: for fixed $r\ge1$, let

$$D_r(n)=\min\{\operatorname{pdeg}(f): f:\{0,1\}^n\to\{0,1\}\text{ is }r\text{-th order sensitive}\},$$

where $f$ is $r$-th order sensitive if for some $x$,

$$f(x^S)\ne f(x)\quad\forall S\subseteq[n],\ 1\le |S|\le r.$$

Since the paper compares separations via power laws such as $\operatorname{pdeg}(f)=n^{\log 3/\log 6}$, the natural “asymptotic separation” is the exponent of $D_r(n)$ relative to $n$. The conjectural question becomes: does this power-law separation strictly decrease as $r$ increases?

Result: The strict-decrease assertion is false for every fixed order $r$. In fact,

$$D_1(n)\le D_r(n)\le C_r(\log n)D_1(n)$$

for a constant $C_r$ depending only on $r$. Hence

$$\frac{\log D_r(n)}{\log n}-\frac{\log D_1(n)}{\log n}\to 0$$

along liminf and limsup, so all fixed sensitivity orders have the same asymptotic power-law separation.

Proof. Choose $m=O_r(\log n)$ subsets $A_1,\dots,A_m\subseteq[n]$ such that every nonempty $S\subseteq[n]$ with $|S|\le r$ has $|S\cap A_j|=1$ for some $j$. Such a family exists by the probabilistic method: random $A_j$ with inclusion probability $1/2$ hits a fixed $S$ in exactly one point with probability at least $2^{-r}$, and a union bound over at most $n^r$ sets $S$ gives $m=O_r(\log n)$.

Let $f$ be first-order sensitive at $a$ with $\operatorname{pdeg}(f)=D_1(n)$, and complement $f$ if needed so $f(a)=0$. For each $A_j$, define

$$g_j(x)=f(y),\qquad y_i=\begin{cases}x_i,&i\in A_j,\\ a_i,&i\notin A_j.\end{cases}$$

Then $\operatorname{pdeg}(g_j)\le D_1(n)$. Define

$$F(x)=g_1(x)\vee\cdots\vee g_m(x).$$

At $x=a$, all $g_j(a)=0$, so $F(a)=0$. If $1\le |S|\le r$, choose $j$ with $|S\cap A_j|=1$. Then $g_j(a^S)=f(a^{\{i\}})=1$, so $F(a^S)=1$. Thus $F$ is $r$-th order sensitive.

Finally,

$$F=1-\prod_{j=1}^m(1-g_j),$$

so $\operatorname{pdeg}(F)\le mD_1(n)=O_r((\log n)D_1(n))$. Since every $r$-th order sensitive function is also first-order sensitive, $D_1(n)\le D_r(n)$. This proves the claim and rules out strict decrease of the asymptotic exponent.

Citation: No prior exact resolution used. Definitions and context: Maitra–Mukherjee–Stanica–Tang, “On Boolean Functions with Low Polynomial Degree and Higher Order Sensitivity,” arXiv:2107.11205.