betaFeedback

WorksComputer Science

Dimension-free exponential entropy quotients over F2\mathbb{F}_2

Abstract

Let XX be a random vector in F2m\mathbb{F}_2^m, and let X′X' be an independent copy. We prove that, for every ε>0\varepsilon>0, there is a subspace GG with dim⁡G≤2320(1+ε)/εH(X)\dim G\le 2^{320(1+\varepsilon)/\varepsilon}H(X) such that H(qGX)≤(1+ε)(H(qGX+qGX′)−H(qGX))H(q_GX)\le(1+\varepsilon)(H(q_GX+q_GX')-H(q_GX)). In particular, the quotient entropy is at most (1+ε)(H(X+X′)−H(X))(1+\varepsilon)(H(X+X')-H(X)). The coefficient is independent of the ambient dimension, and its exponential order in 1/ε1/\varepsilon is necessary. The structural result is a logarithmic rigidity estimate for finite weighted families of laws with averaged subspace entropy sparsity. A common variational quotient controls both a family and its convolution family without decreasing the original family's normalized mean entropy defect. Posterior families preserve averaged sparsity, and a fresh-index argument combines a local-to-global estimate with the entropic Marton theorem to increase the defect ratio at a fixed multiplicative sparsity cost. We also obtain two-input almost-additivity and concentration of moderate-doubling sets on subspace cosets at the same exponential scale. The constants are not optimized.

Introduction

All random variables in this paper take values in finite binary vector spaces, and all entropies are Shannon entropies in bits. For a law XX, with X′X' an independent copy, define its entropy increment and entropy defect by

D(X)=H(X+X′)−H(X),E(X)=2H(X)−H(X+X′)=H(X)−D(X).(1)D(X)=H(X+X')-H(X), \qquad E(X)=2H(X)-H(X+X')=H(X)-D(X). \tag*{(1)}

For a subspace G≤F2mG\leq\mathbb{F}_2^m, write qG:F2m→F2m/Gq_G:\mathbb{F}_2^m\to\mathbb{F}_2^m/G for the quotient map. We prove that an entropy-sized subspace, with a dimension-independent exponential coefficient, makes the remaining entropy nearly additive under independent doubling.

Theorem 1.1 (Exponential entropy quotient). For every ε>0\varepsilon>0 and every law XX on F2m\mathbb{F}_2^m, there is a subspace GG such that

dim⁡G≤2320(1+ε)/εH(X)(2)\dim G\leq2^{320(1+\varepsilon)/\varepsilon H(X)} \tag*{(2)}

and

H(qGX)≤(1+ε)D(qGX)≤(1+ε)D(X).(3)H(q_GX)\leq(1+\varepsilon)D(q_GX)\leq(1+\varepsilon)D(X). \tag*{(3)}

The constant is absolute and is independent of mm.

The first inequality in (3) is stronger than a bound using only the original increment D(X)D(X). No independence among the coordinates of XX is assumed. In particular, the theorem applies to every noninjective linear image of an arbitrarily biased product law, without a restriction on the number or rank density of its representing columns.

The dimension-uniform exponential scale is the point of the theorem. The number 320 is a convenient absolute constant, not an optimal one. Proposition 9.3 shows that any universally valid coefficient C(ε)C(\varepsilon) in the original-input version of (2)–(3) must satisfy

lim inf⁡ε↓0εlog⁡2C(ε)≥2.(4)\liminf_{\varepsilon\downarrow0}\varepsilon\log_2 C(\varepsilon)\geq2. \tag*{(4)}

Thus exponential dependence is necessary, but the optimal unrestricted leading constant is not determined here.

Context and normalization

Abbe, Sandon, Shashkov, and Viazovska [3 Conjecture 7.1] formulate a related entropy assertion using smoothing by a uniform subspace variable. Their displayed coefficient is written exp⁡(Om(1/ε))\exp(O_m(1/\varepsilon)). We distinguish that notation from the absolute, dimension-independent coefficient proved in Theorem 1.1. If UGU_G is independent and uniform on GG, then

H(X+UG)−H(UG)=H(qGX),(5)H(X+U_G)-H(U_G)=H(q_GX), \tag*{(5)}

because, conditional on a quotient value, adding UGU_G makes the law uniform on the corresponding coset. Consequently the quotient and uniform-smoothing formulations are equivalent with these normalizations.

Cohen and Zakharov [2 Theorems 1.2 and 5.5] prove a dimension-independent almost-additivity theorem for two input laws. Their quantitative choice has the form

L(α)=exp⁡(O(α−1log⁡(1/α))).L(\alpha)=\exp\left(O\left(\alpha^{-1}\log(1/\alpha)\right)\right).

More specifically, [2 Corollary 1.3, equation (1.2)] reads in our notation

H(qGU)≤H(U+V)−H(V)+α(H(U)+H(V)),H(q_GU)\le H(U+V)-H(V)+\alpha\left(H(U)+H(V)\right),

with dim⁡G≤L(α)(H(U)+H(V))\dim G\le L(\alpha)(H(U)+H(V)), for independent inputs U,VU,V. By contrast, Corollary 9.2 gives

H(qGU)≤H(U+V)−H(V)+α(H(qGU)+H(qGV)),H(q_GU)\le H(U+V)-H(V)+\alpha\left(H(q_GU)+H(q_GV)\right),

with dim⁡G≤122320/α(H(U)+H(V))\dim G\le\frac{1}{2}2^{320/\alpha}(H(U)+H(V)), and the same conclusion with the inputs interchanged. The error is measured by the remaining quotient entropies, which do not exceed the original entropies. The main quantitative improvement is the removal of the factor log⁡(1/α)\log(1/\alpha) in the exponent.

For two independent copies of one law, the earlier display gives H(qGX)≤D(X)+2αH(X)H(q_GX)\le D(X)+2\alpha H(X), whereas Theorem 1.1 gives the relative and intrinsic bound (3). The earlier almost-additivity theorem can also be iterated to obtain a relative-error bound, but with the weaker quantitative scale; we include that entropy-halving comparison in § 9.1. Thus the point is the improved exponential order, not the first dimension-independent existence theorem. All comparisons of exponential orders concern the small-error limit, not a claim that the explicit constant 320 is better at every fixed error tolerance.

The only external structural theorem used in the proof of Theorem 1.1 is the entropic polynomial Freiman–Ruzsa theorem of Gowers, Green, Manners, and Tao [1 Theorem 1.2]. We use its individual constant-six consequence. The required conditional Balog–Szemerédi–Gowers entropy inequality, also appearing in [1 Lemma A.2], is proved in § 6.2. All numbered source locators refer to the versions specified in the bibliography.

Sparse laws and the proof mechanism

A law ZZ on a binary vector space is called λ\lambda-sparse in entropy if

H(Z∣qWZ)≤λdim⁡Wfor every subspace W.(6)H(Z\mid q_WZ)\le\lambda\dim W\quad\text{for every subspace }W. \tag*{(6)}

Minimizing H(qGX)+λdim⁡GH(q_GX)+\lambda\dim G produces such a quotient at dimension cost at most H(X)/λH(X)/\lambda. The central estimate is the following.

Theorem 1.2 (Sparse-law rigidity). Let 0<λ<10<\lambda<1. Every λ\lambda-sparse law ZZ with H(Z)>0H(Z)>0 satisfies

E(Z)H(Z)≤min⁡{1,320log⁡2(1/λ)}.(7)\frac{E(Z)}{H(Z)}\le\min\left\{1,\frac{320}{\log_2(1/\lambda)}\right\}. \tag*{(7)}

We prove a stronger statement for finite weighted families of laws. The sparsity condition is averaged over the family index, rather than required separately of every component. This distinction is essential: posterior conditioning preserves averaged sparsity even when individual posterior laws have large within-subspace entropy.

Two constructions drive the proof. First, a common variational quotient controls the sparsity of both a family and its convolution family without decreasing the normalized mean entropy defect. Second, a local-to-global estimate samples a fresh family index independently of a subspace built from previous samples. This permits averaged sparsity to be used against subspaces that depend on the earlier indices. Four-sample identities and the entropic Marton theorem then increase the defect ratio by a fixed multiple of its square while multiplying the sparsity parameter by at most four. Since all defect ratios are at most one, iteration gives (7).

The entropy framework builds on [1] and [2]. In particular, the nested interaction inequality is the one in [2 Lemma 5.3], and the random-subspace accumulation argument follows the local-to-global method of [2 Lemma 5.2]. We give the needed calculations in full. The distinction in the present argument is to work throughout with posterior-closed averaged sparsity and to combine these calculations with a ratio-preserving common quotient, so that each ratio-growth step has a fixed multiplicative sparsity cost.

The argument is an existence proof. The family index sets may grow rapidly, and the variational steps minimize over all subspaces. No efficient algorithm for finding the quotient is asserted.

Significance and relation to the predecessor manuscript

The conclusion separates the dimension of the ambient space from the information content of the law. For each fixed error tolerance, the number of directions that must be removed is bounded by a constant times H(X)H(X), regardless of the number of coordinates. In the remaining quotient, independent addition nearly doubles entropy: if Z=qGXZ = q_G X, then (3) is equivalent to

H(Z+Z′)≥(2−ε1+ε)H(Z).H(Z + Z') \geq\left(2 - \frac{\varepsilon}{1+\varepsilon}\right) H(Z).

Thus the additive entropy defect can be confined to a subspace at an entropy-proportional dimension cost. This interpretation does not assert that the quotient coordinates are independent, nor that the quotient is close to a uniform law.

Quantitatively, the bound removes the factor log⁡(1/ε)\log(1/\varepsilon) in the exponent of the cited general comparison estimate. Proposition 9.3 shows that the resulting scale 2Θ(1/ε)2^{\Theta(1/\varepsilon)} is the correct one for the least universal coefficient as ε↓0\varepsilon\downarrow0. Only the scale is settled: the lower leading constant is at least two, whereas the present upper constant is 320. For moderate-doubling sets, Corollary 9.4 translates the entropy theorem into a subspace-coset concentration statement with the corresponding exponential dependence on the error parameter. These are structural existence results, not efficient algorithms or practical small-constant estimates.

The author’s predecessor manuscript [4 Section 12.1] develops the entropy-sparsity formulation and single-law variational reduction used here, and also studies products and structured linear images. The present article incorporates the necessary definition and proves the variational reduction in full, in the stronger weighted-family form of Lemma 9.1. The sparse-law rigidity estimate supplies the missing premise of that reduction for unrestricted laws. No result from the unpublished manuscript is assumed: its role here is attribution and context. The specialized quantitative bounds for products and structured images remain separate from the nonsharp universal bound proved here. The only external structural theorem on which the proof of Theorem 1.1 depends is the entropic Marton theorem, stated in the form used in § 7.

Entropy tools and weighted families

Laws, convolution, and subspace entropy

For a finite-valued variable AA with mass function pp,

H(A)=−∑ap(a)log⁡2p(a),0log⁡20=0.H(A) = -\sum_a p(a)\log_2 p(a), \qquad0\log_2 0 = 0.

Conditional entropy is the average of the entropies of the conditional laws. We use the chain rule and the nonnegativity of conditional mutual information,

I(A;B∣C)=H(A∣C)+H(B∣C)−H(A,B∣C)≥0.I(A;B\mid C)=H(A\mid C)+H(B\mid C)-H(A,B\mid C)\ge0.

We write H(P)H(P) for the entropy of a law PP. Entropy is invariant under translations and bijective changes of coordinates.

For laws P,QP,Q on a common binary vector space VV, let P∗QP*Q denote the law of A+BA+B for independent A∼PA\sim P and B∼QB\sim Q. Define

s(P,Q)=H(P)+H(Q)−H(P∗Q),d(P,Q)=H(P∗Q)−H(P)+H(Q)2.(8)s(P,Q)=H(P)+H(Q)-H(P*Q),\qquad d(P,Q)=H(P*Q)-\frac{H(P)+H(Q)}{2}. \tag*{(8)}

The latter is entropic Ruzsa distance; subtraction and addition coincide in characteristic two. Since adding independent noise does not decrease entropy,

0≤s(P,Q)≤min⁡{H(P),H(Q)}.(9)0\le s(P,Q)\le\min\{H(P),H(Q)\}. \tag*{(9)}

In particular, s(P,P)=E(P)s(P,P)=E(P), d(P,P)=D(P)d(P,P)=D(P), and 0≤D(P),E(P)≤H(P)0\le D(P),E(P)\le H(P).

For a subspace W≤VW\le V, put

FP(W)=H(P)−H(qWP).(10)F_P(W)=H(P)-H(q_WP). \tag*{(10)}

If A∼PA\sim P, then FP(W)=H(A∣qWA)F_P(W)=H(A\mid q_WA). The quantity is nonnegative and nondecreasing under inclusion of subspaces.

Lemma 2.1 (Subspace entropy inequality). For subspaces U,W≤VU,W\le V,

H(qUP)+H(qWP)≥H(qU∩WP)+H(qU+WP).(11)H(q_UP)+H(q_WP)\ge H(q_{U\cap W}P)+H(q_{U+W}P). \tag*{(11)}

Equivalently, FPF_P is supermodular.

Proof. The pair (qUA,qWA)(q_UA,q_WA) determines qU∩WAq_{U\cap W}A, and qU+WAq_{U+W}A is a common function of the two components. If CC is a common function of variables B1,B2B_1,B_2, then

H(B1)+H(B2)−H(B1,B2)−H(C)=I(B1;B2∣C)≥0.H(B_1)+H(B_2)-H(B_1,B_2)-H(C)=I(B_1;B_2\mid C)\ge0.

Applying this identity gives (11). □

Weighted families

A finite weighted family P=(Pi,ai)i∈I\mathcal{P}=(P_i,a_i)_{i\in I} consists of laws on one common space VV, with positive weights summing to one. Zero-weight components may always be omitted. Define

h(P)=∑iaiH(Pi),h(\mathcal{P})=\sum_i a_iH(P_i),
e(P)=∑i,jaiajs(Pi,Pj),e(\mathcal{P})=\sum_{i,j}a_ia_js(P_i,P_j),
FP(W)=∑iaiFPi(W)=h(P)−h(qWP).(12)F_{\mathcal{P}}(W)=\sum_i a_iF_{P_i}(W)=h(\mathcal{P})-h(q_W\mathcal{P}). \tag*{(12)}

Here qWPq_W\mathcal{P} denotes the componentwise quotient with the same weights. We say that P\mathcal{P} is λ\lambda-sparse if

FP(W)≤λdim⁡Wfor every W≤V.(13)F_{\mathcal{P}}(W)\le\lambda\dim W\quad\text{for every }W\le V. \tag*{(13)}

This is an averaged condition, not a componentwise one. Also, h(P)h(\mathcal{P}) is the mean component entropy, not the entropy of the mixture ∑iaiPi\sum_i a_iP_i. (9) gives

0≤e(P)≤h(P).(14)0\le e(\mathcal{P})\le h(\mathcal{P}). \tag*{(14)}

The convolution family R=P∗P\mathcal{R}=\mathcal{P}*\mathcal{P} has components Pi∗PjP_i*P_j and weights aiaja_ia_j. Directly from (8),

h(R)=2h(P)−e(P).(15)h(\mathcal{R})=2h(\mathcal{P})-e(\mathcal{P}). \tag*{(15)}

Posterior families

Draw independent indices I,JI, J with weights aia_i, and draw A∼PIA \sim P_I, B∼PJB \sim P_J independently conditional on the indices. The posterior family Post⁡(P)\operatorname{Post}(\mathcal{P}) has components

Qi,j,t=Law⁡(A∣I=i,J=j,A+B=t)(16)Q_{i,j,t} = \operatorname{Law}(A \mid I=i,J=j,A+B=t) \tag*{(16)}

with weights aiaj(Pi∗Pj)(t)a_i a_j(P_i \ast P_j)(t), omitting zero-weight indices.

Lemma 2.2 (Posterior closure). If Q=Post⁡(P)\mathcal{Q}=\operatorname{Post}(\mathcal{P}), then

h(Q)=e(P),FQ(W)≤FP(W)(W≤V).(17)h(\mathcal{Q})=e(\mathcal{P}), \qquad F_{\mathcal{Q}}(W)\le F_{\mathcal{P}}(W) \quad(W\le V). \tag*{(17)}

In particular, posterior formation preserves averaged λ\lambda-sparsity.

Proof. Given the two indices, either input is determined by the other input and their sum. Thus

h(Q)=H(A∣I,J,A+B)=e(P).h(\mathcal{Q})=H(A\mid I,J,A+B)=e(\mathcal{P}).

For every fixed WW, conditioning gives

FQ(W)=H(A∣I,J,A+B,qWA)F_{\mathcal{Q}}(W)=H(A\mid I,J,A+B,q_W A)
≤H(A∣I,qWA)=FP(W).\le H(A\mid I,q_W A)=F_{\mathcal{P}}(W).

The averaging over all posterior indices is part of the identity; no sparsity assertion about an individual posterior law is used. □

Internal interaction in nested subspaces

We use the fibring framework of [2 Section 2.1]. The nested inequality (22) is [2 Lemma 5.3]; the proof below records it in our notation.

For independent A∼PA\sim P, B∼QB\sim Q, define

sW(P,Q)=H(A∣qWA)+H(B∣qWB)−H(A+B∣qWA,qWB).(18)s_W(P,Q)=H(A\mid q_W A)+H(B\mid q_W B) -H(A+B\mid q_W A,q_W B). \tag*{(18)}

This is the average of ss between independent conditional fiber laws. Consequently,

0≤sW(P,Q)≤min⁡{FP(W),FQ(W)}.(19)0\le s_W(P,Q)\le\min\{F_P(W),F_Q(W)\}. \tag*{(19)}

Lemma 3.1 (Fibring and nested interaction). *For every subspace WW,

s(P,Q)=s(qWP,qWQ)+sW(P,Q)−I(A+B;qWA,qWB∣qW(A+B)).(20)s(P,Q)=s(q_W P,q_W Q)+s_W(P,Q) -I(A+B;q_W A,q_W B\mid q_W(A+B)). \tag*{(20)}

Hence

sW(P,Q)≥s(P,Q)−s(qWP,qWQ).(21)s_W(P,Q)\ge s(P,Q)-s(q_W P,q_W Q). \tag*{(21)}

If U⊆WU\subseteq W, then

FQ(U)≥sW(P,Q)−[H(qUP)−H(qWP)].(22)F_Q(U)\ge s_W(P,Q)-[H(q_U P)-H(q_W P)]. \tag*{(22)}

Proof. Expand the three terms defining s(P,Q)s(P,Q) by their quotient variables. The difference between conditioning A+BA+B on its quotient and conditioning it on both input quotients is the mutual information in (20). This proves (20) and (21).

For completeness, we give the nested calculation explicitly. Let R=qUAR=q_U A, S=qUBS=q_U B, T=qWAT=q_W A, and L=qWBL=q_W B. The variables T,LT,L are functions of R,SR,S, respectively. Expanding the first two terms in (18) by R,SR,S, and conditioning the last residual entropy further on (R,S)(R,S), gives

sW(P,Q)≤sU(P,Q)+H(R∣T)+H(S∣L)−H(R+S∣T,L).(23)s_W(P,Q)\le s_U(P,Q) +H(R\mid T)+H(S\mid L)-H(R+S\mid T,L). \tag*{(23)}

For fixed (T,L)(T,L), the laws of R,SR,S are independent. The second line of (23) is therefore an average interaction, bounded by H(R∣T)H(R\mid T) using (9). Also, sU(P,Q)≤FQ(U)s_U(P,Q)\le F_Q(U) by (19). Since

H(R∣T)=H(qUP)−H(qWP),H(R\mid T)=H(q_U P)-H(q_W P),

equation (22) follows.

A common variational quotient

Lemma 4.1 (Ratio-preserving sparsification). Suppose P\mathcal{P} is λ\lambda-sparse, λ>0\lambda> 0, with h=h(P)>0h = h(\mathcal{P}) > 0. Set d=e(P)/hd = e(\mathcal{P})/h. There is a quotient family P0\mathcal{P}_0 with positive mean entropy such that

  1. e(P0)/h(P0)≥de(\mathcal{P}_0)/h(\mathcal{P}_0) \ge d;

  2. P0\mathcal{P}_0 is 2λ2\lambda-sparse;

  3. P0∗P0\mathcal{P}_0 * \mathcal{P}_0 is 4λ4\lambda-sparse.

Proof. Put R=P∗P\mathcal{R} = \mathcal{P} * \mathcal{P}, and minimize over subspaces G≤VG \le V the finite objective

Φ(G)=h(qGR)+(2+d)h(qGP)+4λdim⁡G.(24)\Phi(G) = h(q_G\mathcal{R}) + (2 + d)h(q_G\mathcal{P}) + 4\lambda\dim G. \tag*{(24)}

Among minimizers choose one of least dimension. Write

f=FP(G),g=FR(G).f = F_{\mathcal{P}}(G), \qquad g = F_{\mathcal{R}}(G).

Equation (15) gives Φ(0)=4h\Phi(0) = 4h. Comparison with zero yields

g+(2+d)f≥4λdim⁡G.g + (2 + d)f \ge4\lambda\dim G.

The input sparsity gives f≤λdim⁡Gf \le\lambda\dim G. Since

e(qGP)−dh(qGP)=g−(2−d)fe(q_G\mathcal{P}) - d h(q_G\mathcal{P}) = g - (2 - d)f
≥4(λdim⁡G−f)≥0,(25)\ge4(\lambda\dim G - f) \ge0, \tag*{(25)}

the ratio does not decrease whenever the output mean entropy is positive.

It cannot vanish. If h(qGP)=0h(q_G\mathcal{P}) = 0, then every quotient component is deterministic, so h(qGR)=0h(q_G\mathcal{R}) = 0 as well. Moreover, h=f≤λdim⁡Gh = f \le\lambda\dim G. Hence

Φ(G)=4λdim⁡G≥4h=Φ(0).\Phi(G) = 4\lambda\dim G \ge4h = \Phi(0).

Minimality would make zero a minimizer too, contradicting the least-dimension choice of a zero-entropy quotient when h>0h > 0.

For any subspace W≤V/GW \le V/G, compare GG with the inverse image of WW, whose dimension is dim⁡G+dim⁡W\dim G + \dim W. Minimality gives

FqGR(W)+(2+d)FqGP(W)≤4λdim⁡W.(26)F_{q_G\mathcal{R}}(W) + (2 + d)F_{q_G\mathcal{P}}(W) \le4\lambda\dim W. \tag*{(26)}

Both terms are nonnegative. Thus qGPq_G\mathcal{P} is 4λ/(2+d)4\lambda/(2 + d)-sparse, and qGRq_G\mathcal{R} is 4λ4\lambda-sparse. Since d≥0d \ge0 and quotienting commutes with convolution, these are the stated bounds.

The common objective in (24) is important. An arbitrary quotient of a sparse family need not satisfy the required new sparsity bound. The lemma simultaneously controls the family and the convolution family while retaining the normalized defect.

An averaged local-to-global estimate

The following estimate is an averaged-sparsity form of the local-to-global sampling argument in [2 Lemma 5.2]. Its right-hand side involves mean component entropy, rather than the entropy of the mixture.

Lemma 5.1 (Averaged density estimate). Let ρ≥0\rho\ge0, and let Q=(Qu,bu)\mathcal{Q} = (Q_u, b_u) be a ρ\rho-sparse family with mean entropy hh. For each ordered pair (u,w)(u,w), choose a subspace V(u,w)V(u,w). With independent family indices, put

A=Eu,wsV(u,w)(Qu,Qw),B=Eu,wdim⁡V(u,w).(27)A = \mathbb{E}_{u,w}s_{V(u,w)}(Q_u,Q_w), \qquad B = \mathbb{E}_{u,w} \dim V(u,w). \tag*{(27)}

Then for every integer N≥1N \ge1,

A≤hN+ρB(N−1)2.(28)A \le\frac{h}{N} + \frac{\rho B(N-1)}{2}. \tag*{(28)}

If B≤26hB \le26h, it follows that

A≤14ρ h.(29)A \le14\sqrt{\rho}\,h. \tag*{(29)}

Proof. Draw u,w1,w2,…u,w_1,w_2,\ldots independently from the family-index law. Hold uu fixed within this sequence, and set

Sk=∑j=1kV(u,wj),S0=0,hk=EH(qSkQu).S_k=\sum_{j=1}^{k}V(u,w_j), \qquad S_0=0, \qquad h_k=\mathbb{E}H(q_{S_k}Q_u).

Then h0=hh_0=h and hk≥0h_k\ge0. Given u,w1,…,wku,w_1,\ldots,w_k, draw the fresh index w=wk+1w=w_{k+1}. Apply (22) with

P=Qu,Q=Qw,W=V(u,w),U=Sk∩V(u,w).P=Q_u,\qquad Q=Q_w,\qquad W=V(u,w),\qquad U=S_k\cap V(u,w).

Monotonicity of FQwF_{Q_w}, followed by the subspace entropy inequality (11), gives

FQw(Sk)≥sV(u,w)(Qu,Qw)−[H(qSkQu)−H(qSk+V(u,w)Qu)].(30)F_{Q_w}(S_k)\ge s_{V(u,w)}(Q_u,Q_w)-\left[H(q_{S_k}Q_u)-H(q_{S_k+V(u,w)}Q_u)\right]. \tag*{(30)}

To check the direction, (11) gives

H(qSk∩VQu)−H(qVQu)≤H(qSkQu)−H(qSk+VQu),H(q_{S_k\cap V}Q_u)-H(q_VQ_u)\le H(q_{S_k}Q_u)-H(q_{S_k+V}Q_u),

which is precisely the replacement used in (30). The subspace SkS_k does not depend on the fresh ww. Conditional on all previously drawn indices, averaging the left side of (30) over ww therefore gives

FQ(Sk)≤ρdim⁡Sk.F_Q(S_k)\le\rho\dim S_k.

Averaging also over the earlier indices yields

A≤hk−hk+1+ρEdim⁡Sk≤hk−hk+1+ρkB.A\le h_k-h_{k+1}+\rho\mathbb{E}\dim S_k\le h_k-h_{k+1}+\rho kB.

Summing for k=0,…,N−1k=0,\ldots,N-1, using hN≥0h_N\ge0, and dividing by NN proves (28). For 0<ρ≤10<\rho\le1, take N=⌈ρ−1/2⌉N=\lceil\rho^{-1/2}\rceil. Then 1/N≤ρ1/N\le\sqrt{\rho} and N−1<ρ−1/2N-1<\rho^{-1/2}, so B≤26hB\le26h gives (29). For ρ>1\rho>1, use A≤hA\le h, which follows from (19). If ρ=0\rho=0, sparsity of the full ambient space forces h=0h=0. □

The subspaces in this lemma may depend on both sampled indices. The proof requires only that the new second index be independent of the subspace built from the previous samples. No componentwise sparsity assumption is introduced.

Four-sample identities and conditional additive energy

This section records the weighted-family form of the four-sample entropy framework used in [1] and [2 Section 3]. All family-index conditioning is retained explicitly.

Let PP have mean entropy H>0H>0 and ratio δ=e(P)/H\delta=e(P)/H. Define

R=P∗P,Q=Post⁡(P).\mathcal{R}=P*P,\qquad Q=\operatorname{Post}(P).

By (15) and (17),

h(R)=(2−δ)H,h(Q)=δH.(31)h(\mathcal{R})=(2-\delta)H,\qquad h(Q)=\delta H. \tag*{(31)}

Draw four independent indexed pairs (Ir,Xr)(I_r,X_r), each with the family-index distribution and conditional law Xr∣Ir=i∼PiX_r\mid I_r=i\sim P_i. Write

T=(I1,I2,I3,I4),S=X1+X2+X3+X4,T=(I_1,I_2,I_3,I_4),\qquad S=X_1+X_2+X_3+X_4,
A=X1+X2,B=X1+X3,C=X2+X3=A+B,A=X_1+X_2,\qquad B=X_1+X_3,\qquad C=X_2+X_3=A+B,

and put J=I(A;B∣S,T)≥0J=I(A;B\mid S,T)\ge0.

Splitting the mean defect

Lemma 6.1 (Four-sample splitting). With the preceding definitions,

e(R)+e(Q)=2δH+J.(32)e(\mathcal{R}) + e(\mathcal{Q}) = 2\delta H + J. \tag*{(32)}

Proof. Conditional on TT, the sums AA and S+AS+A are independent. Averaging their conditional interaction gives

H(A∣S,T)=e(R).H(A \mid S,T) = e(\mathcal{R}).

The analogous conditional entropies of BB and CC agree after averaging, by exchangeability of the four indexed pairs. Conditional on A,S,TA,S,T, the first coordinates X1,X3X_1,X_3 have independent posterior laws. Their posterior indices, before this conditioning, are independent with the distribution defining Q\mathcal{Q}. Hence

e(Q)=2h(Q)−H(B∣A,S,T)=2δH−H(B∣S,T)+J=2δH−e(R)+J.\begin{aligned} e(\mathcal{Q}) &= 2h(\mathcal{Q}) - H(B \mid A,S,T) \\ &= 2\delta H - H(B \mid S,T) + J \\ &= 2\delta H - e(\mathcal{R}) + J. \end{aligned}

This is (32). The symmetry is an averaged symmetry of the indexed pairs; it is not an assertion that all four component laws agree at a fixed tuple of indices.

A conditional Balog–Szemerédi–Gowers inequality

Lemma 6.2. For possibly dependent binary-vector variables U,VU,V, let Z=U+VZ=U+V. Then

Ezd(Law⁡(U∣Z=z),Law⁡(V∣Z=z))≤3I(U;V)+2H(Z)−H(U)−H(V).(33)\mathbb{E}_{z} d\bigl(\operatorname{Law}(U \mid Z=z),\operatorname{Law}(V \mid Z=z)\bigr) \le3I(U;V) + 2H(Z) - H(U) - H(V). \tag*{(33)}

Proof. Draw two conditionally independent trials (U1,V1),(U2,V2)(U_1,V_1),(U_2,V_2) given ZZ. Thus U1+V1=U2+V2=ZU_1+V_1=U_2+V_2=Z. In characteristic two,

L:=U1+V2=U2+V1.L := U_1+V_2=U_2+V_1.

Entropy submodularity gives

H(L)+H(L,U1,V1)≤H(L,U1)+H(L,V1).H(L)+H(L,U_1,V_1)\le H(L,U_1)+H(L,V_1).

The triple (L,U1,V1)(L,U_1,V_1) determines both trials, and conversely, so

H(L,U1,V1)=2H(U,V)−H(Z).H(L,U_1,V_1)=2H(U,V)-H(Z).

Also, H(L,U1)=H(U1,V2)≤H(U)+H(V)H(L,U_1)=H(U_1,V_2)\le H(U)+H(V), and the analogous bound holds for H(L,V1)H(L,V_1). Therefore

H(L∣Z)≤H(L)≤2I(U;V)+H(Z).H(L \mid Z)\le H(L)\le2I(U;V)+H(Z).

Both H(U1∣Z)H(U_1 \mid Z) and H(V2∣Z)H(V_2 \mid Z) equal H(U,V)−H(Z)H(U,V)-H(Z). Subtracting their mean gives (33), by definition (8).

Lemma 6.3 (Posterior doubling estimate). For independent posterior-family indices u,wu,w,

Eu,wD(Qu∗Qw)≤3J.(34)\mathbb{E}_{u,w}D(Q_u * Q_w)\le3J. \tag*{(34)}

Proof. Apply Lemma 6.2 to (A,C)(A,C), conditional on each value of (S,T)(S,T), and average. Since A+C=BA+C=B, the right side becomes

3I(A;C∣S,T)+2H(B∣S,T)−H(A∣S,T)−H(C∣S,T).3I(A;C \mid S,T)+2H(B \mid S,T) -H(A \mid S,T)-H(C \mid S,T).

The three conditional entropies agree after averaging, and I(A;C∣S,T)=JI(A;C \mid S,T)=J: the pair (A,C)(A,C) is in bijection with (A,B)(A,B), while the averaged marginal entropies of B,CB,C agree. Thus the expression is 3J3J.

Given (B=b,S=s,T)(B=b,S=s,T), the law of C=A+BC=A+B is a translate of the law of AA. The Ruzsa distance on the left of (33) is therefore DD of the conditional law of AA. Conditional on these same data, the pairs (X1,X3)(X_1,X_3) and (X2,X4)(X_2,X_4) remain independent subject to their respective sums bb and s+bs+b. Hence

Law⁡(A∣B=b,S=s,T)=QI1,I3,b∗QI2,I4,s+b.\operatorname{Law}(A\mid B=b,S=s,T)=Q_{I_1,I_3,b}*Q_{I_2,I_4,s+b}.

Unconditionally, the two triples (I1,I3,X1+X3)(I_1,I_3,X_1+X_3) and (I2,I4,X2+X4)(I_2,I_4,X_2+X_4) are independent, and each has the posterior-index distribution. Their average is exactly the left side of (34). □

The entropic Marton input

We use the following consequence of [1 Theorem 1.2]. If KK is any law on a binary vector space, there is a subspace VV such that

d(K,UV)≤6D(K).(35)d(K,U_V)\leq6D(K). \tag*{(35)}

where UVU_V is uniform on VV. The theorem in [1] is stated with natural logarithms; dividing all entropy terms by ln⁡2\ln2 preserves the constant.

Uniform smoothing and the elementary entropy bound for an independent sum give

d(K,UV)=H(qVK)+dim⁡V−H(K)2,d(K,UV)≥∣dim⁡V−H(K)∣2.d(K,U_V)=H(q_VK)+\frac{\dim V-H(K)}{2},\qquad d(K,U_V)\geq\frac{\lvert\dim V-H(K)\rvert}{2}.

Consequently (35) implies

H(qVK)≤12D(K),dim⁡V≤H(K)+12D(K)≤13H(K).(36)H(q_VK)\leq12D(K),\qquad\dim V\leq H(K)+12D(K)\leq13H(K). \tag*{(36)}

Lemma 7.1 (Sparse posterior estimate). In the notation of § 6, suppose the posterior family QQ is ρ\rho-sparse. Then

e(Q)≤36J+14ρ δH.(37)e(Q)\leq36J+14\sqrt{\rho}\,\delta H. \tag*{(37)}

Proof. For every ordered pair (u,w)(u,w), apply (36) to Ku,w=Qu∗QwK_{u,w}=Q_u*Q_w, and choose a corresponding subspace V(u,w)V(u,w). Their mean dimension satisfies

Edim⁡V(u,w)≤13EH(Qu∗Qw)≤26h(Q).(38)\mathbb{E}\dim V(u,w)\leq13\mathbb{E}H(Q_u*Q_w)\leq26h(Q). \tag*{(38)}

By (21),

s(Qu,Qw)≤sV(u,w)(Qu,Qw)+s(qVQu,qVQw).s(Q_u,Q_w)\leq s_{V(u,w)}(Q_u,Q_w)+s(q_VQ_u,q_VQ_w).

The last term is at most H(qV(Qu∗Qw))H(q_V(Q_u*Q_w)), since adding independent variables does not decrease entropy and (9) applies. Equation (36) bounds it by 12D(Ku,w)12D(K_{u,w}). Averaging and applying Lemma 6.3 gives

e(Q)≤EsV(u,w)(Qu,Qw)+36J.e(Q)\leq\mathbb{E}s_{V(u,w)}(Q_u,Q_w)+36J.

Lemma 5.1 and (38) bound the first term by 14ρ h(Q)14\sqrt{\rho}\,h(Q). Now use h(Q)=δHh(Q)=\delta H from (31). □

Fixed-cost ratio growth and logarithmic rigidity

Lemma 8.1 (Ratio growth). Let a λ\lambda-sparse family have positive mean entropy and ratio d=e/h>0d=e/h>0. If d≥40λd\geq40\sqrt{\lambda}, there is a 4λ4\lambda-sparse family with positive mean entropy and ratio at least

d+d2148.(39)d+\frac{d^2}{148}. \tag*{(39)}

Proof. Apply Lemma 4.1, and denote its quotient family by P\mathcal{P}. Let its mean entropy be H>0H>0 and ratio be δ≥d\delta\geq d. Its sparsity is at most 2λ2\lambda, while its convolution family R\mathcal{R} is 4λ4\lambda-sparse. Form the posterior family Q\mathcal{Q} from this new quotient family. Lemma 2.2 makes it 2λ2\lambda-sparse. Both mean entropies in (31) are positive.

Set

M=max⁡{e(R)h(R),e(Q)h(Q)},x=M−δ.M=\max\left\{\frac{e(\mathcal{R})}{h(\mathcal{R})},\frac{e(\mathcal{Q})}{h(\mathcal{Q})}\right\},\qquad x=M-\delta.

Equations (31)–(32) give J≤2xHJ \le2xH, and hence x≥0x \ge0. They also give

e(Q)≥[δ2−(2−δ)x]H,(40)e(Q) \ge[\delta^2-(2-\delta)x]H, \tag*{(40)}

because e(R)≤M(2−δ)He(\mathcal{R}) \le M(2-\delta)H and J≥0J \ge0. On the other hand, Lemma 7.1 with ρ=2λ\rho=2\lambda, together with 142<2014\sqrt{2}<20, yields

e(Q)≤72xH+20λ δH.e(Q) \le72xH+20\sqrt{\lambda}\,\delta H.

Combining the bounds gives

δ2−20δλ≤(74−δ)x.\delta^2-20\delta\sqrt{\lambda}\le(74-\delta)x.

The hypothesis δ≥d≥40λ\delta\ge d\ge40\sqrt{\lambda} makes the left side at least δ2/2\delta^2/2, so x≥δ2/148x\ge\delta^2/148. Choose whichever of R\mathcal{R}, QQ attains MM. It has sparsity at most 4λ4\lambda, positive mean entropy, and ratio at least d+d2/148d+d^2/148. □

Theorem 8.2 (Weighted-family rigidity). For 0<λ<10<\lambda<1, every λ\lambda-sparse finite family with positive mean entropy satisfies

e(P)h(P)≤min⁡{1,320log⁡2(1/λ)}.(41)\frac{e(\mathcal{P})}{h(\mathcal{P})}\le\min\left\{1,\frac{320}{\log_2(1/\lambda)}\right\}. \tag*{(41)}

Proof. If the initial ratio is zero, there is nothing to prove. Otherwise write it as d∈(0,1]d\in(0,1], and let N=⌈149/d⌉N=\lceil149/d\rceil. Whenever a growth step is permitted, the successive ratios satisfy

1dj+1≤1dj+dj2/148=1dj−1148+dj≤1dj−1149,(42)\frac{1}{d_{j+1}}\le\frac{1}{d_j+d_j^2/148} =\frac{1}{d_j}-\frac{1}{148+d_j}\le\frac{1}{d_j}-\frac{1}{149}, \tag*{(42)}

using dj≤1d_j\le1.

Suppose that

λ≤d216004−N.\lambda\le\frac{d^2}{1600}4^{-N}.

After j<Nj<N steps the sparsity parameter is at most 4jλ≤d2/16004^j\lambda\le d^2/1600, while the ratio is at least dd. Thus Lemma 8.1 permits all NN steps. Each family remains finite and has positive mean entropy. But (42) would imply

1dN≤1d−N149≤0,\frac{1}{d_N}\le\frac{1}{d}-\frac{N}{149}\le0,

a contradiction. Therefore

λ>d216004−⌈149/d⌉.(43)\lambda>\frac{d^2}{1600}4^{-\lceil149/d\rceil}. \tag*{(43)}

Taking base-two logarithms and multiplying by dd,

dlog⁡2(1/λ)<dlog⁡21600+2dlog⁡2(1/d)+2d⌈149/d⌉≤298+(log⁡21600+2)d+2dlog⁡2(1/d)<312<320.\begin{aligned} d\log_2(1/\lambda)&<d\log_2 1600+2d\log_2(1/d)+2d\lceil149/d\rceil\\ &\le298+(\log_2 1600+2)d+2d\log_2(1/d)\\ &<312<320. \end{aligned}

Here d≤1d\le1 and dlog⁡2(1/d)≤1/(eln⁡2)d\log_2(1/d)\le1/(e\ln2). This proves (41), while the other bound in the minimum is (14). □

Applying Theorem 8.2 to a singleton family proves Theorem 1.2.

Quotient consequences and a lower bound

The one-input theorem

We record the elementary variational step for families, since it also gives the two-input consequence.

Lemma 9.1 (Variational sparsification). For any finite family P\mathcal{P} and any λ>0\lambda> 0, there is a subspace GG such that

dim⁡G≤h(P)λ,qGP is λ-sparse.(44)\dim G \le\frac{h(\mathcal{P})}{\lambda}, \qquad q_G\mathcal{P}\text{ is }\lambda\text{-sparse}. \tag*{(44)}

Proof. Minimize h(qGP)+λdim⁡Gh(q_G\mathcal{P})+\lambda\dim G over all subspaces. Comparison with zero gives the dimension bound. Comparing the minimizer with the inverse image of every further quotient subspace WW gives

FqGP(W)≤λdim⁡W.F_{q_G\mathcal{P}}(W) \le\lambda\dim W.

This is the required sparsity. □\square

Proof of Theorem 1.1. Set

θ=ε1+ε,λ=2−320/θ,\theta=\frac{\varepsilon}{1+\varepsilon}, \qquad\lambda=2^{-320/\theta},

and apply Lemma 9.1 to the singleton family consisting of XX. The selected subspace satisfies (2), and Z=qGXZ=q_GX is λ\lambda-sparse. If H(Z)=0H(Z)=0, the entropy conclusion is immediate. Otherwise Theorem 8.2 gives

E(Z)≤θH(Z),E(Z)\le\theta H(Z),

which is equivalent to H(Z)≤(1+ε)D(Z)H(Z)\le(1+\varepsilon)D(Z). Finally,

D(X)=I(X+X′;X′),D(X)=I(X+X';X'),
D(qGX)=I(qG(X+X′);qGX′)≤D(X)D(q_GX)=I(q_G(X+X');q_GX')\le D(X)

by data processing. This proves (3). □\square

Comparison with the prior bound. To make the distinction in § 1.1 precise, consider instead applying [2 Theorem 1.2] to two independent copies of a current law YY. At cost at most 2L(α)H(Y)2L(\alpha)H(Y), it produces a quotient ZZ with E(Z)≤2αH(Y)E(Z)\le2\alpha H(Y). Set θ=ε/(1+ε)\theta=\varepsilon/(1+\varepsilon) and α=θ/4\alpha=\theta/4. If H(Y)≤(1+ε)D(Y)H(Y)\le(1+\varepsilon)D(Y), stop without taking a further quotient. Otherwise apply the quoted theorem. If H(Z)≥H(Y)/2H(Z)\ge H(Y)/2, then

E(Z)≤θ2H(Y)≤θH(Z),E(Z)\le\frac{\theta}{2}H(Y)\le\theta H(Z),

so ZZ is intrinsically good and the procedure stops. If not, repeat with ZZ, whose entropy has halved. A step from a law that is not already good must remove a nonzero subspace: the zero subspace would imply E(Y)≤θH(Y)/2E(Y)\le\theta H(Y)/2, contradicting E(Y)>θH(Y)E(Y)>\theta H(Y). Thus the process terminates in finite dimension. Lifting the successive kernels and summing their dimensions gives a total cost at most

2L(α)(H(X)+12H(X)+14H(X)+⋯ )≤4L(α)H(X).2L(\alpha)\left(H(X)+\frac{1}{2}H(X)+\frac{1}{4}H(X)+\cdots\right)\le4L(\alpha)H(X).

Data processing for DD yields the original-input conclusion as well. Hence the earlier theorem already gives the qualitative conclusion of Theorem 1.1, with coefficient

4L(ε4(1+ε))=exp⁡(O(ε−1log⁡(1/ε))).4L\left(\frac{\varepsilon}{4(1+\varepsilon)}\right)=\exp\left(O\left(\varepsilon^{-1}\log(1/\varepsilon)\right)\right).

The present argument improves that scale to exp⁡(O(1/ε))\exp(O(1/\varepsilon)).

Two-input almost-additivity

Corollary 9.2. For 0<α<10 < \alpha< 1 and independent laws U,VU,V on a common binary vector space, there is a subspace GG with

dim⁡G≤122320/α(H(U)+H(V))(45)\dim G \le\frac{1}{2}2^{320/\alpha}(H(U)+H(V)) \tag*{(45)}

such that

H(qGU+qGV)≥(1−α)(H(qGU)+H(qGV)).(46)H(q_GU+q_GV) \ge(1-\alpha)(H(q_GU)+H(q_GV)). \tag*{(46)}

In particular, the additive error is at most α(H(U)+H(V))\alpha(H(U)+H(V)). For the same subspace,

H(qGU)≤H(U+V)−H(V)+α(H(qGU)+H(qGV)),H(q_GU) \le H(U+V)-H(V)+\alpha(H(q_GU)+H(q_GV)),

and the analogous inequality holds with U,VU,V interchanged.

Proof. Let P\mathcal{P} consist of the laws of U,VU,V, each with weight 1/21/2, and take λ=2−320/α\lambda=2^{-320/\alpha} in Lemma 9.1. This gives (45). Write P0=qGP\mathcal{P}_0=q_G\mathcal{P}. If its mean entropy is zero, the conclusion is trivial. Otherwise Theorem 8.2 gives

e(P0)≤αh(P0).e(\mathcal{P}_0)\le\alpha h(\mathcal{P}_0).

The two mixed ordered pairs have total weight 1/21/2, and the two self-interaction terms are nonnegative. Therefore

s(qGU,qGV)≤2e(P0)≤α(H(qGU)+H(qGV)),\begin{aligned} s(q_GU,q_GV)\le2e(\mathcal{P}_0) \\ &\le\alpha(H(q_GU)+H(q_GV)), \end{aligned}

which is (46). Quotient entropy does not exceed input entropy, giving the original-input error bound. Finally, data processing gives

H(qGU+qGV)−H(qGV)=I(qGU;qG(U+V))≤I(U;U+V)=H(U+V)−H(V).\begin{aligned} H(q_GU+q_GV)-H(q_GV)=I(q_GU;q_G(U+V)) \\ &\le I(U;U+V)=H(U+V)-H(V). \end{aligned}

Adding s(qGU,qGV)s(q_GU,q_GV) and using (46) proves the displayed mixed-input bound. Interchanging the inputs gives its symmetric version. □

Exponential dependence is necessary

Proposition 9.3. Suppose C(ε)C(\varepsilon) is valid for all binary-vector laws in the assertion

dim⁡G≤C(ε)H(X),H(qGX)≤(1+ε)D(X).\dim G\le C(\varepsilon)H(X),\qquad H(q_GX)\le(1+\varepsilon)D(X).

Then (4) holds.

Proof. Fix c∈(0,2)c\in(0,2), and set p=2−c/εp=2^{-c/\varepsilon}. Take XX to be a single Bernoulli bit with parameter pp. Write

h2(p)=−plog⁡2p−(1−p)log⁡2(1−p).h_2(p)=-p\log_2p-(1-p)\log_2(1-p).

As p↓0p\downarrow0, elementary expansion gives

h2(p)=plog⁡2(1/p)+plog⁡2e+O(p2),h_2(p)=p\log_2(1/p)+p\log_2e+O(p^2),
2h2(p)−h2(2p(1−p))=2p+O(p2log⁡(1/p)).2h_2(p)-h_2(2p(1-p))=2p+O(p^2\log(1/p)).

Consequently

E(X)H(X)=2εc(1+o(1))>ε1+ε\frac{E(X)}{H(X)}=\frac{2\varepsilon}{c}(1+o(1))>\frac{\varepsilon}{1+\varepsilon}

for all sufficiently small ε\varepsilon. The zero subspace does not satisfy the entropy condition, and the only other subspace has dimension one. Hence C(ε)≥1/h2(p)C(\varepsilon)\ge1/h_2(p), so

lim inf⁡ε↓0εlog⁡2C(ε)≥c.\liminf_{\varepsilon\downarrow0}\varepsilon\log_2 C(\varepsilon)\ge c.

Let c↑2c\uparrow2. □

Combining Proposition 9.3 with Theorem 1.1 shows that the correct unrestricted scale is exponential in 1/ε1/\varepsilon. It leaves a substantial gap between the lower leading constant two and the upper constant supplied by the proof.

Concentration of moderate-doubling sets

The following consequence makes the additive-combinatorial content explicit. It gives the conclusion of [2 Theorem 1.1] with an exponential, rather than exp⁡(O(α−1log⁡(1/α)))\exp(O(\alpha^{-1}\log(1/\alpha))), dimension coefficient.

Corollary 9.4 (Subspace-coset concentration). Let 0<α<η≤10 < \alpha< \eta\le1, and let A⊆F2mA \subseteq\mathbb{F}_2^m be nonempty with ∣A+A∣≤∣A∣2−η|A+A| \le|A|^{2-\eta}. There is a subspace GG such that

dim⁡G≤2320/αlog⁡2∣A∣\dim G \le2^{320/\alpha}\log_2 |A|

and

1∣A∣∑a∈Alog⁡2∣A∩(a+G)∣≥η−α1−αlog⁡2∣A∣.\frac{1}{|A|}\sum_{a\in A}\log_2 |A\cap(a+G)| \ge\frac{\eta-\alpha}{1-\alpha}\log_2 |A|.

In particular, some coset of GG intersects AA in at least ∣A∣η−α|A|^{\eta-\alpha} points.

Proof. Let XX be uniform on AA, so H(X)=log⁡2∣A∣H(X)=\log_2|A|. Since X+X′X+X' is supported on A+AA+A,

D(X)≤log⁡2∣A+A∣−log⁡2∣A∣≤(1−η)log⁡2∣A∣.D(X)\le\log_2|A+A|-\log_2|A|\le(1-\eta)\log_2|A|.

Apply Theorem 1.1 with ε=α/(1−α)\varepsilon=\alpha/(1-\alpha). The stated dimension bound follows, and

H(qGX)≤1−η1−αlog⁡2∣A∣.H(q_GX)\le\frac{1-\eta}{1-\alpha}\log_2|A|.

The conditional law of XX on each occupied coset is uniform on its intersection with AA. Therefore

1∣A∣∑a∈Alog⁡2∣A∩(a+G)∣=H(X∣qGX)\frac{1}{|A|}\sum_{a\in A}\log_2|A\cap(a+G)|=H(X\mid q_GX)
=log⁡2∣A∣−H(qGX)=\log_2|A|-H(q_GX)
≥η−α1−αlog⁡2∣A∣.\ge\frac{\eta-\alpha}{1-\alpha}\log_2|A|.

At least one term is no smaller than the average, and (η−α)/(1−α)≥η−α(\eta-\alpha)/(1-\alpha)\ge\eta-\alpha. This proves the last assertion. □

Further questions

The most immediate quantitative question is the optimal leading constant in the unrestricted exponential bound. The constants in the posterior estimate and ratio-growth argument were chosen for transparency rather than optimization. Sharpening them alone would not identify the extremal laws.

It is also natural to seek a constructive version with controlled running time. The present proof allows arbitrary finite family enlargement and global subspace minimization. Neither the number of posterior components nor the cost of these minimizations is bounded in a form that gives an efficient quotient-finding procedure.

The weighted-family formulation separates the information that survives conditioning from assertions that need not survive componentwise. Whether a comparable fixed-cost sparsity argument extends to other ambient groups, or to other entropy functionals, requires additional structure; no such extension is claimed here.

Acknowledgment

OpenAI GPT-6 Astra and other AI-assisted tools were used extensively for proof development, checking, literature retrieval, drafting, and computational diagnostics during the preparation of this manuscript. Such checks do not constitute independent human peer review or formal proof-assistant verification. The proof of the main theorem is given in full, apart from the explicitly cited entropic Marton theorem; finite diagnostics are not used as premises of the proof. Responsibility for the submitted content rests with the named human author.

References

  1. [1]W. T. Gowers, B. Green, F. Manners, and T. Tao, On a conjecture of Marton, arXiv:2311.05762v1, 9 November 2023. Theorem and lemma numbering in this paper refers to version 1. https://arxiv.org/abs/2311.05762v1.
  2. [2]A. Cohen and D. Zakharov, Moderate-doubling sets in F₂ⁿ intersect subspaces, arXiv:2512.19884v1, submitted 22 December 2025. https://arxiv.org/abs/2512.19884v1.
  3. [3]E. Abbe, C. Sandon, V. Shashkov, and M. Viazovska, Polynomial Freiman–Ruzsa, Reed–Muller codes and Shannon capacity, arXiv:2411.13493v2, revised 25 February 2026. https://arxiv.org/abs/2411.13493v2.
  4. [4]J. Park, Entropy quotients of binary products and structured linear images, unpublished manuscript dated 28 October 2026, Section 12. The relevant variational reduction is reproduced and proved in Section 9.1 of the present article.

Paper details

vlnc:W_z6dxunme
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 15

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

OpenAI GPT-6 Astra, other AI-assisted tools

View statement
Looking for related papers…
Contents