\documentclass[11pt]{amsart} \usepackage[margin=1in]{geometry} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage[hidelinks]{hyperref} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\HS}{\mathrm{HS}} \newcommand{\E}{\mathbb E} \newcommand{\AS}{\mathrm{AS}} \DeclareMathOperator{\sgn}{sgn} \DeclareMathOperator{\tr}{tr} \title[An edge comparison with constant $3/2$]{An edge comparison with constant $3/2$\\ and the coefficient $6/\sqrt{2\pi}$ for the average sensitivity\\ of polynomial threshold functions} \author{David Niedbala Giraudin} \address{Meaux, France} \thanks{ORCID 0009-0009-1526-1178.} \date{14 November 2026} \begin{document} \begin{abstract} For every real polynomial threshold function $f$ of degree at most $d$ on the uniform cube $\{-1,1\}^n$ we prove \[ \AS(f)\le\min\Bigl\{n,\;6\,d\,b_n\,\frac{n+d}{n+2d}\Bigr\}\le\frac{6}{\sqrt{2\pi}}\,d\sqrt n<2.394\,d\sqrt n , \] where $b_n=\E|B_n-n/2|$ for $B_n\sim\mathrm{Bin}(n,1/2)$. The previous coefficient was $8/\sqrt{2\pi}\approx3.1915$. The new ingredient is an edge comparison with constant $3/2$ in place of $2$ in OpenAI's weighted-grading argument: for every positive weight and every sign function $h$, the number of ordered equal-sign edges of $h$ is at most $\tfrac32\|MH+HM\|_{\HS}^2$. The proof rests on the exact identity $(Z_iMZ_i-M)^2=I-A_i^2$, where $A_i$ is the grade-diagonal part of the multiplication by $x_i$. Combined with OpenAI's original coupling estimate alone, the lemma already gives $\AS(f)\le 6d\sqrt n$. \end{abstract} \maketitle \section{Result} For $f:\{-1,1\}^n\to\{-1,1\}$ let $\AS(f)=\sum_{i=1}^n\Pr\{f(X)\ne f(X^{\oplus i})\}$, with $X$ uniform and $X^{\oplus i}$ obtained by reversing coordinate $i$. OpenAI~\cite{OAI} proved $\AS(\sgn p)\le 8d\sqrt n$ for every real polynomial $p$ of degree at most $d$ (with $\sgn 0=1$), uniformly in $1\le d\le n$. The probability step of that argument was then sharpened by Lagdive, Aglave and Damre to $3.83$~\cite{LAD1} and to $8/\sqrt{2\pi}$ \cite{LAD2}; Anchen gave a Lean proof of the coefficient $3.762$~\cite{An}, and Q.~Chen gave a self-contained reconstruction of the $8/\sqrt{2\pi}$ bound with the rational witness $399/125$~\cite{Ch}. All these results keep OpenAI's edge comparison \cite[\S4]{OAI}, which carries a factor $2$. We replace it by $3/2$. \begin{theorem}\label{thm:main} Let $n,d\ge1$, let $p$ be a real polynomial of degree at most $d$, and let $f=\sgn p$ on $\{-1,1\}^n$, with $\sgn0=1$. Then \[ \AS(f)\le\min\Bigl\{n,\;6\,d\,b_n\,\frac{n+d}{n+2d}\Bigr\}\le\frac{6}{\sqrt{2\pi}}\,d\sqrt n<\frac{1197}{500}\,d\sqrt n . \] \end{theorem} \begin{corollary} With OpenAI's coupling estimate \cite[\S2]{OAI} in place of the compensated one, Lemma~\ref{lem:edge} gives $\AS(f)\le 6d\sqrt n$. \end{corollary} \section{The weighted grading} We use the notation of \cite[\S3]{OAI}. Put $\Omega=\{-1,1\}^n$, $N=2^n$, and work in $\mathbb R^\Omega$ with the counting inner product, so that the point masses $\delta_x$ form an orthonormal basis; $\|B\|_{\HS}^2=\sum_{x,y}B_{xy}^2$. Let $V_k$ be the span of the characters $\chi_S$ with $|S|\le k$. Fix $w:\Omega\to(0,\infty)$, let $D$ be the multiplication by $\sqrt w$, and let $\Pi_k$ be the orthogonal projection onto $E_k=DV_k\cap(DV_{k-1})^\perp$. Then $\dim E_k=\binom nk$, the $E_k$ are mutually orthogonal and span $\mathbb R^\Omega$, and \[ M=\sum_{k=0}^n\Bigl(k-\frac n2\Bigr)\Pi_k ,\qquad \|M\|_{\HS}^2=\frac{nN}4 . \] Let $Z_i$ be the multiplication by $x_i$. It is a self-adjoint unitary commuting with $D$, and $\Pi_sZ_i\Pi_r=0$ for $|s-r|>1$ \cite[\S3]{OAI}. For an operator $X$ and an integer $t$ put $X^{(t)}=\sum_k\Pi_{k+t}X\Pi_k$; then $X=\sum_tX^{(t)}$, $(XY)^{(t)}=\sum_{r+s=t}X^{(s)}Y^{(r)}$, and $X=0$ if and only if every $X^{(t)}=0$. Write $\rho(x,y)$ for Hamming distance, $x^i$ for $x$ with coordinate $i$ reversed, and \[ A_0=\sum_xM_{xx}^2,\qquad F=\sum_{\rho(x,y)\ge2}M_{xy}^2 , \] all sums being over ordered pairs. \section{The edge comparison} \begin{lemma}\label{lem:edge} Let $w>0$ and $h:\Omega\to\{-1,1\}$, let $H$ be the multiplication by $h$, and let $\mathcal E_h$ be the set of ordered pairs $(x,y)$ with $\rho(x,y)=1$ and $h(x)=h(y)$. Then \[ |\mathcal E_h|\le\frac32\,\|MH+HM\|_{\HS}^2 . \] More precisely, $|\mathcal E_h|\le\|MH+HM\|_{\HS}^2+4\sum M_{xy}^2$, the sum running over the ordered pairs with $\rho(x,y)\ge3$ and $h(x)\ne h(y)$. \end{lemma} \begin{proof} \emph{Step 1: an exact identity.} Put $A_i=Z_i^{(0)}$ and $B_i=Z_i^{(1)}$, so that $Z_i=A_i+B_i+B_i^*$ and $A_i$ is self-adjoint. The parts of $Z_i^2=I$ of shift $2$ and $0$ give $B_i^2=0$ and $A_i^2+B_iB_i^*+B_i^*B_i=I$. Since $[M,\Pi_{k+1}Z_i\Pi_k]=\Pi_{k+1}Z_i\Pi_k$, we have $C_i:=[M,Z_i]=B_i-B_i^*$, hence \[ C_i^*C_i=B_iB_i^*+B_i^*B_i-B_i^2-(B_i^*)^2=I-A_i^2 . \] Put $G_i=Z_iC_i=Z_iMZ_i-M$. It is self-adjoint, and $G_i^2=G_i^*G_i=C_i^*C_i$. Therefore \begin{equation}\label{eq:G2} G_i^2=I-A_i^2,\qquad (G_i)_{xy}=(x_iy_i-1)M_{xy}=-2\,\mathbf 1_{\{x_i\ne y_i\}}M_{xy}. \end{equation} \emph{Step 2: edge deficits.} The diagonal entry of \eqref{eq:G2} at $x$ reads $4\sum_{y:\,x_i\ne y_i}M_{xy}^2=1-(A_i^2)_{xx}$. Separating the neighbour $y=x^i$, \begin{equation}\label{eq:def} \frac14-M_{x\,x^i}^2=\frac14\,a_i(x)+\sum_{\substack{y:\ x_i\ne y_i\\ \rho(x,y)\ge2}}M_{xy}^2, \qquad a_i(x):=(A_i^2)_{xx}=\|A_i\delta_x\|^2\ge0 . \end{equation} Summing \eqref{eq:def} over $x$ and $i$, and using $\sum_{x,i}(\frac14-M_{x\,x^i}^2)=\frac{nN}4-\sum_{\rho=1}M_{xy}^2=A_0+F$, \begin{equation}\label{eq:A0} A_0=\frac14\sum_{i}\|A_i\|_{\HS}^2+\sum_{\rho(x,y)\ge2}(\rho(x,y)-1)M_{xy}^2 . \end{equation} \emph{Step 3: counting.} Call $(x,i)$ an equal slot if $h(x)=h(x^i)$; there are $|\mathcal E_h|$ of them. Put $A_h=\sum_{(x,y)\in\mathcal E_h}M_{xy}^2$ and, for $\rho(x,y)\ge2$, $\nu(x,y)=\#\{i:x_i\ne y_i,\ h(x^i)\ne h(x)\}$. Writing $\frac14=M_{x\,x^i}^2+(\frac14-M_{x\,x^i}^2)$ on each equal slot and using \eqref{eq:def}, then $a_i\ge0$ and \eqref{eq:A0}, \begin{align*} \frac{|\mathcal E_h|}4 &=A_h+\frac14\sum_{\text{equal slots}}a_i(x)+\sum_{\rho(x,y)\ge2}M_{xy}^2\,\bigl(\rho(x,y)-\nu(x,y)\bigr)\\ &\le A_h+A_0+\sum_{\rho(x,y)\ge2}M_{xy}^2\,\bigl(1-\nu(x,y)\bigr). \end{align*} On the other hand $T=MH+HM$ has entries $(h(x)+h(y))M_{xy}$, so $\frac14\|T\|_{\HS}^2=A_0+A_h+F_h$ with $F_h=\sum_{\rho\ge2,\,h(x)=h(y)}M_{xy}^2$. Hence \[ \frac{|\mathcal E_h|-\|T\|_{\HS}^2}4\le\sum_{\{x,y\}:\,\rho\ge2}M_{xy}^2\bigl(2-c(x,y)-2\cdot\mathbf 1_{\{h(x)=h(y)\}}\bigr), \qquad c(x,y)=\nu(x,y)+\nu(y,x), \] the sum running over unordered pairs. A pair with $h(x)=h(y)$ contributes at most $0$. Let $h(x)\ne h(y)$ and $\rho(x,y)=2$, with $x,y$ differing in $i,j$. The edges counted by $c(x,y)$ are $\{x,x^i\}$, $\{x,x^j\}$, $\{y,y^i\}=\{y,x^j\}$ and $\{y,y^j\}=\{y,x^i\}$, the four edges of the square spanned by $x$ and $y$. Each of the edge-disjoint paths $x,x^i,y$ and $x,x^j,y$ contains an edge on which $h$ changes, so $c(x,y)\ge2$ and the contribution is at most $0$. A pair with $h(x)\ne h(y)$ and $\rho\ge3$ contributes at most $2M_{xy}^2$. This proves the second assertion. \emph{Step 4.} By \eqref{eq:A0}, $2\sum_{\rho\ge3}M_{xy}^2\le\sum_{\rho\ge2}(\rho-1)M_{xy}^2\le A_0\le\frac14\|T\|_{\HS}^2$. Therefore $|\mathcal E_h|\le\|T\|_{\HS}^2+2A_0\le\frac32\|T\|_{\HS}^2$. \end{proof} \begin{remark} The edge comparison of \cite[\S4]{OAI} states $|\mathcal E_h|\le2\|MH+HM\|_{\HS}^2$. Identity \eqref{eq:A0} refines its inequality $F\le A_0$, and \eqref{eq:def} identifies each edge deficit exactly. \end{remark} \section{Proof of Theorem~\ref{thm:main}} The reduction is OpenAI's \cite[\S5]{OAI}. After a harmless perturbation $p$ has no zero on $\Omega$; put $w=|p|$, $h=\chi_{[n]}f$. Then $\AS(f)=|\mathcal E_h|/N$, and the random grades $(R,S)$ with $\Pr\{R=r,S=s\}=N^{-1}\|\Pi_sH\Pi_r\|_{\HS}^2$ have both marginals $\mathrm{Bin}(n,1/2)$, satisfy $R+S\ge n-d$, and $N^{-1}\|T\|_{\HS}^2=\E(R+S-n)^2$. With $U=S$, $V=n-R$ (same law, values in $[0,n]$, $V-U\le d$), Lemma~\ref{lem:edge} gives \[ \AS(f)\le\frac32\,\E(U-V)^2 . \] The compensated coupling estimate of Lagdive, Aglave and Damre \cite{LAD2} (see also \cite[Lemma 2]{Ch}) states that equal-law variables in an interval of length $L$, with $V-U\le a$ and $b=\E|U-\E U|$, satisfy $\E(U-V)^2\le4ab\,(L+a)/(L+2a)$. With $L=n$, $a=d$, $b=b_n$ this gives $\AS(f)\le6db_n(n+d)/(n+2d)$; also $\AS(f)\le n$ trivially. The estimate $b_n(n+d)/(n+2d)\le\sqrt{n/(2\pi)}$ for all $n,d\ge1$ is proved in \cite[\S6]{Ch} from the Wallis inequalities; it gives the bound $\frac6{\sqrt{2\pi}}d\sqrt n$. For the rational witness: $\arctan\frac12+\arctan\frac13=\frac\pi4$ and $\arctan x>x-\frac{x^3}3+\frac{x^5}5-\frac{x^7}7$ for $0\frac{1538665}{489888}$ \cite[(20)]{Ch}. Hence \[ \frac{36}{2\pi}=\frac{18}{\pi}<\frac{18\cdot489888}{1538665}=\frac{8817984}{1538665}<\frac{1432809}{250000}=\Bigl(\frac{1197}{500}\Bigr)^2, \] the last inequality being $8817984\cdot250000=2204496000000<2204613059985=1432809\cdot1538665$. \qed \section{Verification} The ancillary script \texttt{VERIF\_AS\_EDGE.py} (Python and numpy only) checks, for random weights and random sign functions with $3\le n\le7$, the identities \eqref{eq:G2}, \eqref{eq:def} and \eqref{eq:A0}, the exact form of Step~3 and the inequality of Lemma~\ref{lem:edge}; it checks Theorem~\ref{thm:main} on random polynomial threshold functions, the binomial estimate in exact arithmetic for $1\le n\le 2000$, and the rational witness in integer arithmetic. These checks are verifications of the statements above, not part of their proofs. \subsection*{Acknowledgements} The construction is OpenAI's \cite{OAI}; the compensated coupling and the binomial estimate are due to Lagdive, Aglave and Damre \cite{LAD2} and to Q.~Chen \cite{Ch}. This note was prepared with the assistance of Claude (Anthropic). \begin{thebibliography}{9} \bibitem{OAI} OpenAI, \emph{Average sensitivity of polynomial threshold functions}, OpenAI Math Release preprint, September 25, 2026, \url{https://github.com/openai/math}. \bibitem{LAD1} P.~Lagdive, V.~Aglave, S.~Damre, \emph{An elementary improvement of the average sensitivity bound for polynomial threshold functions}, Zenodo, \url{https://doi.org/10.5281/zenodo.23269472}. \bibitem{LAD2} P.~Lagdive, V.~Aglave, S.~Damre, \emph{A compensated coupling bound for the average sensitivity of polynomial threshold functions}, Research Square preprint rs-11323154, October 13, 2026. \bibitem{An} Anchen, \emph{Average sensitivity: a Lean proof with coefficient 3.762}, \url{https://github.com/Anchen-AI4Math/average-sensitivity-lean}, October 2026. \bibitem{Ch} Q.~Chen, \emph{A uniform average-sensitivity bound}, October 17, 2026, \url{https://github.com/canghaimeng/openai-math-improvement} (problems/bound-127). \end{thebibliography} \end{document}