The Kneser--Poulsen phenomena for entropy
Gautam Aishwarya Dongbin Li




Faculty of Mathematics, Technion - Israel Institute of Technology, Haifa 3200003, Israel.
gautamaish@gmail.com

Faculty of Science - Mathematics and Statistical Sciences, University of Alberta, Edmonton, AB T6G 2R3, Canada.
dongbin@ualberta.ca
§ ABSTRACT 
     The Kneser–Poulsen conjecture asserts that the volume of a union of balls in Euclidean space cannot be increased by bringing their centres pairwise closer. We prove that its natural information-theoretic counterpart is true. This follows from a complete answer to a question asked in <cit.> about Gaussian convolutions, namely that the Rényi entropy comparisons between a probability measure and its contractive image are preserved when both undergo simultaneous heat flow.

MSC classification:
		37C10, 
            94A17, 
            52A40, 
            52A20. 
	
GA was supported by ISF grant 1468/19 and NSF-BSF grant DMS-2247834. DL acknowledges the support of the Natural Sciences and Engineering Research Council of Canada and the Department of Mathematical and Statistical Sciences at the University of Alberta.


The Kneser–Poulsen phenomena for entropy
    Dongbin Li
    September 9, 2024
========================================



§ INTRODUCTION AND MAIN RESULTS

Owing to the striking resemblance between various phenomena in convex geometry and information theory, one is naturally led to the study of parallels between the two subjects. This direction of research goes back at least to the work of Costa and Cover <cit.> in the early 1980's, when they explicitly observed the similarity between the Brunn–Minkowski inequality in convex geometry and the Entropy Power inequality in information theory, both being cornerstone results in their respective fields. A connection between these inequalities was perhaps observed even earlier by Lieb, appearing implicitly in the work <cit.>. From this point onwards, one finds a continuous stream of works elaborating the underlying dictionary between convex geometry and information theory while enriching both fields in the process (for example, <cit.>). We shall refrain from giving a general overview of this vibrant field and refer the interested reader to the beautifully presented survey article <cit.> (and the references therein) for a bigger picture.

We aim to supplement the evidence in favour of the Kneser–Poulsen conjecture, as well as offer a new potential tool, by observing that the mirroring entropy-version holds. Recall that, the Kneser–Poulsen conjecture in convex and discrete geometry asserts the intuitive statement that volume of the union of a finite collection of balls of a fixed radius cannot increase if their centres are brought closer together.
[Kneser–Poulsen, <cit.>] 
Let {x_1 , … , x_k} and {y_1, ⋯ , y_k} be two sets of points in ℝ^n such that ‖ y_i - y_j‖_2≤‖ x_i - x_j‖_2 for all i, j ∈{1, …, k}. If r> 0, then we have:

    ( ⋃_i=1^k (y_i, r) ) ≤( ⋃_i=1^k (x_i, r) ),

where  is the Lebesgue measure on (^n, ‖·‖_2) and ℬ(x,r) is the ball of radius r centred at x.


    Sometimes a more general version is considered where the radii of the balls are allowed to be different. However, we will restrict ourselves to the original formulation as stated above. 

If K = { x_1 , … , x_k}, the set ⋃_i=1^k (x_i, r) can be rewritten as the Minkowski sum K + rℬ. By an elementary approximation-from-within argument one can go from finite sets to compact sets in order to rephrase Conjecture <ref> in the manner below.
 
For every contraction (that is, a 1-Lipschitz map) T: (K, ‖·‖_2) → (^n, ‖·‖_2) defined on a compact set K 
⊆^n, r>0, we have

    (T[K] + r ) ≤ (K + r ).



Beyond the n=2 case which was resolved by Bezdek and Connelly <cit.>, very little is known. For a general dimension n, the Kneser–Poulsen conjecture has been established in various cases, under rather strong restrictions on the set K and the map T. For example, Csikós <cit.> proved Conjecture <ref> for continuous contractions (see Definition <ref>). A modification of the formulas for volume obtained by Csikós play a key role in Bezdek and Connelly's proof in the plane where they are delicately combined with an old trick (used previously, for example, by Alexander <cit.>) to move the x_i to the y_i in a larger ambient space. Other such examples include the more recent work of Bezdek and Naszódi <cit.> which demonstrates the conjecture for uniform contractions, that is, when there exists λ > 0 such that ‖ y_i - y_j‖_2 < λ < ‖ x_i - x_j‖_2 for all i ≠ j. In the same work, the authors also settle the case when the pairwise distances are reduced in every coordinate. For the current state-of-the-art regarding the Kneser–Poulsen conjecture, including many foundational works as well as recent exciting developments that we have skipped here, we refer the reader to <cit.>. However, despite the progress made so far, the Kneser–Poulsen conjecture remains largely out of reach. This is perhaps due to the fact that, at present, there is no way to deal with arbitrary contractions in a manner amicable to the geometric computations required in this context.  

