Manuscript Oai119-A@1 · Oai119-A.tex · corollary · fdff7292

Corollary: Complete finite Courtade–Kumar certificate

The Courtade–Kumar implication as a corollary · lines 1148–1194 · proof included or linked

Oai119-A@1#cor:finiteCK, Oai119-A@1#eq:strictMI

At $n = 2$ , $ρ = 1/2$ , and $ε = 1/4$ ,

I_{2} (f (X); Y) \leq 1 - h_{2} (1/4)

for every Boolean $f$ . Equality holds precisely for the four signed coordinates. Every other Boolean function satisfies

1 - h_{2} (1/4) - I_{2} (f (X); Y) > \frac{1}{50} bit .

For the named parity comparison,

I_{2} (x_{1} x_{2}; Y) = 1 - h_{2} (3/8) .

Proof. Apply Proposition prop:HtoI to Theorem thm:finite. For a noncoordinate function, $η = Γ (f) > 27/1000$ . By (eq:conversionlower),

φ (s_{0} + η) - φ (s_{0}) \geq \frac{2 s _{0} η + η ^{2}}{2 ℓ} \geq \frac{s _{0} η}{ℓ} .

Now $s_{0} > 4/5$ , by squaring, and $ℓ = \int_{1}^{2} d t / t < 1$ . Consequently the information gap is strictly greater than

\frac{4}{5} \frac{27}{1000} = \frac{108}{5000} > \frac{1}{50} .

For a coordinate, (eq:MI) and $T_{1/2} x_{i} = x_{i} /2$ give the exact value $1 - h_{2} (1/4)$ . For parity, the posterior mean is $\pm 1/4$ , giving $1 - h_{2} (3/8)$ .

Displayed formulas in this passage

Oai119-A@1#eq:strictMI · line 1156
$1 - h_{2} (1/4) - I_{2} (f (X); Y) > \frac{1}{50} bit .$
unlabeled · line 1151
$I_{2} (f (X); Y) \leq 1 - h_{2} (1/4)$
unlabeled · line 1162
$I_{2} (x_{1} x_{2}; Y) = 1 - h_{2} (3/8) .$
unlabeled · line 1172
$φ (s_{0} + η) - φ (s_{0}) \geq \frac{2 s _{0} η + η ^{2}}{2 ℓ} \geq \frac{s _{0} η}{ℓ} .$
unlabeled · line 1181
$\frac{4}{5} \frac{27}{1000} = \frac{108}{5000} > \frac{1}{50} .$

Corollary: Complete finite Courtade–Kumar certificate

Displayed formulas in this passage

Nearby in this section