The logarithmic cost of componentwise constraints
in finite de Finetti approximation

Abstract

We study relative-entropy approximation of $k$ -site marginals of exchangeable $n$ -site laws on a $d$ -symbol alphabet by mixtures of iid laws. Each one-site factor must lie in a prescribed affine slice of the probability simplex. We assume that, under the exchangeable law, each site’s conditional distribution given the other sites lies in this slice. For $k\leq n/2$ , conditioning gives feasible error $O(k^{2}\log d/n)$ , compared with the unrestricted guarantee $O(k^{2}/n)$ . We prove that the logarithmic factor is necessary for a bound uniform over affine slices. For even $n$ , we construct examples with $d=\Theta(n^{8})$ and $k=\lfloor n^{1/4}\rfloor$ whose optimal feasible error is $\Theta(\log n/\sqrt{n})$ . Thus the logarithmic separation persists while the error vanishes. The construction places perfect nonsignalling finite-field CHSH boxes on a random perfect matching. An internal matching edge forces an event that is much rarer under every feasible product mixture; its likelihood ratio supplies the logarithmic factor. For the affine slice specifying an input marginal of support size $s$ , a response-table construction gives $O(sk^{2}/n)$ error for $k\leq\frac{1}{2}\lfloor n/s\rfloor$ , independently of output-alphabet sizes.

Note. This paper was generated entirely by AI, including MiMo, using an automated research pipeline developed by Chenghua Liu and Hanyu Li.

1 Introduction

Suppose a one-site law describes a channel with a prescribed input marginal: it has the form $q(x,a)=\pi(x)W(a\mid x)$ , and only the channel $W$ may vary. A de Finetti approximation is useful here only if each product component has the same input law $\pi$ . The usual empirical-measure construction does not have this property. If $\pi$ is uniform on $r>n$ inputs, an empirical law formed from $n$ sites has at most $n$ input values in its support, so every realised empirical law violates the constraint. Averaging over empirical laws does not repair the individual channels. This elementary support mismatch already prevents direct use of the standard finite de Finetti approximation.

More generally, we require the one-site factors of an iid mixture to lie in an affine slice $F$ of the probability simplex. Such requirements arise when de Finetti theorems are used to round symmetric extensions to feasible points in constrained optimisation [7, 10]. The extension must satisfy more than a one-site constraint: we impose its lifted version, which says that a site’s conditional law remains in $F$ after observing the other sites. Conditioning then gives a natural way to construct feasible mixture components. For the marginal on $k$ retained sites of an exchangeable $n$ -site law, the conditional-information proof of Berta, Gavalakis, and Kontoyiannis [1] yields error at most $k(k-1)\log d/[2(n-k+1)]$ on a $d$ -symbol alphabet. By contrast, without component constraints the empirical construction gives

\log\frac{n^{k}}{(n)_{k}}\leq\frac{k(k-1)}{2(n-k+1)},

where $(n)_{k}=n(n-1)\cdots(n-k+1)$ is the falling factorial. This bound is independent of $d$ [2, 3]. Is the entropy cost $\log d$ inherent in keeping the components feasible, or could another construction retain the unrestricted rate?

We show that the logarithmic factor is necessary. The obstruction already occurs for a prescribed uniform input marginal on $\mathbb{F}_{r}$ , with one-site alphabet $\mathbb{F}_{r}\times\mathbb{F}_{r}$ and $d=r^{2}$ . Theorem 3.1 gives an explicit lower bound of order $k(k-1)\log d/(n-k+1)$ for even $n$ , $2\leq k\leq\sqrt{n}$ , and primes $r$ growing sufficiently quickly with $n$ . A concrete choice makes the separation particularly transparent: take $r=\Theta(n^{4})$ , with the constant specified by the theorem, and $k=\lfloor n^{1/4}\rfloor$ . Then

d=\Theta(n^{8}),\qquad\text{unrestricted error}=O(n^{-1/2}),\qquad\text{optimal feasible error}=\Theta(\log n/\sqrt{n}).

Feasibility thus forces an error larger than the unrestricted guarantee by at least a logarithmic factor, even though the constrained optimum tends to zero. This gives a statistical obstruction to every uniform $o(\log d)$ replacement in the conditioning bound, without a computational hardness assumption.

The construction hides correlations on a uniformly random perfect matching of the $n$ sites. At each edge we use a pair of uniform inputs $x,y\in\mathbb{F}_{r}$ and outputs satisfying $a+b=xy$ . Each input remains uniform after the other endpoint is observed, so the matching law satisfies the lifted constraint. In a $k$ -site marginal, an internal matching edge occurs with probability of order $k^{2}/n$ and forces at least one pair to satisfy the game equation. Two feasible independent sites, however, satisfy it with probability only $O(r^{-1/2})$ , by an elementary point-line incidence count. Hence the probability that any pair wins is at most $O(k^{2}/\sqrt{r})$ , uniformly over all feasible iid mixtures. With $r=\Theta(n^{4})$ , this is smaller by a factor of order $n$ than the probability forced by a matching edge. Binary relative-entropy data processing charges the event’s probability times the logarithm of this ratio, producing $k^{2}\log n/n$ . The finite-field CHSH game and its incidence interpretation are due to earlier work [5]; the matching extension makes their separation compatible with exchangeability at an arbitrarily larger number of sites.

There is a useful converse lesson for the channel example. If the input law has support size $s$ , one can use $s$ sites to record one full table of possible outputs, one for each input. An $n$ -site symmetric extension provides $M=\lfloor n/s\rfloor$ such rows. Sampling the rows with replacement gives feasible iid components, while sampling without replacement recovers the required marginal. Adapting the construction of Christandl and Toner [4] to relative entropy gives error at most $\log(M^{k}/(M)_{k})$ , simultaneously for all $k\leq M$ . For $k\leq M/2$ this is $O(sk^{2}/n)$ , with no output-alphabet cost. The lower-bound examples have $s=r>n$ ; their growing input support prevents even one complete table from fitting inside the extension.

