Optimal chain density, entropy, and space-time tradeoffs for the TSP
July 13, 2026
Abstract
We nearly settle a natural extremal question about set systems over \([n]\): the tradeoff between the size (number of sets) and the number of full chains. This question was initially raised by Johnson, Leader, and Russell [Combin. Probab. Comp., 2015] as a counterpart to Sperner-type results in combinatorics.
Recently, a framework introduced by Ameli, Nederlof, and Wang, and independently by Dallant and Kozma [FOCS 2026] linked this question to the space- and time-complexity of Bellman-Held-Karp-style dynamic programming algorithms for permutation problems such as the traveling salesman (TSP). Precisely, they showed that a space-time product \(\gamma^{n+o(n)}\) is feasible for the TSP, whenever a set system of (normalized) size \(S\) and chain density \(D\) exists, with \(\gamma = S^2/D\). In this paper we show an essentially optimal bound of \(\gamma \approx 3.1819\) for this quantity, closing the gap between the previous best lower and upper bounds of \(\gamma \geq 3.015\) and \(\gamma \leq 3.572\) respectively. This implies a TSP algorithm with space-time product \(\mathcal{O}(3.1819^n)\) for input size \(n\), as well as a limit to further improvements in this broad framework. More generally, we can obtain close to optimal values \(D\) for any feasible value \(S\), effectively settling the question of the number of full chains at every size.
The crucial step towards our results is casting the extremal combinatorics question as an information vs. entropy tradeoff involving two random variables. This reformulation exactly captures the optimal tradeoff for the combinatorial problem, leading to a framework in which primal-dual certificates can be derived, proving rigorous upper and lower bounds on \(\gamma\). We also give a further application of our techniques, improving a bound of Duffus, Sands, and Winkler on the minimum size of fibres in the Boolean lattice.
1 Introduction↩︎
The traveling salesman problem (TSP) is one of the cornerstones of combinatorial optimization and has served as a proving ground for many of the algorithmic techniques invented in the past decades, whether exact, approximate, or heuristic, e.g., see [1]–[4].
Yet, despite significant effort, the fastest algorithm for solving TSP exactly, in the worst case, remains the Bellman-Held-Karp [5], [6] dynamic program with running time and space \(\mathcal{O}^*(2^n)\). When the space budget is bounded by a polynomial, the fastest known algorithm is the Gurevich-Shelah [7] divide-and-conquer with running time \(\mathcal{O}^*(4^n)\).3 A folklore combination of the two methods results in a running time \(\mathcal{O}^*(\mathcal{T}^n)\) and space \(\mathcal{O}^*(\mathcal{S}^n)\) with \(\mathcal{T}\cdot \mathcal{S}= 4\), for various values of \(1 \leq \mathcal{S}\leq 2\) (e.g., see [8]).
While the two extremes (\(\mathcal{T}= 2\) and \(\mathcal{T}=4\)) of this tradeoff have resisted improvement for several decades now, in a surprising breakthrough in 2010, Koivisto and Parviainen [9] improved the tradeoff at intermediate points, in particular, to \(\mathcal{T}\cdot \mathcal{S}\approx 3.93\), for \(\mathcal{T}\approx 2.7\). Their result builds on the classical dynamic programming (DP) approach of Bellman, Held, and Karp, but partitions the space of possible solutions (all permutations of the input) into sets of permutations that are linear extensions of certain partial orders. This allows searching each subset separately, reusing space between successive searches.
Informally, the number of linear extensions determines what fraction of the solution space is covered by one search, and thus the number of repetitions that are needed. The number of downsets (poset ideals) exactly corresponds to the size of the DP table, dominating both the space- and time requirements of a single search. The efficiency of the scheme thus hinges on the existence of partial orders with few downsets and many linear extensions (relatively speaking).
These two goals are, of course, in tension; to support many linear extensions, a partial order must admit all of their prefix sets as downsets; the question is, intuitively, how much “sharing” is possible. Unfortunately, a tight quantitative relation between these two basic parameters of a poset is not known. Koivisto and Parviainen showed that a certain two-level poset class is optimal among a broader class of layered posets, and within this class, the most favorable tradeoff is attained at a concrete constant size of \(n=26\). This construction yielded the above TSP-tradeoff of \(\mathcal{T}\cdot \mathcal{S}\approx 3.93\).
Recently, Ameli, Nederlof, and Wang [10] and independently, Dallant and Kozma [11] described a more general framework for space-time tradeoffs for TSP (as well as for a broader family of permutation problems), where the solution space is partitioned into sets of permutations that arise as maximal chains of set families. The efficiency of the algorithm is then dependent on the number of maximal chains, and on the size of the family (the number of sets it contains).
This scheme generalizes the one by Koivisto and Parviainen; downsets of a poset \(P\) form a set family whose maximal chains are exactly the linear extensions of \(P\). It is, in fact, significantly more general, as there are \(2^{2^n}\) set families, but only \(2^{\mathcal{O}(n^2)}\) partial orders over a ground set of size \(n\) [12]. The framework reduces the algorithm design question to one of extremal combinatorics:
finding a set family of small size with many maximal chains.
More precisely, [10], [11] obtain the space-time tradeoff \(\mathcal{T}\cdot \mathcal{S}= \gamma = S^2/D\), whenever there exists a set family over \([n]\) of size \(S^n\) and number of maximal chains \(D^n \cdot n!\). The quantities \(S\) and \(D\) can be seen as small constants, and it is sufficient to show the existence of a single finite set system with these parameters. (We give more precise definitions in § 1.1.)
The best construction given in [11] yields a value \(\gamma \leq 3.572\) for a TSP space-time tradeoff \(\mathcal{T}\cdot \mathcal{S}\) with the same value. In [10] the lower bound \(\gamma \geq 3.015\) is shown via a delicate argument involving isoperimetric inequalities; a lower bound of \(\gamma \geq 3\) more easily follows from a counting argument [10], [11].
The question of relating these two parameters of set families has also been raised before in extremal combinatorics. Johnson, Leader, and Russell [13] asked which family, of a given size, maximizes the number of maximal chains (and hence their density). They conjectured that extremal families arise from two-level posets, closely related to the constructions found earlier by Koivisto and Parviainen [9]. The results of [10], [11] refute this conjecture, yielding families with a more favorable tradeoff. The optimum value of \(\gamma\) and the exact quantitative nature of the tradeoff between size and chain-density, however, was left open by these works.
1.0.0.1 Our contribution.
In this paper we essentially close the gap, obtaining \(3.1818 < \gamma < 3.1819\), where further refinement appears limited only by computation. To obtain these results, we reformulate the question as the tradeoff between two information-theoretic quantities involving a pair of random variables. We show that the optimal tradeoffs of the two settings coincide: both upper- or lower bound certificates for one problem imply the same for the other. The advantage of the information-theoretic view, besides the simpler formulation, is that it is amenable to the efficient construction of such certificates. Upper bound certificates in the information-theoretic setting are, in turn, transferable back to the original setting, yielding set systems with the required parameters.
As a main algorithmic consequence of our results, we obtain an algorithm for the TSP with running time \(\mathcal{O}^*(\mathcal{T}^n)\) and space \(\mathcal{O}^*(\mathcal{S}^n)\) where \(\mathcal{T}\cdot \mathcal{S}\leq 3.1819\), and we show that a value \(\mathcal{T}\cdot \mathcal{S}\leq 3.1818\) is not attainable in this framework.
Besides this point-wise result, we can, in principle, compute any point on the tradeoff curve between \(S\) and \(D\) with arbitrary accuracy. For easier interpretability, we also derive closed-form, approximate upper and lower bound curves on the optimal tradeoff. This results, in the framework of [10], [11], in TSP algorithms with an improved running time for any space budget \(\mathcal{O}^*(\mathcal{S}^n)\), with \(1 < \mathcal{S}< 2\).
The number of maximal chains is a natural invariant of a set system, and hence its characterization likely has further applications. As an example, we show that our results imply a lower bound on the size of the smallest fibre in the Boolean lattice (a fibre is a subfamily that intersects every maximal antichain). This result improves decades-old bounds by Duffus, Sands, and Winkler [14], as well as by Łuczak [15]; see § 1.4 and § 7.
1.1 The combinatorial problem↩︎
Recall that the Boolean lattice \(2^{[n]}\) consists of all subsets of \([n]=\{1,2,\ldots,n\}\), ordered by inclusion. A subset of \(2^{[n]}\) is called a set system or a (set) family; these terms are used interchangeably. A maximal chain (also: full chain) is a saturated inclusion chain from \(\varnothing\) to \([n]\), i.e., a sequence \[\varnothing=A_0\subset A_1\subset\cdots\subset A_n=[n],\qquad \mathrm{~where~} |A_i|=i.\] There are exactly \(n!\) such chains: each one is encoded by the permutation that lists the elements in the order they are added. For a family \(\mathcal{F}\subseteq 2^{[n]}\), write \(C(\mathcal{F})\) for the number of maximal chains entirely contained in \(\mathcal{F}\) (so each \(A_i\in\mathcal{F}\)), and define the two normalized quantities \[S(\mathcal{F})=|\mathcal{F}|^{1/n}, \qquad D(\mathcal{F})=\left(\frac{C(\mathcal{F})}{n!}\right)^{1/n}.\]
Here \(S(\mathcal{F})\in[1,2]\) measures the exponential size of \(\mathcal{F}\) (per coordinate), while \(D(\mathcal{F})\in [0,1]\) is an exponential measure of the chain-density of \(\mathcal{F}\): large \(D\) (close to one) means \(\mathcal{F}\) contains a large fraction of all \(n!\) maximal chains. The basic extremal quantity we study is \[D_S \;=\; \sup\bigl\{\,D(\mathcal{F}):\mathcal{F}\subseteq 2^{[n]}\text{ for some }n,\; S(\mathcal{F})\le S\,\bigr\}, \qquad \mathrm{~where~} 1<S\le 2,\] or informally: How chain-dense can a family be if its size is at most \(S^n\)?
Of particular interest is the infimum of \(S^2/D_S\), which controls the space-time product achievable for permutation-type problems (such as the TSP) in the framework of [10], [11].
For convenience, we define the base-\(2\) logarithms of the parameters:
\[S^{\ell}(\mathcal{F}) = {\log_2{S(\mathcal{F})}}, \qquad D^{\ell}(\mathcal{F}) = {\log_2{(D(\mathcal{F}))}},\]
and the extremal quantity
\[D^{\ell}_{S^{\ell}} \;=\; \sup\bigl\{\,D^{\ell}(\mathcal{F}):\mathcal{F}\subseteq 2^{[n]}\text{ for some }n,\; S^{\ell}(\mathcal{F})\le S^{\ell}\,\bigr\}, \qquad 0<S^{\ell}\le 1,\]
noting that, for \(\sigma\in(0,1]\):
\[D^\ell_\sigma = \log_2{(D_{2^\sigma})}.\]
1.2 The entropy formulation↩︎
Call a pair of random variables \((Z,T)\) admissible if \(T\sim\operatorname{Unif}[0,1]\) and \(Z\) is an arbitrary auxiliary random variable (not necessarily independent from \(T\)). Denoting by \(\mathsf H\) the Shannon entropy and by \(\mathsf H(\,\cdot\,|\,\cdot\,)\) the conditional entropy, define \[h(Z,T)=\sup_{0\le t\le1}\mathsf H(\mathbf{1}_{\{T\le t\}}\mid Z).\]
Informally, \(h(Z,T)\) is the information content of \(T\) being below a threshold \(t\), given the realization of \(Z\), for the threshold \(t\) that maximizes this value.
For a parameter \(0<\sigma\le1\), we denote \[D^{\mathrm{ent}}_\sigma=- \inf\{\mathsf I(Z;T) \mid (Z,T)\text{ admissible and }h(Z,T)\le\sigma\}.\]
Here, \(\mathsf I(Z;T)\) denotes the mutual information between \(Z\) and \(T\). Intuitively, there is a natural tension between \(\sigma\) and \(D^{\mathrm{ent}}_\sigma\). If \(h(Z,T)\) is suppressed to a low value \(\sigma\), that is, if knowledge of \(Z\) confers significant information about the outcome of \(T\), then \(Z\) and \(T\) are mutually highly dependent; as a consequence, we expect \(D^{\mathrm{ent}}_\sigma\) to have a low value.
The central result of our paper is that the tradeoff between \(\sigma\) and \(D^{\mathrm{ent}}_\sigma\) is identical to the tradeoff between the two combinatorial quantities described earlier. Specifically, we show the following.
Theorem 1. For every \(0<\sigma\le1\), \[D^{\ell}_{\sigma}=D^{\mathrm{ent}}_\sigma.\] In particular, writing \(\sigma = S^{\ell} = \log_2{S}\), \[\begin{align} \inf_{1<S\leq 2}\{\log_2 (S^2/D_S)\} &= \inf_{0<\sigma\leq 1}\{2\sigma - D^{\mathrm{ent}}_\sigma\}\\ &= \inf_{\substack{0<\sigma\leq 1,\\(Z,T)}}\{2\sigma + \mathsf I(Z;T) \mid (Z,T)\text{ admissible and }h(Z,T)\le\sigma\}\\ &= \inf_{(Z,T)}\{2h(Z,T) + \mathsf I(Z;T) \mid (Z,T)\text{ admissible}\}. \end{align}\]
We will also derive upper and lower bounds for \(D^{\mathrm{ent}}_\sigma\), which, via the above theorem, entails bounds on the quantity \(\gamma = S^2/D_S\) that appears as the base of the exponential in the TSP space-time tradeoff. Outside of this concrete algorithmic application, of course, other functions of \(S\) and \(D_S\) may be of interest as well, and these can, in principle, be optimized through similar methods.
We highlight the fact that the correspondence between the two settings is particularly clean: \(h(Z,T)=\log_2 S\) and \(\mathsf I(Z;T)=-\log_2D\).
1.3 Concrete bounds↩︎
We show how this entropy formulation of the problem makes it amenable to primal and dual certificates for rigorous computational upper and lower bounds respectively. In particular, we obtain the following.
Theorem 2. The best space-time product achievable for TSP (and other constant degree idempotent permutation problems) in the framework of [10], [11] is \(\gamma^{n+o(n)}\), where \(\gamma = \inf_{1<S\leq 2}\{(S^2/D_S)\}\) is such that \[3.1818 < \gamma < 3.18184.\]
The upper bound is given in Theorem 5, and the lower bound in Theorem 7.
We expect one can tighten the gap between the upper and lower bounds arbitrarily at the cost of more computation. We can also find bounds of the same nature on \(D_S\) (or equivalently on \(S^2/D_S\)) as a function of \(S\), yielding points close to the optimal space-time tradeoff curve achievable within the [10], [11] framework. The upper and lower bound curves we obtain on \(D_S\) are illustrated in Figure 1. The implied bounds on \(S^2/D_S\) (the relevant value for space-time tradeoffs) are illustrated in Figure 2.
The upper bound curve on \(D_S\) is obtained via lower bounds of the form \(S^\Lambda/D_S \geq 2^{\mu_\Lambda}\) for different values of \(\Lambda\). Each such bound directly gives \(D_S \leq S^\Lambda/2^{\mu_\Lambda}\), and the illustrated upper bound curve of Figure 1 is the lower envelope of those individual curves. The lower bound curve on \(D_S\) is obtained by finding certificates through optimization at discrete points, then interpolating between these points using the concavity of the function \(\sigma \to \log_2 D_{2^\sigma}\). Both approaches lead to piecewise-defined curves which do not have a clean and short explicit closed-form expression.
For the lower bound on \(D_S\) (and thus the upper bound on \(S^2/D_S\)), we also derive a slightly weaker but more convenient closed-form expression as follows (see Figure 4 for an illustration).
theoremrestateTCBAS For every \(0<\sigma\leq 1\), let \[k=\lfloor 1/\sigma\rfloor, \qquad \lambda=k(k+1)\sigma-k.\]
Then \(\lambda\in[0,1]\) and \[D^{\mathrm{ent}}_\sigma \ge -\lambda\log_2 k-(1-\lambda)\log_2(k+1)+I(1-\sigma),\] where \(I \geq 0.654865\).
Equivalently (using the identity \(\log_2 D_{2^\sigma} = D^{\mathrm{ent}}_\sigma\)), for \(S=2^\sigma \in (1,2]\), \[D_S \geq k^{-\lambda}(k+1)^{\lambda-1}2^{I(1-\sigma)}.\]
1.4 A further application↩︎
We also give a different application of our bounds on \(D^{\mathrm{ent}}_\sigma\), beyond the algorithmic improvements for TSP and other permutation problems.
Consider the Boolean lattice \(2^{[n]}\) where two subsets of \([n]\) are comparable if one includes the other. An antichain is a collection of pairwise incomparable subsets of \([n]\). An antichain is maximal if it cannot be extended by adding one more set. A fibre is a subset of \(2^{[n]}\) that intersects every maximal antichain of \(2^{[n]}\).
Lonc and Rival [16] raised the question of the minimal size of a fibre in \(2^{[n]}\). Denoting this quantity by \(\mathrm{MF}_n\), we observe \(\mathrm{MF}_n \leq \mathcal{O}(2^{n/2})\), since the family of all sets comparable to any given set of the middle layer is a fibre. Lonc and Rival [16] conjectured this upper bound to be tight. Duffus, Sands and Winkler [14] made some progress towards the conjecture, showing \(\mathrm{MF}_n \geq \Omega(1.25^{n})\), which was later improved by Łuczak to \(\mathrm{MF}_n \geq \Omega(2^{n/3})\), as reported by Duffus and Sands [15]. There has been no further progress since.
As a corollary of our results we obtain the following.
theoremrestateFIBRE Let \(\sigma\in (0,1]\). If \(D^{\ell}_\sigma \leq -1\), then \(\mathrm{MF}_n \geq 2^{\sigma n}\).
In particular, since \(D^{\ell}_{0.37586} \leq -1\), we have \[\mathrm{MF}_n \geq 2^{0.37586 n}.\]
![Figure 1: Upper and lower bound curves for the tradeoff between (logarithmic) set system size \sigma = \log_2{S} = S^{\ell} (horizontal axis) and set system density D_S = D_{2^{\sigma}} (vertical axis). Red dot indicates the best point-wise tradeoff, i.e., the minimal S^2 / D_S value. Solid red and green indicate the lower and upper bound curves we derive. Note that these are piecewise-defined curves resulting from certificates computed at discrete points; while the bounds could be further refined through more computation, a compact, closed-form description of the optimal tradeoff curve is not available. Upper and lower bounds found in previous works [9]–[11] are also shown.](/article/2607.11311/figures/chain_density_bounds.png "fig:")
![Figure 2: Tradeoff curves (\mathcal{T} vs. \mathcal{S}) for the best exponential running time \mathcal{T}^n and space \mathcal{S}^n achievable for the TSP, with optimal space-time product shown as a red point. Classical \mathcal{S}\cdot \mathcal{T}= 4 tradeoff shown for reference as black line. It may seem that the method improves this baseline only for \mathcal{S}\gtrsim 1.19; note however, that the improvements can be extended to the lower range of \mathcal{S}, by combining the method with Gurevich-Shelah divide-and-conquer. For more details on this, by-now-standard technique, refer to [17], [11].](/article/2607.11311/figures/TS_bounds.png "fig:")
1.4.0.1 Structure of the paper.
In § 2 we introduce the basic information theory toolkit we need. In § 3 we prove the two-way correspondence between the combinatorial and information-theoretic formulations of the problem, proving Theorem 1. Sections § 4, § 5 are dedicated to proving lower bounds for \(D^{\mathrm{ent}}_\sigma\), yielding the algorithmic side of Theorem 2 and Theorem [thm:closed-bound-all-S]. Section § 6 contains the upper bounds for \(D^{\mathrm{ent}}_\sigma\), yielding the barrier side of Theorem 2. In § 7 we describe the application to bounding minimal fibres in the Boolean lattice, proving Theorem [thm:fibre]. In § 8 we conclude with some open questions.
1.4.0.2 Disclosure on the use of AI.
The results of the paper were obtained with the help of OpenAI’s ChatGPT 5.5 tool, which was also used to verify and reformulate arguments and to explore the problem structure, which materially affected all technical sections of the paper. The authors assume full responsibility for the contents, including its correctness and originality.
2 Preliminaries↩︎
Recall the definition of \(D_S\) as a supremum of the density \(D(\mathcal{F})\) over all families with finite ground set, with \(S(\mathcal{F}) \leq S\). For \(\require{upgreek} \upalpha\le 0\), a witness for a lower bound \(\require{upgreek} \upalpha \leq D_S^\ell\), or simply a set system witness, is a family \(\mathcal{F}\) with \(S(\mathcal{F}) \leq S\) and \(\require{upgreek} D^\ell(\mathcal{F}) \geq \upalpha\). Note that such a witness also implies a corresponding upper bound on \(\gamma\).
Similarly, a witness for a lower bound \(\require{upgreek} \upalpha \leq D^{\mathrm{ent}}_\sigma\) is a pair \((Z,T)\), where \(T\sim\operatorname{Unif}[0,1]\) and \(Z\) is an arbitrary random variable, where \(h(Z,T) \leq \sigma\), and \(\require{upgreek} -\mathsf I(Z;T) \geq \upalpha\). We refer to it as a \((Z,T)\) witness.
2.0.0.1 Information theory.
In the following, we briefly list some properties and facts from information theory that we use; all of them are standard, e.g., see [18].
We refer to [18] for the standard definitions of the entropy \(\mathsf H(X)\) of a random variable \(X\) or \(\mathsf H(p)\) of a probability vector \(p\), and the conditional entropy \(\mathsf H(X \mid Y)\), as well as for the definition of the mutual information \(\mathsf I(X;Y)\) of two random variables, and the conditional mutual information \(\mathsf I(X;Y \mid W)\).
An easy upper bound on the entropy is \(\mathsf H(X)\le\log_2|\mathcal{X}|\), where \(\mathcal{X}\) is the support set of \(X\), and applying a function cannot increase entropy: \[\mathsf H(f(X))\le\mathsf H(X).\]
Since conditioning cannot increase entropy, \[\mathsf H(X\mid Y,W)\le\mathsf H(X\mid Y);\] in particular, conditioning on a function of \(Y\) instead of \(Y\) can only increase entropy: \[\mathsf H(X\mid f(Y))\ge\mathsf H(X\mid Y).\]
Finally, \(\mathsf H(X\mid Y)=0\) if and only if \(X\) is a function of \(Y\) (up to a set of probability zero).
When \(X\) is discrete, \[\mathsf I(X;Y)=\mathsf H(X)-\mathsf H(X\mid Y)\;\le\;\mathsf H(X);\] in particular \(\mathsf I(X;Y)=\mathsf H(X)\) when \(X\) is a function of \(Y\). For the continuous entropy, if \(Y\) has a density and the quantities below are finite, then the analogous statement holds: \[\mathsf I(X;Y)=\mathsf H_{\mathrm{cont}}(Y)-\mathsf H_{\mathrm{cont}}(Y\mid X).\]
The chain rule for mutual information states \[\mathsf I(X,W;Y)=\mathsf I(W;Y)+\mathsf I(X;Y\mid W).\] Two consequences we use: if \(R\) is independent of the pair \((X,Y)\), then \(\mathsf I(X;(Y,R))=\mathsf I(X;Y)\); and if \(B\) is independent of \(Y\), then \(\mathsf I((B,X);Y)=\mathsf I(X;Y\mid B)\).
The data processing inequality says that for every (measurable) function \(f\), \[\mathsf I(X;f(Y))\le\mathsf I(X;Y).\] In words, processing a variable cannot increase mutual information. By symmetry the same holds for a function applied to \(X\).
3 Equivalence between the combinatorial and entropy formulations↩︎
In this section we show the main equivalence between the combinatorial and information-theoretic formulations of our tradeoff, proving Theorem 1.
3.1 From set system witnesses to \((Z,T)\) witnesses↩︎
Here we show that any set system witnessing
\(\require{upgreek} D^{\ell}_{\sigma} \geq \upalpha\) can be used to construct an admissible pair \((Z,T)\) witnessing \(\require{upgreek} D^{\mathrm{ent}}_\sigma \geq \upalpha\), and thus \(D^{\ell}_{\sigma} \leq D^{\mathrm{ent}}_\sigma\).
Lemma 1. Let \(\mathcal{F}\subseteq2^{[n]}\) satisfy \(C(\mathcal{F})>0\). Then there is an admissible pair \((Z,T)\) such that \[h(Z,T)\le \frac{1}{n}\log_2|\mathcal{F}|=S^{\ell}(\mathcal{F}), \qquad \mathsf I(Z;T)=\frac{1}{n}\log_2\frac{n!}{C(\mathcal{F})}=- D^{\ell}(\mathcal{F}).\]
Proof. Let \(U_1,\ldots,U_n\) be independent uniform random variables on \([0,1]\). Their increasing order \(\pi\) determines a uniformly random maximal chain: if \(U_{\pi(1)}<\cdots<U_{\pi(n)}\), then the chain is \[\varnothing, \{\pi(1)\}, \{\pi(1),\pi(2)\}, \ldots, [n].\] Let \(E_\mathcal{F}\) be the event that this chain is contained in \(\mathcal{F}\), and let \(\mathbb{Q}=\mathbb{P}(\,\cdot\mid E_\mathcal{F})\). Since each of the \(n!\) maximal chains is equally likely, \[\mathbb{P}(E_\mathcal{F})=\frac{C(\mathcal{F})}{n!}.\]
Choose \(J\) uniformly from \([n]\), independently of the \(U_i\)’s under \(\mathbb{Q}\), and set \[T=U_J, \qquad Z=(J,U_1,\ldots,U_{J-1}).\] The event \(E_\mathcal{F}\) depends only on the order of the \(U_i\)’s, not on their sorted values. Therefore a uniformly chosen coordinate remains uniform after conditioning on \(E_\mathcal{F}\) and \(T\sim\operatorname{Unif}[0,1]\) under \(\mathbb{Q}\).
Under the original probability distribution, \((U_1,\ldots,U_n)\) is uniform on the cube \([0,1]^n\). The event \(E_\mathcal{F}\) is a union of exactly \(C(\mathcal{F})\) disjoint regions of \([0,1]^n\), one for each valid maximal chain. Each order region has volume \(1/n!\). Therefore, under \(\mathbb{Q}\), the vector \[U=(U_1,\ldots,U_n)\] is uniform on a region of volume \[\frac{C(\mathcal{F})}{n!}.\] Consequently \[\mathsf H_{\mathrm{cont}}(U_1,\ldots,U_n)=\log_2\frac{C(\mathcal{F})}{n!} = D^{\ell}(\mathcal{F}).\] By the chain rule for continuous entropy, \[\mathsf H_{\mathrm{cont}}(U_1,\ldots,U_n) =\sum_{j=1}^n\mathsf H_{\mathrm{cont}}(U_j\mid U_1,\ldots,U_{j-1}).\]
Since \(T=U_J\) and \(Z=(J,U_1,\ldots,U_{J-1})\), we have \[\begin{align} \mathsf H_{\mathrm{cont}}(T \mid Z) &= \mathsf H_{\mathrm{cont}}(U_J \mid J, U_1, \ldots, U_{J-1})\\ &= \sum_{j=1}^n \mathbb{Q}(J=j) \cdot \mathsf H_{\mathrm{cont}}(U_j | U_1, \ldots, U_{j-1})\\ &= \frac{1}{n}\sum_{j=1}^n \mathsf H_{\mathrm{cont}}(U_j | U_1, \ldots, U_{j-1})\\ &= \frac{1}{n}\mathsf H_{\mathrm{cont}}(U_1,\ldots,U_n). \end{align}\]
On the other hand, \(T\) is uniform on \([0,1]\), so \(\mathsf H_{\mathrm{cont}}(T)=\log_2 1=0\). Thus \[\begin{align} \mathsf I(Z;T) &=\mathsf H_{\mathrm{cont}}(T)-\mathsf H_{\mathrm{cont}}(T\mid Z) \\ &=-\frac{1}{n}\mathsf H_{\mathrm{cont}}(U_1,\ldots,U_n) \\ &= -D^{\ell}(\mathcal{F}). \end{align}\]
It remains to bound the threshold entropy. Fix \(t\) and define \(B_j(t)=\mathbf{1}_{\{U_j\le t\}}\) and \(X_t=(B_1(t),\ldots,B_n(t))\). Interpret the random vector \(X_t\) as a (random) subset of \([n]\) (a value of \(1\) at some index means this index is included in the subset). Note that this subset is a prefix set of the maximal chain determined by \(U_1,\ldots,U_n\), and thus is in \(\mathcal{F}\) if the latter is a maximal chain contained in \(\mathcal{F}\). Under \(\mathbb{Q}\) this is true with probability \(1\), so the subset of \([n]\) represented by \(X_t\) is in \(\mathcal{F}\), and \(X_t\) has support at most \(|\mathcal{F}|\). Therefore \[\mathsf H(X_t)\le\log_2|\mathcal{F}|.\] Moreover \(\mathbf{1}_{\{T\le t\}}=B_J(t)\), so \[\begin{align} \mathsf H(\mathbf{1}_{\{T\le t\}}\mid Z) &=\frac{1}{n}\sum_{j=1}^n \mathsf H(B_j(t)\mid U_{<j}) \\ &\le \frac{1}{n}\sum_{j=1}^n \mathsf H(B_j(t)\mid B_1(t),\ldots,B_{j-1}(t)) \\ &=\frac{1}{n}\mathsf H(X_t) \le \frac{1}{n}\log_2|\mathcal{F}| = S^{\ell}(\mathcal{F}). \end{align}\]
Taking the supremum over \(t\) proves the lemma. ◻
3.2 From \((Z,T)\) witnesses to set system witnesses↩︎
We now prove the reverse direction of 1. The point is that a witness \((Z,T)\) can be converted into large families of permutations whose prefix sets form the desired set systems. We first carry this out when \(Z\) has finite range. The general case is then obtained by coarsening \(Z\) into finitely many values, losing only an arbitrarily small amount in the threshold entropy and losing nothing in mutual information.
Proposition 3. Let \((Z,T)\) be an admissible pair such that \(Z\) takes finitely many values and \(d=\mathsf I(Z;T)<\infty\). Let \(h=h(Z,T)\). For every \(\eta>0\) there are set systems \(\mathcal{F}_n\subseteq2^{[n]}\) with \(C(\mathcal{F}_n)>0\) such that \[\begin{align} \mathrm{(i)}~~ \limsup_{n\to\infty}S^{\ell}(\mathcal{F}_n) & \le h+\eta \\ \mathrm{(ii)}~~\liminf_{n\to\infty} D^{\ell}(\mathcal{F}_n) & \ge -d. \end{align}\]
Proof. Write the values of \(Z\) as \(1,\ldots,s\), and set \[p_i=\mathbb{P}(Z=i)>0, \qquad F_i(t)=\mathbb{P}(T\le t\mid Z=i).\] Since \(T\) is uniform on \([0,1]\), the conditional distribution functions obey \[\label{eq:mixture-uniform-main} \sum_{i=1}^s p_iF_i(t)= \mathbb{P}(T\leq t) = t, \qquad 0\le t\le1.\tag{1}\] In particular, each \(F_i\) is continuous: if \(F_i\) had a discontinuity at some point, then so would \(t\to \mathbb{P}(T\leq t)\) (because all \(F_i\) are non-negative), contradicting the uniformity of \(T\). Because each \(F_i\) is also trivially bounded and monotone, it is uniformly continuous.
For later use, note that \[\label{eq:d-h-finite-main} h = h(Z,T) =\sup_{0\le t\le1}\sum_{i=1}^s p_i\mathsf H_2(F_i(t)),\tag{2}\] because, conditional on \(Z=i\), the bit \(\mathbf{1}_{\{T\le t\}}\) is Bernoulli with parameter \(F_i(t)\).
Choose a partition \[0=t_0<t_1<\cdots<t_L=1\] fine enough so that the following holds. Whenever \(t_{a-1}\le t\le t_a\), the values \(F_i(t)\) and \(F_i(t_{a-1})\) are close enough, for every \(i\), that any vector \(x=(x_1,\ldots,x_s)\) satisfying \[F_i(t_{a-1})\le x_i\le F_i(t_a) \qquad\text{for all }i\] obeys \[\label{eq:rectangle-entropy-control} \sum_{i=1}^s p_i\mathsf H_2(x_i) \le h+\frac{\eta}{3}.\tag{3}\] Such a partition exists from the uniform continuity of the finitely many functions \(F_i\) and of the binary entropy function: after refining the partition, each \(x_i\) can be made to be arbitrarily close to \(F_i(t_{a-1})\), and the value at the left endpoint is at most \(h\) by 2 .
Let \(A\) be the interval of the partition containing \(T\), so \(A=a\) when \(t_{a-1}<T\le t_a\). Define \[\Delta_a=t_a-t_{a-1}, \qquad q_{ia}=p_i\bigl(F_i(t_a)-F_i(t_{a-1})\bigr).\] Thus \(q_{ia}\) is the joint probability of the event \(\{Z=i,A=a\}\). Its row and column sums are \[\sum_a q_{ia}=p_i, \qquad \sum_i q_{ia}=\Delta_a,\] where the second identity is 1 applied at \(t_a\) and \(t_{a-1}\).
We now turn this finite table into a set system. For each \(n\), choose integers \(n_{ia}\ge0\) with \[\frac{n_{ia}}{n}\to q_{ia} \qquad\text{for every }i,a,\] and with total sum \(\sum_{i,a}n_{ia}=n\). Let \[n_i=\sum_a n_{ia}, \qquad m_a=\sum_i n_{ia}.\] Then \(n_i/n\to p_i\) and \(m_a/n\to\Delta_a\). Partition the ground set into classes \[[n]=B_1\sqcup\cdots\sqcup B_s, \qquad |B_i|=n_i,\] and partition the positions of a permutation into consecutive blocks \[R_a=\{m_1+\cdots+m_{a-1}+1, m_1+\cdots+m_{a-1}+2, \ldots,m_1+\cdots+m_a\}, \qquad |R_a|=m_a.\] Let \(\Pi_n\) be the set of permutations \(\pi\) of \([n]\) such that, for every \(i\) and \(a\), \[\#\{j\in R_a:\pi(j)\in B_i\}=n_{ia}.\] For \(\pi\in\Pi_n\) and \(0\le k\le n\), let \[P_k(\pi)=\{\pi(1),\ldots,\pi(k)\}, \qquad P_0(\pi)=\varnothing.\] Define \[\mathcal{F}_n=\{P_k(\pi):\pi\in\Pi_n,\;0\le k\le n\}.\] Every permutation in \(\Pi_n\) gives a maximal chain contained in \(\mathcal{F}_n\). Hence \[C(\mathcal{F}_n)\ge |\Pi_n|.\]
We first estimate the chain density. A permutation in \(\Pi_n\) can be specified as follows. For each \(a\) and each \(i\), choose which \(n_{ia}\) positions \(j\in R_a\) have \(\pi(j)\in B_i\). Then, for each \(i\), assign the elements of \(B_i\) to all positions of that type. This gives \[|\Pi_n|=\frac{\prod_i n_i!\prod_a m_a!}{\prod_{i,a}n_{ia}!}.\] By Stirling’s formula, with the convention \(0\log 0=0\), \[\begin{align} \lim_{n\to\infty}\frac{1}{n}\log_2\frac{n!}{|\Pi_n|} &=\sum_{i,a}q_{ia}\log_2\frac{q_{ia}}{p_i\Delta_a} \\ &=\mathsf I(Z;A). \end{align}\]
Since \(A\) is a function of \(T\), data processing gives \(\mathsf I(Z;A)\le\mathsf I(Z;T)=d\). Together with \(C(\mathcal{F}_n)\ge |\Pi_n|\), this implies \[\liminf_{n\to\infty}D^{\ell}(\mathcal{F}_n) =\liminf_{n\to\infty}\frac{1}{n}\log_2\frac{C(\mathcal{F}_n)}{n!} \ge -d,\] which proves \(\mathrm{(ii)}\).
It remains to estimate the size of \(\mathcal{F}_n\). Let \(X\in\mathcal{F}_n\) be a prefix whose size lies in the position block \(R_a\). For each type \(i\), let \[x_i(X)=\frac{|X\cap B_i|}{n_i}.\] All elements placed in earlier position blocks have already appeared in the prefix, and no element placed in later position blocks has appeared yet. Hence \[\frac{\sum_{b<a}n_{ib}}{n_i} \le x_i(X) \le \frac{\sum_{b\le a}n_{ib}}{n_i}.\] The two endpoints converge to \(F_i(t_{a-1})\) and \(F_i(t_a)\), respectively. By 3 and the convergence \(n_i/n\to p_i\), it follows that, for all sufficiently large \(n\), the following holds \[\label{eq:profile-entropy-control-n} \sum_{i=1}^s\frac{n_i}{n}\mathsf H_2(x_i(X)) \le h+\frac{2\eta}{3}.\tag{4}\]
For a fixed profile \((k_1,\ldots,k_s)\), where \(k_i=|X\cap B_i|\), the number of sets with that profile is at most \[\prod_i\binom{n_i}{k_i} \le 2^{\sum_i n_i\mathsf H_2(k_i/n_i)},\] using the standard binomial estimate \[\binom{N}{K}\le 2^{N\mathsf H_2(K/N)}.\] Thus 4 shows that each profile \((k_1,\ldots,k_s)\) contributes at most \(2^{n(h+2\eta/3)}\) sets. There are at most \(\prod_i(n_i+1)\) possible profiles, which is polynomial in \(n\). Therefore \[\frac{1}{n}\log_2|\mathcal{F}_n| \le h+\frac{2\eta}{3}+o(1).\] Taking the limsup and using the remaining slack in \(\eta\) proves \(\mathrm{(i)}\). ◻
We next remove the assumption that \(Z\) has finite range.
Lemma 2. Let \((Z,T)\) be admissible with \(\mathsf I(Z;T)<\infty\). For every \(\rho>0\) there is a finite-valued random variable \(Z_\rho\), which is a function of \(Z\), such that
\[\begin{align} \mathrm{(i)} ~~ \mathsf I(Z_\rho;T) & \le\mathsf I(Z;T), \\ \mathrm{(ii)} ~~h(Z_\rho,T) & \le h(Z,T)+\rho. \end{align}\]
Proof. Fix \(\varepsilon>0\) and choose a grid \[0=t_0<t_1<\cdots<t_L=1\] such that the distance between consecutive points is at most \(\varepsilon\). Let \(B_t=\mathbf{1}_{\{T\le t\}}\). If \(t_{a-1}\le t\le t_a\), then \(B_t\) and \(B_{t_a}\) differ only when \(t<T\le t_a\), an event of probability at most \(\varepsilon\). Hence, for any random variable \(W\), \[\label{eq:grid-threshold-reduction} \mathsf H(B_t\mid W) \le \mathsf H(B_{t_a}\mid W)+\mathsf H_2(\varepsilon),\tag{5}\] because \(B_t\) is determined by \(B_{t_a}\) together with the error bit \(B_t\oplus B_{t_a}\).
For the grid points \(t_0,\ldots,t_{L}\), fix versions of the conditional probabilities \[g_a(Z)=\mathbb{P}(T\le t_a\mid Z).\] Partition the cube \([0,1]^{L+1}\) into finitely many boxes of side length at most \(\delta\), and let \(Z_\rho\) be the index of the box containing \((g_0(Z),\ldots,g_{L}(Z))\). Then \(Z_\rho\) is finite-valued and is a function of \(Z\), so \((i)\) follows from data processing.
Let \[\omega_{\mathsf H_2}(\delta) = \sup\{ |\mathsf H_2(p)-\mathsf H_2(q)| : |p-q|\le \delta,\;p,q\in[0,1] \}\] be a modulus of continuity for the binary entropy function. Fix a grid point \(t_a\), and write \[g_a(Z)=\mathbb{P}(T\le t_a\mid Z).\] Since \(Z_\rho\) is obtained from \(Z\), conditioning first on \(Z\) and then averaging over the cell of \(Z_\rho\) gives \[\mathbb{P}(T\le t_a\mid Z_\rho) = \mathbb{E}(g_a(Z)\mid Z_\rho).\] Now consider one cell of the partition. By construction, the \(a\)-th coordinate \(g_a\) varies by at most \(\delta\) inside that cell. Therefore the average \(\mathbb{E}(g_a(Z)\mid Z_\rho)\), which is an average of values of \(g_a\) from the same cell, is also within \(\delta\) of each value \(g_a(Z)\) in that cell. Thus, almost surely, \[\left| \mathbb{P}(T\le t_a\mid Z_\rho)-g_a(Z) \right| \le \delta.\] Applying the modulus of continuity of \(\mathsf H_2\), we get the point-wise bound \[\mathsf H_2\!\left(\mathbb{P}(T\le t_a\mid Z_\rho)\right) \le \mathsf H_2(g_a(Z))+\omega_{\mathsf H_2}(\delta).\] Taking expectations gives \[\mathsf H(B_{t_a}\mid Z_\rho) \le \mathsf H(B_{t_a}\mid Z)+\omega_{\mathsf H_2}(\delta).\] Finally, \[\mathsf H(B_{t_a}\mid Z)\le h(Z,T),\] because \(h(Z,T)\) is the supremum of \(\mathsf H(B_t\mid Z)\) over all thresholds \(t\). Hence, for every grid point \(t_a\), \[\mathsf H(B_{t_a}\mid Z_\rho) \le h(Z,T)+\omega_{\mathsf H_2}(\delta).\]
Now apply 5 with \(W=Z_\rho\) to get \[\begin{align} \mathsf H(B_t\mid Z_\rho) &\leq \mathsf H(B_{t_a}\mid Z_\rho)+\mathsf H_2(\varepsilon)\\ &\leq h(Z,T)+\omega_{\mathsf H_2}(\delta)+\mathsf H_2(\varepsilon). \end{align}\]
Taking the supremum over all \(t\): \[h(Z_\rho,T) \le h(Z,T)+\omega_{\mathsf H_2}(\delta)+\mathsf H_2(\varepsilon).\] Choosing \(\delta\) and \(\varepsilon\) so that the last two terms sum to at most \(\rho\) proves \(\mathrm{(ii)}\). ◻
Proof of 1. We first prove \(D^{\ell}_{\sigma}\le D^{\mathrm{ent}}_\sigma\). By 1, every family \(\mathcal{F}\) with \(S^{\ell}(\mathcal{F})\le\sigma\) gives an admissible pair \((Z,T)\) with \(h(Z,T)\le\sigma\) and \[-\mathsf I(Z;T)=D^{\ell}(\mathcal{F}).\] Taking the supremum over all such families gives \(D^{\ell}_{\sigma}\le D^{\mathrm{ent}}_\sigma\).
For the reverse inequality, fix \(0<\tau<\sigma\) and an admissible pair \((Z,T)\) with \(h(Z,T)\le\tau\) and \(\mathsf I(Z;T)<\infty\). Apply 2 with a small parameter \(\rho>0\), and then apply 3 to the finite-valued pair \((Z_\rho,T)\). If \(\rho\) and the parameter \(\eta\) in the proposition are chosen so that \(\tau+\rho+\eta\le\sigma\), we obtain set systems \(\mathcal{F}_n\) with \[\limsup_n S^{\ell}(\mathcal{F}_n)\le\sigma \qquad\text{and}\qquad \liminf_n D^{\ell}(\mathcal{F}_n) \ge -\mathsf I(Z_\rho;T) \ge -\mathsf I(Z;T).\] Thus \(D^{\ell}_{\sigma}\ge -\mathsf I(Z;T)\). Taking the supremum over all witnesses with \(h(Z,T)\le\tau\) gives \[D^{\ell}_{\sigma}\ge D^{\mathrm{ent}}_\tau.\] Finally let \(\tau\) approach \(\sigma\) from below and use the continuity of \(D^{\mathrm{ent}}\) from 6. This proves \(D^{\ell}_{\sigma}\ge D^{\mathrm{ent}}_\sigma\), and hence \(D^{\ell}_{\sigma}=D^{\mathrm{ent}}_\sigma\).
The formula involving \(S^2/D_S\) is then just a change of variables. Since \(S=2^\sigma\) and \(D^{\ell}_{\sigma}=\log_2 D_{2^\sigma}\), \[\log_2\frac{S^2}{D_S}=2\sigma-D^{\ell}_{\sigma}=2\sigma-D^{\mathrm{ent}}_\sigma.\] The remaining equalities in the statement follow directly from the definition of \(D^{\mathrm{ent}}_\sigma\): for a fixed admissible pair \((Z,T)\), the smallest feasible choice of \(\sigma\) is \(h(Z,T)\), and the expression \(2\sigma+\mathsf I(Z;T)\) only increases when \(\sigma\) is made larger. ◻
4 Algorithm from Theorem 2 via a lower bound on \(D^{\mathrm{ent}}_\sigma\), for \(\frac{1}{2}\leq \sigma\leq 1\)↩︎
We now describe explicit witnesses for lower bounds on \(D^{\mathrm{ent}}_\sigma\) for \(\sigma\geq \frac{1}{2}\). By Theorem 1 and the framework from [10], [11], this entails the algorithmic side of Theorem 2 (upper bound on \(\gamma\)).
The value of the resulting bounds will be expressed in terms of an integral which we now define. For \(\sigma\in(1/2,1)\), let \((x_\sigma,y_\sigma)\in(1/2,1)\times(0,1/2)\) be defined by the equations \[\label{eq:tangent-point} \mathsf H_2(x_\sigma)+\mathsf H_2(y_\sigma)=2\sigma, \qquad x_\sigma\mathsf H_2'(x_\sigma)+y_\sigma\mathsf H_2'(y_\sigma)=0.\tag{6}\] Let \(f_\sigma\) be the lower branch of the level curve \[\mathsf H_2(x)+\mathsf H_2(f_\sigma(x))=2\sigma,\] for \(x_\sigma\le x\le1-y_\sigma\). Define \[I_\sigma= \int_{x_\sigma}^{1-y_\sigma} \Phi(f_\sigma'(x))\,dx, \qquad \Phi(r)=(1+r)\mathsf H_2\left(\frac{1}{1+r}\right),\] and \[a_\sigma= (x_\sigma+y_\sigma) \mathsf H_2\left(\frac{x_\sigma}{x_\sigma+y_\sigma}\right) +\frac{1}{2} I_\sigma.\] At the endpoint \(\sigma=1/2\), we interpret \((x_{1/2},y_{1/2})=(1/2,0)\) and write \[I=I_{1/2},\] so that \(a_{1/2}=I/2\).
Theorem 4. For every \(\sigma\in[1/2,1)\), \[D^{\mathrm{ent}}_{\sigma} \geq a_\sigma-1.\]
Proof. Take \(Z\) uniform on \(\{1,2\}\). We specify the conditional CDFs \(F_1,F_2\) of \(T\) given \(Z=1,2\) by a monotone path \[\Gamma(t)=(F_1(t),F_2(t))\] from \((0,0)\) to \((1,1)\) satisfying \((F_1(t)+F_2(t))/2=t\).
For any fixed \(t\in[0,1]\), we have \[\begin{align} \mathsf H(\mathbf{1}_{\{T\leq t\}} \mid Z) &= \frac{1}{2}\mathsf H(\mathbf{1}_{\{T\leq t\}} \mid Z=1) + \frac{1}{2}\mathsf H(\mathbf{1}_{\{T\leq t\}} \mid Z=2)\\ &= \frac{1}{2}\mathsf H_2(F_1(t)) + \frac{1}{2}\mathsf H_2(F_2(t)). \end{align}\] Thus, the quantity \[\begin{align} h(Z,T) = \sup_{0\leq t \leq 1} \mathsf H(\mathbf{1}_{\{T\leq t\}} \mid Z) \end{align}\] is at most \(\sigma\) whenever the path \(\Gamma(t)=(F_1(t),F_2(t))\) stays in the region \(\mathsf H_2(x)+\mathsf H_2(y)\leq 2\sigma\) for all \(t\in[0,1]\).
For \(\sigma\in [1/2,1)\), use the path consisting of the line segment from \((0,0)\) to \((x_\sigma,y_\sigma)\), the boundary arc \(y=f_\sigma(x)\) from \((x_\sigma,y_\sigma)\) to \((1-y_\sigma,1-x_\sigma)\), and the reflected line segment to \((1,1)\). See Figure 3 for an illustration. The tangency condition in 6 ensures that the line segment lies inside the entropy sublevel region; the arc lies on its boundary, and the last segment follows by symmetry. Hence this is a valid witness with \(h(Z,T)\le\sigma\).
It remains to compute \(\mathsf I(Z;T) = \mathsf H(Z)-\mathsf H(Z \mid T)\). We have \(\mathsf H(Z)=1\), since \(Z\) takes one of two values with equal probability.
Fix \(t\), and assume that for an infinitesimal increment from \(t\) to \(t+dt\), \(F_1(t)\) increases by \(dx\) and \(F_2(t)\) by \(dy\). Then we have \[\begin{align} \mathbb{P}(t\leq T \leq t+dt) &= \frac{1}{2}\mathbb{P}(t\leq T \leq t+dt \mid Z=1) + \frac{1}{2}\mathbb{P}(t\leq T \leq t+dt \mid Z=2) \\ &= \frac{1}{2}(dx+dy). \end{align}\] By Bayes’ rule, \[\begin{align} \mathbb{P}(Z=1 \mid t\leq T \leq t+dt) &= \frac{dx}{dx+dy}. \end{align}\] Hence, the contribution to \(\mathsf H(Z \mid T)\) of this infinitesimal piece of the path is \[\mathbb{P}(t\leq T \leq t+dt) \cdot \mathsf H(Z \mid t\leq T \leq t+dt) = \frac{1}{2}(dx+dy)\cdot\mathsf H_2\left(\frac{dx}{dx+dy}\right).\] The boundary arc therefore contributes exactly \(\frac{1}{2}I_\sigma\). The first straight segment contributes \[\frac{1}{2}(x_\sigma+y_\sigma) \mathsf H_2\left(\frac{x_\sigma}{x_\sigma+y_\sigma}\right),\] and the reflected segment contributes the same amount.
Thus we have \(\mathsf H(Z \mid T) = a_\sigma\), and \(\mathsf I(Z;T) = 1-a_\sigma\). ◻
For any given \(\frac{1}{2} \leq \sigma < 1\) we can compute (lower bounds on) \(I_\sigma\) and \(a_\sigma\) numerically up to a specified precision using standard numerical integration methods, to get concrete lower bounds on \(D^{\mathrm{ent}}_\sigma\). The interval over which the integral is computed is discretized into many subintervals, and the contribution of each subinterval is lower bounded using the concavity of the binary entropy function.
For example, we have the following.
Lemma 3. The following lower bounds hold. \[\begin{align} &a_{0.5} \geq 0.3274327, \quad a_{0.6} \geq 0.5073334, \quad a_{0.7} \geq 0.6522079, \\ &a_{0.8} \geq 0.7800100, \quad a_{0.9} \geq 0.8952229. \end{align}\]
In particular, for \(\sigma = \frac{1}{2}\) we get
Lemma 4. \[2a_\frac{1}{2}=I=I_\frac{1}{2} \geq 0.654865\] Thus, \[D^{\mathrm{ent}}_\frac{1}{2} \geq a_\frac{1}{2} -1 \geq -0.672568.\]
Optimizing \(2\sigma-(a_\sigma-1)\) we get that this value is minimized roughly at \(\sigma \approx 0.515617\), where we get the following.
Theorem 5. Let \(\sigma^* = 0.515617\). We have \[a_{\sigma^*} \geq 0.361376.\] Thus, \[D^{\mathrm{ent}}_{\sigma^*} \geq a_{\sigma^*} - 1 \geq -0.638624,\] and \[\begin{align} \inf_{0<\sigma\leq 1}\{2\sigma-D^{\mathrm{ent}}_\sigma\} \leq 2\sigma^*-D^{\mathrm{ent}}_{\sigma^*} \leq 1.669858 \end{align}\] In terms of \(S\) and \(D_S\), this is \[\inf_{1<S \leq 2}{\frac{S^2}{D_S}} \leq 2^{1.669858} < 3.18184.\]
5 Closed-form lower bound on \(D^{\mathrm{ent}}_\sigma\), for \(0<\sigma\leq 1\)↩︎
![Figure 4: Closed-form lower bound curve for chain density D_S (Theorem [thm:closed-bound-all-S]) and obtained upper bound curve.](/article/2607.11311/figures/chain_density_closed_form_comparison.png "fig:")
In this section we adapt the \(\sigma=\frac{1}{2}\) witness from the previous section into a closed-form bound for every value of \(0<\sigma\leq 1\), yielding Theorem [thm:closed-bound-all-S]. Recall that the preceding section gives \[D^{\mathrm{ent}}_{1/2}\geq \frac{1}{2}I-1.\] The idea is to use the same two-state transition repeatedly to get witnesses at \(\sigma=1/k\), and then interpolate between these points using concavity of \(D^{\mathrm{ent}}_\sigma\).
Note that although this bound is not tight in general, it has the advantage of having a simple expression, while not being too far from the computed upper bounds (as illustrated in Figure 4).
We first prove the discrete estimates at the points \(\sigma=1/k\).
Lemma 5. For every integer \(k\ge1\), \[D^{\mathrm{ent}}_{1/k}\ge -\log_2 k+\frac{k-1}{k}I.\]
Proof. The case \(k=1\) is witnessed by taking \(Z\) to be constant, so assume \(k\ge2\). Take \(Z\) uniform on \([k]=\{1,\ldots,k\}\). We specify the conditional CDFs \[F_i(t)=\mathbb{P}(T\le t\mid Z=i),\qquad i=1,\ldots,k,\] by a monotone path \[\Gamma(t)=(F_1(t),\ldots,F_k(t))\] from \((0,\ldots,0)\) to \((1,\ldots,1)\) satisfying \[\frac{1}{k}\sum_{i=1}^k F_i(t)=t.\] This last identity guarantees that the unconditional distribution of \(T\) is uniform on \([0,1]\).
The path is as follows. First move the first coordinate from \(0\) to \(1/2\). Then, for \(j=1,\ldots,k-1\), move only the pair of coordinates \((F_j,F_{j+1})\) from \((1/2,0)\) to \((1,1/2)\) along the arc \(\mathsf H_2(F_j)+\mathsf H_2(F_{j+1}) = 1\). Finally move the last coordinate from \(1/2\) to \(1\). All other coordinates remain fixed during each step. See Figure 5 for an illustration.
At every point of this path, the sum of the coordinate entropies is at most \(1\). Therefore, for every threshold \(t\), \[\mathsf H(\mathbf{1}_{\{T\le t\}}\mid Z) =\frac{1}{k}\sum_{i=1}^k \mathsf H_2(F_i(t)) \le \frac{1}{k}.\] So this is a valid witness for \(D^{\mathrm{ent}}_{1/k}\).
It remains to compute its mutual information. We use \[\mathsf I(Z;T)=\mathsf H(Z)-\mathsf H(Z\mid T).\] Since \(Z\) is uniform on \([k]\), we have \(\mathsf H(Z)=\log_2 k\).
Consider an infinitesimal piece of the CDF path. Suppose the coordinates increase by \[(dx_1,\ldots,dx_k),\] where only some of these increments may be nonzero. Conditional on \(Z=i\), the probability that \(T\) falls in this infinitesimal piece is \(dx_i\). Since the states of \(Z\) are equally likely, the unconditional probability of \(T\) falling in this piece is \[\frac{1}{k}\sum_i dx_i.\] Given that \(T\) lies in this piece, Bayes’ rule says that the posterior probability of \(Z=i\) is \[\frac{dx_i}{\sum_r dx_r}.\] Thus the contribution of this piece to \(\mathsf H(Z\mid T)\) is \[\frac{1}{k}\left(\sum_i dx_i\right) \mathsf H\left(\frac{dx_1}{\sum_r dx_r},\ldots, \frac{dx_k}{\sum_r dx_r}\right).\] On a straight piece where only one coordinate moves, this contribution is \(0\). On each two-coordinate endpoint arc, the total contribution is exactly \(I/k\), because the corresponding two-coordinate path entropy is the integral \(I\). There are \(k-1\) such arcs. Hence \[\mathsf H(Z\mid T)=\frac{k-1}{k}I.\] Consequently \[\mathsf I(Z;T)=\log_2 k-\frac{k-1}{k}I.\] Since \(D^{\mathrm{ent}}_{1/k}\) is the negative of the least possible mutual information among witnesses with \(h(Z,T)\le1/k\), this gives \[D^{\mathrm{ent}}_{1/k}\ge -\log_2 k+\frac{k-1}{k}I,\] as claimed. ◻
![Figure 5: Illustration of the monotone path \Gamma(t)=(F_1(t),F_2(t),F_3(t)) used in the proof of Theorem [thm:closed-bound-all-S] (in the k=3 case). The path stays inside the region \mathsf H_2(x)+\mathsf H_2(y)+\mathsf H_2(z)\leq 1 (whose intersection with the lower faces of the cube is shown in light blue) at all times. It is composed of four pieces: an initial straight segment, two distinct two-coordinate transitions staying on a face of the cube, and a final straight segment. The two coordinate transitions trace the same path on their respective faces as the pieces of the curve in Figure 3 between (\frac{1}{2},0) and (1,\frac{1}{2}) in the \sigma=\frac{1}{2} case.](/article/2607.11311/figures/monotone_path_3D.png "fig:")
We also need the following basic properties of \(D^{\mathrm{ent}}_\sigma\).
Lemma 6. The function \(\sigma\mapsto D^{\mathrm{ent}}_\sigma\) is finite, continuous, nondecreasing, and concave on \((0,1]\), with \(D^{\mathrm{ent}}_1=0\).
Proof. The function \(D^{\mathrm{ent}}\) is nondecreasing in \(\sigma\), because increasing \(\sigma\) relaxes the constraint \(h(Z,T)\le\sigma\).
To prove concavity, let \(0<\sigma_1,\sigma_2\le1\) and \(0\le\lambda\le1\). Choose admissible pairs \((Z_1,T)\) and \((Z_2,T)\) with \(h(Z_i,T)\le\sigma_i\). We may use the same uniform variable \(T\) for both witnesses by describing each witness through the conditional law of \(Z_i\) given \(T=t\).
Let \(B\) be independent of \(T\), with \[\mathbb{P}(B=1)=\lambda, \qquad \mathbb{P}(B=2)=1-\lambda.\] Conditional on \(B=i\) and \(T=t\), sample \(Z_i\) according to the conditional law of the \(i\)th witness. Set \(W=(B,Z_B)\). Then \[\mathsf I(W;T)=\lambda\mathsf I(Z_1;T)+(1-\lambda)\mathsf I(Z_2;T),\] and, for every threshold \(t\), \[\mathsf H(\mathbf{1}_{\{T\le t\}}\mid W) =\lambda\mathsf H(\mathbf{1}_{\{T\le t\}}\mid Z_1) +(1-\lambda)\mathsf H(\mathbf{1}_{\{T\le t\}}\mid Z_2).\] Therefore \[h(W,T)\le\lambda\sigma_1+(1-\lambda)\sigma_2.\] Taking infima over the two witnesses shows that \(-D^{\mathrm{ent}}_\sigma\) is convex, and thus \(D^{\mathrm{ent}}_\sigma\) is concave.
For finiteness, fix \(\sigma>0\) and choose an integer \(K\) with \(1/K\le\sigma\). Divide \([0,1]\) into \(K\) equal bins \[B_j=\left(\frac{j-1}{K},\frac{j}{K}\right],\qquad j=1,\ldots,K,\] and let \(Z\) be the bin containing \(T\). Given \(Z\), the threshold bit \(\mathbf{1}_{\{T\le t\}}\) is uncertain only when \(t\) lies in the same bin as \(T\); this occurs with probability \(1/K\). Hence \[h(Z,T)\le \frac{1}{K}\le\sigma.\] Also \(\mathsf I(Z;T)=\mathsf H(Z)=\log_2K<\infty\). Thus \(D^{\mathrm{ent}}_\sigma> -\infty\). Since mutual information is always nonnegative, we also have \(D^{\mathrm{ent}}_\sigma\le0\), so \(D^{\mathrm{ent}}_\sigma\) is finite.
Finally, \(D^{\mathrm{ent}}_1=0\): the constant witness gives \(D^{\mathrm{ent}}_1\ge0\), while nonnegativity of mutual information gives \(D^{\mathrm{ent}}_1\le0\). A finite concave function is continuous on the interior of its domain, and continuity at \(1\) follows from concavity together with the value \(D^{\mathrm{ent}}_1=0\). ◻
Proof of [thm:closed-bound-all-S]. If \(\sigma = 1\), both sides of the claimed inequality are \(0\). So assume \(0<\sigma<1\).
With \(k=\lfloor1/\sigma\rfloor\), we have \[\frac{1}{k+1}<\sigma\le\frac{1}{k}.\] The number \[\lambda=k(k+1)\sigma-k\] is exactly the coefficient for writing \(\sigma\) as a convex combination of the neighboring grid points: \[\sigma=\lambda\frac{1}{k}+(1-\lambda)\frac{1}{k+1}.\] By concavity of \(D^{\mathrm{ent}}\) and 5, \[\begin{align} D^{\mathrm{ent}}_\sigma &\ge \lambda D^{\mathrm{ent}}_{1/k}+(1-\lambda)D^{\mathrm{ent}}_{1/(k+1)} \\ &\ge \lambda\left(-\log_2 k+\frac{k-1}{k}I\right) +(1-\lambda)\left(-\log_2(k+1)+\frac{k}{k+1}I\right) \\ &=-\lambda\log_2 k-(1-\lambda)\log_2(k+1) +I\left(\lambda\frac{k-1}{k}+(1-\lambda)\frac{k}{k+1}\right). \end{align}\] The coefficient of \(I\) simplifies to \[\lambda\frac{k-1}{k}+(1-\lambda)\frac{k}{k+1} =1-\left(\lambda\frac{1}{k}+(1-\lambda)\frac{1}{k+1}\right) =1-\sigma.\] This proves the theorem. ◻
6 Computing a lower bound on \(2\sigma-D^{\mathrm{ent}}_\sigma\), and upper bounds on \(D^{\mathrm{ent}}_\sigma\)↩︎
In this section we explain how the lower bound on \[\gamma := \inf_{0<\sigma\le1}\{2\sigma-D^{\mathrm{ent}}_\sigma\} = \inf_{(Z,T)}\{\mathsf I(Z;T)+2h(Z,T)\}\] is computed. We note that this entails the lower bound of Theorem 2 (lower bound on \(\gamma\)), again by using the equivalence Theorem 1 and the algorithmic framework.
The right-hand side is an optimization over all admissible pairs \((Z,T)\), and is therefore infinite-dimensional. The key point is that the finite discretization below approximates the continuous problem with an explicit error bound.
Fix an integer \(K\ge2\), let \(Y\sim\operatorname{Unif}([K])\), and define \[\mathsf B_K(Z,Y) = \mathsf I(Z;Y) +2\max_{1\le k<K}\mathsf H(\mathbf{1}_{\{Y\le k\}}\mid Z).\] Let \[\gamma_K = \inf_{Y\sim\operatorname{Unif}([K])}\mathsf B_K(Z,Y),\] where the infimum is over all couplings of the auxiliary variable \(Z\) with the uniform variable \(Y\).
Lemma 7. For every \(K\ge2\), \[\gamma_K\le \gamma\le \gamma_K+2\mathsf H_2(1/K).\]
Proof. We first prove the lower bound \(\gamma\ge \gamma_K\). Let \((Z,T)\) be any admissible pair, and discretize \(T\) into \(K\) equal bins: \[Y=\min(K,\lceil KT\rceil),\] with the convention that \(Y=1\) when \(T=0\). Since \(T\) is uniform on \([0,1]\), the variable \(Y\) is uniform on \([K]\).
The variable \(Y\) is a function of \(T\), so by data processing, \[\mathsf I(Z;Y)\le \mathsf I(Z;T).\] Also, for each \(1\le k<K\), \[\mathbf{1}_{\{Y\le k\}}=\mathbf{1}_{\{T\le k/K\}},\] and therefore \[\mathsf H(\mathbf{1}_{\{Y\le k\}}\mid Z) \le \sup_{0\le t\le1}\mathsf H(\mathbf{1}_{\{T\le t\}}\mid Z) =h(Z,T).\] Thus \[\mathsf B_K(Z,Y) \le \mathsf I(Z;T)+2h(Z,T).\] Since \(\gamma_K\) is the infimum of \(\mathsf B_K\) over all finite \(K\)-bin witnesses, \(\mathsf B_K(Z,Y)\ge \gamma_K\). Hence \[\mathsf I(Z;T)+2h(Z,T)\ge \gamma_K.\] Taking the infimum over all admissible \((Z,T)\) gives \(\gamma\ge \gamma_K\).
We now prove the upper bound \(\gamma\le \gamma_K+2\mathsf H_2(1/K)\). Let \((Z,Y)\) be a witness for the finite version with \(Y\sim\operatorname{Unif}([K])\). Turn it into a continuous witness by spreading each bin uniformly: let \(R\sim\operatorname{Unif}[0,1]\) be independent of \((Z,Y)\) and put \[T=\frac{Y-1+R}{K}.\] Then \(T\sim\operatorname{Unif}[0,1]\). Also, \(T\) almost surely determines \(Y\), and the extra within-bin randomness \(R\) is independent of \(Z\) once \(Y\) is known. Hence \[\mathsf I(Z;T)=\mathsf I(Z;Y).\] It remains to compare threshold entropies. Fix a threshold \(t\in[0,1]\), and let \(\ell\) be the bin containing \(t\). Put \[A=\mathbf{1}_{\{Y\le \ell-1\}}, \qquad W=\mathbf{1}_{\{T\le t\}}.\] The bits \(A\) and \(W\) can differ only when \(Y=\ell\), an event of probability \(1/K\). Therefore \[\mathbb{P}(A\ne W)\le 1/K.\] Since \(W\) is determined by \(A\) together with the error bit \(A\oplus W\), \[\begin{align} \mathsf H(W\mid Z) &\le \mathsf H(A\mid Z)+\mathsf H(A\oplus W) \\ &\le \mathsf H(A\mid Z)+\mathsf H_2(1/K). \end{align}\] Here we used that \(\mathsf H_2\) is increasing on \([0,1/2]\) and \(K\ge2\). Taking the supremum over \(t\) gives \[h(Z,T) \le \max_{1\le k<K}\mathsf H(\mathbf{1}_{\{Y\le k\}}\mid Z) +\mathsf H_2(1/K).\] Thus the continuous witness obtained from \((Z,Y)\) has objective at most \[\mathsf I(Z;Y) +2\max_{1\le k<K}\mathsf H(\mathbf{1}_{\{Y\le k\}}\mid Z) +2\mathsf H_2(1/K) =\mathsf B_K(Z,Y)+2\mathsf H_2(1/K).\] Taking the infimum over finite witnesses \((Z,Y)\) proves \(\gamma\le \gamma_K+2\mathsf H_2(1/K)\). ◻
We now describe the finite certificate used to lower bound \(\gamma_K\). Let \[\triangle_K=\bigl\{r=(r_1,\ldots,r_K)\in[0,1]^K: \sum_{j=1}^K r_j=1\bigr\}.\] For \(r\in\triangle_K\), let \[C_k(r)=\sum_{j=1}^k r_j, \qquad 1\le k<K.\] We use the convention \(0\log_2 0=0\), so that \(r_j\log_2(Kr_j)\) is interpreted as \(0\) when \(r_j=0\).
Proposition 6. Suppose there exist numbers \(\lambda_1,\ldots,\lambda_{K-1}\ge0\), a vector \(a=(a_1,\ldots,a_K)\in\mathbb{R}^K\), and a number \(E\) such that \[\label{eq:finite-dual-load} \sum_{k=1}^{K-1}\lambda_k\le2\qquad{(1)}\] and, for every \(r\in\triangle_K\), \[\label{eq:finite-dual-simplex-cert} \sum_{j=1}^K r_j\log_2(Kr_j) +\sum_{k=1}^{K-1}\lambda_k\mathsf H_2(C_k(r)) \ge E+\sum_{j=1}^K a_j(r_j-1/K).\qquad{(2)}\] Then \(\gamma_K\ge E\). Consequently \(\gamma\ge E\).
Proof. Let \((Z,Y)\) be an arbitrary coupling with \(Y\sim\operatorname{Unif}([K])\). Given \(Z\), let \[r_j(Z)=\mathbb{P}(Y=j\mid Z), \qquad j=1,\ldots,K.\] This is a random point of \(\triangle_K\). Since \(Y\) is uniform on \([K]\), \[\mathbb{E}\left[r_j(Z)\right]=1/K \qquad\text{for every }j.\] Average ?? over \(Z\). The affine term on the r.h.s.vanishes, and we obtain \[\mathbb{E}\left[\sum_{j=1}^K r_j(Z)\log_2(Kr_j(Z))\right] +\sum_{k=1}^{K-1}\lambda_k \mathbb{E}\left[\mathsf H_2(C_k(r(Z)))\right] \ge E.\] The first term is the mutual information, written explicitly as \[\mathsf I(Z;Y) =\mathsf H(Y)-\mathsf H(Y\mid Z) =\mathbb{E}\left[\sum_{j=1}^K r_j(Z)\log_2(Kr_j(Z))\right].\] Also, \[C_k(r(Z))=\mathbb{P}(Y\le k\mid Z),\] so \[\mathbb{E}\left[\mathsf H_2(C_k(r(Z)))\right] =\mathsf H(\mathbf{1}_{\{Y\le k\}}\mid Z).\] Thus \[\mathsf I(Z;Y) +\sum_{k=1}^{K-1}\lambda_k \mathsf H(\mathbf{1}_{\{Y\le k\}}\mid Z) \ge E.\] By ?? , \[\sum_{k=1}^{K-1}\lambda_k \mathsf H(\mathbf{1}_{\{Y\le k\}}\mid Z) \le 2\max_{1\le k<K}\mathsf H(\mathbf{1}_{\{Y\le k\}}\mid Z).\] Therefore \(\mathsf B_K(Z,Y)\ge E\). Since \((Z,Y)\) was arbitrary, \(\gamma_K\ge E\). The last statement follows from 7. ◻
One can show via a duality argument that for every \(\epsilon\), there is a \((\lambda, a)\) certificate with value at least \(\gamma_K-\epsilon\). We will however not use this here, and thus leave out the proof.
Given a candidate certificate, it remains to verify ?? . Although this is an inequality on the \((K-1)\)-dimensional simplex, its structure allows its verification to be reduced to a one-dimensional dynamic program. Set \[s_0=0, \qquad s_j=C_j(r)\quad(1\le j<K), \qquad s_K=1.\] Then \(r_j=s_j-s_{j-1}\) and \[0=s_0\le s_1\le\cdots\le s_K=1.\] Define \[\ell_j(x)=x\log_2(Kx)-a_jx, \qquad 0\le x\le1.\] After substituting \(r_j=s_j-s_{j-1}\), the certificate inequality is equivalent to \[\sum_{j=1}^K \ell_j(s_j-s_{j-1}) +\sum_{k=1}^{K-1}\lambda_k\mathsf H_2(s_k) +\frac{1}{K}\sum_{j=1}^K a_j -E \ge0\] for every nondecreasing sequence \((s_j)_{j=0}^K\) with \(s_0=0\) and \(s_K=1\).
Now define \[V_0(0)=0, \qquad V_0(x)=+\infty\quad(x\ne0),\] and, for \(1\le j<K\), \[V_j(x)=\lambda_j\mathsf H_2(x)+\inf_{0\le y\le x} \{V_{j-1}(y)+\ell_j(x-y)\}.\] The final step is \[V_K(1)=\inf_{0\le y\le1}\{V_{K-1}(y)+\ell_K(1-y)\}.\] Unwinding the recursion gives \[\begin{align} &\inf_{r\in\triangle_K} \biggl[ \sum_{j=1}^K r_j\log_2(Kr_j) +\sum_{k=1}^{K-1}\lambda_k\mathsf H_2(C_k(r)) -\sum_{j=1}^K a_j(r_j-1/K) \biggr] \\ & =V_K(1)+\frac{1}{K}\sum_{j=1}^K a_j. \end{align}\] Thus, if \(V_K(1)+\frac{1}{K}\sum_{j=1}^K a_j\) is at least \(E\), then ?? holds and 6 proves \(\gamma\ge E\).
The numerical computation thus has two stages. First, we search for good coefficients \((\lambda,a)\) to maximize \(V_K(1)+\frac{1}{K}\sum_{j=1}^K a_j\). In theory, a certificate can be computed yielding the exact infimum up to some arbitrarily chosen precision. However, the computational cost is prohibitive, so we resort to looking for \((\lambda,a)\) heuristically.
In the second stage (the actual proof), the dynamic program is verified, pessimistically rounding intermediate values to ensure the final bound is valid. To run the dynamic program, the continuous variable \(x\in [0,1]\) is discretized into \(M\) discrete bins (for some large value of \(M\)) and the worst-case values inside the bins are bounded using the values at the endpoints and the concavity/convexity of the functions involved. Larger values of \(M\) result in more computation, but smaller loss in this process and thus a better final bound.
The certificate we use for \(K=400\) and \(M=300\;000\) gives the following.
Theorem 7. \[\inf_{0<\sigma\le1}\{2\sigma-D^{\mathrm{ent}}_\sigma\} = \gamma> E_{400} > 1.669845.\] Equivalently, \[\inf_{1<S\le2}\frac{S^2}{D_S}> 2^{1.669845} > 3.1818.\]
The finite-continuous comparison in 7 also shows that the finite computation converges to the continuous optimum: indeed \(\gamma_K\le \gamma\le \gamma_K+2\mathsf H_2(1/K)\), and the error term tends to zero. In theory, the described approach can thus be used to compute a bound which is tight up to an arbitrarily chosen precision. However, the coefficients \((\lambda,a)\) are expensive to optimize exactly, and this explicit error term is a worst-case bound and decreases rather slowly. For the upper side of the final numerical interval it is therefore better to use the explicit witnesses from the previous section. Since 4 gives \(D^{\mathrm{ent}}_\sigma\ge a_\sigma-1\) for \(1/2\le\sigma\le1\), we have \[\gamma =\inf_{0<\sigma\le1}\{2\sigma-D^{\mathrm{ent}}_\sigma\} \le \inf_{1/2\le\sigma\le1}\{2\sigma-a_\sigma+1\}.\]
The right-hand side is at most \[1.669858, \qquad 2^{1.669858}<3.1818328,\] attained near \(\sigma=0.515617\). We conjecture that the two quantities coincide exactly, that is, \[\inf_{0<\sigma\le1}\{2\sigma-D^{\mathrm{ent}}_\sigma\} =\inf_{1/2\le\sigma\le1}\{2\sigma-a_\sigma+1\}.\]
Computing upper bounds for \(D^{\mathrm{ent}}_\sigma\)
The lower bound of \(2\sigma-D^{\mathrm{ent}}_\sigma > 1.669845\) from the previous theorem immediately gives the following upper bound on \(D^{\mathrm{ent}}_\sigma\). \[D^{\mathrm{ent}}_\sigma \leq 2\sigma-1.669845.\] This is essentially tight near \(\sigma \approx 0.515617\). However, this bound gets worse the further we are from this value of \(\sigma\).
The lower bound on \(1/D_S\) given in [11] (where this quantity is denoted as \(P_S\)), when translated to our setting using Theorem 1, gives the following.
Proposition 8 ([11]). For every \(0<\sigma\leq 1\), and every integer \(k \geq 0\), \[D^{\mathrm{ent}}_\sigma \leq k\sigma-\log_2(k+1).\]
This gives better bounds when \(\sigma\) is near \(0\) or \(1\), but is overall very loose.
One way to get better upper bounds of this nature is to essentially look for lower bounds on \(\Lambda\sigma-D^{\mathrm{ent}}_\sigma\), for different values of \(\Lambda > 0\). This can be done by trivial modifications of the method outlined above (in short, replace the constraint ?? with \(\sum_{k=1}^{K-1}\lambda_k\leq \Lambda\)). A lower bound of \(\mu_\Lambda\) on this value then gives \[D^{\mathrm{ent}}_\sigma \leq \Lambda\sigma-\mu_\Lambda.\] Choosing \(\Lambda\) smaller makes the resulting bound better for larger values of \(\sigma\), while choosing a larger value for \(\Lambda\) favors good bounds for smaller \(\sigma\).
Below are some recorded bounds for some different values of \(\Lambda\), computed with \(K=100\) and \(M=50\;000\) (except for the case \(\Lambda=2\) which was computed earlier).4
Proposition 9. We have \(D^{\mathrm{ent}}_\sigma \leq \Lambda\sigma-\mu_\Lambda\), for each of the following \((\Lambda,\mu_\Lambda)\) pairs: \[\begin{align} & (\Lambda=1.1, \mu_\Lambda=1.0925), & & (\Lambda=1.2, \mu_\Lambda=1.1778), & & (\Lambda=1.3, \mu_\Lambda=1.2554), & & (\Lambda=1.6, \mu_\Lambda=1.4507), \\ & (\Lambda=2,\mu_\Lambda=1.6698), & & (\Lambda=2.5,\mu_\Lambda=1.9189), & & (\Lambda=3,\mu_\Lambda=2.1276), & & (\Lambda=4,\mu_\Lambda=2.4737), \\ & (\Lambda=5,\mu_\Lambda=2.7515), & & (\Lambda=7,\mu_\Lambda=3.1855), & & (\Lambda=10,\mu_\Lambda=3.6605), & & (\Lambda=13,\mu_\Lambda=4.0160), \\ & (\Lambda=16,\mu_\Lambda=4.3001), & & (\Lambda=20,\mu_\Lambda=4.6072), & & (\Lambda=30,\mu_\Lambda=5.1659), & & (\Lambda=60,\mu_\Lambda=6.0930). \end{align}\]
7 An application to fibres in the Boolean lattice: Proof of Theorem [thm:fibre]↩︎
Here we give another consequence of our bounds on \(D^{\mathrm{ent}}_\sigma\), beyond the algorithmic applications to TSP and other permutation problems. This proves Theorem [thm:fibre].
Let \(B_n = 2^{[n]}\) denote the \(n\)-dimensional Boolean lattice, with the sets composing them being compared by inclusion. Recall that an antichain of \(B_n\) is a subfamily of \(B_n\) consisting of sets which are pairwise incomparable. An antichain is maximal if it cannot be extended to a larger antichain by adding a set. A fibre of \(B_n\) is a family \(\mathcal{A}\subseteq B_n\) that intersects every maximal antichain.
We let \(\mathrm{MF}_n\) denote the size of a smallest fibre in \(B_n\). It is easy to show that \(\mathrm{MF}_n \leq O(2^{n/2})\): consider the family of all sets comparable to any given set of the middle layer of \(B_n\); this is a fibre and has size \(O(2^{n/2})\).
Lonc and Rival [16] conjectured that this is tight. Duffus, Sands and Winkler [14] made some progress towards that conjecture, by showing \(\mathrm{MF}_n \geq \Omega(1.25^{n})\). This was later improved by Łuczak to \(\mathrm{MF}_n \geq \Omega(2^{n/3})\), as reported by Duffus and Sands [15]. There has been no further progress since.
We exploit our bounds on \(D^{\mathrm{ent}}_\sigma\) to improve on this lower bound, showing the following.
For the proof, we need the following additional fact from [14]: every fibre of \(B_n\) contains at least \(n!/2^{n-1}\) maximal chains.
Proof. Fix \(\sigma\), and assume \(D^\ell_\sigma \leq -1\) (equivalently, \(D_{2^\sigma} \leq \frac{1}{2}\)). Let \(\mathcal{A}\) be a fibre of \(B_n\). Since \(\mathcal{A}\) contains at least \(n!/2^{n-1}\) maximal chains, we have \[D(\mathcal{A}) \geq \frac{1}{2}2^{1/n} > \frac{1}{2}.\] Then if \(S(\mathcal{A}) \leq 2^{\sigma}\), by definition of \(D_{2^\sigma}\) we would have \(D(\mathcal{A}) \leq D_{2^\sigma} \leq \frac{1}{2}\), a contradiction.
Thus \(S(\mathcal{A}) \geq 2^{\sigma}\), i.e.\(|\mathcal{A}|\geq 2^{\sigma n}\).
For the second statement, it suffices to note that taking \(\Lambda=3\) in 9 gives \[D^\ell_\sigma = D^{\mathrm{ent}}_\sigma \leq 3\sigma-2.1276.\] Thus, \(D^\ell_\sigma \leq -1\) for any \(\sigma \leq \frac{2.1276-1}{3} = 0.37586\ldots\), and the statement follows. ◻
Note that this approach cannot be used to prove bounds above \(2^{0.38531n}\), as we know from Theorem [thm:closed-bound-all-S] that \(D^{\mathrm{ent}}_{0.38531} > -1\). Different ideas would thus be needed to prove the conjecture of Lonc and Rival.
8 Conclusion↩︎
We gave an essentially tight tradeoff between the normalized size and the normalized chain-density of set systems. This provides a fairly complete answer to the extremal combinatorics question raised by Johnson, Leader, and Russell, and implies an improved space-time tradeoff for TSP (and related permutation problems) in the recently introduced framework of [10], [11].
The special case of set systems arising as the family of downsets of a partial order (here, the maximal chains correspond to linear extensions of the same partial order) remains open; while the barrier side of our bounds still hold in this setting, our set system constructions are not of this restricted form. In this setting, the construction of Koivisto and Parviainen [9] was improved by Ameli, Nederlof, and Wang [10]. Their construction remains the best to date, leaving the gap \(3.1818 \leq \gamma \leq 3.7493\) in the partial order case. For regular bipartite posets, [10] show a lower bound of 3.6, implying a clear separation of this special case from the general set systems attaining an optimal tradeoff.
Solving the TSP in time \(c^n\) for \(c<2\), or providing some argument for why this would not be possible, remains, as one of the landmark questions of computer science, entirely open. Likewise, the question of whether a polynomial-space algorithm exists with running time \(c^n\) for \(c<4\) remains unsolved. More modestly, obtaining an algorithm that improves our space-time tradeoff \(\mathcal{T}\cdot \mathcal{S}\approx 3.1819\) via different techniques remains an interesting research direction.
References↩︎
\(^1\)Email: andoni@cs.columbia.edu., hantao.yu@columbia.edu↩︎
\(^2\)Email: justin.dallant@tu-dresden.de, laszlo.kozma@tu-dresden.de↩︎
TSP asks for a permutation of \(n\) cities, minimizing the sum of pairwise distances between consecutive cities in the permutation. The mentioned results hold for arbitrary distance functions, but no better bounds are known even under a metric assumption. The \(\mathcal{O}^*(\cdot)\) notation is used to suppress polynomial factors.↩︎
The certificates, as well as the code used to verify them, will be made available on the author’s GitHub repository.↩︎