Proof. The hull \(\mathop{\mathrm{absconv}}\{R_x:x\in X\}\) is the convex hull of the finitely many vectors \(\pm R_x\). It is compact, convex, and symmetric, and contains zero. Thus \(K\) has the same three properties and contains \(tB_\infty^Y\), which gives it nonempty interior in the full ambient space. The corresponding properties of \(L\) are immediate.

Each point \(3R_x\) belongs to \(K\), and two distinct such points have uniform distance at least \(3\). Every translate of \(L\) has uniform diameter \(2\), whatever its center. Hence it contains at most one of these \(|X|\) points. This proves the first inequality in (2).

For the polar estimate, the support function \(h_K(\delta)=\sup_{z\in K}\langle z,\delta\rangle\) is exactly \[ h_K(\delta) =3\max_{x\in X}|\langle R_x,\delta\rangle| +t\sum_{y\in Y}|\delta_y| =3\|f_\delta\|_{\infty,X}+t\|\delta\|_1. \tag{3}\] Indeed, a linear functional attains its maximum over the finite convex hull at one of the vectors \(\pm R_x\). Its maximum over \(B_\infty^Y\) is \(\sum_y|\delta_y|\), attained by choosing the sign of each coordinate. The two choices in the Minkowski sum are independent, so their maxima add. The same cube calculation gives \[L^\circ=B_1^Y=\{\lambda\in\mathbb R^Y:\|\lambda\|_1\le1\}.\]

Order the approximating list. Assign each \(\lambda\in B_1^Y\) to the first list function within \(\varepsilon\) of \(f_\lambda\), thereby partitioning \(B_1^Y\) into at most \(M\) nonempty clusters. From each nonempty cluster choose one actual vector \(\lambda^{(k)}\in B_1^Y\). For any \(\lambda\) in that cluster, the triangle inequality gives \[\|f_\lambda-f_{\lambda^{(k)}}\|_{\infty,X} \le2\varepsilon, \qquad \|\lambda-\lambda^{(k)}\|_1\le2.\] Consequently (3) implies \[h_K(\lambda-\lambda^{(k)})\le6\varepsilon+2t.\] For every \(c>0\), the definition of the polar and positive homogeneity give the equivalence \[\delta\in cK^\circ \quad\Longleftrightarrow\quad h_K(\delta)\le c.\] Each cluster is therefore contained in \(\lambda^{(k)}+(6\varepsilon+2t)K^\circ\). These at most \(M\) translates cover \(B_1^Y=L^\circ\), proving the second inequality. Selecting representatives inside the coefficient ball is what controls the contribution of the added cube, even when the original list functions lie outside \(\mathcal F\). ◻

Proof. Positivity and the identity \(\sum_j\gamma_j=1\) follow by telescoping. If \(0\le d<h\), the sum in (7) runs from \(j=d\) to \(j=h-1\) and equals \[\frac{\log(h+1)-\log(d+1)}{\log(h+1)}.\] If \(d\ge h\), including \(d=\infty\), both sides are zero.

For finite \(d\), the extra indices counted on the left of (8) satisfy \(j<d\le3j+2\). When this index set is nonempty, it is the integer interval from \[a_d=\max\left\{0,\left\lceil\frac{d+1}{3}\right\rceil-1\right\} \quad\text{to}\quad b_d=\min\{h-1,d-1\}.\] Since \(b_d+2\le d+1\) and \(a_d+1\ge(d+1)/3\), its weight is \[\sum_{j=a_d}^{b_d}\gamma_j =\frac{\log((b_d+2)/(a_d+1))}{\log(h+1)} \le\frac{\log3}{\log(h+1)}.\] An empty interval contributes zero. If \(d=\infty\), all the indicators vanish. This also covers all distances at and beyond the cutoff \(h\). ◻

Proof. For each \(i\in[u]\), fix a representative map \[\rho_i:L_i(X)\longrightarrow X, \qquad L_i(\rho_i(\sigma))=\sigma.\] These maps are fixed for the entire approximation problem, before any coefficient vector is chosen.