The conditioning method is closely related to the quantum and nonsignalling de Finetti arguments of Brandão and Harrow [6] and the constrained quantum results of Berta et al. [7]. Other constrained reductions provide domination inequalities [8, 9], and fixed-point constraints lead to rates governed by the structure of channel algebras [11]. Our lower bound concerns relative entropy to componentwise-feasible mixtures. Its witness uses a rare event with a large likelihood ratio, so conclusions for total variation or optimisation complexity require additional arguments.

2 Feasible mixtures and the conditioning bound

Let $\mathcal{Z}$ be a finite alphabet, with $|\mathcal{Z}|=d$ , and write $\Delta(\mathcal{Z})$ for its probability simplex. Given a linear map $\Gamma:\mathbb{R}^{\mathcal{Z}}\to\mathbb{R}^{t}$ and a vector $\eta\in\mathbb{R}^{t}$ , consider the nonempty affine slice

F=F_{\Gamma,\eta}:=\{q\in\Delta(\mathcal{Z}):\Gamma(q)=\eta\}.

For an exchangeable law $P_{n}$ on $\mathcal{Z}^{n}$ , $n\geq 1$ , let $P_{j}$ denote its $j$ -site marginal, with $P_{0}=1$ . We impose the lifted affine constraint

(\id^{\otimes(n-1)}\otimes\Gamma)(P_{n})=P_{n-1}\otimes\eta.

(CP)

Exchangeability gives the corresponding identity at every coordinate. This is stronger than the one-site condition $\Gamma(P_{1})=\eta$ : it requires feasibility of the conditional law of a site after all other sites have been observed. We call $(\Gamma,\eta,P_{n})$ admissible when these conditions hold.

For a Borel probability measure $\mu$ on $F$ , define

M_{k,\mu}:=\int_{F}q^{\otimes k}\,\,\mathrm{d}\mu(q),\qquad\varepsilon_{\mathrm{con}}(P_{n},F;k):=\inf_{\mu\in\mathcal{P}(F)}D(P_{k}\|M_{k,\mu}),\quad 1\leq k\leq n,

where $\mathcal{P}(F)$ denotes the set of such measures. All logarithms are natural, and

D(P\|Q):=\sum_{z:P(z)>0}P(z)\log\frac{P(z)}{Q(z)},

with value $+\infty$ if $P$ is not absolutely continuous with respect to $Q$ . The worst-case constrained error is

B_{\mathrm{con}}(d,n,k):=\sup_{(\Gamma,\eta,P_{n})\ \mathrm{admissible}}\varepsilon_{\mathrm{con}}(P_{n},F_{\Gamma,\eta};k),

where the supremum includes all nonempty affine slices of a $d$ -symbol simplex. The restriction $\mu\in\mathcal{P}(F)$ applies to every factor $q$ in the mixture, rather than only to the averaged one-site law $\int q\,\,\mathrm{d}\mu(q)$ .

Without the support restriction on $\mu$ , there is an alphabet-independent bound

\inf_{\mu\in\mathcal{P}(\Delta(\mathcal{Z}))}D(P_{k}\|M_{k,\mu})\leq L(n,k):=\log\frac{n^{k}}{(n)_{k}},\qquad(n)_{k}:=n(n-1)\cdots(n-k+1).

(1)

Song, Attiah, and Yu [2] proved this bound and its worst-case sharpness; Gavalakis, Johnson, and Kontoyiannis [3] placed it in a general sampling-without-replacement framework. In particular, $L(n,k)\leq k(k-1)/[2(n-k+1)]$ . The empirical-measure mixture underlying this bound need not be supported on $F$ .

A different construction conditions on a suitably chosen block of coordinates and mixes the resulting one-site posterior laws. The entropy estimate of Berta, Gavalakis, and Kontoyiannis [1], applied to posterior laws that remain in $F$ under (CP), gives

B_{\mathrm{con}}(d,n,k)\leq\frac{k(k-1)}{2(n-k+1)}\log d,\qquad 1\leq k<n.

(2)

Compatibility with linear constraints is discussed in [1]. The following proof tracks the posterior laws explicitly. Its entropy average is also where the factor $\log d$ enters; the lower bound will show that a uniform argument cannot remove this factor.

Lemma 2.1 (Posterior preservation).

Suppose $P_{n}$ is exchangeable and satisfies (CP). For every $i\in[n]:=\{1,\ldots,n\}$ and every $I\subseteq[n]\setminus\{i\}$ ,

\Gamma(P_{Z_{i}\mid Z_{I}})=\eta\qquad\text{almost surely}.

In particular, all these posterior laws belong to $F$ .

Proof.

Move the constrained coordinate in (CP) to position $i$ by exchangeability, and sum over all coordinates outside $I\cup\{i\}$ . For every value $z_{I}$ , the resulting identity is

\Gamma\bigl(P(Z_{I}=z_{I},Z_{i}=\cdot)\bigr)=P(Z_{I}=z_{I})\eta.

Whenever $P(Z_{I}=z_{I})>0$ , division by this probability proves the claim. ∎

Proposition 2.2 (Conditioning upper bound).

For every admissible $(\Gamma,\eta,P_{n})$ and every $1\leq k<n$ , there is $\mu\in\mathcal{P}(F)$ such that

D(P_{k}\|M_{k,\mu})\leq\frac{k(k-1)}{2(n-k+1)}\log d.

(3)

Proof.

We give the conditioning argument of [1], keeping track of its support. Write $Z_{a}^{b}=(Z_{a},\ldots,Z_{b})$ , with an empty tuple when $a>b$ . Let $H$ denote Shannon entropy and let $I(U;V\mid W)=H(U\mid W)-H(U\mid V,W)$ denote conditional mutual information. For $k\leq\ell\leq n$ and $1\leq i\leq k$ , exchangeability gives

I(Z_{1}^{i-1};Z_{i}\mid Z_{k+1}^{\ell})=I(Z_{1}^{i-1};Z_{\ell}\mid Z_{k}^{\ell-1}).

