PaperlayerView exact revision on arXiv

Source-linked AI summary

The Hellinger Conjecture for Antipodal Boolean Functions

Vu Khac Ky

arXiv:2610.10618v1cs.ITmath.COmath.ITmath.PR

TL;DR

The balanced Hellinger conjecture asks whether a single input bit minimizes the overlap of output laws induced by a Boolean decision under binary symmetric noise. The paper proves a sharp bound for antipodal decisions and extends it to independent binary-input channels. It also identifies settings beyond the main theorem that remain outside its argument.

  • Problem

    The balanced Hellinger conjecture asks whether retaining one input bit minimizes the Bhattacharyya coefficient of the two conditional output distributions under binary symmetric noise.

    Source: §1 · p. 1

  • Method

    The paper studies the induced-channel Bhattacharyya parameter for balanced Boolean functions and applies the argument to independent binary-input channels.

    Source: §1 · p. 2

  • Results

    For independent binary-input channels, every antipodal Boolean function satisfies Z_W(f) ≥ min_i Z_i, with equality for a signed dictator on a coordinate of minimum affinity.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The bound also applies when flipping a fixed nonempty coordinate subset reverses the function, and concavity gives a corresponding bound for randomized binary functions.

    Source: §4 · p. 8

    The argument assumes independent uniform input bits; biased inputs and arbitrary correlated channels generally fall outside its stated framework.

    Source: §6.2 · p. 12

Abstract

from arXiv · show

The balanced Hellinger conjecture compares the overlap of two output laws induced by a Boolean decision under binary symmetric noise. We prove that a single input coordinate minimizes this overlap among antipodal decisions, whose values reverse when all input signs are reversed, throughout the noise interval. The proof uses a normalized nuclear norm of the cross-class block of the Gram matrix of square-root channel densities. Multiplication by an antipodal decision exchanges the even and odd Fourier spaces preserved by the Gram matrix. A coordinate exchange attains the minimum cost of matching their spectra. A matrix contraction extends the sharp bound to arbitrary independent binary-input channels. Fixed coordinate flips and randomized decisions follow from the same argument and concavity. These extensions give bounds for information and testing, including linear Gaussian observations, and a weighted edge-boundary inequality.

1 Introduction and main results

The paper studies whether a single input bit minimizes the overlap of the two output laws induced by an antipodal Boolean decision under binary symmetric noise. It presents a spectral-matching argument for this symmetry and extends the bound to independent channels.

1 Introduction and main results

  • The balanced Hellinger conjecture asks whether retaining one input bit minimizes the Bhattacharyya coefficient under binary symmetric noise.For antipodal functions, reversing all input signs exchanges the two classes.Source: §1 · p. 1
  • For independent binary-input channels, every antipodal Boolean function has Z_W(f) ≥ min_i Z_i, with equality for a signed dictator on a minimum-affinity coordinate.The main results assume independent uniform input bits; coordinate channels may differ and have arbitrary measurable output spaces.Source: §1 · p. 2

1.1 Why symmetry helps

  • Multiplication by an antipodal function exchanges the even and odd spaces preserved by the Gram matrix, and a coordinate exchange attains the minimum spectral-matching cost.For equal coordinate affinities, pairing Fourier basis functions that differ by one fixed coordinate explains the sharpness.Source: §1.1 · p. 2

1.2 Related work

  • The paper distinguishes its full-output setting with a sign-reversing symmetry from prior work proving the weak conjecture for arbitrary Boolean functions and one-bit output statistics [10, Theorem 1.1].The Courtade–Kumar conjecture is described as recently proved for all Boolean functions and noise levels [12, Theorem 1.2], [5, Theorem 1.1].Source: §1.2 · p. 3

2 A matrix lower bound

This section reduces class-conditional output overlap to a matrix bound, then uses the spectra of two symmetry-exchanged invariant spaces to obtain a lower bound. The exchange-map optimization depends only on the two eigenvalue lists.

2 A matrix lower bound

  • The matrix result applies to any finite uniform input alphabet, while a separate result concerns two invariant spaces exchanged by a symmetry.The proof uses the nuclear norm of the matrix difference to lower-bound the sum of absolute differences between ordered eigenvalues.Source: §2 · p. 4, §2.2 · p. 5