A common index. Fix \(f=f_\mu\in\mathcal F_+\), and use \(\mu(S)=\sum_{y\in S}\mu_y\) for subsets \(S\subseteq Y\). Averaging (4) gives \[\frac1u\sum_{i=1}^u\mu\{(v,T):i\notin T\} =\sum_{(v,T)\in Y}\mu_{(v,T)}\frac{|[u]\setminus T|}{u} \le\theta.\] Choose \(i_0\in[u]\) for which the omitted mass is at most \(\theta\), and retain the columns in \[Y_0=\{(v,T)\in Y:i_0\in T\}.\] This one index will serve at every level \(j\).

A bounded number of pivots at each level. Fix \(j\in\{0,\ldots,h-1\}\) and, for \(x\in X\), let \[I_x=\{(v,T)\in Y_0:d_T(x,v)\le j\}.\] Starting with an empty union, add a set \(I_z\) whenever its mass outside the current union is greater than \(\theta\). If \(k_j\) sets are added, their successive contributions give \(k_j\theta<1\); in particular \(k_j\le s\). The process therefore terminates with pivots \(z_{j,1},\ldots,z_{j,k_j}\) and union \[U_j=\bigcup_{k=1}^{k_j}I_{z_{j,k}} \quad\text{such that}\quad \mu(I_x\setminus U_j)\le\theta\qquad(x\in X).\] The empty choice is allowed. Assign every column of \(U_j\) to the first pivot whose set contains it, and denote its assigned slot by \(\kappa_j(y)\).

For a pivot \(z=z_{j,k}\), retain only its label \(L_{i_0}(z)\), and replace it by \(z'=\rho_{i_0}(L_{i_0}(z))\). If \(y=(v,T)\) is assigned to this pivot, then \(i_0\in T\), \(d_T(v,z)\le j\), and \(d_T(z,z')\le1\). Consequently, \[ d_T(v,z')\le j+1. \tag{11}\] For every \(x\in X\), the triangle inequality now gives the two implications \[\begin{align*} d_T(x,v)\le j &\ \Longrightarrow\ d_T(x,z')\le2j+1, \tag{12}\\ d_T(x,z')\le2j+1 &\ \Longrightarrow\ d_T(x,v)\le3j+2. \tag{13}\end{align*}\] All distances used in these triangle inequalities are finite under their respective hypotheses, even if the graph is disconnected. Figure 1 illustrates the two bounds.

Write \(z'_{j,k}=\rho_{i_0}(L_{i_0}(z_{j,k}))\) and define \[A_j(x)=\sum_{y=(v,T)\in U_j}\mu_y \mathbf1_{\{d_T(x,z'_{j,\kappa_j(y)})\le2j+1\}}.\] For comparison, let \[f_{\mu,j}(x)=\sum_{y=(v,T)\in Y}\mu_y \mathbf1_{\{d_T(x,v)\le j\}}.\] Every assigned column counted by \(f_{\mu,j}(x)\) is counted by \(A_j(x)\), by (12). The other columns counted by \(f_{\mu,j}(x)\) have total mass at most \(2\theta\): at most \(\theta\) lies outside \(Y_0\), and at most \(\theta\) lies in \(I_x\setminus U_j\). Conversely, (13) bounds every column counted by \(A_j(x)\). Hence \[ f_{\mu,j}(x)-2\theta \le A_j(x) \le\sum_{y=(v,T)\in Y}\mu_y\mathbf1_{\{d_T(x,v)\le3j+2\}}. \tag{14}\]

Combining the levels. Let \(F=\sum_{j=0}^{h-1}\gamma_jA_j\). By (7), \(f_\mu=\sum_j\gamma_jf_{\mu,j}\). Thus the lower bound in (14) gives \(F\ge f_\mu-2\theta\). For the upper bound, apply (8) separately to each distance \(d_T(x,v)\) and sum with weights \(\mu_{(v,T)}\). Since the total mass is at most one and \(\log3/\log(h+1)\le\theta\), this yields the pointwise interval \[ f_\mu-2\theta\le F\le f_\mu+\theta. \tag{15}\]