Indeed, both expressions involve the same first $i-1$ coordinates, one distinguished additional coordinate, and $\ell-k$ conditioning coordinates, all distinct. Summing over $\ell$ and using the chain rule,

	$\displaystyle\sum_{\ell=k}^{n}\sum_{i=1}^{k}I(Z_{1}^{i-1};Z_{i}\mid Z_{k+1}^{\ell})$	$\displaystyle=\sum_{i=1}^{k}I(Z_{1}^{i-1};Z_{k}^{n})$
		$\displaystyle\leq\sum_{i=1}^{k}H(Z_{1}^{i-1})\leq\frac{k(k-1)}{2}\log d.$		(4)

Choose $\ell_{*}\in\{k,\ldots,n\}$ for which the inner sum is at most its average, and set $Y=Z_{k+1}^{\ell_{*}}$ . Conditional on $Y$ , the first $k$ coordinates have a common one-site law $q_{Y}=P_{Z_{1}\mid Y}$ . Let $\mu$ be the law of $q_{Y}$ . The chain rule for relative entropy and joint convexity give

	$\displaystyle D(P_{k}\\|M_{k,\mu})$	$\displaystyle\leq\mathbb{E}_{Y}D(P_{Z_{1}^{k}\mid Y}\\|q_{Y}^{\otimes k})$
		$\displaystyle=\sum_{i=1}^{k}I(Z_{1}^{i-1};Z_{i}\mid Y)$
		$\displaystyle\leq\frac{k(k-1)}{2(n-k+1)}\log d.$

Finally, Lemma 2.1 gives $q_{Y}\in F$ almost surely, so this mixing measure is feasible. ∎

A direct repair of each empirical law can lose information that the mixture never needed to preserve. For example, let $d\geq n$ , $F=\{u_{d}\}$ , and $P_{n}=u_{d}^{\otimes n}$ . The optimal feasible approximation is exact. On a sample with $n$ distinct symbols, however, its empirical law $\widehat{q}$ satisfies

D(\widehat{q}\|u_{d})=\log(d/n).

Thus a proof that charges this repair cost for individual components can pay a positive error on an iid input. Posterior conditioning avoids that cost in this example: every posterior is already $u_{d}$ . Establishing a lower bound therefore requires a law that is separated from all feasible mixtures, not merely from repaired empirical components.

3 The random-matching lower bound

The lower bound uses the slice of laws with a fixed uniform input marginal. Let $\mathbb{F}_{r}$ be the field with $r$ elements, let $u_{r}$ be its uniform law, and write $X$ for the first coordinate of $\mathcal{Z}=\mathbb{F}_{r}\times\mathbb{F}_{r}$ . The parameter $\theta$ measures how much of the game-value separation remains after accounting for the probability that two observed sites are matched together.

Theorem 3.1 (Logarithmic alphabet-size lower bound).

Fix $0<\theta<1/2$ . Let $n\geq 6$ be even, and let $r$ be a prime such that

r^{1/2-\theta}\geq 2e(n-1).

On the alphabet $\mathcal{Z}=\mathbb{F}_{r}\times\mathbb{F}_{r}$ , of size $d=r^{2}$ , set

F:=\{q\in\Delta(\mathcal{Z}):q_{X}=u_{r}\}.

There is an exchangeable law $P_{n}$ satisfying (CP) for this fixed-input-marginal constraint such that, for every integer $2\leq k\leq\sqrt{n}$ and every $\mu\in\mathcal{P}(F)$ ,

D(P_{k}\|M_{k,\mu})\geq\frac{3\theta\,k(k-1)\log d}{16(n-1)}\geq\frac{3\theta}{32}\,\frac{k(k-1)\log d}{n-k+1}.

(5)

For $\theta=1/4$ , the second lower bound has constant $3/128$ and requires $r\geq[2e(n-1)]^{4}$ . Comparison with (2) already gives matching rates in this range. To see how these rates interact when the error is small, take a prime $r$ within a constant factor of this threshold and $k=\lfloor n^{1/4}\rfloor$ : the upper and lower bounds are both of order $\log n/\sqrt{n}$ . We give the general polynomial-alphabet sequences after the proof and then improve their exponent using the stronger prime-field game bound of [5].

3.1 A matching extension that preserves the constraint

The construction needs an edge law with two properties: a pair drawn from it must always win the game, and revealing one endpoint must leave the other input uniform. The first creates the separating event; the second allows the edge to be placed inside an admissible extension. Write $z=(x,a)\in\mathcal{Z}=\mathbb{F}_{r}\times\mathbb{F}_{r}$ . The linear map and target vector defining the slice in Theorem 3.1 are

(\Gamma q)(x)=\sum_{a\in\mathbb{F}_{r}}q(x,a),\qquad\eta=u_{r}.

Define the symmetric two-site law

R\bigl((x,a),(x^{\prime},b)\bigr):=r^{-3}\mathbf{1}\{a+b=xx^{\prime}\}.

(6)

There are $r^{3}$ satisfying quadruples, so $R$ is normalized, and both one-site marginals are uniform on $\mathcal{Z}$ . For every $(x,a)$ and $x^{\prime}$ , there is exactly one admissible $b$ , whence

\sum_{b}R\bigl((x,a),(x^{\prime},b)\bigr)=r^{-3}=R_{1}(x,a)u_{r}(x^{\prime}).

(7)

Thus the second input is uniform and independent of the entire first site; the symmetric identity holds at the other endpoint. Equivalently, $R$ is the joint law of independent uniform inputs and a perfect nonsignalling $\mathrm{CHSH}_{r}$ box. No quantum realization is required.

Let $\mathsf{M}$ be a uniformly random perfect matching of $[n]$ . Conditional on $\mathsf{M}$ , place an independent copy of $R$ on each edge, and define

P_{n}:=\mathbb{E}_{\mathsf{M}}\bigotimes_{\{i,j\}\in\mathsf{M}}R_{ij}.

