PaperlayerView exact revision on arXiv

Source-linked AI summary

Shannon's problem on the monotonicity of entropy and a Conjecture of Tao

Ziran Liu

arXiv:2609.00399v1math.PRcs.ITmath.COmath.IT

TL;DR

The paper addresses whether discrete convolution sums satisfy a useful entropy-monotonicity bound, despite the failure of literal normalized-sum monotonicity for discrete laws. It proves Tao’s fixed-order conjecture on torsion-free abelian groups and develops separate results on one-real-direction entropy monotonicity and spectral covering.

  • Problem

    For discrete laws, literal monotonicity of the entropy of normalized sums is not the right general statement, leaving the appropriate entropy-increment bound as the question.

    Source: §1.1 · pp. 1–2

  • Method

    The proof separates spectral recurrence from spatial localization, using the exact convolution spectrum before introducing a flat progression model to localize mass.

    Source: §9 · p. 58

  • Results

    The paper proves Tao’s discrete entropy-monotonicity conjecture for every fixed convolution order and finitely supported laws on torsion-free abelian groups.

    Source: §9 · p. 58

  • Takeaways & Limitations

    The proof also formulates one-real-direction entropy monotonicity and rank-independent spectral covering as independently stated components.

    Source: §9 · p. 58

    The result is restricted to torsion-free groups: finite-subgroup uniform inputs have zero increments, and the Gaussian constant cannot be increased.

    Source: §1.2 · p. 4

Abstract

from arXiv · show

Let $X_1,X_2,\ldots$ be i.i.d. finitely supported random variables in a torsion-free abelian group, and write $S_k=X_1+\cdots+X_k$, and $H(S_k)$ is the Shannon entropy $S_k$, for all $k \ge 1$. We prove that, for every fixed $n\geq1$, \[ H(S_{n+1})-H(S_n) \geq \frac12\log\frac{n+1}{n} -o_{H(X_1)\to\infty}(1), \] uniformly over the ambient group and the input law. This proves a conjecture of Tao [29] in 2010.

1. Introduction

The paper proves Tao’s high-entropy entropy-increment conjecture for each fixed convolution order on torsion-free abelian groups. This discrete result addresses why normalized-sum monotonicity does not transfer literally to discrete laws.

1.1. Shannon’s problem and entropy monotonicity.

  • Shannon’s entropy-power inequality established the normalized entropy comparison for two summands; Lieb stated the conjecture that the normalized sequence is nondecreasing for all k.Artstein, Ball, Barthe, and Naor later proved that continuous monotonicity for all k [1].Source: §1.1 · p. 1
  • Discrete laws lack continuous scaling to remove lattice spacing, and additive collisions preserve arithmetic information, so literal normalized-sum monotonicity is not the right general target.A deterministic variable already has zero entropy increment, ruling out an exact analogue for every law.Source: §1.1 · p. 2, §1.2 · p. 2

1.2. Tao’s conjecture and the main theorem.

  • Tao’s proposed discrete target recovers the Gaussian lower bound for unnormalized entropy increments in the high-entropy regime, assuming torsion is excluded [29].Tao’s earlier result covered two summands, while the general fixed-n statement was conjectured but not established there [29].Source: §1.2 · p. 2
  • For every fixed n, sufficiently high input entropy gives H(S_{n+1}) − H(S_n) ≥ 1/2 log((n+1)/n) − ε, uniformly over torsion-free groups and input laws.The threshold depends on n and ε; no uniformity as n → ∞ is asserted.Source: §1.2 · p. 3
  • With torsion, uniform laws on finite subgroups have zero entropy increment, so no positive uniform high-entropy increment bound holds over general abelian groups.The paper also notes that the Gaussian constant cannot be increased, even in the torsion-free setting.Source: §1.2 · p. 4
  • A universal dimensional factor requires a nondegeneracy assumption, since an input law may be supported on a rank-one subgroup.The theorem’s uniformity is independent of ambient or support-generated rank, but is only for each fixed order.Source: §1.2 · pp. 3–4