In the pioneering comparison of the Brunn–Minkowski inequality and the Entropy Power inequality discussed earlier, one immediately observes that Euclidean balls correspond to Gaussian measures and (the logarithm of) volume corresponds to the Shannon–Boltzmann entropy. Indeed, on one hand, the Brunn–Minkowski inequality can be stated in the form 

    (A + B) ≥ (A^∗ + B^∗),

where A^∗, B^∗ denote Euclidean balls having the same volume as A,B, respectively. On the other hand, the Entropy Power inequality asserts that 

    h(X + Y) ≥ h(X^∗ + Y^∗),

where h(·) denotes the Shannon–Boltzmann entropy (see Definition <ref>), X,Y are independent random vectors, X^∗, Y^∗ are independent Gaussian random vectors having the same entropy as X,Y, respectively. 

These correspondences, summarised in Table <ref>, indicate that the Shannon–Boltzmann entropy of the heat flow X + √(s)Z is the natural information-theoretic analogue of the volume of a tube K + r. In this paper, we prove that the information-theoretic analogue mimics the geometric phenomena predicted by the Kneser–Poulsen conjecture <ref>. Before we state our main result concretely, which is more general than the last claim, we set up some notation.




    (K + r )   h(X + √(s) Z).













  §.§.§ Some notation and definitions

Throughout, unless stated otherwise, all sums X + Y of random vectors will be sums of independent random vectors. The density of a random vector X with respect to the Lebesgue measure (if it exists) will sometimes be denoted by f_X. The letter Z is reserved for a random vector having the standard Gaussian distribution in the ambient space, that is, if the discussion is in ^n we will have f_Z(x) = 1/(2 π)^n/2e^- ‖ x ‖^2_2/2. The word “Gaussian” will also be used for scalings of Z.

  
Let X be an ^n-valued random vector with density f with respect to the Lebesgue measure. Then, the Rényi entropy of order α∈ (0,1)∪ (1, ∞) of X is given by,

    h_α(X) = 1/1 - αlog∫_^n f^αx̣.

The Rényi entropy of orders 0, 1, and ∞ are obtained via taking respective limits,

    h_0(X) = log ((f)), 
       h_1(X) =  -∫ f log f, 
       h_∞(X) = - log‖ f ‖_∞.

The special case h_1 (·) is called the Shannon-Boltzmann entropy, often denoted simply by h(·). 


For an ^n-valued random vector X with distribution μ having density f with respect to the Lebesgue measure, we will abuse notation and use h_α(X), h_α (μ) , and h_α(f), interchangeably. A property of Rényi entropies that we shall use later is that h_α(X,Y) = h_α(X) + h_α(Y) holds if X,Y are independent vectors taking values in ^n, ^m, respectively. 
 
  Let T : K →^n be a contraction, i.e., a 1-Lipschitz (K, ‖·‖_2) → (^n, ‖·‖_2). The map T is said to be a continuous contraction if each point x ∈ K can be joined to T(x) ∈ T[K] by a curve c_x: [0,1] →^n such that ‖ c_x(t) - c_y(t) ‖_2 is monotonically decreasing. In this case, we call T_t: x ↦ c_x(t) a continuously contracting family of maps.



 §.§ The main result

It is simple to check that h_α(X) ≥ h_α(T(X)) if T is a contraction. However, when the distributions of X and T(X) both undergo simultaneous heat flow to X + √(s)Z, and T(X) + √(s)Z, respectively, there may not be a contraction mapping the former to the latter. Our main result says that nevertheless their Rényi entropies may be compared.

    Let T: ^n →^n be a 1-Lipschitz map. Then for every ^n-valued random vector X, s ≥ 0, we have  
    
    h_α(X + √(s)Z) ≥ h_α(T(X) + √(s)Z),

    for all α∈ [0, ∞].

    Suppose T_t is a continuously contracting family of maps starting in a set K ⊂^n (that is, T_0 is defined on K) with smooth trajectories, and X is a K-valued random vector. Then, the stronger conclusion holds: for any convex function ϕ: [0, ∞) → satisfying ϕ (0) = 0, 
    
    ∫ϕ (f_T_t(X) + √(s)Z) x̣

    is monotonically increasing in t.


    Continuous contractions induce totally-ordered curves with respect to a majorisation order <cit.>. The second part of our result says that such curves continue to be totally-ordered under the action of Gaussian convolution. 