(8)

A matching makes each site interact with only one partner. Randomising the matching hides that partner and restores permutation symmetry, while the linear conditional-input identity survives the average. In particular, we choose the extension once, before specifying $k$ .

Proposition 3.2 (Admissibility of the matching law).

The law $P_{n}$ in (8) is exchangeable and satisfies (CP) for $F=\{q:q_{X}=u_{r}\}$ .

Proof.

The uniform law on perfect matchings is permutation invariant, and $R$ is symmetric under exchange of its endpoints. Hence $P_{n}$ is exchangeable.

Fix a matching $\mathsf{M}$ , let $j$ be the partner of coordinate $n$ , and denote the associated product law by $P_{n}^{\mathsf{M}}$ . Applying $\Gamma$ at coordinate $n$ , identity (7) replaces $R_{j,n}$ by its marginal at $j$ , tensored with $u_{r}$ . All other edge factors are unchanged. Therefore

(\id^{\otimes(n-1)}\otimes\Gamma)(P_{n}^{\mathsf{M}})=(P_{n}^{\mathsf{M}})_{[n-1]}\otimes u_{r}.

Averaging over $\mathsf{M}$ proves (CP). ∎

In probabilistic notation, this identity says that

P_{Z_{-i},X_{i}}=P_{Z_{-i}}\otimes u_{r}\qquad(i\in[n]),

(9)

where $Z_{-i}$ is the tuple of all sites except $i$ . The correlations are sparse: writing $u_{\mathcal{Z}}$ for the uniform law on $\mathcal{Z}$ ,

P_{2}=\frac{1}{n-1}R+\frac{n-2}{n-1}u_{\mathcal{Z}}^{\otimes 2}.

(10)

The two observed sites are matched together with probability $1/(n-1)$ . Otherwise they belong to different independent edge factors, and marginalizing their partners leaves two independent uniform variables.

3.2 An incidence bound for feasible product laws

For two distinct sites, let

W_{ij}:=\{A_{i}+A_{j}=X_{i}X_{j}\}.

The classical value of the finite-field game can be written as

\omega_{r}:=\frac{1}{r^{2}}\max_{f,g:\mathbb{F}_{r}\to\mathbb{F}_{r}}\bigl|\{(x,y)\in\mathbb{F}_{r}^{2}:f(x)+g(y)=xy\}\bigr|.

(11)

A feasible product law cannot exploit the other site’s input: each output is generated by a channel acting on its own uniformly distributed input. Randomisation in these channels is a mixture of deterministic functions. For a deterministic pair, winning pairs of inputs are incidences between a graph and lines with distinct slopes. The field property limits how often two graph points can lie on these lines, which gives the required bound. This is the same incidence interpretation used in [5].

Lemma 3.3 (Finite-field incidence bound).

For every $q,q^{\prime}\in F$ ,

(q\otimes q^{\prime})(W_{12})\leq\omega_{r}\leq\beta_{r}:=\frac{1+\sqrt{4r-3}}{2r}\leq\frac{3}{2\sqrt{r}}.

(12)

Proof.

Write $q(x,a)=r^{-1}s(a\mid x)$ and $q^{\prime}(y,b)=r^{-1}t(b\mid y)$ , where $s, t$ are stochastic channels. For functions $f,g:\mathbb{F}_{r}\to\mathbb{F}_{r}$ , set

\lambda_{s}(f):=\prod_{x\in\mathbb{F}_{r}}s(f(x)\mid x),\qquad\lambda_{t}(g):=\prod_{y\in\mathbb{F}_{r}}t(g(y)\mid y).

These are probability distributions, and

s(a\mid x)=\sum_{f}\lambda_{s}(f)\mathbf{1}\{f(x)=a\},\qquad t(b\mid y)=\sum_{g}\lambda_{t}(g)\mathbf{1}\{g(y)=b\}.

Consequently,

(q\otimes q^{\prime})(W_{12})=\sum_{f,g}\lambda_{s}(f)\lambda_{t}(g)\frac{I(f,g)}{r^{2}},

where $I(f,g)$ is the number of pairs satisfying $f(x)+g(y)=xy$ . This proves the first inequality in (12).

To bound $I(f,g)$ , consider the graph points $\mathcal{G}_{g}=\{(y,g(y)):y\in\mathbb{F}_{r}\}$ and the lines

\ell_{x}:=\{(y,z):z=xy-f(x)\},\qquad x\in\mathbb{F}_{r}.

Put $t_{x}=|\ell_{x}\cap\mathcal{G}_{g}|$ , so that $I(f,g)=\sum_{x}t_{x}$ . Two distinct graph points have different first coordinates, and any line through both has the uniquely determined slope

x=\frac{g(y)-g(y^{\prime})}{y-y^{\prime}}.

Hence a pair of distinct graph points belongs to at most one of the lines $\ell_{x}$ . Counting ordered pairs gives

\sum_{x}t_{x}(t_{x}-1)\leq r(r-1).

Cauchy–Schwarz now yields

I(f,g)^{2}\leq r\sum_{x}t_{x}^{2}=rI(f,g)+r\sum_{x}t_{x}(t_{x}-1)\leq rI(f,g)+r^{2}(r-1).

Solving this quadratic inequality and dividing by $r^{2}$ gives $\omega_{r}\leq(1+\sqrt{4r-3})/(2r)$ . Finally, $\sqrt{4r-3}\leq 2\sqrt{r}$ and $1/(2r)\leq 1/(2\sqrt{r})$ , proving the last inequality. ∎

3.3 A rare-event relative-entropy witness

A single observed edge would distinguish the box from every feasible product law, but its location is unknown. We therefore test whether any observed pair wins. This incurs a factor $\binom{k}{2}$ in the product-law upper bound and gains the same factor from the number of possible internal matching edges. Their ratio depends on $(n-1)\omega_{r}$ , not on $k$ . We keep the game value symbolic so that either incidence estimate can be inserted into the same proof.

