= Solution
It is enough to consider three alternatives $A,B,C$. Encode each voter's three pairwise preferences by $(x_i,y_i,z_i)$, where $x_i=1$ means $A>B$, $y_i=1$ means $B>C$, and $z_i=1$ means $C>A$. A valid ranking excludes $(1,1,1)$ and $(-1,-1,-1)$. Independence of irrelevant alternatives gives three <Boolean function>[Boolean functions] $u,v,w$ for the social comparisons. Unanimity and transitivity force $u=v=w$: fixing arbitrary $x$, taking $y=-x$ and $z$ constantly equal to $u(x)$ shows $v(-x)=-u(x)$, and cyclic symmetry gives the claim.
Choose the voters' valid rankings independently and uniformly. A social <Condorcet paradox> is absent exactly when
$$
u(x)u(y)+u(y)u(z)+u(z)u(x)=-1.
$$
Thus transitivity for every profile gives $3\mathbb E[u(x)u(y)]=-1$. Conditional on $x_i$, the bit $y_i$ equals $x_i$ with probability $1/3$ and differs with probability $2/3$, so $(x,y)$ has correlation $-1/3$. Therefore
$$
\operatorname{Stab}_{-1/3}(u)=-\frac13.
$$
The Fourier formula, valid for negative correlation, gives
$$
\sum_{S\subseteq[n]}\left(-\frac13\right)^{|S|}\widehat u(S)^2=-\frac13,
\qquad
\sum_S\widehat u(S)^2=1
$$
by <Parseval identity>. Among the numbers $(-1/3)^m$, the unique minimum is $-1/3$, attained at $m=1$. Equality in this weighted average therefore forces all Fourier mass onto level one. Hence $u$ is a linear Boolean function with zero constant term. Such a function can have only one nonzero coefficient: otherwise varying two coordinates would make it assume more than two values. Thus $u(x)=x_j$ or $u(x)=-x_j$ for some $j$, making voter $j$ a dictator and proving <Arrow theorem>.
Solved by gpt-5.6-sol high.
Back to article page