Note that the main theorem completely answers <cit.> for Gaussian noise. Moreover, as explained in <cit.>, a result such as Theorem <ref> for the uniform distribution on a ball rather than the Gaussian would immediately yield the Kneser–Poulsen conjecture. 

Examples satisfying the hypothesis for the second part of Theorem <ref> appear quite naturally in probability theory. The (reverse) Ornstein–Uhlenbeck flow on strongly log-concave measures <cit.>, the (reverse) heat flow for log-concave measures <cit.>, and the maps inducing displacement interpolation when the final transport map is 1-Lipschitz— are all examples of continuous contractions.

Of course, the information-theoretic analog of the Kneser–Poulsen conjecture is the special case α=1.
 
    For every 1-Lipschitz map T: ^n →^n and random vector X, we have h(X + √(s)Z) ≥ h(T(X) + √(s)Z).

Perhaps from an adjacent viewpoint, the Kneser–Poulsen theorem for information transmission would be the following statement.
 
    Suppose Alice wants to communicate with Bob using the alphabet K = { x_1 , ⋯ , x_k} over a noisy channel with additive white Gaussian noise: Bob receives the random point x + Z when Alice sends x. The optimal rate at which information can be reliably transmitted across this noisy channel cannot be improved by bringing points in K pairwise closer.

In information theory, this optimal rate is called the channel capacity 𝒞 (see <cit.> for a quick mathematical introduction). Shannon, in his landmark work <cit.>, showed that this quantity has a clean mathematical expression which translates to the following in the setting of Corollary <ref>:

    𝒞 = sup_X I (X; X + Z),

where the supremum is over all random vectors taking values in K, and the mutual information I(X; X + Z) = h(X+Z) - h(X+Z | X) = h(X+Z) - h(Z) measures the amount of information shared between the “input”X and the “output” X + Z. Theorem <ref> shows I (X; X + Z) ≥ I(T(X); T(X)+Z) thereby proving Corollary <ref> in a pointwise-sense. We suspect that Corollary <ref> may hold in more generality, for every radially-symmetric log-concave noise W instead of the Gaussian Z. It is possible to approach the Kneser–Poulsen conjecture directly based on Rényi-generalisations of channel capacity, but this will be pursued elsewhere. 



 §.§ Plan of proof of Theorem <ref>
 We first prove the second part using a mass-transport argument. Given a curve {μ_t}_t ∈ [0,1] of probability measures and a velocity-field v_t compatible with it, in Proposition <ref> we obtain a formula for a velocity-field ṽ_t compatible with the noise-perturbed curve {μ_t⋆ν}_t ∈ [0,1], where ν is any measure with density. In Section <ref> we show, under the assumption ν = γ is the standard Gaussian measure, that if T_t is continuously contracting, μ_0 any probability measure, μ_t = T_t_#μ_0, then ·ṽ_t≤ 0. Proposition <ref> allows us to deduce the second part of Theorem <ref> from this divergence condition. The first part elegantly follows from the second part, using the same old trick of extending the phase space. Only this time, thanks to the tensorisation properties of both the Gaussian measure and Rényi entropies, the argument goes through in all dimensions effortlessly. 



 §.§ Acknowledgements

We would like to express our heartfelt gratitude to Irfan Alam, Serhii Myroshnychenko, and Oscar Zatarain-Vera, for many enriching discussions around the Kneser–Poulsen theme. We are indebted to Boaz Slomka for introducing us to the Kneser–Poulsen conjecture. 
 


§ PREPARATION: CURVES OF PROBABILITY MEASURES, PERTURBATIONS BY CONVOLUTIONS

Let {μ_t}_t ∈ [0,1] be a curve of probability measures in ^n. We say that a time-dependent velocity-field { v_t}_t ∈ [0,1] is compatible with {μ_t}_t ∈ [0,1] if the transport equation

    ∂_tμ_t + · (v_tμ_t) = 0

is satisfied in the weak sense. The latter equation means that 

    /ṭ∫ f μ̣_t = ∫⟨ f , v_t⟩μ̣_t,

for all test functions f. 

