On Boolean Functions with Low Polynomial Degree and Higher Order Sensitivity

NEW

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

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

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,

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

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

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

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,

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.