Proposition 3.4 (Matching-event witness).

Let $n\geq 6$ be even and $2\leq k\leq\sqrt{n}$ . For the law $P_{n}$ in (8), suppose $\omega_{r}\leq\beta<3/[4(n-1)]$ . Then, for every $\mu\in\mathcal{P}(F)$ ,

D(P_{k}\|M_{k,\mu})\geq\frac{3k(k-1)}{8(n-1)}\log\frac{3}{4e(n-1)\beta}.

(13)

Proof.

Set $m=\binom{k}{2}$ and $E=\bigcup_{1\leq i<j\leq k}W_{ij}$ . For each feasible $q$ , the union bound and Lemma 3.3 give $(q^{\otimes k})(E)\leq m\omega_{r}$ . Integrating over $\mu$ ,

M_{k,\mu}(E)\leq m\beta.

(14)

This bound is uniform in the mixing measure; it uses neither independence between the events $W_{ij}$ nor a bound on the number of mixture components.

Let $J$ be the number of matching edges contained in $[k]$ . An internal edge satisfies the game relation with probability one, so $P_{k}(E)\geq\Pr\{J\geq 1\}$ . A specified edge belongs to a uniform perfect matching with probability $1/(n-1)$ , and two specified disjoint edges both belong with probability $1/[(n-1)(n-3)]$ . Overlapping edges cannot both belong. There are $3\binom{k}{4}$ unordered pairs of disjoint candidate edges. The first two inclusion-exclusion terms imply

	$\displaystyle\Pr\{J\geq 1\}$	$\displaystyle\geq\frac{m}{n-1}-\frac{3\binom{k}{4}}{(n-1)(n-3)}$
		$\displaystyle=\frac{m}{n-1}\left(1-\frac{(k-2)(k-3)}{4(n-3)}\right)\geq\frac{3m}{4(n-1)}.$		(15)

For the last inequality, use $(k-2)(k-3)\leq k^{2}-3\leq n-3$ .

Write

p=P_{k}(E),\qquad q=M_{k,\mu}(E),\qquad p_{0}=\frac{3m}{4(n-1)},\qquad q_{0}=m\beta.

Here $p_{0}/q_{0}=3/[4(n-1)\beta]$ : the number of candidate pairs cancels from the likelihood ratio. The assumptions give $0<q_{0}<p_{0}<1$ , and the event bounds give $p\geq p_{0}$ and $q\leq q_{0}$ . If $q=0$ , the relative entropy is infinite. Otherwise data processing under $\mathbf{1}_{E}$ yields

D(P_{k}\|M_{k,\mu})\geq d_{\mathrm{Ber}}(p\|q),

where $d_{\mathrm{Ber}}$ is the relative entropy between Bernoulli laws. Its derivative with respect to its second argument is $(q-p)/[q(1-q)]$ , so it is decreasing for $0<q\leq p$ . Therefore

	$\displaystyle d_{\mathrm{Ber}}(p\\|q)$	$\displaystyle\geq d_{\mathrm{Ber}}(p\\|q_{0})$
		$\displaystyle\geq p\log\frac{p}{q_{0}}-p=p\log\frac{p}{eq_{0}}.$

Here the second term in binary relative entropy is bounded by

(1-p)\log\frac{1-p}{1-q_{0}}\geq(1-p)\log(1-p)\geq-p,

with the usual limiting convention at $p=1$ . The function $x\mapsto x\log(x/(eq_{0}))$ has derivative $\log(x/q_{0})$ , which is nonnegative for $x\geq q_{0}$ . It follows that

D(P_{k}\|M_{k,\mu})\geq p_{0}\log\frac{p_{0}}{eq_{0}}=\frac{3m}{4(n-1)}\log\frac{3}{4e(n-1)\beta},

which is (13). ∎

Proof of Theorem 3.1.

Use the matching law (8), which is admissible by Proposition 3.2. By Lemma 3.3, we may take $\beta=3/(2\sqrt{r})$ in Proposition 3.4. The parameter assumption implies

\frac{\sqrt{r}}{2e(n-1)}\geq r^{\theta}>1,

so this choice satisfies the hypothesis of the witness bound, and

\log\frac{3}{4e(n-1)\beta}=\log\frac{\sqrt{r}}{2e(n-1)}\geq\theta\log r.

Since $\log d=2\log r$ , (13) gives

D(P_{k}\|M_{k,\mu})\geq\frac{3\theta k(k-1)\log d}{16(n-1)}.

Finally, $k\leq\sqrt{n}$ implies $2(n-k+1)\geq n-1$ , yielding the second inequality in (5). ∎

Two features clarify the scope of the witness. First, identical one-site factors are unnecessary: the same lower bound holds for any mixture of laws $q_{1}\otimes\cdots\otimes q_{k}$ with each $q_{i}\in F$ , because Lemma 3.3 applies to every pair $q_{i},q_{j}$ . Second, every marginal in Theorem 3.1 has full support. Indeed, $k\leq n/2$ , so a perfect matching with no internal edge in $[k]$ exists and has positive probability. Conditional on any such matching, the marginal is $u_{\mathcal{Z}}^{\otimes k}$ . This also gives a full-support feasible product law, so the lower bound is not forced by an unavoidable support mismatch.

The witness combines a probability of order $k^{2}/n$ with a logarithm of $\sqrt{r}/n$ . A polynomial alphabet is enough to make this logarithm a fixed fraction of $\log d$ . Taking $k=o(\sqrt{n/\log d})$ then makes the matching upper bound vanish. Fix $0<\theta<1/2$ . For sufficiently large even $n$ , let $r_{n}$ be the least prime at least

R_{n}:=\left\lceil[2e(n-1)]^{1/(1/2-\theta)}\right\rceil.

Bertrand’s postulate gives $R_{n}\leq r_{n}\leq 2R_{n}$ . Thus

r_{n}=\Theta\!\left(n^{2/(1-2\theta)}\right),\qquad d_{n}=r_{n}^{2}=\Theta\!\left(n^{4/(1-2\theta)}\right).