Given a one-parameter family of maps T_t, say such that the trajectory T_t(x) of each point x is smooth, paths of measures and compatible velocity-fields arise naturally in the following manner. Fix a probability measure μ_0, define μ_t = T_t_#μ_0. Define v_t as the trajectory field of T_t using the equation /ṭ T_t(x) = v_t (T_t(x)). Then v_t is a time-dependent velocity field compatible with μ_t. 
 
    Velocity-fields v_t corresponding to continuous contractions have the monotonicity property ⟨ v_t(x) - v_t (y) , x - y ⟩≤ 0 on the support of v_t.


Let x_0, y_0 be such that T_t(x_0) = x, T_t(y_0) = y, then 

    0 ≥/ṭ‖ T_t(x_0) - T_t(y_0) ‖_2^2   = 2 ⟨ v_t(T_t(x_0)) - v_t(T_t(x_0)) , T_t(x_0) - T_t(y_0) ⟩
       = 2 ⟨ v_t(x) - v_t (y) , x - y ⟩ .

 
Given a curve of probability measures, the dynamics of its noise-perturbation is described below.
 
    Let {μ_t} be a curve of probability measures and v_t a time-dependent velocity-field compatible with it. Suppose ν is a measure having smooth density. Then, a time-dependent velocity field compatible with the curve μ̃_̃t̃ = μ_t⋆ν is given by the conditional expectation
    
    ṽ_̃t̃(x) = [ v_t(X_t) | X_t + Y = x ],

    where X_t∼μ_t, Y ∼ν is independent of the X_t. 


  Let f be a test function. Suppose ν has density g with respect to the Lebesgue measure. Then,
  
    /ṭ∫ f(x) (̣μ_t⋆ν)(x) 
           = /ṭ∫[ ∫ f(x) g(x-y)  x̣] μ̣_t(y) 
       = ∫⟨_y( ∫ f(x) g (x-y) x̣) , v_t(y) ⟩μ̣_t(y) 
       = ∫⟨ -∫ f(x) ( g)(x-y) x̣ , v_t (y) ⟩μ̣_t(y) 
       = ∫⟨∫ f (x) g(x-y) x̣ , v_t (y) ⟩μ̣_t(y) 
       = ∫⟨ f (x)  , ∫ v_t (y) g(x-y) μ̣_t(y) ⟩x̣
       = ∫⟨ f (x) , ∫ v_t(y) g (x-y) μ̣_t(y)/μ_t⋆ g (x)⟩μ_t⋆ g (x) x̣
       = ∫⟨ f (x) ,  [ v_t(X_t) | X_t + Y = x ] ⟩(̣μ_t⋆ν)(x).

  Thus, the continuity equation ∂_tμ̃_̃t̃ + · (ṽ_̃t̃μ̃_̃t̃) = 0 is verified. 