A finite encoding. The center \(v\) of an assigned column no longer occurs in its indicator in \(A_j\). Grouping columns by assigned slot and by \(T\) gives exactly \[ A_j(x)=\sum_{k=1}^{s}\sum_{T\in\mathcal T} w_{j,k,T}\mathbf1_{\{d_T(x,z'_{j,k})\le2j+1\}}, \tag{16}\] where \[w_{j,k,T}= \sum_{\substack{v\in X:\ (v,T)\in U_j\,,\ \kappa_j(v,T)=k}} \mu_{(v,T)}.\] Unused slots have all weights zero and are padded with a fixed realized \(L_{i_0}\)-label. Such a label exists because \(X\) is nonempty. Each weight belongs to \([0,1]\), and there are at most \(M_0=s2^u\) weights at each level. Round each weight down to a multiple of \(\delta=\theta/M_0\), writing \[\widetilde w_{j,k,T} =\delta\left\lfloor\frac{w_{j,k,T}}{\delta}\right\rfloor.\] Let \(\widetilde A_j\) be (16) with these rounded weights, and put \(A=\sum_j\gamma_j\widetilde A_j\). Since every indicator is at most one, \[0\le A_j(x)-\widetilde A_j(x)\le M_0\delta=\theta.\] The weights \(\gamma_j\) sum to one, so \(0\le F-A\le\theta\). Together with (15), this proves (9).

It remains to count one list that works for all \(\mu\). For fixed \(i_0\), the data determining \(A\) are the \(s\) pivot labels at each of the \(h\) levels and the rounded weights in (16). The label determines \(z'_{j,k}\) through the fixed map \(\rho_{i_0}\), so no original pivot or column center must also be specified. There are at most \(q^{hs}\) choices of labels. Each rounded weight has at most \[\left\lfloor\frac{M_0}{\theta}\right\rfloor+1 \le1+\frac{M_0}{\theta}\] possible values, and there are at most \(hM_0\) such weights. Enumerate these choices for every \(i_0\in[u]\), allowing also codes that do not arise from a coefficient vector. This gives a fixed finite list of functions containing every approximant constructed above, with \[Q\le u\,q^{hs} \left(1+\frac{s2^u}{\theta}\right)^{hs2^u}.\] Taking logarithms proves (10). The graphs and the representative maps are shared data defining this list; they are not additional choices for each approximant. ◻

Proof. Write \(\lambda=\lambda^+-\lambda^-\), where \(\lambda_y^+=\max\{\lambda_y,0\}\) and \(\lambda_y^-=\max\{-\lambda_y,0\}\). Each part is nonnegative and has total mass at most one. Apply Proposition 4 to choose \(A^+,A^-\in\mathcal A\) with \[\|f_{\lambda^+}-A^+\|_{\infty,X}\le3\theta, \qquad \|f_{\lambda^-}-A^-\|_{\infty,X}\le3\theta.\] Then \(A^+-A^-\) approximates \(f_\lambda\) to error at most \(6\theta\). There are at most \(Q^2\) differences in \(\mathcal A-\mathcal A\). Order this finite list and assign each \(\lambda\in B_1^Y\) to its first approximant with error at most \(6\theta\). The nonempty fibers form the claimed partition, and the triangle inequality proves (17). The approximating functions need not belong to \(\mathcal F\); the clusters themselves consist of actual coefficient vectors in \(B_1^Y\). ◻

Proof. We induct on \(k\). When \(k=0\), the polynomial is a nonzero constant, and its zero probability is zero. For \(k\ge1\), write \[P(z_1,\ldots,z_k) =\sum_{j=0}^{e}P_j(z_1,\ldots,z_{k-1})z_k^j, \qquad P_e\ne0.\] The total degree of \(P_e\) is at most \(d-e\), so the induction hypothesis bounds the probability that this leading coefficient vanishes by \((d-e)/p\). Conditional on any values of the first \(k-1\) variables for which it does not vanish, the resulting univariate polynomial has degree \(e\) and at most \(e\) roots, by successive division by linear factors. Its conditional zero probability is therefore at most \(e/p\). The sum of these two bounds is \(d/p\). This argument also covers \(e=0\) and, in particular, all nonzero constant polynomials. ◻

Proof. Choose \(t_1,\ldots,t_u\) independently and uniformly in \(E\). Fix a nonzero form \(Z\). For \(z=\sum_{a=1}^r z_a e_a\), its diagonal polynomial is \[ \begin{aligned} P_Z(z_1,\ldots,z_r)&=Z(z,\ldots,z)\\ &=\sum_{\substack{\alpha_1+\cdots+\alpha_r=h\\\alpha_a\ge0}} \frac{h!}{\alpha_1!\cdots\alpha_r!} Z(e_1^{[\alpha_1]},\ldots,e_r^{[\alpha_r]}) z_1^{\alpha_1}\cdots z_r^{\alpha_r}, \end{aligned} \tag{22}\] where \(e_a^{[\alpha_a]}\) means that \(e_a\) is repeated \(\alpha_a\) times among the arguments. At least one displayed value of \(Z\) is nonzero. Since \(p>h\), every displayed multinomial coefficient is nonzero in \(\mathbb F_p\). Distinct multisets give distinct monomials, so \(P_Z\) is a nonzero polynomial of total degree \(h\). This is the diagonal recovery of a symmetric multilinear form when \(h!\) is invertible; see (Ferrero and Micali 1979, Corollary 1.2) and (Drápal and Vojtěchovský 2009, Proposition 3.3). The coordinate argument above gives the precise fact needed here.

For an ordered tuple \(\mathbf i=(i_1,\ldots,i_h)\in[u]^h\), let \(\mathop{\mathrm{supp}}(\mathbf i)=\{i_1,\ldots,i_h\}\). The expression \(Z(t_{i_1},\ldots,t_{i_h})\), considered as a polynomial in the scalar coordinates of the vectors with indices in \(\mathop{\mathrm{supp}}(\mathbf i)\), has total degree \(h\) and is nonzero: setting all those vector variables equal to \(z\) gives the nonzero polynomial (22). Lemma 6 therefore gives \[ \Pr\bigl(Z(t_{i_1},\ldots,t_{i_h})=0\bigr)\le\frac hp. \tag{23}\] This applies to every pattern of repeated indices.

For this fixed \(Z\), evaluations on tuples with pairwise disjoint index supports depend on disjoint subsets of the independent vectors \(t_i\). Their zero events are consequently independent. There are at most \(u^{hw}\) ordered lists of \(w\) ordered \(h\)-tuples, and fewer than \(p^{D_h}\) choices of nonzero \(Z\). A union bound shows that the probability that some nonzero \(Z\) has \(w\) zero tuples with pairwise disjoint supports is at most \[ p^{D_h}u^{hw}\left(\frac hp\right)^w =\left(\frac{h^2u^{2h}}p\right)^{D_h}<1. \tag{24}\] The count includes all forms over the chosen field; no independence between different forms is needed. Fix vectors for which this event does not occur.

For each nonzero \(Z\), take a family of zero tuples with pairwise disjoint supports that is maximal under inclusion. It contains at most \(w-1\) tuples. Delete the union of their supports, and let \(T\) be the remaining indices. The number deleted is at most \[h(w-1)<hw\le\theta u.\] If any zero tuple were supported in \(T\), its support would be disjoint from all the selected supports, contradicting maximality. Thus (21) holds. Since \(\theta<1\), the set \(T\) is nonempty. The construction imposed no requirement that the sampled vectors be distinct or nonzero. ◻

Proof. The cardinality of \(X\) follows from (18). The contraction \(L_i(x)\) is a symmetric \((h-1)\)-linear form, so its possible values belong to a space of cardinality \(p^{D_{h-1}}\). This bounds the realized labels even if a contraction is not surjective.

Fix distinct \(x,y\in X\), and apply Proposition 7 to \(Z=y-x\). Let \(T\in\mathcal T\) be the resulting nonempty set. Recall that distinct vertices are adjacent in the graph for \(T\) if their labels agree at some \(i\in T\). Suppose there were a path \[x=x_0,x_1,\ldots,x_k=y,\qquad 1\le k\le h.\] For each edge choose \(i_j\in T\) such that \(L_{i_j}(x_j)=L_{i_j}(x_{j-1})\), and put \(\Delta_j=x_j-x_{j-1}\). Thus \[\Delta_j(t_{i_j},v_2,\ldots,v_h)=0 \qquad\text{for every }v_2,\ldots,v_h\in E.\] Choose any \(i_*\in T\), and form the \(h\)-tuple consisting of \(t_{i_1},\ldots,t_{i_k}\) followed by \(h-k\) copies of \(t_{i_*}\). Every \(\Delta_j\) vanishes on this tuple, since it is symmetric and one of its arguments is \(t_{i_j}\). The identity \(Z=\sum_{j=1}^k\Delta_j\) implies that \(Z\) also vanishes on the tuple, contrary to (21). This proves (25); vertices in different components have infinite distance and already satisfy it.

At the column \((x,T)\), the logarithmic profile gives \(g_{(x,T)}(x)=1\) and \(g_{(x,T)}(y)=0\), because \(d_T(x,y)>h\). All column values lie in \([0,1]\), so this unit difference also gives the exact equality (26). ◻

Proof of Theorem 1. Fix \(a,b\ge1\). Put \[\theta=\frac1{1000a}, \qquad s=\lceil1/\theta\rceil,\] and choose a positive integer \(h\) with \(\log3/\log(h+1)\le\theta\). Such an integer exists because \(\log(h+1)\) tends to infinity. Choose a positive integer \(r\) so that \[ r+h-1>8bh^2s. \tag{28}\] As in Section 4, define \[D_j=\binom{r+j-1}{j}\quad(0\le j\le h), \qquad w=2D_h, \qquad u=\left\lceil\frac{hw}{\theta}\right\rceil.\] The number \[ C=C_{h,\theta,u} =\log u+hs2^u\log\left(1+\frac{s2^u}{\theta}\right) \tag{29}\] is now fixed. Choose a prime \(p\) satisfying \[ p>\max\left\{ h,\ h^2u^{2h},\ \exp\left(\frac{8bC}{D_h}\right) \right\}. \tag{30}\] All quantities on the right have already been determined, and primes exceed every finite bound.

Apply Proposition 7 with these parameters, and form the label maps and graph profiles in Proposition 8. The row index set \(X\) consists of the symmetric \(h\)-linear forms on \(\mathbb F_p^r\), so \[m=|X|=p^{D_h}>1.\] Each label map takes at most \(q=p^{D_{h-1}}\) values. The columns are indexed by \(Y=X\times\mathcal T\), where \[\mathcal T=\{T\subseteq[u]:|[u]\setminus T|\le\theta u\},\] and the real row vectors satisfy \[ \|R_x-R_{x'}\|_\infty=1\qquad(x\ne x'). \tag{31}\] In particular, \(Y\) is a finite nonempty set. The finite field serves only to construct the indices and label maps; the matrix entries and the convex bodies below are real.

By Proposition 4, the positive column class has a uniform \(3\theta\) approximation list of cardinality \(Q\) satisfying \[\log Q\le hs\log q+C =hsD_{h-1}\log p+C.\] Corollary 5 gives a uniform \(6\theta\) approximation list of at most \(Q^2\) functions for the absolutely convex column hull. Thus Lemma 2 applies with \(\varepsilon=6\theta\) and \(t=\theta\). It gives admissible bodies in dimension \(n=|Y|\), \[ K=3\mathop{\mathrm{absconv}}\{R_x:x\in X\}+\theta B_\infty^Y, \qquad L=B_\infty^Y, \tag{32}\] such that \[N(K,L)\ge m, \qquad N(L^\circ,38\theta K^\circ)\le Q^2.\] Since \(38\theta=38/(1000a)<a^{-1}\), increasing the covering body preserves this cover, and therefore \[ N(L^\circ,a^{-1}K^\circ)\le Q^2. \tag{33}\]

It remains to compare the two entropies. The exact identity \[\frac{D_{h-1}}{D_h}=\frac{h}{r+h-1}\] yields \[ \frac{\log(Q^2)}{\log m} \le \frac{2h^2s}{r+h-1} +\frac{2C}{D_h\log p} <\frac1{4b}+\frac1{4b} =\frac1{2b}, \tag{34}\] where the strict inequalities follow respectively from (28) and (30). Combining (33) with \(N(K,L)\ge m>1\) gives \[b\log N(L^\circ,a^{-1}K^\circ) \le b\log(Q^2) <\frac12\log m <\log N(K,L).\] Identifying \(\mathbb R^Y\) with \(\mathbb R^n\) makes \(L=[-1,1]^n\) and proves the claimed counterexample for the arbitrary proposed constants \(a,b\). ◻