(16)

Take $k_{n}=\lfloor n^{1/4}\rfloor$ , and denote the corresponding matching law and affine slice by $P_{n}$ and $F_{n}$ . Define

t_{n}:=\frac{k_{n}(k_{n}-1)\log d_{n}}{n-k_{n}+1}=\Theta\!\left(\frac{\log n}{\sqrt{n}}\right)\longrightarrow 0.

(17)

The constants in these asymptotic statements may depend on the fixed parameter $\theta$ . Combining Propositions 2.2 and 3.1 gives

\frac{3\theta}{32}t_{n}\leq\varepsilon_{\mathrm{con}}(P_{n},F_{n};k_{n})\leq B_{\mathrm{con}}(d_{n},n,k_{n})\leq\frac{1}{2}t_{n}.

(18)

In particular, the optimal error of the constructed law, not merely the lower bound, tends to zero.

For any fixed $\delta>0$ , choosing $\theta=\delta/[2(4+\delta)]$ gives

d_{n}=\Theta(n^{4+\delta}),\qquad\varepsilon_{\mathrm{con}}(P_{n},F_{n};k_{n})\geq\frac{3\delta}{64(4+\delta)}t_{n}.

(19)

This explicit family already rules out every sublogarithmic replacement in the uniform bound.

Corollary 3.5 (No uniform sublogarithmic replacement).

There do not exist a constant $C\in(0,\infty)$ and a function $h:\mathbb{N}\to[0,\infty)$ with $h(d)=o(\log d)$ such that

\varepsilon_{\mathrm{con}}(P_{n},F;k)\leq C\,\frac{k(k-1)h(d)}{n-k+1}

for every admissible $(\Gamma,\eta,P_{n})$ on every finite alphabet and every $1<k<n$ .

Proof.

Apply the proposed bound to (18) for any fixed $\theta\in(0,1/2)$ . Cancelling $k_{n}(k_{n}-1)/(n-k_{n}+1)>0$ gives

\frac{3\theta}{32}\leq C\frac{h(d_{n})}{\log d_{n}}\longrightarrow 0,

a contradiction. ∎

The incidence estimate determines how many input symbols are needed to make $n\omega_{r}$ polynomially small. Improving that estimate reduces the alphabet size without changing the witness. Bavarian and Shor [5, Theorem 1.3] prove that there are universal constants $C_{0}\geq 1$ and $\epsilon>0$ such that

\omega_{r}\leq C_{0}r^{-1/2-\epsilon}\qquad\text{for every prime }r.

(20)

Decreasing $\epsilon$ if necessary, we may assume $0<\epsilon<1/2$ . Inserting this estimate into the matching-event bound gives a polynomial alphabet exponent strictly below four.

Corollary 3.6 (A polynomial alphabet exponent below four).

There exist universal constants $\gamma\in(2,4)$ and $c>0$ , and admissible matching laws with $d_{n}=\Theta(n^{\gamma})$ and $k_{n}=\lfloor n^{1/4}\rfloor$ , such that, for all sufficiently large even $n$ ,

c\,t_{n}\leq\varepsilon_{\mathrm{con}}(P_{n},F_{n};k_{n})\leq B_{\mathrm{con}}(d_{n},n,k_{n})\leq\frac{1}{2}t_{n},\qquad t_{n}=\frac{k_{n}(k_{n}-1)\log d_{n}}{n-k_{n}+1}=\Theta\!\left(\frac{\log n}{\sqrt{n}}\right).

Proof.

Set $\alpha=1/2+\epsilon/2$ and $\gamma=2/\alpha=4/(1+\epsilon)$ . Choose $r_{n}$ to be the least prime at least $\lceil n^{1/\alpha}\rceil$ . Bertrand’s postulate gives $r_{n}=\Theta(n^{1/\alpha})$ , hence $d_{n}=r_{n}^{2}=\Theta(n^{\gamma})$ . Use the matching law over $\mathbb{F}_{r_{n}}$ , and put $\beta=C_{0}r_{n}^{-1/2-\epsilon}$ . Since $n\leq r_{n}^{\alpha}$ ,

(n-1)\beta\leq C_{0}r_{n}^{-\epsilon/2}\longrightarrow 0,

so Proposition 3.4 applies for all sufficiently large $n$ . Moreover,

	$\displaystyle\log\frac{3}{4e(n-1)\beta}$	$\displaystyle\geq\frac{\epsilon}{2}\log r_{n}+\log\frac{3}{4eC_{0}}$
		$\displaystyle\geq\frac{\epsilon}{4}\log r_{n}$

for all sufficiently large $n$ . Consequently,

D(P_{k_{n}}\|M_{k_{n},\mu})\geq\frac{3\epsilon\,k_{n}(k_{n}-1)\log d_{n}}{64(n-1)}\geq\frac{3\epsilon}{128}t_{n}.

Take $c=3\epsilon/128$ , and apply Proposition 2.2 for the upper bound. The claimed asymptotic size of $t_{n}$ follows from $d_{n}=\Theta(n^{\gamma})$ and $k_{n}=\lfloor n^{1/4}\rfloor$ . ∎

4 Fixed input support and feasible response tables

The lower bound fixes the input marginal but lets its support grow with $n$ . We now exploit the additional structure available when that support is small. The right empirical objects are complete response tables, each of which prescribes an output for every possible input. Every table defines a feasible deterministic channel, so their empirical mixtures retain the prescribed input law exactly. Let

\mathcal{Z}=\bigsqcup_{x\in\mathcal{X}}\{x\}\times\mathcal{A}_{x},\qquad F_{\pi}:=\{q\in\Delta(\mathcal{Z}):q_{X}=\pi\},

where $\mathcal{X}$ is finite, $\pi\in\Delta(\mathcal{X})$ , and each $\mathcal{A}_{x}$ is a nonempty finite output alphabet. Write $s=|\supp\pi|$ . A table requires $s$ physical sites, one per input; thus there are $M=\lfloor n/s\rfloor$ complete rows. The construction of Christandl and Toner [4], combined with relative-entropy data processing, turns the unrestricted sampling bound $L(n,k)$ into $L(M,k)$ .