1.3. Companion main results.

The companion results extend entropy monotonicity to a setting with one real direction, control large-spectrum characters, and transfer approximate periods into sharp entropy increments.

1.3. Companion main results.

  • Theorem 1.7 extends continuous entropy monotonicity to one embedded real direction with a discrete quotient, assuming finite quotient-label support and bounded, compactly supported conditional densities.Its entropy difference is independent of the Haar-measure normalization.Source: §1.3 · p. 5
  • Theorem 1.7 is proved by regularizing along the real direction, using a fiberwise de Bruijn identity and a conditional-score variance drop.At the large-time endpoint, the discrete quotient contributes a nonnegative label-entropy increment.Source: §1.3 · p. 5
  • Theorem 1.8 bounds the number of characters needed to cover the large spectrum, independently of progression rank, side lengths, displacement support, and ambient group.The covering controls the characters’ phases along the progression’s first direction.Source: §1.3 · pp. 5–6
  • Theorem 1.9 transfers a nonzero approximate period into the sharp entropy increment for i.i.d. sums on a torsion-free abelian group.The proof embeds the discrete shift as a real unit translation in a quotient and combines Theorem 1.7 with a Jensen–Shannon decomposition and maximal coupling.Source: §1.3 · p. 6

1.4. Proof strategy.

The proof uses bounded entropic doubling to obtain exact-spectrum recurrence, then a separate flat localization and a diagonal selection to produce nonzero near-period shifts and reach a contradiction.

1.4. Proof strategy.

  • Concavity of i.i.d. convolution-entropy increments supplies the small-doubling reduction, while recurrence is imposed on the exact law’s large spectrum.A proxy spectrum leaves a positive error floor as the threshold shrinks, obstructing the nth-root step.Source: §1.4 · pp. 7–8
  • Tao’s inverse theorem and a coupling-lifting argument represent each exact law as a uniform progression variable plus a possibly dependent bounded-entropy displacement.The progression can be enlarged for comparison without changing the original dependent coupling.Source: §1.4 · p. 7
  • A separate bounded-rank progression supports a flat probability mass function, which localizes one copy of the law and helps convert a global L2 estimate into total variation.The two progression data sets need not be related.Source: §1.4 · p. 8
  • The proof fixes the localization error before lowering the spectral threshold and increasing the recurrence scale through blockwise diagonal selection.This avoids requiring uniform control of structural constants as the localization error tends to zero, then produces nonzero near-period shifts for the contradiction.Source: §1.4 · p. 8

1.5. Earlier work.

Earlier work established continuous entropy monotonicity and developed discrete entropy and additive-combinatorial analogues. The fixed-order discrete bound here differs from prior results because it permits arbitrary finitely supported laws and varying torsion-free groups.

1.5. Earlier work.

  • Continuous work established normalized entropy monotonicity for all convolution orders, alongside related Fisher-information, entropic central-limit, and information-inequality approaches.The cited entropic central limit theorem concerns convergence in relative entropy, not consecutive convolution-order comparisons.Source: §1.5.1 · p. 9

1.5.2. Entropy, sumsets, and inverse structure.

  • Entropy sumset theory links Shannon-entropy inequalities with additive structure; the proof invokes Tao’s inverse theorem and the Tao–Vu containing theorem for generalized arithmetic progressions.Tao also formulated the fixed-order conjecture addressed here [29].Source: §1.5.2 · p. 9

1.5.3. Partial results for Tao’s fixed-order conjecture.

  • Earlier fixed-order bounds applied under log-concavity or other regularity conditions, whereas this theorem permits arbitrary finitely supported laws and support-generated rank that can grow with the law.The cited higher-dimensional result gives an increment with error O_d,n(H(X1)e^-H(X1)/d) for its regularity class.Source: §1.5.3 · p. 9, §1.5.4 · p. 9

