WorksComputer Science
Dimension-free exponential entropy quotients over
Abstract
Let be a random vector in , and let be an independent copy. We prove that, for every , there is a subspace with such that . In particular, the quotient entropy is at most . The coefficient is independent of the ambient dimension, and its exponential order in 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 , with an independent copy, define its entropy increment and entropy defect by
For a subspace , write 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 and every law on , there is a subspace such that
and
The constant is absolute and is independent of .
The first inequality in (3) is stronger than a bound using only the original increment . No independence among the coordinates of 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 in the original-input version of (2)–(3) must satisfy
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 . We distinguish that notation from the absolute, dimension-independent coefficient proved in Theorem 1.1. If is independent and uniform on , then
because, conditional on a quotient value, adding 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
More specifically, [2 Corollary 1.3, equation (1.2)] reads in our notation
with , for independent inputs . By contrast, Corollary 9.2 gives
with , 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 in the exponent.
For two independent copies of one law, the earlier display gives , 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 on a binary vector space is called -sparse in entropy if
Minimizing produces such a quotient at dimension cost at most . The central estimate is the following.
Theorem 1.2 (Sparse-law rigidity). Let . Every -sparse law with satisfies
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 , regardless of the number of coordinates. In the remaining quotient, independent addition nearly doubles entropy: if , then (3) is equivalent to
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 in the exponent of the cited general comparison estimate. Proposition 9.3 shows that the resulting scale is the correct one for the least universal coefficient as . 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 with mass function ,
Conditional entropy is the average of the entropies of the conditional laws. We use the chain rule and the nonnegativity of conditional mutual information,
We write for the entropy of a law . Entropy is invariant under translations and bijective changes of coordinates.
For laws on a common binary vector space , let denote the law of for independent and . Define
The latter is entropic Ruzsa distance; subtraction and addition coincide in characteristic two. Since adding independent noise does not decrease entropy,
In particular, , , and .
For a subspace , put
If , then . The quantity is nonnegative and nondecreasing under inclusion of subspaces.
Lemma 2.1 (Subspace entropy inequality). For subspaces ,
Equivalently, is supermodular.
Proof. The pair determines , and is a common function of the two components. If is a common function of variables , then
Applying this identity gives (11). □
Weighted families
A finite weighted family consists of laws on one common space , with positive weights summing to one. Zero-weight components may always be omitted. Define
Here denotes the componentwise quotient with the same weights. We say that is -sparse if
This is an averaged condition, not a componentwise one. Also, is the mean component entropy, not the entropy of the mixture . (9) gives
The convolution family has components and weights . Directly from (8),
Posterior families
Draw independent indices with weights , and draw , independently conditional on the indices. The posterior family has components
with weights , omitting zero-weight indices.
Lemma 2.2 (Posterior closure). If , then
In particular, posterior formation preserves averaged -sparsity.
Proof. Given the two indices, either input is determined by the other input and their sum. Thus
For every fixed , conditioning gives
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 , , define
This is the average of between independent conditional fiber laws. Consequently,
Lemma 3.1 (Fibring and nested interaction). *For every subspace ,
Hence
If , then
Proof. Expand the three terms defining by their quotient variables. The difference between conditioning 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 , , , and . The variables are functions of , respectively. Expanding the first two terms in (18) by , and conditioning the last residual entropy further on , gives
For fixed , the laws of are independent. The second line of (23) is therefore an average interaction, bounded by using (9). Also, by (19). Since
equation (22) follows.
A common variational quotient
Lemma 4.1 (Ratio-preserving sparsification). Suppose is -sparse, , with . Set . There is a quotient family with positive mean entropy such that
;
is -sparse;
is -sparse.
Proof. Put , and minimize over subspaces the finite objective
Among minimizers choose one of least dimension. Write
Equation (15) gives . Comparison with zero yields
The input sparsity gives . Since
the ratio does not decrease whenever the output mean entropy is positive.
It cannot vanish. If , then every quotient component is deterministic, so as well. Moreover, . Hence
Minimality would make zero a minimizer too, contradicting the least-dimension choice of a zero-entropy quotient when .
For any subspace , compare with the inverse image of , whose dimension is . Minimality gives
Both terms are nonnegative. Thus is -sparse, and is -sparse. Since 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 , and let be a -sparse family with mean entropy . For each ordered pair , choose a subspace . With independent family indices, put
Then for every integer ,
If , it follows that
Proof. Draw independently from the family-index law. Hold fixed within this sequence, and set
Then and . Given , draw the fresh index . Apply (22) with
Monotonicity of , followed by the subspace entropy inequality (11), gives
To check the direction, (11) gives
which is precisely the replacement used in (30). The subspace does not depend on the fresh . Conditional on all previously drawn indices, averaging the left side of (30) over therefore gives
Averaging also over the earlier indices yields
Summing for , using , and dividing by proves (28). For , take . Then and , so gives (29). For , use , which follows from (19). If , sparsity of the full ambient space forces . □
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 have mean entropy and ratio . Define
By (15) and (17),
Draw four independent indexed pairs , each with the family-index distribution and conditional law . Write
and put .
Splitting the mean defect
Lemma 6.1 (Four-sample splitting). With the preceding definitions,
Proof. Conditional on , the sums and are independent. Averaging their conditional interaction gives
The analogous conditional entropies of and agree after averaging, by exchangeability of the four indexed pairs. Conditional on , the first coordinates have independent posterior laws. Their posterior indices, before this conditioning, are independent with the distribution defining . Hence
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 , let . Then
Proof. Draw two conditionally independent trials given . Thus . In characteristic two,
Entropy submodularity gives
The triple determines both trials, and conversely, so
Also, , and the analogous bound holds for . Therefore
Both and equal . Subtracting their mean gives (33), by definition (8).
Lemma 6.3 (Posterior doubling estimate). For independent posterior-family indices ,
Proof. Apply Lemma 6.2 to , conditional on each value of , and average. Since , the right side becomes
The three conditional entropies agree after averaging, and : the pair is in bijection with , while the averaged marginal entropies of agree. Thus the expression is .
Given , the law of is a translate of the law of . The Ruzsa distance on the left of (33) is therefore of the conditional law of . Conditional on these same data, the pairs and remain independent subject to their respective sums and . Hence
Unconditionally, the two triples and 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 is any law on a binary vector space, there is a subspace such that
where is uniform on . The theorem in [1] is stated with natural logarithms; dividing all entropy terms by preserves the constant.
Uniform smoothing and the elementary entropy bound for an independent sum give
Consequently (35) implies
Lemma 7.1 (Sparse posterior estimate). In the notation of § 6, suppose the posterior family is -sparse. Then
Proof. For every ordered pair , apply (36) to , and choose a corresponding subspace . Their mean dimension satisfies
By (21),
The last term is at most , since adding independent variables does not decrease entropy and (9) applies. Equation (36) bounds it by . Averaging and applying Lemma 6.3 gives
Lemma 5.1 and (38) bound the first term by . Now use from (31). □
Fixed-cost ratio growth and logarithmic rigidity
Lemma 8.1 (Ratio growth). Let a -sparse family have positive mean entropy and ratio . If , there is a -sparse family with positive mean entropy and ratio at least
Proof. Apply Lemma 4.1, and denote its quotient family by . Let its mean entropy be and ratio be . Its sparsity is at most , while its convolution family is -sparse. Form the posterior family from this new quotient family. Lemma 2.2 makes it -sparse. Both mean entropies in (31) are positive.
Set
Equations (31)–(32) give , and hence . They also give
because and . On the other hand, Lemma 7.1 with , together with , yields
Combining the bounds gives
The hypothesis makes the left side at least , so . Choose whichever of , attains . It has sparsity at most , positive mean entropy, and ratio at least . □
Theorem 8.2 (Weighted-family rigidity). For , every -sparse finite family with positive mean entropy satisfies
Proof. If the initial ratio is zero, there is nothing to prove. Otherwise write it as , and let . Whenever a growth step is permitted, the successive ratios satisfy
using .
Suppose that
After steps the sparsity parameter is at most , while the ratio is at least . Thus Lemma 8.1 permits all steps. Each family remains finite and has positive mean entropy. But (42) would imply
a contradiction. Therefore
Taking base-two logarithms and multiplying by ,
Here and . 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 and any , there is a subspace such that
Proof. Minimize over all subspaces. Comparison with zero gives the dimension bound. Comparing the minimizer with the inverse image of every further quotient subspace gives
This is the required sparsity.
Proof of Theorem 1.1. Set
and apply Lemma 9.1 to the singleton family consisting of . The selected subspace satisfies (2), and is -sparse. If , the entropy conclusion is immediate. Otherwise Theorem 8.2 gives
which is equivalent to . Finally,
by data processing. This proves (3).
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 . At cost at most , it produces a quotient with . Set and . If , stop without taking a further quotient. Otherwise apply the quoted theorem. If , then
so is intrinsically good and the procedure stops. If not, repeat with , whose entropy has halved. A step from a law that is not already good must remove a nonzero subspace: the zero subspace would imply , contradicting . Thus the process terminates in finite dimension. Lifting the successive kernels and summing their dimensions gives a total cost at most
Data processing for yields the original-input conclusion as well. Hence the earlier theorem already gives the qualitative conclusion of Theorem 1.1, with coefficient
The present argument improves that scale to .
Two-input almost-additivity
Corollary 9.2. For and independent laws on a common binary vector space, there is a subspace with
such that
In particular, the additive error is at most . For the same subspace,
and the analogous inequality holds with interchanged.
Proof. Let consist of the laws of , each with weight , and take in Lemma 9.1. This gives (45). Write . If its mean entropy is zero, the conclusion is trivial. Otherwise Theorem 8.2 gives
The two mixed ordered pairs have total weight , and the two self-interaction terms are nonnegative. Therefore
which is (46). Quotient entropy does not exceed input entropy, giving the original-input error bound. Finally, data processing gives
Adding and using (46) proves the displayed mixed-input bound. Interchanging the inputs gives its symmetric version. □
Exponential dependence is necessary
Proof. Fix , and set . Take to be a single Bernoulli bit with parameter . Write
As , elementary expansion gives
Consequently
for all sufficiently small . The zero subspace does not satisfy the entropy condition, and the only other subspace has dimension one. Hence , so
Let . □
Combining Proposition 9.3 with Theorem 1.1 shows that the correct unrestricted scale is exponential in . 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 , dimension coefficient.
Corollary 9.4 (Subspace-coset concentration). Let , and let be nonempty with . There is a subspace such that
and
In particular, some coset of intersects in at least points.
Proof. Let be uniform on , so . Since is supported on ,
Apply Theorem 1.1 with . The stated dimension bound follows, and
The conditional law of on each occupied coset is uniform on its intersection with . Therefore
At least one term is no smaller than the average, and . 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]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]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]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]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.