Boolean functions on $S_n$ which are nearly linear

We show that if $f\text{\hspace{0.17em}⁣}:S_n\to \{0,1\}$ is $ϵ$-close to linear in $L_2$ and $\mathbb{E}[f]\le 1\mathrm{/}2$ then $f$ is $O(ϵ)$-close to a union of “mostly disjoint” cosets, and moreover this is sharp: any such union is close to linear. This constitutes a sharp Friedgut-Kalai-Naor theorem for the symmetric group. Using similar techniques, we show that if $f\text{\hspace{0.17em}⁣}:S_n\to \mathbb{R}$ is linear, $\mathrm{Pr}[f\mathrm{\notin }\{0,1\}]\le ϵ$, and $\mathrm{Pr}[f=1]\le 1\mathrm{/}2$, then $f$ is $O(ϵ)$-close to a union of mostly disjoint cosets, and this is also sharp; and that if $f\text{\hspace{0.17em}⁣}:S_n\to \mathbb{R}$ is linear and $ϵ$-close to $\{0,1\}$ in $L_{\mathrm{\infty }}$ then $f$ is $O(ϵ)$-close in $L_{\mathrm{\infty }}$ to a union of disjoint cosets.