1.5.4. Other discrete entropy-power regimes.

  • Other discrete entropy-power results use different structural assumptions, ambient algebra, or quantifier order, and do not supply this arbitrary-law, law-uniform fixed-n statement.The cited regimes include fixed-lattice central limits, finite-variance real laws, prime fields, and log-concavity.Source: §1.5.4 · p. 10

1.5.5. Free-probability analogues.

  • Free-probability work provides a parallel entropy-monotonicity theory, but no free-probability theorem is used in this proof.The paper also places standard information identities, Pontryagin duality, and score decompositions in their cited traditions.Source: §1.5.5 · p. 10, §1.5.6 · p. 10

1.6. Organization.

The paper moves from notation and identities to auxiliary theorems, then combines structural, Fourier, and entropy tools to prove the main result.

1.6. Organization.

  • Section 2 establishes notation and entropy and Fourier identities, and Section 3 proves Theorem 1.7.Source: §1.6 · p. 10
  • Sections 4 and 5 prove concavity and a small-doubling reduction, then develop inverse-additive interfaces and a flat high-probability core.Source: §1.6 · p. 10
  • Sections 6–8 build the quotient and near-period results, establish Theorems 1.9 and 1.8, and prove Theorem 1.2; the appendices provide two technical lemmas.Source: §1.6 · p. 10

2. entropy, conditional information, and Fourier analysis

This section establishes the information-theoretic, Fourier, and Haar-entropy conventions needed in later arguments. It supplies compatible countable-state identities, normalized Plancherel, and elementary entropy inequalities.

2.1. Discrete entropy and conditional information.

  • Entropy and convolution calculations can be restricted to the subgroup generated by the supports without changing the relevant quantities.For finitely supported laws in a torsion-free group, that subgroup is isomorphic to Z^d for some finite d.Source: §2.1 · pp. 11–12
  • Compatible countable-state relative-entropy and conditional-information identities keep later arguments well-defined, including when entropy differences could be indeterminate.Conditional entropies involving a finite-valued variable are defined from compatible kernels.Source: §2.1 · pp. 13–14

2.2. Fourier analysis on discrete abelian groups.

  • The Fourier section fixes conventions and verifies normalized Plancherel on arbitrary discrete abelian groups.It also establishes compactness of the dual and separation of points by characters.Source: §2.2 · pp. 16–17

2.3. Haar entropy and elementary inequalities.

  • Independent convolution does not decrease entropy, and entropy differences on one group are unchanged by overall Haar-measure normalization.For independent discrete variables A and B with finite entropies, H(A+B) is at least each of H(A) and H(B).Source: §2.3 · pp. 17–18

3. Hybrid entropy monotonicity by heat flow

The section develops a hybrid heat-flow proof by modeling Haar measure through discrete labels and real fibers, establishing a de Bruijn identity, Fisher-information decay, and small- and large-time entropy limits. These endpoints recover the unsmoothed entropy, so monotonicity along the flow yields the desired nonnegativity at time zero.

3.1. The fiber model and Haar entropy.

  • Haar measure is represented by counting measure on discrete labels and Lebesgue measure on real fibers, yielding an entropy decomposition into label and conditional-coordinate contributions.The fiber model also ensures the relevant convolution densities are bounded, compactly supported, and have finite Haar entropy.Source: §3.1 · pp. 18–20

3.2. Heat flow and the de Bruijn identity.

  • For every k ≥ 1 and t > 0, the proof establishes a fiberwise de Bruijn identity, justifying entropy differentiation and integration by parts with explicit Gaussian-tail and boundary estimates.The authors supply these regularity arguments for the discrete-label, real-fiber Haar setting rather than importing them from the Euclidean case.Source: §3.2 · pp. 20–21