We need one more ingredient to allow us to conclude entropic inequalities from compatible velocity-fields.
 
    Let μ_t be a curve in the space of probability measures and a time-dependent velocity field v_t compatible with it. Suppose each μ_t has density ρ_t with respect to the Lebesgue measure. Then, if · v_t≤ 0 for all t, then ∫ f (ρ_t) x̣ is monotone in t for every convex function f : ^n → [0, ∞) such that f(0) = 0.


    We have, 
    
    /ṭ∫ f (ρ_t) x̣   = ∫ f ' (ρ_t) ρ̇_̇ṫx̣ = - ∫ f ' (ρ_t) · (v_tρ_t) x̣
       = ∫⟨ρ_t (f ' (ρ_t)) , v_t⟩x̣.

    Note that, ρ_t (f ' (ρ_t)) =  (ψ∘ρ_t), where ψ (w) = w f'(w) - f (w). Thus, 
    
    ∫⟨ρ_t (f ' (ρ_t)) , v_t⟩x̣ = ∫⟨ (ψ∘ρ_t), v_t⟩x̣ = - ∫ψ (ρ_t) · v_tx̣.

    On the other hand, since f is convex with f (0) = 0, 
    
    ψ (ρ_t) = ρ_t f ' ( ρ_t ) - f (ρ_t) = ρ_t(  f ' (ρ_t) - f (ρ_t) - f(0)/ρ_t - 0) ≤ 0.

    This shows that, /ṭ∫ f (ρ_t) x̣≥ 0 if · v_t≤ 0.
  



§ PROOF OF THEOREM <REF>
 
Let T_t be a family of continuously contracting maps in ^n having smooth trajectories. Call the corresponding velocity field v_t. Now, let μ_0 be any probability measure and μ_t := T_t_#μ_0. Consider μ̃_̃t̃ = μ_t⋆ν, where ν̣= g x̣ = e^-Vx̣. We are interested when ν is the distribution of √(s)Z, and thus g = C_se^-‖ x ‖_2^2/2s,  g(x) = - g (x)  V (x) =  - g (x) x/s. We shall write the proof for s=1, the case of a general s works in exactly the same manner. 

Recall that, by Proposition <ref>, a velocity-field compatible with μ̃_̃t̃ is given by

    ṽ_̃t̃(x) = ∫ v_t(y) g (x - y) μ̣_t(y)/∫  g (x - y) μ̣_t(y).

Hence,

    ṽ_̃t̃(x) =    ∫ v_t(y) 
     ⊗_x( g (x - y) ) μ̣_t(y) /∫  g (x - y) μ̣_t(y)
       - ∫_x( g (x - y) ) μ̣_t(y) ⊗∫ v_t(y) g (x - y) μ̣_t(y)/( ∫  g (x - y) μ̣_t(y) )^2
    
    =     - ∫ v_t(y) 
     ⊗ V (x - y) g (x - y) μ̣_t(y) /∫  g (x - y) μ̣_t(y)
        +  ∫ V (x - y)g (x - y) μ̣_t(y) ⊗∫ v_t(y) g (x - y) μ̣_t(y)/( ∫  g (x - y) μ̣_t(y) )^2.

Let Y = Y_t,x be a random vector with density f_x(y) = g(x-y)/∫ g(x-y) μ̣_t(y) with respect to μ_t. Then, by taking trace,

    ·ṽ_t (x) 
       = - ⟨ v_t(Y) ,  V (x-Y) ⟩  + ⟨ V (x-Y) ,  v_t(Y) ⟩
       = - ⟨ v_t (Y) , x ⟩ + ⟨ v_t(Y), Y ⟩ + ⟨ x ,  v_t (Y) ⟩ - ⟨ Y ,  v_t(Y) ⟩
       = ⟨ v_t (Y) , Y ⟩  - ⟨ Y ,  v_t(Y) ⟩
       = ⟨ v_t(Y) -  v_t(Y) , Y-  Y ⟩.

Now, since (Y -  Y) = 0, v_t (Y) can be replaced with any constant of choice. Extending v_t to Y if necessary (by a theorem of Minty <cit.>), we choose the constant to be v_t( Y) so that 

    ·ṽ_̃t̃ (x) = ⟨ v_t (Y) - v_t ( Y) , Y -  Y ⟩≤ 0.


This, by an application of Proposition <ref>, establishes the second part of Theorem <ref>.

For the first part, suppose an arbitrary 1-Lipschitz map T: ^n →^n is given. Consider the continuous contraction in ^2n defined by the trajectories S_t (x) = (√(1-t)x, √(t)T(x)). The standard Gaussian in ^2n can be written as Z = (Z_1, Z_2), where Z_1, Z_2 are independent ^n-valued standard Gaussians. For any ^n-valued random vector X, we have

    h_α (X + Z_1) + h_α(Z_2)    = h_α(X + Z_1, Z_2)  
       =h_α ((X,0) + Z) ≥ h_α (S_1(X,0) + Z) 
       = h_α((0, T(X)) + (Z_1, Z_2)) 
       =h_α (Z_1, T(X) + Z_2) 
       = h_α(Z_1) + h_α (T(X) + Z_1).

Cancelling off the Rényi entropy of the standard Gaussian on both sides completes the proof.

    When n=1, since “divergence = derivative”, much stronger conclusions can be drawn by looking at the continuous contractions-part of the proof:
    
    
  * The proof works for arbitrary log-concave probability densities g (that is, whenever V is convex). This requires an application of Chebyshev's other inequality <cit.> after the first equality in Equation <ref>.
     
  * The transport maps induced by the velocity fields ṽ_t are contractions.     
    
    These one-dimensional results are already known albeit with a different proof <cit.>.




§ RELATED MATTERS: COSTA'S EPI FOR CONTINUOUS CONTRACTIONS

The entropy power inequality is commonly expressed in terms of the entropy power, which is defined by 

    N(X) = 1/2 π e e^2 h(X)/n,

for an ^n-valued random vector. Analogous to the volume-radius in convex geometry <cit.>, N(X) is the variance of the Gaussian having same entropy as X.










amsplain

