The Gotsman–Linial conjecture for average sensitivity of polynomial threshold functions

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a polynomial threshold function of degree at most $d$, abbreviated an $(n,d)$-PTF. For a Boolean function $f$, let $\mathbf{AS}[f]$ denote its average sensitivity. Let $p^*_{n,d}$ be the monic univariate polynomial of degree $d$ with non-repeated roots at the $d$ integers closest to $0$ having parity opposite to $n$, and define

$$f^*_{n,d}(x_1,\ldots,x_n)=\operatorname{sgn}\left(p^*_{n,d}\left(\sum_{i\in[n]}x_i\right)\right).$$

Gotsman–Linial conjecture. For every $(n,d)$-PTF $f$,

$$\mathbf{AS}[f]\leq\mathbf{AS}[f^*_{n,d}].$$

Gotsman and Linial proved the claim for $d=0$ and $d=1$, but the paper shows that it is false for almost all relevant pairs $(n,d)$, with a multiplicative separation of $1+\Theta_d(n^{-1})$.