073ed03
==============================================================
THE HELLINGER CONJECTURE
Why One Vote Tells You the Most
==============================================================
A plain-language guide to the research paper
"Hellinger contraction with arbitrary Boolean output bias".
This version is written so a motivated high-school student can follow it
from start to finish. The mathematics is unchanged and complete: the same
theorem is proved, down to the exact arithmetic a computer checks.
Nothing is hidden behind "it can be shown". Where a finite computation is
involved, we say exactly what is computed and why the computation counts
as a proof.
Every decimal in the paper is an exact fraction. For example .84 means
the rational number 84/100. The programs that check the arithmetic use
exact integer and rational arithmetic, never floating point.
--------------------------------------------------------------
0. HOW TO READ THIS
--------------------------------------------------------------
There is one question and one answer.
The question: a row of people each holds a secret coin (+1 or -1). I never
see the coins. A messenger carries each coin to me over a faulty wire that
sometimes flips it. From the noisy message I want to learn ONE yes/no fact
about the whole row. The fact I may learn is a Boolean function f of the
true coins. Which fact should I pick so the noisy message tells me the
most about it?
The answer: read a single coin. Ignore all the others. That one coin,
carried over the faulty wire, is the most informative single fact you can
ask about the row.
That is startling but true, and the whole document is the proof. It is
long only because we must rule out every clever summary of many coins.
Read 0-6 for the question and the answer with no machinery. Read 7-12 for
the proof. Appendix A is a glossary; skim it first if words like
"variance" or "mutual information" are new.
--------------------------------------------------------------
1. THE CAST: THE CUBE, THE NOISE, THE SUMMARY
--------------------------------------------------------------
THE CUBE. A point in the Boolean cube is a row of n signs, each +1 or -1,
written x = (x_1, ..., x_n). There are 2^n such rows. We pick one
uniformly at random: every row is equally likely. Averaging over the
uniform cube is written E[...].
(A sign is just a coin: +1 = heads, -1 = tails.)
THE NOISE. Nature holds a true row x. Each coordinate goes through its own
private faulty wire. Wire i returns
y_i = x_i with probability (1+rho)/2,
y_i = -x_i with probability (1-rho)/2,
independently across wires, for a fixed number rho with -1 <= rho <= 1.
rho = 1 : perfect wires, y = x (no noise).
rho = 0 : useless wires, each y_i is a fresh fair coin, unrelated to x.
rho < 0 : wires that lie more often than not.
We write y for the noisy row the messenger actually brings. The single
number rho measures how good the wires are. Equivalently E[x_i y_i] = rho
for every coordinate i.
THE NOISE OPERATOR. If u is any function of the true row, define
T_rho u(x) = E[ u(y) | x ],
the average of u over the noisy version of x. This noise operator is the
central character. Two facts we use constantly:
(i) Applying the noise twice is like applying more noise once: the
wire qualities multiply.
(ii) On the special test functions (the characters, section 8), noise
simply rescales them: T_rho chi_S = rho^|S| chi_S.
THE SUMMARY. A Boolean function is a rule f : {-1,+1}^n -> {-1,+1}. It
picks out one yes/no fact about the true row. "Is person 1 a +1?" and "do
people 1,2,3 all agree?" are two examples. The quantity T_rho f(x) is the
average summary value over the noisy row: a number strictly between -1
and +1 once 0 < rho < 1.
The average summary is m = E[f], between -1 and +1. It measures how
lopsided the summary is. Two summaries we keep returning to:
* A constant: always +1 (or always -1). Utterly uninformative.
* A DICTATOR: f(x) = x_1, or -x_1. It reports one single coin.
--------------------------------------------------------------
2. HOW CLOSE ARE TWO PROBABILITY DISTRIBUTIONS?
--------------------------------------------------------------
Suppose the messenger's noisy row y can arise from two situations. In
situation "+" the fact is true; in situation "-" it is false. Each
situation turns the message y into a probability distribution: P_+ is how
likely each message is when the fact is +1, and P_- is how likely when it
is -1. The more different P_+ and P_- are, the more the message reveals.
We need a precise ruler for "how different". Use the HELLINGER AFFINITY.
For two distributions P, Q on the same finite set,
affinity(P,Q) = sum_z sqrt( P(z) * Q(z) ).
It lies between 0 and 1. It equals 1 exactly when P = Q (the two
situations produce indistinguishable messages). It is 0 when P and Q live
on disjoint messages. Small affinity = easy to tell apart = the message
reveals a lot. Big affinity = hard to tell apart = the message reveals
little. (The Hellinger distance is 1 minus this affinity, or twice it,
depending on the textbook; only the affinity matters here.)
The single most useful profile in the whole story is
H(t) = sqrt( 1 - t^2 ), for -1 <= t <= 1.
Why this shape? It is exactly what falls out when you take the affinity of
two distributions that differ by a small tilt. We see it appear next.
--------------------------------------------------------------
3. THE AFFINITY OF THE TWO CONDITIONALS
--------------------------------------------------------------
Fix a summary f with mean m = E[f], and consider the two conditional
distributions of the message y, given f(x)=+1 and given f(x)=-1. Bayes'
formula turns them into
P_+(y) = 2^{-n} (1 + T_rho f(y)) / (1 + m),
P_-(y) = 2^{-n} (1 - T_rho f(y)) / (1 - m).
Multiply, take square roots, sum over all messages:
affinity(P_+, P_-)
= E[ sqrt(1 - (T_rho f)^2) ] / sqrt(1 - m^2)
= E[ H(T_rho f) ] / H(m).
So the affinity between "the fact is true" and "the fact is false", as
seen through the noisy wire, is exactly E[H(T_rho f)] / H(m).
This is the object the conjecture bounds. The numerator E[H(T_rho f)]
says how much noise has washed out the summary; H(m) = sqrt(1-m^2)
normalizes by how lopsided the summary is.
--------------------------------------------------------------
4. THE CONJECTURE, EXACTLY
--------------------------------------------------------------
Here is the statement. It is the heart of the paper.
THEOREM (Hellinger conjecture, full bias).
For every n >= 1, every Boolean f : {-1,+1}^n -> {-1,+1}, and every
rho in [-1,1], writing m = E[f] and H(t) = sqrt(1-t^2),
H(m) - E[ H(T_rho f) ] <= 1 - H(rho). (*)
In words: the loss of Hellinger affinity caused by the noisy wire is
at most 1 - sqrt(1-rho^2). Equality holds for every dictator
f(x) = +x_i or -x_i.
Re-read it using section 3. Divide both sides by H(m):
1 - affinity(P_+, P_-) <= (1 - H(rho)) / H(m).
The left side is how distinguishable the two conditionals are; think of it
as "how much the message leans one way". The right side is a fixed budget
depending only on the wire quality rho and the lopsidedness m. The theorem
says no summary can make the message lean more than the budget allows.
For the champion, the dictator, m=0 so H(m)=1, T_rho f = rho x_1, so
H(T_rho f) = sqrt(1-rho^2 x_1^2) = sqrt(1-rho^2) = H(rho) at every x.
Thus E[H(T_rho f)] = H(rho) and (*) reads 1 - H(rho) <= 1 - H(rho):
equality. The dictator uses the budget exactly.
--------------------------------------------------------------
5. WHY A SINGLE COIN IS THE CHAMPION (INTUITION)
--------------------------------------------------------------
Suppose a summary could average cleverly: let f be "do a majority of the
first 1000 coins vote +1?". A majority is steadier than one coin (smaller
variance), and steadier things usually survive noise better. So why is a
dictator better?
The catch is the normalization in (*): H(m) = sqrt(1-m^2). A steadier
summary is less lopsided, m is closer to 0, H(m) is closer to 1, and the
budget (1-H(rho))/H(m) is ... smaller. The theorem compares the affinity
LOSS, not the affinity itself. A majority has high affinity E[H(T_rho f)]
but it must be measured against its own H(m).
The sharp fact is: a single coin, at the same lopsidedness, both (a) is
the least steady and (b) is exactly as noisy as the wire allows, so it
saturates the trade-off. Any aggregate summary is slightly steadier but
never steady enough to pay for it. Proving this "never" is the work.
One reformulation is worth remembering. If f is balanced (m=0), (*) reads
E[ sqrt(1-(T_rho f)^2) ] >= sqrt(1-rho^2), the small-noise square-root
sensitivity inequality. The genuinely hard regime is m not zero, where
lopsidedness and noise compete directly.
--------------------------------------------------------------
6. THE BONUS: HOW MUCH INFORMATION DOES ONE BIT CARRY?
--------------------------------------------------------------
A second, equally famous question sits right next door, and the Hellinger
theorem settles it too.
MUTUAL INFORMATION. When two random things A and B are linked, the
mutual information I(A;B) is the number of bits about A you learn by
seeing B (and the same the other way). It is between 0 (independent) and
the entropy of each answer. A fair coin carries 1 bit; a coin that lands
heads with probability p carries
h_2(p) = -p log_2 p - (1-p) log_2(1-p),
and h_2(1/2) = 1.
THE COURTADE-KUMAR QUESTION (2014). Nature picks the true row x, hides it,
and hands you the noisy row y. You may ask one Boolean question f(x). How
many bits about f(x) does y reveal, i.e. what is I(f(X);Y)? The claim is
that a dictator wins.
COROLLARY (Courtade-Kumar bound).
With epsilon = (1-rho)/2 the flip probability of each wire,
I( f(X) ; Y ) <= 1 - h_2(epsilon),
and equality holds for dictators.
The right side is the capacity of one faulty wire: exactly the number of
bits a single noisy coin delivers. So one coin delivers the most
information per bit of summary, and no multi-coin summary beats it.
WHY IT FOLLOWS FROM (*). For a single bit, I(f;Y) equals the entropy of f
minus the average entropy of f after seeing y. Using the conditional
probabilities from section 3 this becomes a difference of the convex
function
phi(t) = h_2( (1 - sqrt(1-t^2)) / 2 )
evaluated at t = H(m) and at t = H(T_rho f). Jensen's inequality and the
Hellinger bound (*) then squeeze the answer under 1 - h_2(epsilon). The
algebra is done slowly in section 12. The point here: bounding an
affinity closes the information question as a by-product.
--------------------------------------------------------------
7. THE MASTER PLAN OF THE PROOF
--------------------------------------------------------------
Fix, once and for all:
s = sqrt(1 - rho^2) noise level (0 = perfect wire, 1 = useless wire)
r = rho^2 = 1 - s^2 signal level (1 = perfect wire, 0 = useless wire)
d = T_rho f the noised summary
m = E[f] summary mean (0 <= m <= 1 after a symmetry)
h = H(m) its Hellinger height
b = E[H(d)] average Hellinger height of the noised summary
The target (*) is then simply h - b <= 1 - s, because
H(rho)^2 = 1 - rho^2 = s^2, so H(rho) = s.
Two machines, joined at s = .84.
MACHINE A - low to moderate noise (0 <= s <= .84).
Sort the function into a staircase, then induct on the number of active
coins, one coin at a time, guided by a small profile. Section 9. It
proves the target outright in this range.
MACHINE B - high noise (.84 <= s < 1).
Suppose, for contradiction, the target fails somewhere here. It holds
at s=.84 and is continuous, so there is a FIRST failure: an s in
[.84,1) where h-b equals 1-s exactly and the noised signal is still
barely moving (its energy is no more than the wire allows). Show the
only function able to sit on such an "edge" is a dictator. Then no
failure can exist. Section 10.
At that first-failure edge the mean m must fall in one of three bands,
and each band has its own veto:
0 <= m <= r^2/2 : central band calibrated energy 10.4a
r^2/2 <= m <= .74 : intermediate band parity and angles 10.4b
.74 <= m < 1 : large bias direct norm bound 10.4c
Each veto says: in this band the energy is strictly too big to be a
failure, unless the function is a dictator. Dictators have equality and
so are never failures, so all bands are excluded.
The map, in ASCII:
+-------------------------------------------------------------+
| target: H(m) - E[H(T_rho f)] <= 1 - H(rho) |
| m = E f >= 0, s = sqrt(1-rho^2), r = 1 - s^2 |
+-----------------------------+-------------------------------+
|
+-------------------+--------------------+
| |
s <= .84| s >= .84
Machine A: Machine B:
sorting + dimension exclude a first failure
induction (section 9) (section 10)
|
+--------------------------+------------------+
| | |
0<=m<=r^2/2 r^2/2<=m<=.74 .74<=m<1
central band intermediate large bias
section 10.4a section 10.4b section 10.4c
That is the whole architecture. Everything else makes a box rigorous.
--------------------------------------------------------------
8. TOOLBOX: FOURIER, NOISE, AND ENERGY
--------------------------------------------------------------
This section collects the few formulas used everywhere: the calculus and
linear algebra of the Boolean cube.
CHARACTERS. For a subset S of {1,...,n} define the character
chi_S(x) = product of x_i over i in S.
So chi_empty = 1 (constant), chi_{i} = x_i (one coin), chi_{i,j} = x_i x_j
(agreement of two coins). The characters are orthonormal:
E[chi_S chi_T] = 1 if S = T, else 0.
FOURIER EXPANSION. Every function u has a unique expansion
u = sum_S hat_u(S) chi_S, hat_u(S) = E[ u chi_S ].
The numbers hat_u(S) are Fourier coefficients: how much of u resonates
with the set S.
VARIANCE (PARSEVAL). Orthonormality gives
Var(u) = E[u^2] - (E u)^2 = sum_{S nonempty} hat_u(S)^2.
Variance is the total squared energy in the nonzero frequencies. Write
W_k(u) = sum over |S|=k of hat_u(S)^2, the energy at degree k. Then
Var(u) = W_1 + W_2 + ... . Degree 1 is single coins; higher degree is
multi-coin interaction.
NOISE ON CHARACTERS. The noise operator rescales each character by its
own factor:
T_rho chi_S = rho^|S| chi_S.
Multi-coin interactions are damped by rho^|S|, so they fade faster under
noise than single coins. First hint that single coins are special.
EDGE PROJECTIONS AND ENERGY. For coordinate i let E_i average over that
one coin, and set D_i = I - E_i. Concretely
D_i u(x) = ( u(x) - u(x with coin i flipped) ) / 2,
the half-difference of u across the i-th edge of the cube. Put
N = sum_i D_i. Then for any two functions u, v,
E[ u N v ] = sum_i E[ (D_i u)(D_i v) ] = sum_S |S| hat_u(S) hat_v(S).
The left index counts every Fourier degree times its size. When u = v,
sum_i E[(D_i u)^2] is the total wiggle of u across all edges, the ENERGY.
It is never negative and vanishes only for constants. It reappears as the
rate at which noise changes H(d) as we shrink rho (section 10).
--------------------------------------------------------------
9. MACHINE A: SORTING AND DIMENSION INDUCTION (s <= .84)
--------------------------------------------------------------
GOAL. For every Boolean f and every noise level s <= .84, prove
E[ H(T_rho f) ] >= H(m) - 1 + s, (* rearranged)
the almost-noiseless up to fairly-noisy range. The idea is to peel the
function apart coin by coin.
9.1 SORT INTO A STAIRCASE (COMPRESSION).
Call a Boolean function INCREASING if flipping any coin from -1 to +1
never changes the answer from +1 to -1. It is a staircase on the cube.
LEMMA (compression). For every Boolean f there is an increasing
Boolean f~ with the SAME mean and E[H(T_rho f~)] <= E[H(T_rho f)].
Since we LOWER-bound E[H], and increasing functions give the smallest
values, proving the target for increasing functions proves it for all.
Proof idea: on one coordinate the function splits into two halves; sort
the halves so the smaller sits below the larger. The mean is preserved,
and the Hellinger height can only drop, because the map
u -> H(a+u) + H(a-u) shrinks as u grows. Repeat coordinate by coordinate.
9.2 PEEL OFF ONE COIN.
Fix an increasing f with mean m and at least four active coins. The
first-level Fourier coefficient of coin i is x_i = E[f x_i]; it is
positive exactly when coin i is active. One active coin has a small one:
0 < x = min_i x_i <= b(m), b(m) = min{ 3/8, 9/16 - |m|/2, 1-|m| }.
Why? The least active coefficient is at most the average of any four,
which is E[f Z] for Z the average of four coins. At fixed mean m the
largest possible E[f Z] is a threshold read off the law of Z, and it
equals exactly b(m). Peeling this coin splits f into two sections f_-,
f_+ with means m-x and m+x, both CLOSER to zero.
9.3 THE GUIDING CURVE G AND THE PROFILE B.
We cannot induct on H itself; it is too curved to close the step. We
induce on a smoother concave curve G : [0,1] -> [0,inf) chosen so that
G(p) + G(1-p) = 2 H(2p-1).
Averaging G over a value and its mirror therefore reproduces H exactly.
Our G is
G(p) = H(2p-1) * ( 1 + (2p-1) / (1 + H(2p-1) * lambda(H(2p-1))) ),
lambda(h) = L + U h + V h^2,
with constants L, U, V, where U < 0 and L + U > 0.
We also need a nonnegative PROFILE polynomial B on [-1,1] with B(0)=1
and B(+-1)=0, written
B(m) = (1 - m^2) P(m),
P(m) = 1 + 10^-8 * sum_j c_j ( T_j(m) - T_j(0) ),
where T_j are the Chebyshev polynomials and the c_j are exact integers.
The claim we propagate, for increasing f, is
E[ G( (1 + T_rho f)/2 ) ] >= s B(m). (**)
Because G averages back to H, proving (**) and its mirror and averaging
delivers the Hellinger target.
9.4 THE FOUR SCALAR FACTS.
For each range of s we fix a parameter row (L, U, V, alpha, Lambda, mu).
Here are the seven rows, each entry an exact thousandth (842 means .842);
row i covers s from s_lo to s_hi:
i s_lo s_hi L U V alpha Lambda mu
0 0 70 940 -440 300 960 1000 956
1 70 160 940 -440 300 930 1050 953
2 160 300 886 -398 250 860 1150 985
3 300 490 842 -335 180 770 1150 1024
4 490 630 842 -335 180 690 1150 1058
5 630 750 842 -335 180 632 1160 1087
6 750 840 842 -335 180 583 1160 1111
Every row has L + U >= .488 > 0, so lambda > 0 throughout. With such a
row fixed, four finite statements hold (Lemma scalar):
(1) PAIR / INTERPOLATION INEQUALITY. For 0 <= p0 <= p1 <= 1, let
z = p1-p0, delta = (1-rho)/2, and
D = ( G(p_delta) + G(p_{1-delta}) - G(p0) - G(p1) ) / 2,
S = alpha G(p1) + (1-alpha) G(p0).
Then D >= 0 and
D ( S + Lambda D ) >= mu s^2 ( z - (G(p1)-G(p0))/(4L) )^2.
The factor z - (G(p1)-G(p0))/(4L) is a "shear": how far the chord from
G(p0) to G(p1) sits from the tangent slope 4L. This two-point gift says
the gap between the mirror average and the endpoints, together with the
shear, controls the whole step.
(2) REFLECTION. For every m in [-1,1],
(s/2) ( B(m) + B(-m) ) >= H(m) - 1 + s.
(3) PROFILE CLOSURE. For 0 < x <= b(m) and
B_+ = B(m+x), B_- = B(m-x),
C = (B_+ - B_-)/(2x), A = (2B(m) - B_+ - B_-)/(2x^2),
one has
A [ B(m) + (2alpha-1) x C + (Lambda-1) x^2 A ]
<= mu ( 1 - (s/(2L)) C )^2.
(4) BASE CASE. Every increasing Boolean function on at most three coins
satisfies (**).
These are dimension-free finite facts, proved by exact arithmetic in the
appendix: (1) by interval arithmetic on three regions of the p-plane,
(2)-(3) by checking that the Bernstein coefficients of 17 concrete
polynomials are all positive, (4) by interval-evaluating three tiny
functions and both mirror signs. Nothing here is approximate.
9.5 THE INDUCTION STEP.
Induct on the number of active coins.
Base: at most three coins, done by (4).
Step: f increasing with at least four coins. Peel a coin by 9.2 with
0 < x <= b(m). Its sections f_-, f_+ have fewer active coins and means
m-x, m+x, so by induction
E G((1+T_rho f_-)/2) >= s B(m-x), E G((1+T_rho f_+)/2) >= s B(m+x).
Write p0 = (1+T_rho f_-)/2 and p1 = (1+T_rho f_+)/2, so p0 <= p1 on
the smaller cube, and set y = E G(p1)/s, t = E G(p0)/s, e = E D / s.
The parent, at the two values of the peeled coin, uses p_delta and
p_{1-delta}. Apply the pair inequality (1) pointwise and average.
After Cauchy-Schwarz it becomes one quadratic inequality in e, whose
nonnegative solution is a "root" R_x(y,t):
R_x = (y+t)/2 + [ sqrt( Q^2 + 4 Lambda mu v^2 ) - Q ] / (2 Lambda),
Q = alpha y + (1-alpha) t, v = x - (s/(4L))(y-t).
The crux: R_x is INCREASING in both y and t. Its derivatives are
bounded below by a rational number that is positive on every row of the
table (the appendix records the exact fraction, e.g. 12133/44180000).
So we may substitute the lower bounds y >= B(m+x), t >= B(m-x). The
induction hypothesis then gives the parent at least
R_x( B(m+x), B(m-x) ).
Expanding around m, this is B(m) minus the left side of the profile
closure (3) plus the root correction. Profile closure (3) says exactly
that the correction beats the deficit, so
R_x( B(m+x), B(m-x) ) >= B(m),
which is (**) for f. Induction complete.
9.6 AVERAGE WITH THE MIRROR.
Let f be increasing with mean m. Its mirror f*(x) = -f(-x) is also
increasing, with mean -m, and noise commutes with reversal. Apply (**) to
f and to f* and average. The identity G(p) + G(1-p) = 2H(2p-1) turns the
average back into H, and reflection (2) finishes:
E[ H(T_rho f) ] >= (s/2)( B(m) + B(-m) ) >= H(m) - 1 + s.
That is the theorem for 0 <= s <= .84. Machine A is done.
--------------------------------------------------------------
10. MACHINE B: THE CONTINUATION ARGUMENT (.84 <= s < 1)
--------------------------------------------------------------
Now the high-noise regime. Dimension induction has stopped; we ride the
noise flow instead. This is the heart of the paper.
10.0 THE ENERGY IDENTITY: HOW FAST NOISE EATS THE SUMMARY.
Recall d = T_rho f. Introduce the noise "time"
tau = -log rho, rho = e^{-tau} (tau = 0 perfect, tau -> inf useless).
Changing tau changes rho, hence d, h, b, s. Three facts, all one-liners
from the definitions:
b = E[H(d)], s = sqrt(1 - rho^2), K = r/s.
d b / d tau = E(d) (the ENERGY, defined next),
d s / d tau = r/s = K.
The ENERGY is
E(d) = E sum_i (D_i d) * D_i( d / H(d) ).
For each edge of the cube, D_i d is half the change of d, and
D_i(d/H(d)) is half the change of d/H(d); the energy is the sum of their
products over every edge. It is the total "wiggle" of the noised summary,
weighted by the curvature of the Hellinger profile. (In a moment it is
bounded below by an honest variance.)
The first identity is why the method works: the rate at which noise
changes the Hellinger height of the summary equals the energy. This is
the Hellinger edge derivative of Chen, Gohari, and Nair.
10.1 THE CROSSING TRICK: TURN A FAILURE INTO AN EDGE.
The target is b >= h - 1 + s. Look at the GAP
G(tau) = b - (h - 1 + s).
It is continuous, and at s = .84 it is >= 0 (Machine A). If the target
ever fails, G becomes negative. Let tau_0 be the left endpoint of the
first interval where G < 0. There G = 0, and moving right G can only fall,
so the right derivative is <= 0:
G(tau_0) = 0 => b = h - 1 + s,
G'(tau_0+) <= 0 => E(d) - K <= 0 => E(d) <= K = r/s.
So a failure forces an EDGE where BOTH
b = h - 1 + s AND E(d) <= r/s. (crossing)
If only dictators sit on such an edge, there is no failure, because
dictators meet the target with equality. So the one remaining task is:
prove that no non-dictator has a crossing. That task splits by the mean
m into three bands.
10.2 CHANGE OF VARIABLE: VARIANCE BEATS ENERGY.
To use E(d) <= r/s we need a lower bound on E(d) in plain terms. Let
F(x) = integral from 0 to x of (1 - z^2)^{-3/4} dz, g = F(d).
F is odd, increasing, finite at +-1. Its derivative is F' = H^{-3/2}.
Two edge values of d, say z_- <= z_+, give edge contributions
(1/4)(z_+ - z_-)( z_+/H(z_+) - z_-/H(z_-) ),
(1/4)( F(z_+) - F(z_-) )^2 .
The derivative of z/H(z) is H(z)^{-3} = (F'(z))^2, so Cauchy-Schwarz on
the segment [z_-,z_+] makes the first at least the second. Therefore
E(d) >= sum_i E[ (D_i g)^2 ] >= Var(g). (basic energy)
So the energy controls the variance of the new function g = F(d). Since
g is d pushed through a fixed increasing map, a small energy says the
noised summary is nearly CONSTANT -- a near-degenerate configuration.
This is the lever that rules out crossings.
10.3 THE BOOLEAN SPECTRAL BOUNDS.
We also need to know how lopsided f can be. With p = (1-m)/2 and
w = min{ 2p, 4 sqrt(3/2) p^{3/2} },
the first Fourier level of f is small, and:
W_1(f) <= w,
Var(d) <= r [ (1-r) w + r h^2 ],
E[ d_odd^2 ] <= r [ (1-r^2) w + r^2 h^2 ].
Here d_odd = (d(x)-d(-x))/2 is the odd part of d; odd degrees other than
one are at least three, which is why the second bound carries 1-r^2.
These are the standard Boolean hypercontractive bounds (Holder's
inequality on the cube, in the paper). They say: where the mean is
small the degree-one weight is small, and where it is large the higher
degrees are suppressed.
10.4 THE THREE BANDS.
At a crossing (10.1) the mean lies in [0,1]. Cut it into three:
CENTRAL 0 <= m <= r^2/2
INTERMEDIATE r^2/2 <= m <= .74
LARGE BIAS .74 <= m < 1
The next three subsections prove, respectively:
PROPOSITION (central). For 0 < rho < 1, s >= .84, and
0 <= m <= r^2/2: if b = h-1+s and E(d) <= r/s, then f is a signed
coordinate. (No non-dictator crossing here.)
PROPOSITION (intermediate). For r^2/2 <= m <= .74 and .84 <= s < 1:
if b = h-1+s, then E(d) > r/s. (A crossing is impossible here.)
PROPOSITION (large bias). For .74 <= m < 1 and .84 <= s <= 1 one has
h - b <= 1 - s directly. (The target holds; no crossing to exclude.)
With the crossing trick these finish Machine B. Each is a real estimate;
the rest of this section gives the idea of each, with the exact finite
arithmetic entrusted to its certificate.
10.4a THE CENTRAL BAND (0 <= m <= r^2/2).
GOAL. A crossing here can only be a dictator. The mean is tiny; the
noised summary must be nearly a noised single coin.
STEP 1 - CALIBRATE TO A SINGLE SYMMETRIC PAIR. At a crossing the
Hellinger height b of the noised summary is pinned. The best single-coin
configuration with that height is a SYMMETRIC PAIR: the function d takes
the two values +x_0 and -x_0 equally often, with
y = sqrt(b), x_0 = sqrt(1 - b^2), M = F(x_0)^2, alpha = F(x_0)/x_0.
Check the height: H(x_0) = sqrt(1 - x_0^2) = sqrt(1 - (1-b^2)) = b. Its
"transformed squared amplitude" is F(x_0)^2 = M, and its edge cost is
x_0^2/b. So the pair (+-x_0) is exactly the symmetric, single-coin-like
configuration that matches the crossing's height b. The plan is: show f
must actually BE this configuration, i.e. a signed coordinate.
STEP 2 - THE CALIBRATED EDGE COST. The basic energy (10.2) threw away a
nonnegative margin. Keep it. For 0 <= v < F(1)^2 define
Phi(v) = x^2/H(x) - v, x = F^{-1}(sqrt v), j(v) = Phi(v)/v.
The calibrated edge inequality is, for every edge,
(D_i d) D_i(d/H(d)) >= (D_i g)^2 + Phi( (D_i g)^2 ).
It keeps the exact cost of a noised coordinate. The functions j and Phi
are nonnegative, increasing, and convex, and Phi'(v)/v is increasing; all
proved in the paper by differentiating the noise curve.
STEP 3 - THE CALIBRATION CONSTANTS. Around the calibration point M we
need two numbers: the slope and the lost excess,
p_* = Phi'(M) = (1 + b^2)/(2 alpha b^{3/2}) - 1, (slope)
Delta = M + Phi(M) - K = (s - b)(1 + 1/(bs)). (loss)
Both are >= 0. Their sizes are tiny in the central band, and the bounds
are exact rational comparisons:
Phi(M)/M < .0063, p_* < .019, p_*/M < .0532, Delta/M < .008.
STEP 4 - THE ENERGY BOOKKEEPING. Let a_i be the degree-one Fourier
coefficients of g, and set
q = sum_i a_i^2 (degree-one weight),
l = max_i a_i^2 (largest single-coordinate weight),
H_0 = Var(g) - q (weight above degree one).
Combine the calibrated edge inequality with the tangent line of Phi at M
and Jensen's inequality on the largest coordinate. The result is
E(d) >= K + (1+p_*)(Var g - M) + (1-p_*) H_0 - p_*(q - l) + Delta.
Read it: the energy is at least the budget K, plus a reward for having
MORE variance than the calibration, plus a reward for higher-degree
content, minus a small penalty for the first level spreading out. At a
crossing the energy is <= K, so all the rewards must be nearly zero. Two
facts pin that down.
STEP 5 - VARIANCE GAIN. Set V_0 = E[(g^2 - M)^2] and the constant
C_0 = .034. The variance cannot lag the calibration much:
Var(g) - M >= C_0 V_0 - Delta/(1 + p_*).
If m > 0 there is a strict bonus + .016 m^2. If m = 0 the inequality is
strict unless g^2 = M at every point. The proof is a pointwise remainder
estimate: write R = g - alpha d, use the differential equation satisfied
by the noise curve k, and show the remainder exceeds C_0 times the spread
of g^2 minus small pieces. The crux is two explicit polynomials in the
unit square, P_1 and P_2, that must be positive; they are checked by
positive Bernstein coefficients (see section 11).
STEP 6 - FIRST-LEVEL CONCENTRATION. The penalty -p_*(q-l) is controlled
by how far the first level spreads. Put
L_1 = sum_i a_i x_i, P = L_1^2 - q, W = E[P^2].
Then q - l <= W/(2q), and a degree-three estimate plus Cauchy-Schwarz
gives
sqrt(W) <= sqrt(V_0) + 4.32 sqrt(q H_0).
The constants satisfy, on every row of the parameter table,
p_*/((1+p_*) q C_0) + p_* (4.32)^2/(1 - p_*) < 1.95 < 2.
Weighted Cauchy-Schwarz then absorbs the whole penalty:
p_* W /(2q) <= (1+p_*) C_0 V_0 + (1-p_*) H_0.
STEP 7 - CLOSE. Substitute the variance gain into the energy bookkeeping
and absorb the penalty. If the variance gain is strict, the energy is
strictly above K, contradicting the crossing. The only surviving case is
m = 0 and g^2 = M everywhere. Then |d| = rho everywhere (F is odd and
strictly increasing). Parseval with m = 0 forces every Fourier weight of
f above degree one to vanish, so f = sum_i c_i x_i with sum c_i^2 = 1.
The identity f^2 = 1 then forces at most one nonzero c_i, of square 1.
So f is a signed coordinate. That is the central band.
(The finite arithmetic here is the pair of polynomial sign checks P_1,
P_2 above, plus the rational comparisons in STEP 3. The supplied program
central-band certificate does all of it with exact rationals.)
10.4b THE INTERMEDIATE BAND (r^2/2 <= m <= .74).
GOAL. If b = h-1+s here, then E(d) > r/s: a crossing is impossible.
The bias is real but not huge. The trick is to split d into its even and
odd parts and to linearize around m.
STEP 1 - PARITY. For a function u write u_even(x) = (u(x)+u(-x))/2 and
u_odd(x) = (u(x)-u(-x))/2. Every nonconstant even degree is at least 2,
and every odd degree other than 1 is at least 3. Applying the basic
energy (10.2) to both g and its even part,
E(d) >= sum_i E(D_i g)^2 >= Var(g) + Var(g_even).
The even part pays an EXTRA variance. The odd part is capped by 10.3:
Var(d_odd) <= r [ (1-r^2) w + r^2 h^2 ].
STEP 2 - LINEARIZE AT m. Let a = F'(m) = h^{-3/2} and measure the
concavity deficit of H at m:
V = h - H(d) - m (d - m)/h >= 0, and E[V] = h - b = v.
(First inequality: H is concave. Second: it is exactly b = h - v.)
Expand Var(g) around the affine approximation F(m) + a(d-m). The cross
and square terms produce the pointwise expression
Psi = 2a(d-m)( g - F(m) ) - (a^2/2)(d-m)^2 - 3V.
Putting together the parity energy, the variance expansion, and the odd
cap gives the ENERGY REDUCTION
E(d) >= 3v + E[Psi] - (r/2) Q, Q = (1-r^2) w / h^3 + r^2 / h.
So the crossing (E(d) <= r/s) is excluded as soon as
E[Psi] > (r/2)(Q - Q_*), Q_* = 6/(1+s) - 2/s = 2(2s-1)/(s(1+s)),
because the exact identity 3v - (r/2) Q_* = r/s makes the bookkeeping
line up. Everything now hinges on a POINTWISE lower bound for Psi.
STEP 3 - POINTWISE BOUNDS ON Psi. The paper proves, for every -1 < d < 1,
Psi >= (1/2 - 2m^2) V^2 if 0 <= m <= 1/5,
Psi >= -(1/100) V if 1/5 <= m <= 2/3,
Psi >= -(1/50) V if 2/3 <= m <= 37/50.
The first line is a positive GAIN (a multiple of V^2). The other two are
tiny LOSSES (a small multiple of V). Since E V = v and, by Jensen,
E V^2 >= v^2, these become global bounds E[Psi] >= (1/2-2m^2) v^2, or
E[Psi] >= -(1/100) v, or E[Psi] >= -(1/50) v.
STEP 4 - CLOSE WITH EXPLICIT MARGINS. Split into three sub-ranges.
* r^2/2 <= m <= 1/5. Bound Q <= Q_0 = (1 + r^2 m)/(h(1+m)) using
w <= 1-m. The hypothesis m >= r^2/2 plus the crude h >= 1 - .51 m^2
give, after rearrangement, (1-Q)/m beyond a quantity R(m,s) that the
exact rationals squeeze. The upshot is
(1+s)/(2v) (Q - Q_*) < 1/2 - 2m^2,
and multiplying by v^2 turns the positive gain into the needed
strict inequality.
* 1/5 <= m <= 2/3. For r <= .2944 the function Q_0 is convex in m, so
Q is at most its endpoint maximum, computed exactly: Q < .866.
Meanwhile Q_* is increasing in s with Q_*(.84) = 425/483 > .879. The
exact margin is
.92 (.879 - .866) - .01 = 49/25000 > 0.
* 2/3 <= m <= .74. The other piece of w (the p^{3/2} term) gives
Q < .852 throughout, and the exact margin is
.92 (.879 - .852) - .02 = 121/25000 > 0.
Each margin forces E[Psi] to exceed (r/2)(Q-Q_*), hence E(d) > r/s. The
crossing is impossible. That is the intermediate band.
STEP 5 - WHERE THE POINTWISE BOUNDS COME FROM. The three lines of STEP 3
are proved in ANGULAR coordinates. Put beta = arcsin m and let t be half
the angular gap between d and m. Then d - m = 2 cos(c) sin(t) for a shift
c, the height H(d) and the deficit V become clean (V = 2 sin^2(t)/h), and
Psi/V becomes
4 sqrt(q) A - q^2 - 3,
where A is an explicit integral in the angular variable and q is a simple
function of t and beta. Keeping three terms of a positive expansion of
1/sqrt(cos) and bounding sqrt(q) by an exact rational identity squeezes
Psi/V between two explicit polynomials in T (the scaled bias) and
x = tan(t/2). Those polynomials must keep one sign on stated rectangles;
the paper checks that their Bernstein coefficients are all positive
(orders up to (8,18) for the shear polynomials and (6,20) for the two
large-sign polynomials, six polynomials after the chart choices), using
exact rational arithmetic. Positive Bernstein coefficients on a square
prove the polynomial is positive there. That is the finite heart of the
intermediate band.
10.4c THE LARGE-BIAS BAND (.74 <= m < 1).
GOAL. Prove h - b <= 1 - s directly; there is no crossing to exclude.
When the output is very lopsided the target is easiest to meet, and a
direct moment estimate does the job.
STEP 1 - REPARAMETRIZE BY AN INDICATOR. Let A = {x : f(x) = -1}, of
probability p = (1-m)/2, which lies in (0, .13] because m >= .74. Let
U = T_rho 1_A = (1-d)/2. Then
H(d) = 2 sqrt(U) sqrt(1-U), E[U] = p.
Expand sqrt(1-U) binomially. For 0 <= z <= 1,
1 - sqrt(1-z) = sum_{k>=1} c_k z^k,
c_k = binom(2k,k) / ((2k-1) 4^k), c_1 = 1/2,
c_{k+1} = c_k (k - 1/2)/(k + 1).
This gives the exact SERIES IDENTITY
h - b = 2(sqrt p - E sqrt U)
+ 2 sum_{k>=1} c_k ( E[U^{k+1/2}] - p^{k+1/2} ).
So bounding h-b means comparing moments E[U^q] of the noised indicator
with the moments p^q of the raw indicator, for exponents q that are half
integers.
STEP 2 - TWO NORM INEQUALITIES. The noise semigroup controls moment
growth. For q > 0 with q != 1, put p_q = 1 + r(q-1). Then for every
u_0 >= 0,
E[(T_rho u_0)^q] <= (E[u_0^{p_q}])^{q/p_q} if q > 1,
E[(T_rho u_0)^q] >= (E[u_0^{p_q}])^{q/p_q} if 0 < q < 1.
The first is forward (Bonami-Beckner) hypercontractivity; the second is
the reverse (Borell) inequality. Both are proved in the paper from the
cube logarithmic Sobolev inequality by Gross's semigroup method. They are
the only external theorems in this band.
STEP 3 - THE SERIES BOUND. Apply the q = 1/2 line to E sqrt U (a lower
bound, with p_{1/2} = (2-r)/2) and the q_k = k+1/2 lines to E[U^{k+1/2}]
(upper bounds). Both bracket types become nonnegative, and
h - b <= 2( p^{1/2} - p^{1/(2-r)} )
+ 2 sum_{k>=1} c_k ( p^{q_k/(1+r(q_k-1))} - p^{q_k} ).
Each bracket increases in p on [0,.13] (the derivative condition reduces
to p <= (a/b)^{1/(b-a)} >= e^{-2} > .13), so replace p by the worst case
p_* = 13/100.
STEP 4 - FOUR NOISE INTERVALS, EXACT RATIONALS. Split .84 <= s < 1 into
[.84,.88], [.88,.92], [.92,.96], [.96,1].
On each, bound the first difference by a trapezoid estimate and each
series term by one of three explicit rational bounds, using only rational
arithmetic. To evaluate p_*^z without floating point, use the exponential
envelope
S_N(x) = sum_{j=0}^N x^j / j!, E(z) = 1 / S_40( (51/25) z ),
which dominates p_*^z for all z >= 0. Two exact brackets pin the log and
the root:
2.04 < log(100/13) < 2.041, sqrt(p_*) < 0.361.
The first ten binomial coefficients and the tail are exactly
(c_1,...,c_10) = (1/2, 1/8, 1/16, 5/128, 7/256,
21/1024, 33/2048, 429/32768, 715/65536, 2431/262144),
1 - sum_{k<=10} c_k = 46189/262144.
Carrying the rational evaluation on the four intervals gives integer
ceilings (in units of 1e-9) for the three bound pieces B, S, T, and the
resulting upper bounds:
interval B(ceil) S(ceil) T(ceil) max of (h-b)/(1-s)
[.84,.88] 746521967 60049597 2525240 0.982
[.88,.92] 748896408 56019174 1084482 0.969
[.92,.96] 750555827 51401364 283275 0.954
[.96,1] 751524751 46967364 36923 0.940
Every total is strictly below 1, so h - b < 1 - s throughout .84 <= s < 1.
The endpoint s = 1 is trivial (rho = 0, both sides 0). That completes the
large-bias band, and with it Machine B.
(The companion large-bias certificate checks the coefficient data, the
logarithm brackets, every table entry, and the final comparisons in exact
rational arithmetic.)
--------------------------------------------------------------
11. THE COMPUTER'S PART: HOW A FINITE CHECK BECOMES A PROOF
--------------------------------------------------------------
Several times we said "checked by exact arithmetic". This section says
what that means and why it is a proof, not an experiment.
11.1 THE PRINCIPLE. Every constant here is a rational number. The claims
still to be checked are always of the form "this explicit polynomial (or
interval expression) is positive on this explicit box", together with a
finite list of rational comparisons. A program decides such claims
exactly, using integer and rational arithmetic with no rounding. When it
reports "all coefficients are positive" or "the lower endpoint is
positive", that is a true finite statement about integers, and running it
over the finitely many boxes proves the claim on the whole region. There
is no floating-point approximation anywhere to trust or distrust.
11.2 THE BERNSTEIN CRITERION (THE STAR TOOL). Any polynomial P on the
unit square can be written in the Bernstein basis:
P(x,y) = sum_{i=0}^{N} sum_{j=0}^{K} b_ij
* binom(N,i) x^i (1-x)^{N-i}
* binom(K,j) y^j (1-y)^{K-j}.
The basis functions are nonnegative and sum to 1 on the square. So if
every coefficient b_ij is >= 0, then P >= 0 on the whole square. The
coefficients come from the ordinary power coefficients c_ab by
b_ij = sum_{a<=i, b<=j} c_ab * binom(i,a)/binom(N,a)
* binom(j,b)/binom(K,b),
pure integer arithmetic once denominators are cleared. To prove P
strictly positive on a rectangle, map the rectangle affinely to the unit
square (still rational), then subdivide until every box has all Bernstein
coefficients positive. Positivity of coefficients is checked exactly.
This is how the paper certifies the profile polynomials (9.4), the
central-band signs P_1 and P_2 (10.4a), and the intermediate signs
(10.4b): each becomes "the Bernstein coefficients of a concrete
polynomial are all positive on every box of a finite list".
11.3 INTERVAL ARITHMETIC AND THE MEAN-VALUE TEST. When a quantity is not
one polynomial but a rational expression with square roots, use INTERVAL
ARITHMETIC. Store an interval [a/Q, b/Q] with integers a <= b at a fixed
scale Q. Addition, subtraction, multiplication, division obey the
endpoint rules; multiplication takes the least and greatest of the four
endpoint products; a reciprocal needs zero excluded; a square root needs a
nonnegative interval and integer square bounds. Every operation rounds
OUTWARD, so the true value stays enclosed. A failed domain check never
certifies a box; it forces a subdivision.
To sharpen the test, carry the three first derivatives with the value. If
I_c encloses P(center) and J_i encloses dP/dx_i on the whole box, the
mean-value theorem gives
P(box) lies inside I_c +/- sum_i h_i * (bound on J_i),
with h_i the box half-widths. A positive lower bound after this step
certifies the box. This is the "center plus derivative" test used for the
pair and base-case computations.
11.4 THE ACTUAL PROGRAMS. The finite work is split into small programs,
each checking one family of statements:
interval_certificate.cpp the three pair regions of 9.4(1), by
interval arithmetic with the mean-value
test, to stated subdivision depths.
profile_certificate.py the 17 induction profiles of 9.4: the
positivity of P, the reflection E_B, and
the closure signs J, V; plus the three-coin
base case, on 128 subintervals per row.
central_band.py the central-band polynomial signs P_1, P_2.
(intermediate) the six U and L_eps polynomials of 10.4b,
on their charts.
large_bias.py the coefficient data, the logarithm
brackets, and the four-interval rational
table of 10.4c.
profile_formula_audit.py an independent reconstruction of the
profiles and the printed data.
The C++ program uses outward-rounded integer intervals with 128-bit
intermediates and a hard overflow guard; the Python programs use
arbitrary-precision integers. An overflow guard failure causes further
subdivision, never a silent acceptance.
11.5 WHY THE CHECK IS TRUSTWORTHY. Three reasons.
(a) EXACTNESS. No floating point enters any certificate. Every step is
integer or rational.
(b) REDUNDANCY. The audit script rebuilds the polynomial coefficients
by a different route and compares them to the printed data.
(c) DIRECTION. The tests can only OVER-estimate the size of an error,
never hide it. A failed check refines the box; a successful check
is a genuine finite proof on that box.
The output is a finite list of true integer inequalities -- exactly the
kind of object a skeptic can recheck by hand or by a fresh program. That
is the sense in which the theorem is computer-assisted: not "we believe
it numerically", but "here are the finitely many exact statements that
close the proof".
--------------------------------------------------------------
12. FROM AFFINITY TO INFORMATION: THE CK ALGEBRA, SLOWLY
--------------------------------------------------------------
This closes the loop promised in section 6: the Hellinger bound (*)
implies the Courtade-Kumar information bound. Recall epsilon = (1-rho)/2,
so rho = 1 - 2 epsilon, and H(rho) = s.
THE CONVERSION FUNCTION. Define
phi(t) = h_2( (1 - H(t)) / 2 ), H(t) = sqrt(1 - t^2).
Here is the identity that makes it work. For any u in [-1,1],
phi(H(u)) = h_2( (1 - H(H(u)))/2 ) = h_2( (1 - |u|)/2 ).
And h_2((1-|u|)/2) = h_2((1+u)/2), because binary entropy is symmetric
under p <-> 1-p and the two probabilities (1-|u|)/2 and (1+u)/2 are
complementary. So
phi(H(u)) = h_2( (1+u)/2 ) for every u in [-1,1].
THE MUTUAL INFORMATION. For a single bit f(X),
I(f;Y) = H_2(f(X)) - H_2(f(X)|Y). The first term is h_2((1+m)/2). The
posterior mean of f given the message y is E[f(X)|Y=y] = T_rho f(y) = d,
so the conditional bit has probability (1+d)/2, and the second term is
E[h_2((1+d)/2)]. Using the identity,
I(f;Y) = phi(H(m)) - E[ phi(H(d)) ] = phi(h) - E[phi(H(d))].
STEP 1 - phi IS INCREASING AND CONVEX. Differentiate; the paper gets
phi'(t) = ( t / (2 v log 2) ) * log((1+v)/(1-v)) >= 0,
phi''(t) = ( log((1+v)/(1-v)) - 2v ) / (2 v^3 log 2) >= 0,
where v = sqrt(1 - t^2). The last numerator is >= 0 because its
derivative in v is 2 v^2/(1-v^2) >= 0 and it vanishes at v = 0.
STEP 2 - JENSEN. Since H(d) has average b = E[H(d)] and phi is convex,
E[ phi(H(d)) ] >= phi( E[H(d)] ) = phi(b).
Therefore I(f;Y) <= phi(h) - phi(b).
STEP 3 - USE THE HELLINGER BOUND. Because H is concave,
b = E[H(d)] <= H(E d) = H(m) = h, so delta := h - b >= 0. The Hellinger
theorem (*) is exactly delta <= 1 - s. So the interval [b,h] has length
delta <= 1-s, and it sits inside [0,1].
STEP 4 - STEEPEN THE INCREMENTS. For a convex increasing phi, the gain
over a window of fixed length grows as the window moves right. Hence,
since h <= 1,
phi(h) - phi(b) = phi(h) - phi(h - delta)
<= phi(1) - phi(1 - delta).
Because delta <= 1-s we have 1-delta >= s, and phi is increasing, so
phi(1-delta) >= phi(s). Thus
phi(1) - phi(1 - delta) <= phi(1) - phi(s).
STEP 5 - READ OFF THE ANSWER. phi(1) = h_2((1 - 0)/2) = h_2(1/2) = 1.
And phi(s) = h_2((1 - H(s))/2) = h_2((1-rho)/2) = h_2(epsilon). Therefore
I(f;Y) <= 1 - phi(s) = 1 - h_2(epsilon).
That is the Courtade-Kumar bound. A dictator has m=0 and d=rho x_1, so
every inequality above is an equality, giving I = 1 - h_2(epsilon). The
endpoint cases (delta = 0, rho = 0 or 1) follow by continuity.
--------------------------------------------------------------
13. ENDPOINTS, SYMMETRIES, AND THE MAIN THEOREM
--------------------------------------------------------------
13.1 THE REDUCTIONS. A few clean reductions let us assume the nice case.
* Negative noise. T_{-rho} f(x) = T_rho f(-x). As (-x) runs over the
cube exactly as x does, both expectations are unchanged. So assume
rho >= 0, i.e. 0 <= s <= 1.
* Constant f. If f is constant, T_rho f = f and both sides of (*) are
0. So assume f nonconstant, which for 0<rho<1 gives -1<T_rho f(x)<1
at every x; all derivatives below are legitimate.
* Sign of the mean. Replacing f by -f preserves both sides of (*) and
sends m to -m. So assume m = E[f] >= 0.
* Endpoints. rho = 0 (s = 1): T_0 f = m, so the left side is
H(m)-H(m) = 0. rho = 1 (s = 0): the left side is H(m) <= 1, and the
right side is 1. Both hold. The interesting range is 0 < rho < 1.
13.2 ASSEMBLING THE MAIN THEOREM.
THEOREM (Hellinger conjecture). For every n >= 1, every Boolean
f : {-1,+1}^n -> {-1,+1}, and every rho in [-1,1],
H(m) - E[ H(T_rho f) ] <= 1 - H(rho).
Equality holds for signed coordinates (dictators).
PROOF. By 13.1 assume 0 < rho < 1, f nonconstant, m >= 0. Then
s = sqrt(1-rho^2) is in (0,1).
* If s <= .84: the dimension induction (section 9, Theorem
induction) gives E[H(T_rho f)] >= H(m) - 1 + s, which is (*).
* If s >= .84: suppose (*) fails. By the crossing trick (10.1) the
failure produces a crossing b = h-1+s with E(d) <= r/s. The mean
m lies in the central, intermediate, or large-bias band (10.4).
The central band (10.4a) says a crossing forces a signed
coordinate. The intermediate band (10.4b) says a crossing is
impossible. The large-bias band (10.4c) says (*) already holds.
So no non-dictator fails, and the only functions that reach the
boundary are dictators, which have equality.
Combining the two ranges and the endpoints proves (*) for every
n, f, rho. []
13.3 THE INFORMATION COROLLARY. Corollary of section 6 and the algebra
of section 12: for epsilon = (1-rho)/2,
I(f(X);Y) <= 1 - h_2(epsilon),
with equality for dictators.
That is the full result of the paper: the single coin is the most
informative one-bit summary a noisy message can carry, measured either by
Hellinger affinity or by information.
--------------------------------------------------------------
APPENDIX A. GLOSSARY FOR HIGH-SCHOOL READERS
--------------------------------------------------------------
BOOLEAN FUNCTION. A rule that takes a row of signs (+1/-1)^n and returns
one sign +1 or -1. "The answer to one yes/no question about the row."
UNIFORM CUBE. All 2^n rows, each equally likely. E[...] means average
over them.
CHARACTER chi_S. The product of the coins in a set S. The characters are
an orthonormal "basis of sounds" for functions on the cube.
FOURIER COEFFICIENT. hat_u(S) = E[u chi_S]. The amount of u that "rings"
at the frequency S. Degree |S| = number of coins in S.
VARIANCE. Var(u) = E[u^2] - (E u)^2, the spread of u. By Parseval it is
the sum of the squares of the nonzero Fourier coefficients.
NOISE OPERATOR T_rho. Averages u over the noisy version of the row. On
characters it just scales them: T_rho chi_S = rho^|S| chi_S. Multi-coin
frequencies fade faster under noise.
BINARY SYMMETRIC CHANNEL. The faulty wire: it flips a coin with
probability epsilon = (1-rho)/2, independently for each coin.
HELLINGER AFFINITY. For two distributions P, Q, the number
sum_z sqrt(P(z) Q(z)), in [0,1]. It is 1 when they are identical and
small when they are easy to tell apart. The Hellinger distance is 1 minus
it (or twice it, by convention).
ENTROPY h_2(p). The information (in bits) of a coin that lands heads with
probability p: h_2(p) = -p log_2 p - (1-p) log_2(1-p). Maximum 1 bit at
p=1/2, minimum 0 at p=0 or 1.
MUTUAL INFORMATION I(A;B). The number of bits about A that seeing B
reveals. Zero when independent; the entropy of A when B determines A.
CONVEX / CONCAVE. A convex function bends up (its graph lies below its
chords); a concave function bends down (lies above its chords).
JENSEN'S INEQUALITY. For convex f and a random variable Z:
E[f(Z)] >= f(E[Z]). For concave f the inequality reverses. This is the
workhorse behind feeding averages through curved functions.
CAUCHY-SCHWARZ. (sum a_i b_i)^2 <= (sum a_i^2)(sum b_i^2), the
"two-vectors-are-longest-aligned" inequality. It converts products of
sums into squared sums, again and again here.
HYPERCONTRACTIVITY. The property that the noise operator either raises or
lowers L^q norms in a controlled, exact way. The forward (Bonami-Beckner)
and reverse (Borell) versions are the two norm inequalities of 10.4c.
SEMIGROUP. The family of operators T_{e^{-tau}} for tau >= 0, with the
"apply again = apply more noise" rule. We differentiate along tau to get
the energy identity.
DICTATOR / SIGNED COORDINATE. The function f(x) = x_i or -x_i. It reports
one coin and ignores the rest. It is the extremal example everywhere.
BERNSTEIN BASIS. An alternative polynomial basis (powers of x times powers
of 1-x) whose coefficients are nonnegative exactly when the polynomial is
nonnegative on the box. The certificate tool of section 11.
INTERVAL ARITHMETIC. Doing arithmetic with whole intervals and rounding
outward, so the true answer is always enclosed. Used with the mean-value
test to certify rational expressions.
--------------------------------------------------------------
APPENDIX B. SYMBOLS
--------------------------------------------------------------
n number of coins (coordinates)
x, y true row and noisy row in {-1,+1}^n
rho wire quality in [-1,1]; E[x_i y_i] = rho
epsilon flip probability, (1-rho)/2
T_rho noise operator
f Boolean summary, values +-1
m mean of f, E[f]
h H(m)
H(t) sqrt(1-t^2), the Hellinger profile
d T_rho f, the noised summary
b E[H(d)]
s sqrt(1-rho^2), the noise level
r rho^2 = 1 - s^2, the signal level
v 1 - s, the budget
K r/s, the target energy
E(d) the energy, E sum_i (D_i d) D_i(d/H(d))
F(x) integral of (1-z^2)^{-3/4} dz
g F(d)
Phi(v) calibrated edge excess, x^2/H(x) - v with x = F^{-1}(sqrt v)
M, alpha calibration point M = F(x_0)^2, alpha = F(x_0)/x_0
p_*, Delta calibration slope and loss
C_0 .034, the central variance constant
q, l, H_0 degree-one weight, largest coordinate weight, higher weight
L_1, W linear part sum a_i x_i and E[(L_1^2 - q)^2]
V concavity deficit (intermediate band)
Psi pointwise energy expression (intermediate band)
Q, Q_* intermediate-band bookkeeping quantities
U T_rho 1_A, the noised indicator (large bias)
p (1-m)/2, indicator probability (large bias)
c_k binomial coefficients of 1 - sqrt(1-z)
G, B guiding curve and induction profile (Machine A)
lambda(h) L + U h + V h^2 in the guiding curve
p_* worst-case probability .13 (large bias) OR slope (central);
context disambiguates -- both are local to their sections
--------------------------------------------------------------
CLOSING NOTE
--------------------------------------------------------------
The theorem says something you can state to anyone: among all one-bit
summaries of a noisy message, reading a single coin is optimal, whether
you measure how distinguishable the two conditionals are (Hellinger
affinity) or how many bits you learn (mutual information). The proof is
long because "no summary beats one coin" must survive every bias, every
noise level, and every dimension. It is split cleanly: sorting and
induction for low noise, a noise-flow energy argument for high noise, and
three bias bands each with a finite exact certificate. The computers do
only finite arithmetic on concrete polynomials, and every one of those
arithmetic statements is checkable by hand. That is the entire paper,
told straight.