3.3. Conditional scores and Fisher-information decay.

  • The conditional score identity and leave-one-out variance argument yield J_{k+1}(t) ≤ k/(k+1) J_k(t) for every k ≥ 1 and t > 0.The score of the output is the conditional expectation of an input score; the variance comparison uses a product-space Hoeffding/ANOVA decomposition.Source: §3.3 · pp. 22, 24, 25

3.4. The heat-flow endpoints.

  • For every integer k ≥ 1, the section identifies the small- and large-time limits of the heat-flow entropy for Y_k, whose quotient label is L_k.The endpoint analysis treats the real coordinate conditional on each label and verifies finiteness of the smoothed entropies.Source: §3.4 · p. 26
  • As s decreases to 0, h(f * ϕ_s) converges to h(f), and applying this endpoint result on finitely many fibers gives (3.24).The passage also establishes h(f * ϕ_s) ≥ h(f) for the smoothed densities.Source: §3.4 · p. 27
  • D_k(t) = F_{k+1}(t) − F_k(t) is nonincreasing, so D_k(t) ≥ D_k(T) whenever T > t > 0.Source: §3.4 · p. 28
  • D_k(t) ≥ 0 for every t > 0; letting t decrease to 0 and using (3.24) yields the zero-time conclusion.The proof uses Lemma 2.5 on the discrete quotient for the inequality at positive times.Source: §3.4 · p. 28

4. Discrete concavity and the small-doubling reduction

This section proves that convolution-entropy increments are nonincreasing and uses that fact to turn a small final increment into a small entropic-doubling bound. A mutual-information comparison yields the concavity inequality underlying the reduction.

4. Discrete concavity and the small-doubling reduction

  • The convolution-entropy increments d_k=H(S_{k+1})−H(S_k) are nonincreasing in k.The proof applies the entropy inequality H(A+B+C)+H(B)≤H(A+B)+H(B+C) to consecutive summands.Source: §4 · pp. 28–29
  • For independent finitely supported A, B, and C, the mutual-information comparison I(A;V)≤I(A;U) yields the entropy inequality used for concavity.Here U=A+B and V=U+C; the comparison follows from the conditional-independence and chain-rule argument.Source: §4 · p. 28
  • If d_n≤C for Q=S_n and an independent copy Q′, then H(Q+Q′)−H(Q)≤nC and exp{H(Q+Q′)−H(Q)}≤e^{nC}.The reduction uses the nonincreasing increments d_k and also establishes H(Q)≥H(X_1).Source: §4 · p. 29

5. From inverse entropic doubling to a flat core

The section combines Tao’s inverse entropy theorem and Tao–Vu properization with new coupling and covering arguments to construct a flat high-probability core. The imported results have distinct roles: the paper supplies the intervening steps without strengthening either theorem’s assumptions.

5.1. Inverse-theorem and properization inputs.

  • The inverse entropy theorem gives a uniform variable on a progression image and a displacement whose entropy is bounded, without requiring independence from the source variable.The reversed coupled form has U + Z = Y almost surely and H(Z) ≤ L(K) + η.Source: §5.1 · pp. 29–30
  • Tao–Vu properization enlarges a symmetric progression image to a proper progression of rank at most d and size at most CTVu(d)|P|.This imported result provides structural control, not a coupling or product-reference identity.Source: §5.1 · pp. 32–33
  • Tao’s inverse theorem supplies a bounded-rank progression, a uniform reference variable, and a transport-entropy bound; Tao–Vu properization supplies a proper outer progression with rank and size control.The paper proves the coupling lift and reversal, displacement truncation, dependent product-reference identity, and exact-spectrum covering argument itself.Source: §5.1 · p. 33

5.2. Construction of the flat core.

  • The augmented progression cover encloses the original progression image plus a finite set by enlarging the difference progression and then properizing it.The construction adjoins steps for differences among the finite-set elements before applying properization.Source: §5.2 · pp. 33–34
  • The flat-core proposition constructs a proper affine progression and a conditional law that forms a high-probability core; its constants depend on n, C, and η.The stated constants have no uniform control as η decreases to zero.Source: §5.2 · p. 34