2.1 From mixture affinity to a Gram matrix

  • The difference G − D_fGD_f removes within-class entries and doubles entries between classes; its nuclear norm is four times that of the cross-class block.If the function is constant, both sides of the stated bound are zero.Source: §2.1 · p. 4
  • For a finite uniform input, the Gram-matrix bound relates the affinity of the two output mixtures to the nuclear norm of the cross-class block.The Gram matrix uses pairwise inner products of square-root channel densities; the cross-class block contains entries between inputs assigned opposite function values.Source: §2.1 · p. 4

2.2 Exchanging two invariant subspaces

  • An exchange map can align the eigenbases of the two restrictions, so the minimum nuclear-norm cost depends only on their eigenvalue lists.The right-hand side of the exchange bound is the minimum over all such maps.Source: §2.2 · p. 5

3 Proof of the main theorems

The proof reduces the affinity bound to matching the even and odd spectra of a channel Gram matrix; a coordinate exchange realizes the sharp match. Coordinatewise monotonicity then extends the bound to unequal independent channels.

3.1 Even and odd Fourier subspaces

  • The Gram matrix preserves even and odd Fourier subspaces, while multiplication by an antipodal function exchanges them, yielding a lower bound from matching their eigenvalues.The bound is independent of the particular antipodal function.Source: §3.1 · p. 6

3.2 The exact matching cost

  • Pairing Walsh functions whose index sets differ by one coordinate attains the minimum spectral matching cost, and multiplication by that coordinate realizes the pairing.This coordinate exchange explains why signed dictators attain equality.Source: §3.2 · pp. 6–7
  • For equal coordinate affinities h, every antipodal Boolean function has q_f(h) ≥ h, with equality for signed dictators.For binary symmetric noise, the corresponding bound is 1 − ρ^2.Source: §3.2 · p. 7

3.3 Unequal coordinate channels

  • For unequal independent coordinate channels, coordinatewise monotonicity yields Z_W(f) ≥ min_i Z_i, with equality for a signed dictator on a minimum-affinity coordinate.The argument lowers affinities to their minimum even when eigenvalue ordering fails.Source: §3.3 · p. 7
  • Unrestricted eigenvalue matching can fall below min_i z_i; decreasing affinities while retaining the Boolean multiplier preserves the needed restriction.For z = (1/4, 1/2, 1/2, 3/4), the unrestricted normalized matching cost is 15/64 < 1/4.Source: §3.3 · p. 7

4 Other sign-reversing symmetries

The same bound applies when reversing any nonempty fixed subset of coordinates changes the function’s sign, and concavity extends it to randomized decisions with that symmetry. The section also gives examples of functions and circuits covered by these results.

4.1 A fixed subset of reversed coordinates

  • If a nonempty coordinate set S reverses f’s sign, then f is balanced and Z_W(f) ≥ min_{i∈S} Z_i.The stronger matrix bound q_f(z) ≥ min_{i∈S} z_i also holds.Source: §4.1 · p. 8
  • When several sign-reversing sets exist, the strongest bound uses the set maximizing min_{i∈S} Z_i; in particular, f(x)=x_i u(x_{[n]\{i}}) has bound Z_i.This applies for any Boolean function u of the remaining coordinates.Source: §4.1 · p. 8

4.2 Randomization

  • If g has the same sign-reversal symmetry, the randomized decision B is balanced and its output-law affinity is at least min_{i∈S} Z_i.A signed dictator on a minimum-affinity coordinate in S attains equality.Source: §4.2 · p. 8

4.3 Examples

  • Linear thresholds with zero threshold are antipodal when the weighted sum never vanishes; opposite tie assignments preserve antipodality, and fair tiebreaking is covered by the randomized bound.The randomized result also covers conditional means g(x)=tanh(a^T x).Source: §4.3 · p. 9
  • Circuits with no constant inputs and gates that reverse their outputs when all inputs reverse compute antipodal functions, even with shared variables or gates.The intermediate gate outputs need not be independent.Source: §4.3 · p. 9

5 Information and testing

The section converts the affinity bound into bounds for divergence, testing, and information, then applies the results to independent and correlated Gaussian observations. Output symmetry gives a Chernoff-information bound, while correlated Gaussian observations are handled through stochastic degradation from a product channel.

5.1 Divergence, error probability, and mutual information

  • For a sign-reversal set S, the Rényi divergence D_1/2(P+∥P−) is at most −2 log z*, and under binary symmetric noise this bound is −log(1 − ρ^2), sharp for a dictator.Source: §5.1 · p. 9
  • When channels on S are output-symmetric, Chernoff information is at most −log z*, with equality for a signed dictator on a minimum-affinity coordinate.Source: §5.1 · p. 10
  • For independent repetitions from the two class-conditional laws, Chernoff information is the optimal equal-prior error exponent; repeating observations of one fixed hidden input is a different model.Source: §5.1 · p. 10

