A nonnegative-only adversary estimate need not capture the general bound

Let f be the sorted four-bit function and define $f^{(1)}=f$ and $f^{(k+1)}=f\circ (f^{(k)},f^{(k)},f^{(k)},f^{(k)})$ on their natural block domains. Since $f$ is total on $\{0,1{\}}^4$ and nonconstant, induction shows every $f^{(k)}$ is total on $\{0,1{\}}^{4^k}$ and nonconstant: each outer bit string is realized by independently choosing a preimage of each bit under $f^{(k)}$, and outer strings with either $f$-value lift in the same way. Thus every composition domain is nonempty and both adversary bounds in [F2] apply. The signed matrix in [F1] and repeated composition in [F2] give ${\mathrm{Adv}}^{\pm }(f^{(k)})\ge {\mathrm{Adv}}^{\pm }(f{)}^k>(2.511486{)}^k$.

The base coordinate distributions in [F1] have mismatch overlap at least $\eta =2\mathrm{/}5$. If $P_X^{(k)}$ is a distribution over the $4^k$ input coordinates with cross-output overlap at least ${\eta }^k$, define for an input $X=(X_1,\dots ,X_4)$ to $f^{(k+1)}$ $P_X^{(k+1)}(j,r)=p_{\tilde{X}}(j)P_{X_j}^{(k)}(r),{\tilde{X}}_j=f^{(k)}(X_j)$. For opposite outputs of $f^{(k+1)}$, the outer strings $\tilde{X},\tilde{Y}$ have opposite $f$-values. For each $j$ with ${\tilde{X}}_j\mathrm{\ne }{\tilde{Y}}_j$, the inner pair $X_j,Y_j$ has opposite $f^{(k)}$-values and contributes overlap at least ${\eta }^k$. Summing those $j$ gives total overlap at least $\eta \cdot {\eta }^k={\eta }^{k+1}$; normalization follows by multiplying two probability distributions.

By induction and [F3], $\mathrm{Adv}(f^{(k)})\le {\eta }^{-k}=(5\mathrm{/}2{)}^k$. Since $2.511486>2.5$, the signed lower bound grows strictly faster than this nonnegative upper bound for every $k\ge 1$. Thus negative weights produce a strict adversary separation, and repeated composition amplifies it.