6. A locally compact model for a discrete near-period

The section embeds a discrete group and a chosen nonzero shift in a locally compact quotient where that shift becomes a unit real translation. Unit jitter converts discrete entropy into Haar entropy, while a Jensen–Shannon decomposition bounds the overhead from near-periods.

6.1. The quotient and its Haar cells.

  • The quotient construction gives a locally compact abelian group with injective discrete and real embeddings satisfying j(r) = e(1), so translation by r becomes translation by one along the real fiber.The identity component is e(R), and the quotient by it is discrete, including when r is not primitive.Source: §6.1 · pp. 36–37

6.2. Unit jitter and entropy.

  • Adding an independent uniform unit jitter to an embedded discrete variable gives a Haar density whose entropy equals the variable’s Shannon entropy.The density is constant on each unit cell, whose Haar measure is one.Source: §6.2 · p. 38

6.3. Jensen–Shannon overhead and near-period absorption.

  • The multi-jitter overhead is expressed as conditional mutual information between the jitter count and the shifted variable given the fractional part.The k-jitter overhead is defined as I(Kk; Y + rKk | Fk).Source: §6.3 · pp. 39, 41
  • When shifts are near-periods, the overhead is bounded by h2(α) + α log k for α ≤ 1/2.The decomposition bounds the conditional mutual information using the probability of a mismatch in a maximal coupling.Source: §6.3 · pp. 41–42

7. Proof of the near-period transfer theorem

The proof embeds the discrete sums in the quotient group and adds independent jitters, verifying the transfer theorem’s hypotheses and finiteness conditions. It then combines the lower- and upper-order bounds to establish (1.8).

7. Proof of the near-period transfer theorem

  • The proof maps each discrete summand into the quotient and adds an independent uniform jitter, then verifies the transfer theorem’s hypotheses and finite-entropy requirements.The quotient label has finite support, and the conditional real-coordinate density is bounded with compact support.Source: §7 · p. 43
  • Substituting (7.2) and (7.3) into (7.1) and rearranging proves (1.8); on the upper-order side, Lemma 6.4 is applied to Y = Sn+1 and k = n+1 when nθ ≤ 1/2.Source: §7 · p. 43

8. Exact-spectrum recurrence and proof of the main theorem

This section develops quantitative recurrence from a rank-independent large-spectrum cover and applies it to the exact spectrum of p^*n, alongside a flat proxy for spatial localization and total-variation control. It also constructs a high-mass core and proper affine GAP reference for entropy transport, using these tools to complete the proof of the main entropy-increment bound.

8. Exact-spectrum recurrence and proof of the main theorem.

  • Recurrence is imposed on the large spectrum of the exact power q = p^*n, giving the complementary estimate |b_p| < a^(1/n) before the flat proxy is used.The resulting spectral L2 estimate contains no term involving δ; the proxy is introduced afterward to convert global L2 control into total variation on a finite high-mass set.Source: §8 · pp. 43–44, §8.2 · pp. 51–52

8.1.1. Two finite-dimensional tools.

  • Finite phase nets and a Gram–Bessel estimate give a large-spectrum cover of size bounded independently of progression rank, side lengths, displacement support, and ambient group.The cover selects characters whose phases along the longest progression direction approximate every character in the large spectrum.Source: §8.1.1 · p. 46

8.1. A directional large-spectrum cover from entropy transport.

  • A directional large-spectrum cover yields a nonzero recurrence shift R ≤ J M_tr(a,L), with simultaneous phase errors at most 1/J.The recurrence bound uses the cover cardinality rather than the rank or side lengths of the progression.Source: §8.1.1 · pp. 46, 49