5.2 Independent and correlated Gaussian observations

  • Correlated Gaussian observations are treated as degraded outputs of product Gaussian channels, and the bound need not be attained by a dictator for a given nondiagonal A.Source: §5.2 · p. 11
  • For linear Gaussian observations, affinity is at least e^(−L/2) and Chernoff information is at most L/2; both constants are sharp among models with the same L.Source: §5.2 · p. 11

6 Scope of the argument

Balancedness does not imply the sign-reversal symmetry used by the argument, even for monotone Boolean functions. The section describes limits on extending the method, including extremizer classification and scope beyond its assumptions.

6.1 Balancedness does not imply sign-reversal symmetry

  • A monotone Boolean function can be balanced without having any fixed sign-reversing coordinate set, so balance alone does not provide the symmetry used in the proof.The example’s slice means are 1/2 and −1/2, while a nonzero even-degree Fourier coefficient rules out such a set.Source: §6.1 · p. 12
  • Adding an input bit can make a Boolean function antipodal, but the added noise parameter prevents this construction from immediately proving the general conjecture.Removing the added bit’s noise also removes the useful lower bound.Source: §6.1 · p. 12

6.2 Equality and scope

  • Classifying all extremizers requires tracking equality through the Gram triangle inequality and spectral comparison, plus coordinatewise monotonicity for unequal channels.An interior classification must treat ρ = 0 and ρ = 1 separately, where every balanced function has equality; stability would also need to control losses at each step.Source: §6.2 · p. 12
  • The product-channel theorem assumes independent uniform bits; biased inputs and general correlated channels fall outside its argument, as does the balanced problem without sign-reversal symmetry.The linear Gaussian result covers a particular correlated observation model through stochastic degradation, not a general removal of those assumptions.Source: §6.2 · p. 12

A A weighted edge-boundary limit

A small-noise expansion turns the nuclear-norm bound into a weighted edge-boundary inequality. The weighted adjacency block across the two function classes records the edges cut by the function, and signed dictators on minimum-weight coordinates attain the stated constants.

A weighted edge-boundary limit

B An extension by one input bit

An arbitrary Boolean function can be extended to an antipodal Boolean function by adding one input bit. The extension bound does not directly recover the original balanced conjecture because its noise parameter must be set to one, where the bound becomes zero.

B An extension by one input bit

  • Decomposing f into odd and even parts gives the antipodal Boolean extension g(x0, x) = fo(x) + x0fe(x).Source: B An extension by one input bit · p. 13
  • The added bit’s correlation s controls Mρ(s), an even concave function that is nonincreasing on [0, 1].At s = 1, Mρ(1) equals the original functional Zρ(f).Source: B An extension by one input bit · p. 13
  • Setting s = ρ gives a dictator bound, but recovering the original functional requires s = 1, where the bound becomes zero.Balancedness removes the constant Fourier coefficient but not the other even degrees, and concavity alone gives the wrong direction to control this loss.Source: B An extension by one input bit · p. 13

C.1 Convexity of the entropy comparison function √

The comparison function is monotone and convex on the closed interval, as shown by derivative signs in the interior and continuity at the endpoints.

C.1 Convexity of the entropy comparison function √

  • Both derivatives are nonnegative for 0 < z < 1, with positivity of the logarithm supporting the sign argument.Source: §C.1 · p. 14
  • The integral representation of the logarithm gives a lower bound of 2u used in establishing the derivative signs.Source: §C.1 · p. 14
  • Continuity and F(0) = 0, F(1) = 1 extend monotonicity and convexity to the closed interval without endpoint substitution into derivative formulas.Source: §C.1 · p. 14

C.2 Spectral matching with unequal affinities

For unequal coordinate affinities, an exact spectral comparison gives a normalized matching cost of 15/64, below the minimum affinity 1/4.

C.2 Spectral matching with unequal affinities

  • The Walsh eigenvalue indexed by T is the product of (1 − z_i) over i in T.Source: §C.2 · p. 14
  • For z = (1/4, 1/2, 1/2, 3/4), the parity-sorted spectrum has 64b = (189, 105, 105, 45, 21, 9, 9, 5).Source: §C.2 · p. 14
  • The normalized cost is 15/64, below min_i z_i = 1/4, explaining the use of coordinatewise monotonicity after the equal-affinity spectral comparison.Source: §C.2 · p. 14
Loading 2610.10618v1…