Proposition 4.1 (Fixed input support).

Suppose $P_{n}$ is exchangeable and satisfies (CP) for $F_{\pi}$ , and let $n\geq s$ . Set $M=\lfloor n/s\rfloor$ . There is a single probability measure $\mu\in\mathcal{P}(F_{\pi})$ such that, simultaneously for every $1\leq k\leq M$ ,

D(P_{k}\|M_{k,\mu})\leq L(M,k)=\log\frac{M^{k}}{(M)_{k}}\leq\frac{k(k-1)}{2(M-k+1)}.

(21)

Proof.

We first identify the conditional structure forced by the lifted constraint. Discard zero-mass inputs, which occur with probability zero at every site, and assume $\pi(x)>0$ for all $x\in\mathcal{X}$ . Thus $|\mathcal{X}|=s$ . The lifted constraint at coordinate $i$ is

P_{Z_{-i},X_{i}}=P_{Z_{-i}}\otimes\pi.

(22)

After summing over all outputs, this shows that $X_{i}$ has law $\pi$ and is independent of $X_{-i}$ . Applying the identity at $i=n$ , then to the inherited identities on the first $n-1$ coordinates, proves inductively that $X^{n}\sim\pi^{\otimes n}$ .

For $S\subseteq[n]$ , define

T_{S}(a_{S}\mid x_{S}):=P(A_{S}=a_{S}\mid X_{S}=x_{S}).

Divide (22) by the positive input mass $\pi^{\otimes n}(x^{n})$ . This gives

\sum_{a_{i}}T_{[n]}(a^{n}\mid x^{n})=T_{[n]\setminus\{i\}}(a_{-i}\mid x_{-i}),

independently of $x_{i}$ . Repeated summation gives

\sum_{a_{S^{c}}}T_{[n]}(a^{n}\mid x^{n})=T_{S}(a_{S}\mid x_{S})\qquad(S\subseteq[n]).

(23)

This is the nonsignalling condition: unobserved inputs do not affect observed outputs. Exchangeability of $P_{n}$ , together with the iid input law, also makes these conditional laws permutation covariant. Conversely, these nonsignalling identities with iid inputs imply (22). Thus the lifted fixed-input constraint has an exact interpretation in terms of symmetric nonsignalling conditional laws.

We can now construct a random table with $M$ complete response rows. Choose an injection $\iota:[M]\times\mathcal{X}\to[n]$ , and fix an input string $\bar{x}\in\mathcal{X}^{n}$ with $\bar{x}_{\iota(j,x)}=x$ . Assign arbitrary inputs to unused sites. Draw $\bar{A}\sim T_{[n]}(\,\cdot\mid\bar{x})$ and form the table

\Lambda=(\lambda_{1},\ldots,\lambda_{M}),\qquad\lambda_{j}(x):=\bar{A}_{\iota(j,x)}.

Each row specifies one output in $\mathcal{A}_{x}$ for each input $x$ . By (23), the law $\nu$ of $\Lambda$ is independent of the inputs at unused sites. For a realized table $\lambda=(\lambda_{1},\ldots,\lambda_{M})$ , set

q_{\lambda}(x,a):=\pi(x)\frac{1}{M}\sum_{j=1}^{M}\mathbf{1}\{\lambda_{j}(x)=a\}.

(24)

This is a probability law with input marginal $\pi$ . Let $\mu$ be the law of $q_{\Lambda}$ , so $\mu\in\mathcal{P}(F_{\pi})$ .

The two distributions to be compared differ only in how they sample table rows. Fix $k\leq M$ . Let $U_{\mathrm{dist}}^{(k)}$ be uniform on the ordered $k$ -tuples of distinct elements of $[M]$ , and let $U_{\mathrm{iid}}^{(k)}$ be uniform on $[M]^{k}$ . Define the map

\Phi_{k}(\lambda,i^{k},x^{k}):=\bigl((x_{\ell},\lambda_{i_{\ell}}(x_{\ell}))\bigr)_{\ell=1}^{k}.

Under $\nu\otimes U_{\mathrm{dist}}^{(k)}\otimes\pi^{\otimes k}$ , the law of this map is $P_{k}$ . To see this, fix $i^{k}$ and $x^{k}$ . Distinct rows select the distinct physical sites $\iota(i_{\ell},x_{\ell})$ , $1\leq\ell\leq k$ , whose prescribed inputs are $x^{k}$ . Marginalizing the unselected outputs by (23) and permuting these sites to the first $k$ positions gives exactly $T_{[k]}(\,\cdot\mid x^{k})$ . Under $\nu\otimes U_{\mathrm{iid}}^{(k)}\otimes\pi^{\otimes k}$ , by contrast, the displayed pairs are conditionally iid given the table, with law $q_{\lambda}$ , so their joint law is $M_{k,\mu}$ .

Data processing under $\Phi_{k}$ therefore gives

	$\displaystyle D(P_{k}\\|M_{k,\mu})$	$\displaystyle\leq D\!\left(\nu\otimes U_{\mathrm{dist}}^{(k)}\otimes\pi^{\otimes k}\,\middle\\|\nu\otimes U_{\mathrm{iid}}^{(k)}\otimes\pi^{\otimes k}\right)$
		$\displaystyle=D\!\left(U_{\mathrm{dist}}^{(k)}\middle\\|U_{\mathrm{iid}}^{(k)}\right)=\log\frac{M^{k}}{(M)_{k}}.$

Indeed, the likelihood ratio on distinct tuples is the constant $M^{k}/(M)_{k}$ . The construction of $\nu$ and $\mu$ did not depend on $k$ , proving the simultaneous assertion. Finally,