8.2. Exact spectrum and a flat core.

  • For any fixed δ, Theorem 8.5 yields a sequence of nonzero shifts whose limsup defect is at most 3δ, but the sequence need not have defect tending to zero.Source: §8.2 · p. 51
  • For each j, the exact-spectrum argument finds a translate D_j=B_j−t_j carrying mass at least 1−δ and completes the proof of the total-variation estimate (8.33).The construction uses the resulting core to establish the stated estimate through the final limsup argument.Source: §8.2 · pp. 52, 54

8.3. A proper spectral reference from entropy transport.

  • Lemma 8.7 gives a proper affine GAP A of rank bounded in terms of K and a coupling U+Z=Q with U supported on A.The construction controls the size of A by a K-dependent factor over the intermediate GAP P, while the reference size satisfies log |P| ≥ H(Q)−L(K)−1.Source: §8.3 · pp. 54–56

8.4. Proof of the main theorem.

  • The proof takes the liminf of the increment, yielding a lower bound b_n−Ψ(3δ+ξ) before letting ξ decrease to zero.Here Ψ(u) = h2(nu) + nu log(n + 1); it is continuous at zero and increasing on [0, 1/(2n)].Source: §8.4 · pp. 57–58

9. Conclusion

The paper proves Tao’s discrete entropy monotonicity conjecture for every fixed convolution order and finitely supported law on a torsion-free abelian group. It identifies two independently formulated components and separates spectral recurrence from spatial localization in the convolution-power application.

9. Conclusion

  • The proof has two independent components: a one-real-direction entropy monotonicity theorem and an entropy-transport directional covering theorem.The covering theorem turns bounded relative entropy against a uniform progression reference into a rank-independent cover of exact large-spectrum phases along one progression direction.Source: §9 · p. 58
  • The paper proves Tao’s discrete entropy monotonicity conjecture for every fixed convolution order and finitely supported laws on torsion-free abelian groups.Source: §9 · p. 58
  • The application constructs recurrence from the exact spectrum of q = p∗n, then uses a separate flat progression model to localize mass and convert an L2 estimate into total variation.This avoids a stability comparison between the exact law and its flat approximation, allowing near-period transfer to recover the sharp Gaussian increment.Source: §9 · p. 58

Appendix A. An approximate-identity lemma

Appendix A proves an approximate-identity lemma for bounded, compactly supported probability densities on R. Its proof uses finite-interval approximations and translation continuity to establish L1 convergence.

Appendix A. An approximate-identity lemma

  • The resulting Gaussian smoothing converges to the original density in L1 as the variance parameter s decreases to zero.The proof bounds the integral by separating sufficiently small translations from the Gaussian tail probability.Source: Appendix A · pp. 58–59
  • A bounded compactly supported density is approximated through finite-valued functions and finite unions of bounded intervals.The proof approximates bounded measurable sets by finite unions of intervals and combines these approximations to construct a function close in L1.Source: Appendix A · pp. 58–59
  • Translation preserves the L1 norm, allowing the approximation bounds to transfer to sufficiently small translations.Source: Appendix A · p. 59

Appendix B. Relative entropy lower semicontinuity

Appendix B establishes lower semicontinuity of relative entropy under L1 convergence of probability densities, relative to a fixed strictly positive probability density. The proof uses a variational formula and handles the extended-real case.

Appendix B. Relative entropy lower semicontinuity

  • Relative entropy with respect to a strictly positive probability density is lower semicontinuous when the probability densities converge in L1.Source: Appendix B · p. 59
  • The proof begins with a variational formula and applies Jensen’s inequality under the probability measure with density f.Source: Appendix B · p. 60
  • The argument also covers infinite relative entropy, using monotone truncation for the positive part and an integrable bound for the negative part.The negative part uses 0 ≤ −u log u ≤ e−1 for 0 < u ≤ 1.Source: Appendix B · p. 60
Loading 2609.00399v1…