\log\frac{M^{k}}{(M)_{k}}=\sum_{j=0}^{k-1}-\log\left(1-\frac{j}{M}\right)\leq\sum_{j=0}^{k-1}\frac{j}{M-j}\leq\frac{k(k-1)}{2(M-k+1)}.

∎

When $s=1$ , the rows are ordinary one-site observations and (21) becomes the unrestricted bound (1). For fixed $s$ and $k\leq M/2$ , it is $O(sk^{2}/n)$ , independently of all output-alphabet sizes and of the smallest positive input probability. The matching examples instead have $s=r_{n}>n$ , so no complete response row fits inside their extension. This accounts for the different behaviour of the two constructions: conditioning pays for the entropy of a site, while the table method pays for the number of sites needed to specify one feasible channel. Determining which other affine slices admit comparably efficient representations of feasible components remains open.

Appendix A Finite fields versus residue rings

The construction and the elementary incidence proof extend without change from prime fields to arbitrary finite fields. Primes are sufficient for the explicit sequences and are essential to the application of (20) in the form used above. By contrast, replacing a field by a composite residue ring invalidates the pair-counting argument: $y-y^{\prime}$ need not be invertible, so two graph points can have more than one admissible slope.

Two small examples verify this distinction directly. Over $\mathbb{Z}/4\mathbb{Z}$ , with function values indexed by $0,1,2,3$ , set

f=(0,0,0,2),\qquad g=(0,1,0,3).

The sets of winning second inputs for first inputs $0,1,2,3$ are, respectively,

\{0,2\},\quad\{0,1,3\},\quad\{0,2\},\quad\{1,2,3\}.

Thus $I(f,g)=2+3+2+3=10$ , exceeding the putative field bound $\lfloor 2(1+\sqrt{13})\rfloor=9$ .

Over $\mathbb{Z}/6\mathbb{Z}$ , set

f=(0,0,0,0,0,2),\qquad g=(0,3,2,0,0,5).

Here the complete winning sets are

\begin{array}[]{c|cccccc}x&0&1&2&3&4&5\\ \hline\cr\{y:f(x)+g(y)=xy\}&\{0,3,4\}&\{0,2,5\}&\{0,3\}&\{0,1,4\}&\{0,2,3\}&\{1,2,4,5\}.\end{array}

The total is $I(f,g)=3+3+2+3+3+4=18$ , whereas the corresponding field expression would give $\lfloor 3(1+\sqrt{21})\rfloor=16$ . These explicit lists require no external computation or auxiliary data.

References

[1] M. Berta, L. Gavalakis, and I. Kontoyiannis, A third information-theoretic approach to finite de Finetti theorems, in 2024 IEEE International Symposium on Information Theory (ISIT), 2024. doi:10.1109/ISIT57864.2024.10619572; arXiv:2304.05360.
[2] R. Song, K. M. Attiah, and W. Yu, Coded downlink massive random access and a finite de Finetti theorem, IEEE Transactions on Information Theory 71(9), 6932–6949, 2025. doi:10.1109/TIT.2025.3564114; arXiv:2405.08301.
[3] L. Gavalakis, O. Johnson, and I. Kontoyiannis, Finite de Finetti bounds in relative entropy, arXiv:2407.12921, 2024.
[4] M. Christandl and B. Toner, Finite de Finetti theorem for conditional probability distributions describing physical theories, Journal of Mathematical Physics 50(4), 042104, 2009. doi:10.1063/1.3114986; arXiv:0712.0916.
[5] M. Bavarian and P. W. Shor, Information causality, Szemerédi–Trotter and algebraic variants of CHSH, in Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (ITCS), 2015. doi:10.1145/2688073.2688112; arXiv:1311.5186.
[6] F. G. S. L. Brandão and A. W. Harrow, Quantum de Finetti theorems under local measurements with applications, Communications in Mathematical Physics 353, 469–506, 2017. doi:10.1007/s00220-017-2880-3; arXiv:1210.6367.
[7] M. Berta, F. Borderi, O. Fawzi, and V. B. Scholz, Semidefinite programming hierarchies for constrained bilinear optimization, Mathematical Programming 194, 781–829, 2022. doi:10.1007/s10107-021-01650-1; arXiv:1810.12197.
[8] R. Arnon-Friedman and R. Renner, de Finetti reductions for correlations, Journal of Mathematical Physics 56(5), 052203, 2015. doi:10.1063/1.4921341; arXiv:1308.0312.
[9] C. Lancien and A. Winter, Flexible constrained de Finetti reductions and applications, Journal of Mathematical Physics 58(9), 092203, 2017. doi:10.1063/1.5003633; arXiv:1605.09013.
[10] J. A. Zeiss, G. Koßmann, R. Schwonnek, and M. Plávala, Finite de Finetti for convex bodies and polynomial optimization, arXiv:2601.15184, 2026.
[11] G. Koßmann and J. A. Zeiss, Fixed points in de Finetti hierarchies, arXiv:2607.23689, 2026.

The logarithmic cost of componentwise constraints in finite de Finetti approximation

Abstract

1 Introduction

2 Feasible mixtures and the conditioning bound

Lemma 2.1 (Posterior preservation).

Proof.

Proposition 2.2 (Conditioning upper bound).

Proof.

3 The random-matching lower bound

Theorem 3.1 (Logarithmic alphabet-size lower bound).

3.1 A matching extension that preserves the constraint

Proposition 3.2 (Admissibility of the matching law).

Proof.

3.2 An incidence bound for feasible product laws

Lemma 3.3 (Finite-field incidence bound).

Proof.

3.3 A rare-event relative-entropy witness

Proposition 3.4 (Matching-event witness).

Proof.

Proof of Theorem 3.1.

Corollary 3.5 (No uniform sublogarithmic replacement).

Proof.

Corollary 3.6 (A polynomial alphabet exponent below four).

Proof.

4 Fixed input support and feasible response tables

Proposition 4.1 (Fixed input support).

Proof.

Appendix A Finite fields versus residue rings

References

The logarithmic cost of componentwise constraints
in finite de Finetti approximation