Answer: A deterministic polynomial-time algorithm returns a feasible rational control satisfying $\mathcal M(x)\ge(1-1/e-\epsilon)\mathrm{OPT}$ under the stated uniqueness promise.
Theorem 5 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor an Ising system with non-negative interac- tions J ≥0 and non-negative initial biases b0 ≥0, the total activity M is monotonic and submodular in the activated nodes V .
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(\tau\) types with rational masses \(\mu_a\), nonnegative rational biases \(b_a\), a symmetric nonnegative rational interaction matrix \(K\), and a budget \(B\), consider populations of size \(N\) whose type proportions approach \(\mu\), with type-\(a\) agents interacting with type-\(b\) agents at strength \(K_{ab}/N\). Choose fractions \(x_a\in[0,1]\) of each type to pin active, subject to \(\sum_a\mu_a x_a\le B\). For free-agent type magnetizations \(r_a\in[-1,1]\), set \(q_a=x_a+(1-x_a)r_a\), and let \(r^*(x)\) be the unique maximizer of \(\frac12\sum_{a,b}\mu_a\mu_b K_{ab}q_aq_b+\sum_a\mu_a b_aq_a+\sum_a\mu_a(1-x_a)s(r_a)\), where \(s\) is binary entropy. Define \(\mathcal M(x)=\sum_a\mu_a q_a^*(x)\). Determine whether an algorithm polynomial in \(\tau\), input bit length \(L\), and \(1/\epsilon\) can return feasible \(x\) with \(\mathcal M(x)\ge(1-1/e-\epsilon)\mathrm{OPT}\), or establish a complexity barrier for this approximation problem.
A society is given by its support: the list of \(\tau\ge1\) types with positive binary-rational masses \(\mu_a\), normalized by \(\sum_a\mu_a=1\); \(\tau\) is the support size, not the number of possible types. The interaction dimension is \(m=\tau\). Input also includes binary-rational biases \(b_a\ge0\), a symmetric entrywise nonnegative binary-rational matrix \(K\), and a binary-rational budget \(B\in[0,1]\); let \(L\) be the total input bit length.
A control \(x\in[0,1]^\tau\) pins fraction \(x_a\) of type \(a\) to spin \(+1\), at unit cost per unit mass, with \(\sum_a\mu_ax_a\le B\). Free spins have type magnetizations \(r_a\in[-1,1]\), giving \(q_a=x_a+(1-x_a)r_a\).
Let \(s(r)\) be binary entropy of probability \((1+r)/2\), using natural logarithms and its continuous endpoint values. Define \(\Phi_x(r)=\frac12\sum_{a,b}\mu_a\mu_bK_{ab}q_aq_b+\sum_a\mu_ab_aq_a+\sum_a\mu_a(1-x_a)s(r_a)\).
Promise that for every feasible \(x\), maximizing \(\Phi_x\) over the coordinates with \(x_a<1\) has a unique global maximizer \(r^*(x)\); fully pinned coordinates have \(q_a^*(x)=1\). Define \(\mathcal M(x)=\sum_a\mu_aq_a^*(x)\) and \(\mathrm{OPT}=\max_{x\text{ feasible}}\mathcal M(x)\).
Can an algorithm, given rational \(0<\epsilon<1-1/e\), return a feasible rational \(x\) satisfying \(\mathcal M(x)\ge(1-1/e-\epsilon)\mathrm{OPT}\) in time polynomial in \(m,\tau,L,1/\epsilon\), or is there a complexity barrier to this approximation guarantee?
For finite Ising systems with nonnegative interactions and biases, total expected magnetization is monotone and submodular in the nodes pinned to \(+1\), yielding a \(1-1/e\) greedy guarantee with exact objective evaluations. [Source](https://arxiv.org/html/1803.00110v2)
For continuous external-field allocation, mean-field magnetization is known to be smooth and concave on a stable nonnegative branch under strong connectivity; that result concerns field allocation rather than fractional pinning. [Source](https://papers.neurips.cc/paper/6119-maximizing-influence-in-an-ising-network-a-mean-field-optimal-solution.pdf) No result settling the precise promised fractional-pinning problem was located.
The requested approximation is achievable in deterministic polynomial time under the uniqueness promise.
The proof below establishes fractional diminishing returns, gives a polynomial bit-time equilibrium evaluation routine, and reduces the problem to monotone submodular maximization under one knapsack constraint. The numerical evaluation argument includes convergence and rational rounding explicitly.
Throughout, inequalities between vectors are coordinatewise. Write
$$
v_a=1-x_a,\qquad w_a=\mu_av_a,
$$
and define
$$
\kappa=\sum_{a,b}\mu_a\mu_bK_{ab},\qquad
\beta=\sum_a\mu_ab_a,\qquad
C=2\kappa+2\beta+1.
$$
For any $r\in[-1,1]^\tau$, replace $r_a$ by $|r_a|$. The resulting magnetization satisfies
$$
x_a+v_a|r_a|\ge |x_a+v_ar_a|.
$$
Consequently, every interaction product after replacement is at least its original value: if the original product is nonnegative, compare absolute values; if it is negative, the new product is nonnegative. Bias contributions also do not decrease, and entropy is unchanged.
Thus a nonnegative global maximizer always exists. On feasible controls, the uniqueness promise identifies it with the prescribed equilibrium.
Set $z_a=r_a^2$ and
$$
G_x(z)=\Phi_x(\sqrt z),\qquad z\in[0,1]^\tau.
$$
Symmetry of $K$ gives
$$
G_x(z)
=c_x+
\sum_a w_a\left(b_a+\sum_b\mu_bK_{ab}x_b\right)\sqrt{z_a}
+\frac12\sum_{a,b}\mu_a\mu_bK_{ab}v_av_b\sqrt{z_az_b}
+\sum_a w_ag(z_a),
$$
where $c_x$ is independent of $z$ and $g(z)=s(\sqrt z)$.
Square roots and geometric means are concave, and all their coefficients here are nonnegative. For completeness, concavity of the geometric mean follows from Cauchy–Schwarz:
$$
\sqrt{((1-t)u+tu')((1-t)v+tv')}
\ge (1-t)\sqrt{uv}+t\sqrt{u'v'}.
$$
Integrating the power series for $\operatorname{arctanh}r$ yields
$$
g(z)=\log 2-\sum_{k=1}^{\infty}\frac{z^k}{2k(2k-1)}.
$$
The series converges uniformly on $[0,1]$, so it also gives the endpoint values. On $(0,1)$, termwise differentiation gives
$$
g''(z)
=-\sum_{k=2}^{\infty}
\frac{k-1}{2(2k-1)}z^{k-2}
\le-\frac16.
$$
The resulting strong-concavity inequality extends to the endpoints by continuity. Therefore,
$$
G_x((1-t)z+tz')
\ge
(1-t)G_x(z)+tG_x(z')
+\frac{t(1-t)}{12}\sum_a w_a(z_a-z'_a)^2.
$$
Every unpinned coordinate has $w_a>0$. Hence $G_x$ has a unique maximizer on those coordinates. Fully pinned coordinates are irrelevant to both its value and the resulting magnetization.
Let $z^*(x)$ denote this maximizer, with arbitrary values in fully pinned coordinates, and define
$$
q_a^+(x)=x_a+v_a\sqrt{z_a^*(x)},\qquad
M^+(x)=\sum_a\mu_aq_a^+(x).
$$
This defines a nonnegative equilibrium throughout the entire control cube, including infeasible controls. On feasible controls,
$$
M^+(x)=\mathcal M(x).
$$
Applying strong concavity between $z^*(x)$ and an arbitrary $z$, using maximality at the intermediate point, dividing by $t$, and letting $t\downarrow0$, gives the useful gap bound
$$
G_x(z^*(x))-G_x(z)
\ge
\frac1{12}\sum_a w_a(z_a^*(x)-z_a)^2.
$$
For fixed $z$, let $d=\|x-y\|_\infty$. Each nonnegative magnetization changes by at most $d$. An interaction product changes by at most $2d$, and the entropy contribution changes by at most $d\log2$. Thus
$$
|G_x(z)-G_y(z)|
\le(\kappa+\beta+\log2)d
\le Cd.
$$
Writing $z_x=z^*(x)$ and $z_y=z^*(y)$, maximality of $z_y$ implies
$$
G_x(z_x)-G_x(z_y)\le2Cd.
$$
The gap bound therefore gives
$$
\sum_a w_a(z_{x,a}-z_{y,a})^2\le24Cd.
$$
For nonnegative $u,v$,
$$
|\sqrt u-\sqrt v|\le |u-v|^{1/2}.
$$
Hölder’s inequality, together with $\sum_a w_a\le1$, consequently gives
$$
\sum_a w_a|\sqrt{z_{x,a}}-\sqrt{z_{y,a}}|
\le
\left(\sum_a w_a(z_{x,a}-z_{y,a})^2\right)^{1/4}.
$$
Changing the control itself contributes at most $d$, so
$$
|M^+(x)-M^+(y)|
\le d+(24Cd)^{1/4}.
$$
Each component $q_a^+$ is also continuous. At a control with $x_a<1$, the preceding weighted squared-distance bound controls its $z_a$ coordinate because $w_a>0$. At a control with $x_a=1$,
$$
0\le1-q_a^+(y)\le1-y_a.
$$
Since the feasible set is compact, $\mathrm{OPT}$ is attained.
The same Hölder calculation proves an accuracy conversion that does not involve the smallest positive weight. If
$$
G_x(z^*(x))-G_x(z)\le\Delta,
$$
then
$$
\left|
\sum_a\mu_a\bigl[x_a+v_a\sqrt{z_a}\bigr]-M^+(x)
\right|
\le(12\Delta)^{1/4}.
$$
We prove that $M^+$ is monotone and satisfies
$$
M^+(x+te_i)-M^+(x)
\ge
M^+(y+te_i)-M^+(y)
$$
whenever $x\le y$, $t\ge0$, and both incremented controls belong to the cube.
First increase every bias by a fixed $\lambda>0$. Let
$$
A_{ab}=\mu_bK_{ab},\qquad
h=b+\lambda\mathbf1+Aq.
$$
At the nonnegative maximizer, every unpinned free magnetization lies strictly between zero and one. Indeed, its objective derivative is
$$
w_a\bigl(h_a-\operatorname{arctanh}r_a\bigr).
$$
It is positive at $r_a=0$, since $h_a\ge\lambda$, and tends to negative infinity as $r_a\uparrow1$. Stationarity gives $r=\tanh h$ on the unpinned coordinates. Accordingly, the magnetization satisfies
$$
q=x+(1-x)\odot\tanh(b+\lambda\mathbf1+Aq).
$$
This identity also holds on pinned coordinates.
Its Jacobian with respect to $q$ is
$$
J=\operatorname{diag}\bigl((1-x_a)(1-r_a^2)\bigr)A.
$$
It is entrywise nonnegative. Moreover,
$$
(q-Jq)_a
=x_a+(1-x_a)
\left[
\tanh h_a-(h_a-b_a-\lambda)\operatorname{sech}^2h_a
\right]>0.
$$
For an unpinned coordinate, this follows from $h_a>0$, $b_a+\lambda>0$, and
$$
\tanh h-h\operatorname{sech}^2h>0\qquad(h>0).
$$
The latter function vanishes at zero and has derivative
$$
2h\operatorname{sech}^2h\tanh h>0.
$$
For a pinned coordinate, $(q-Jq)_a=1$.
Because $q>0$, the weighted maximum norm
$$
\|u\|_q=\max_a\frac{|u_a|}{q_a}
$$
satisfies
$$
\|J\|_q\le\max_a\frac{(Jq)_a}{q_a}<1.
$$
It follows that
$$
(I-J)^{-1}=\sum_{k=0}^{\infty}J^k
$$
exists and is entrywise nonnegative.
The implicit-function theorem now applies on the interior of the control cube. Continuity of the equilibrium, already proved above and equally valid for the perturbed biases, identifies its local solution with the maximizing branch.
For a nonnegative control direction $u$, differentiating the equilibrium identity gives
$$
(I-J)q_u=u\odot(1-r).
$$
Thus $q_u\ge0$.
For two nonnegative directions $u,v$, a second differentiation gives
$$
(I-J)q_{uv}
=
-(1-r^2)\odot
\bigl[u\odot(Aq_v)+v\odot(Aq_u)\bigr]
-2(1-x)\odot r\odot(1-r^2)
\odot(Aq_u)\odot(Aq_v).
$$
Every term on the right is entrywise nonpositive. Therefore $q_{uv}\le0$.
In particular, every first coordinate derivative of every component of $q$ is nonnegative, and every second coordinate derivative, including a repeated-coordinate derivative, is nonpositive. The same statements hold for their positive weighted sum $M^+$.
Integrating the first derivatives proves monotonicity. The second-derivative signs show that $\partial_iM^+$ decreases when any control coordinate increases. Integrating $\partial_iM^+$ over an increment of length $t$ proves the stated diminishing-returns inequality in the interior.
Continuity extends these inequalities to the boundary. Explicitly, replace a boundary control $x$ by
$$
x^{(\delta)}=\delta\mathbf1+(1-2\delta)x
$$
and an increment $t$ by $(1-2\delta)t$, then let $\delta\downarrow0$.
For each fixed control, the perturbed and original concave objectives differ uniformly by at most $\lambda$, because their difference is
$$
\lambda\sum_a\mu_aq_a\in[0,\lambda].
$$
The original-objective gap at a perturbed maximizer is consequently at most $2\lambda$. The accuracy conversion from Section 3 shows that the corresponding magnetizations differ by at most
$$
(24\lambda)^{1/4}.
$$
They therefore converge to $M^+$ as $\lambda\downarrow0$.
Passing to the limit proves monotonicity and diminishing returns for the original biases on the entire cube.
The following lemma supplies the finite-precision guarantee needed for equilibrium evaluation.
Lemma. Let
$$
Q=[\rho,1-\rho]^n,\qquad 0<\rho\le\frac14,
$$
where $\rho$ is rational. Let $F$ be convex and differentiable on a neighborhood of $Q$, with Euclidean Lipschitz constant at most a known rational $H\ge1$. Suppose rational approximations to $F(c)$ and $\nabla F(c)$ at rational $c\in Q$ can be computed in polynomial time in the input and point encoding lengths and the requested number of accuracy bits.
For rational $0<\zeta\le1$, a deterministic algorithm returns rational $c\in Q$ satisfying
$$
F(c)\le\min_QF+2\zeta
$$
in polynomial bit time in those input lengths and $\log(1/\zeta)$.
Let $z^*$ minimize $F$ on $Q$, and let $c_0=\frac12\mathbf1$. Set
$$
t=\frac{\zeta}{8Hn},\qquad
z_0=(1-t)z^*+tc_0,\qquad
r=\frac{\zeta}{64Hn}=\frac t8.
$$
Each coordinate of $z_0$ is at distance at least $t/4$ from the boundary of $Q$. Therefore $B(z_0,r)\subseteq Q$.
The diameter of $Q$ is at most $n$. By Lipschitz continuity,
$$
F(z_0)-F(z^*)\le Htn=\frac{\zeta}{8}.
$$
Every point in $B(z_0,r)$ has additional objective increase at most
$$
Hr=\frac{\zeta}{64n}.
$$
Thus the convex sublevel set
$$
D=\{z\in Q:F(z)\le F(z^*)+\zeta/2\}
$$
contains a Euclidean ball of radius $r$.
Initialize an ellipsoid centered at $c_0$ with shape matrix $n^2I$. It contains $Q$.
At a current center $c$ outside $Q$, use a violated coordinate constraint to give a central halfspace containing $Q$.
At a center $c\in Q$, compute rational values $\widehat F(c)$ and $d$ satisfying
$$
|\widehat F(c)-F(c)|\le\frac{\zeta}{4},\qquad
\|d-\nabla F(c)\|_2\le\frac{\zeta}{8n}.
$$
Record this center and its approximate value. If $d=0$, convexity gives
$$
F(c)-F(z^*)
\le \nabla F(c)\cdot(c-z^*)
\le\frac{\zeta}{8},
$$
so return $c$. Otherwise use the central cut
$$
d\cdot(z-c)\le0.
$$
Suppose, for contradiction, that every recorded center has
$$
F(c)>F(z^*)+\zeta.
$$
For every $z\in D$, convexity then implies
$$
\nabla F(c)\cdot(z-c)
\le F(z)-F(c)<-\frac{\zeta}{2}.
$$
The gradient approximation changes this inner product by at most $\zeta/8$, because $\|z-c\|_2\le n$. Hence every such cut contains $D$. Cuts at infeasible centers contain $D$ as well.
We next show that a polynomial number of rationally rounded ellipsoid updates makes this impossible.
For $n\ge2$, write
$$
E(c,P)=\{z:(z-c)^\mathsf TP^{-1}(z-c)\le1\},
$$
with $P$ positive definite. For a nonzero cut normal $d$, the exact update is
$$
c'=c-\frac{Pd}{(n+1)\sqrt{d^\mathsf TPd}},
$$
$$
P'=\frac{n^2}{n^2-1}
\left(
P-\frac{2}{n+1}
\frac{Pdd^\mathsf TP}{d^\mathsf TPd}
\right).
$$
These formulas give an ellipsoid containing the retained half. To verify this, transform the original ellipsoid to the unit ball and the cut to its first coordinate being nonpositive. Write a point as $(u,w)$, where
$$
-1\le u\le0,\qquad \|w\|_2^2\le1-u^2.
$$
Its squared norm in the updated ellipsoid is at most
$$
\frac{(n+1)^2}{n^2}
\left(u+\frac1{n+1}\right)^2
+\frac{n^2-1}{n^2}(1-u^2)
=
1+\frac{2(n+1)}{n^2}u(u+1)
\le1.
$$
The volume ratio is
$$
\gamma_n=
\left(\frac{n^2}{n^2-1}\right)^{n/2}
\sqrt{\frac{n-1}{n+1}}.
$$
Expanding the logarithms gives
$$
\log\gamma_n
=
-\sum_{k=1}^{\infty}
\frac{1}{2k(2k-1)n^{2k-1}}
\le-\frac1{2n}.
$$
Also, Cauchy–Schwarz in the $P$ inner product gives
$$
\frac{n^2}{(n+1)^2}P
\preceq P'
\preceq\frac{n^2}{n^2-1}P.
$$
Choose an integer $q$ with $2^q\ge n/r$, and set
$$
T=8n^2(q+1),\qquad
\theta=\frac1{100n^2},\qquad
\ell=4^{-(T+1)}.
$$
Choose a fixed dyadic mesh $h$ satisfying
$$
h\le\frac{\theta\ell}{8n}.
$$
At each update, approximate and round $c'$ to a rational mesh point $\widetilde c$ so that
$$
\|\widetilde c-c'\|_2\le\theta\sqrt\ell.
$$
Round $P'$ symmetrically to a mesh matrix $D'$ so that
$$
\|D'-P'\|_{\mathrm{op}}\le\frac{\theta\ell}{2}.
$$
The chosen mesh permits both bounds. Replace the shape matrix by
$$
\widetilde P
=(1+\theta)^2
\left(D'+\frac{\theta\ell}{2}I\right).
$$
The exact-update spectral bounds and induction show that, during these $T$ updates, every $P'$ satisfies $P'\succeq\ell I$. Indeed, the minimum eigenvalue decreases at each exact update by a factor no smaller than $4/9$, and rounding as defined above does not decrease it.
Let
$$
S=D'+\frac{\theta\ell}{2}I.
$$
The rounding bounds give
$$
P'\preceq S\preceq P'+\theta\ell I
\preceq(1+\theta)P'.
$$
For a point $z\in E(c',P')$, the triangle inequality in the $S^{-1}$ norm gives
$$
\|z-\widetilde c\|_{S^{-1}}
\le1+\frac{\|\widetilde c-c'\|_2}{\sqrt\ell}
\le1+\theta.
$$
Therefore
$$
E(c',P')\subseteq E(\widetilde c,\widetilde P).
$$
Moreover,
$$
P'\preceq\widetilde P\preceq(1+\theta)^3P'.
$$
Thus rounding inflates volume by at most $(1+\theta)^{3n/2}$, and each rounded update decreases volume by a factor at most
$$
\exp\left(-\frac1{2n}+\frac{3n\theta}{2}\right)
\le\exp\left(-\frac1{4n}\right).
$$
After $T$ updates, the volume is less than that of a radius-$r$ ball, since
$$
T>4n^2\log(n/r).
$$
Under the contradiction assumption, every ellipsoid contains $D$, which contains such a ball. This is impossible.
Hence some recorded center has objective gap at most $\zeta$. Returning the recorded center with smallest approximate value gives true gap at most
$$
\zeta+2\left(\frac{\zeta}{4}\right)\le2\zeta.
$$
For $n=1$, use rational intervals and midpoint cuts instead. Each update halves the interval length, and the same preserved-sublevel argument applies.
Here $q$ and $T$ are polynomial in $n$, the encoding length of $H$, and $\log(1/\zeta)$. The quantities $\ell$ and $h$ therefore have polynomial encoding lengths.
The largest shape eigenvalue grows by a factor less than two per rounded update. Hence it is at most $n^22^T$. Each center displacement is bounded by the square root of the preceding largest eigenvalue, plus the rounding error. All center coordinates consequently have polynomially many magnitude bits. Rounding bounds their denominator lengths as well.
Each rounded shape matrix has polynomial encoding length. Computing the next rational $P'$ temporarily uses only polynomially many bits, followed by rounding back to the fixed mesh. The only irrational operation in the center update is a square root of a positive rational. Since that rational has polynomial encoding length, it can be approximated to the required mesh accuracy by bisection in polynomial bit time.
All oracle queries have polynomial encoding length and request polynomially many accuracy bits. Rational arithmetic, rounding, and comparisons likewise take polynomial time. This proves the lemma.
We apply the lemma to the convex minimization objective
$$
F=-G_x.
$$
Let $0<\rho\le1/4$. Clip every unpinned $z$ coordinate to $[\rho,1-\rho]$. Each square root changes by at most $\sqrt\rho$.
For $r,r'\in[0,1]$,
$$
|s(r)-s(r')|\le2\sqrt{|r-r'|}.
$$
To verify this, put $d=|r-r'|$. Since $|s'(r)|=\operatorname{arctanh}r$ is increasing, the largest entropy change over an interval of length $d$ occurs at the right endpoint and equals $s(1-d)$. With $t=d/2$, this is
$$
-t\log t-(1-t)\log(1-t).
$$
The inequalities
$$
-(1-t)\log(1-t)\le t,\qquad
t\log(1/t)\le\frac2e\sqrt t
$$
give the claimed bound. The second inequality follows by maximizing $u e^{-u/2}$ for $u=\log(1/t)$.
Thus clipping decreases $G_x$ by at most
$$
(\kappa+\beta)\sqrt\rho+2\rho^{1/4}
\le(\kappa+\beta+2)\rho^{1/4}.
$$
For a desired full-objective gap $\Delta$, choose dyadic $\rho$ satisfying
$$
\rho\le\frac14,\qquad
\rho\le
\left(\frac{\Delta}{2(\kappa+\beta+2)}\right)^4.
$$
The loss from clipping is then at most $\Delta/2$, and $\rho$ has polynomial encoding length in $L+\log(1/\Delta)$.
Drop fully pinned coordinates, and let $n$ be the remaining dimension. If $n=0$, the magnetization is exactly one.
For a remaining coordinate,
$$
\frac{\partial G_x}{\partial z_a}
=
\frac{w_a}{2\sqrt{z_a}}
\left[
b_a+\sum_b\mu_bK_{ab}q_b
-\operatorname{arctanh}\sqrt{z_a}
\right].
$$
Let
$$
U=\max_a\left(b_a+\sum_b\mu_bK_{ab}\right).
$$
On the truncated box, $\operatorname{arctanh}\sqrt{z_a}\le\log(4/\rho)$. A valid rational Euclidean Lipschitz bound is therefore
$$
H=\frac{n(U+4/\rho)}{\rho}.
$$
Its encoding length is polynomial.
Function values and gradients can be approximated in polynomial bit time. Square roots are computed by bisection. For logarithms of positive rationals, normalize the argument as $2^kt$ with $1\le t\le2$ and use
$$
\log t
=
2\sum_{j=0}^{\infty}
\frac{u^{2j+1}}{2j+1},
\qquad
u=\frac{t-1}{t+1}\in[0,1/3].
$$
The tail decreases geometrically; the same series computes $\log2$. The arguments in our objective and gradient are bounded away from their singularities by quantities with polynomial encoding length. Thus polynomially many guard bits suffice for all products, divisions, and sums.
The numerical lemma with $\zeta=\Delta/4$ returns a rational point whose truncated objective gap is at most $\Delta/2$. Including clipping loss, its full gap is at most $\Delta$.
Given rational $0<\eta<1$, take
$$
\Delta=\frac{\eta^4}{192}.
$$
The accuracy conversion in Section 3 gives magnetization error at most
$$
(12\Delta)^{1/4}=\frac{\eta}{2}.
$$
Compute the remaining square roots and weighted sum to error at most $\eta/2$, then clamp the rational answer to $[0,1]$.
This produces a deterministic rational oracle satisfying
$$
0\le\widehat M(x)\le1,\qquad
|\widehat M(x)-M^+(x)|\le\eta,
$$
in polynomial time in the input and control encoding lengths and $\log(1/\eta)$. Fix all rounding and tie choices, so repeated evaluations at the same control return the same value.
If $B=0$, positivity of the masses makes $x=0$ the only feasible control, so return it. Suppose henceforth that $B>0$.
The uniform control $x_a=B$ is feasible. Since $q_a^+(x)\ge x_a$,
$$
\mathrm{OPT}\ge B.
$$
Choose $p\ge1$ and $\delta=2^{-p}$ satisfying
$$
\delta\le\frac{\epsilon B}{8},\qquad
\delta\le\frac{(\epsilon B/8)^4}{24C}.
$$
Because positive rational $B$ has $\log(1/B)=O(L)$ and $C$ has magnitude at most $2^{O(L)}$, we can choose
$$
p=O(L+\log(1/\epsilon)).
$$
Round any control downward by
$$
\bar x_a
=
\delta\min\{\lfloor x_a/\delta\rfloor,\,2^p-1\}.
$$
The rounded control remains feasible, and $\|x-\bar x\|_\infty\le\delta$, including when $x_a=1$. The continuity bound proves
$$
M^+(x)-M^+(\bar x)\le\frac{\epsilon B}{4}.
$$
Introduce $N=\tau p$ items, indexed by $(a,j)$ for $0\le j<p$. Item $(a,j)$ contributes $\delta2^j$ to coordinate $a$ and has positive rational cost
$$
c_{a,j}=\mu_a\delta2^j.
$$
For a set $S$ of items, define
$$
x_a(S)=\sum_{j:(a,j)\in S}\delta2^j,\qquad
f(S)=M^+(x(S)).
$$
Every set gives a control in the cube, because the total contribution to a coordinate is $1-\delta$. Binary expansion represents every rounded control exactly.
The function $f$ is nonnegative and monotone. It is submodular because, for $S\subseteq T$ and an item $(a,j)\notin T$, fractional diminishing returns gives
$$
f(S\cup\{(a,j)\})-f(S)
\ge
f(T\cup\{(a,j)\})-f(T).
$$
Let $V$ be the optimal item-set value under budget $B$. Rounding an optimal original control shows
$$
V\ge\mathrm{OPT}-\frac{\epsilon B}{4}.
$$
Evaluations on item sets exceeding the budget use the established extension $M^+$, so they require no uniqueness promise outside the feasible region.
Set
$$
\eta=\frac{\epsilon B}{8(N^2+1)}.
$$
Use Section 6 to define a deterministic rational function $\widehat f$ satisfying
$$
0\le\widehat f(S)\le1,\qquad
|\widehat f(S)-f(S)|\le\eta.
$$
Approximate evaluations need not preserve submodularity. Define the corrected rational function
$$
g(S)=\widehat f(S)+2\eta|S|(2N-|S|).
$$
We verify that $g$ is exactly nonnegative, monotone, and submodular.
Nonnegativity is immediate. Adding an item changes $\widehat f$ by at least $-2\eta$, while the correction increases by
$$
2\eta(2N-2|S|-1)\ge2\eta.
$$
Thus $g$ is monotone.
For submodularity, comparable sets give exact cancellation. For incomparable $S,T$, put
$$
a=|S\setminus T|\ge1,\qquad b=|T\setminus S|\ge1.
$$
Expanding the quadratic correction shows that its contribution to
$$
g(S)+g(T)-g(S\cup T)-g(S\cap T)
$$
is $4\eta ab\ge4\eta$. The corresponding expression for $f$ is nonnegative, and the four evaluation errors contribute at worst $-4\eta$. Hence the expression for $g$ is nonnegative.
Also, for every set,
$$
f(S)-\eta
\le g(S)
\le f(S)+\eta+2\eta N^2.
$$
We now use the following precise external result: a nonnegative monotone submodular set function, supplied by exact value evaluations, admits a deterministic $(1-1/e)$ approximation under one knapsack constraint, using $O(N^5)$ value evaluations. This is [Sviridenko’s theorem](https://thibaut.horel.org/submodularity/papers/sviridenko2004.pdf).
All its hypotheses hold for $g$. Its oracle values are exact rationals, computable in polynomial time. Multiplying the rational costs and budget by their common denominator gives integer data of polynomial encoding length. The algorithm uses rational arithmetic and comparisons, so its remaining work also has polynomial bit complexity. Include the empty set when handling instances with fewer than three feasible items.
Write $\alpha=1-1/e$, and let $S$ be the theorem’s feasible output. Since $\max g\ge V-\eta$,
$$
\begin{aligned}
f(S)
&\ge g(S)-\eta-2\eta N^2\\
&\ge\alpha V-(\alpha+1+2N^2)\eta\\
&\ge\alpha V-\frac{\epsilon B}{4}.
\end{aligned}
$$
Combining this with the rounding bound gives
$$
\begin{aligned}
\mathcal M(x(S))
&=f(S)\\
&\ge\alpha\mathrm{OPT}
-\frac{(\alpha+1)\epsilon B}{4}\\
&\ge\alpha\mathrm{OPT}-\frac{\epsilon B}{2}\\
&\ge(\alpha-\epsilon)\mathrm{OPT},
\end{aligned}
$$
where the last inequality uses $B\le\mathrm{OPT}$.
The output $x(S)$ is rational and exactly feasible.
There are
$$
N=\tau\,O(L+\log(1/\epsilon))
$$
items. Their costs, the control coordinates, and all oracle values have polynomial encoding length. The requested evaluation precision has
$$
\log(1/\eta)
=
O\bigl(L+\log(1/\epsilon)+\log N\bigr)
$$
bits. Sections 5–6 establish polynomial bit-time evaluations, and the knapsack algorithm makes polynomially many of them.
Therefore the complete algorithm runs in time polynomial in the total input length, $\tau$, and $\log(1/\epsilon)$, and hence in the requested parameters $m,\tau,L,1/\epsilon$, since $m=\tau$.
No quantitative stability gap is required. The uniqueness promise identifies the computable nonnegative equilibrium with the task’s specified equilibrium on every feasible control.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The argument establishes the requested deterministic polynomial-time approximation under the uniqueness promise. I found no major or minor mathematical gaps. The numerical evaluation argument addresses finite precision, and the cited knapsack theorem applies to the corrected oracle function.
The conclusion concerns the requested approximation guarantee; it does not claim polynomial-time exact maximization of $\mathrm{OPT}$.
The replacement argument in Section 2.1 is valid. For $x_a,v_a\ge0$,
$$
x_a+v_a|r_a|\ge |x_a+v_ar_a|.
$$
The replacement makes every resulting magnetization nonnegative. Consequently, each interaction product increases or stays unchanged, whether its original value was positive or negative. Nonnegative biases ensure that the bias term does not decrease, and entropy is unchanged because it is even.
A nonnegative global maximizer therefore exists. The uniqueness promise identifies this maximizer with the prescribed equilibrium on every feasible control.
The expansion of $G_x$ is correct, including the coefficients of the linear square-root terms and the quadratic geometric-mean terms. Symmetry of $K$ is used correctly to combine the cross terms. The displayed geometric-mean inequality follows from Cauchy–Schwarz and establishes the required concavity.
The entropy expansion and its differentiated coefficients are correct:
$$
g''(z)
=
-\sum_{k=2}^{\infty}
\frac{k-1}{2(2k-1)}z^{k-2}
\le-\frac16.
$$
Termwise differentiation is valid on compact subintervals of $(0,1)$. Uniform convergence of the original series supplies continuity at the endpoints, allowing the strong-concavity inequality to extend there.
The resulting strong-concavity coefficient is correctly stated as
$$
\frac{t(1-t)}{12}\sum_a w_a(z_a-z'_a)^2.
$$
Positive weights on every unpinned coordinate yield uniqueness on those coordinates. Fully pinned coordinates contribute neither dependence on $z_a$ nor ambiguity in $q_a^+$.
The objective-gap bound follows correctly from maximality at the intermediate point and passage to the limit. This construction provides the extension $M^+$ on the entire cube without invoking the uniqueness promise outside the feasible region.
For fixed $z$, changing the control by at most $d$ changes each $q_a$ by at most $d$. Since these magnetizations belong to $[0,1]$, each interaction product changes by at most $2d$. The stated objective bound is therefore valid:
$$
|G_x(z)-G_y(z)|\le Cd.
$$
Combining this with the two maximization inequalities correctly gives an objective gap of at most $2Cd$, and hence
$$
\sum_a w_a(z_{x,a}-z_{y,a})^2\le24Cd.
$$
The square-root inequality and weighted Hölder inequality give the claimed fourth-root bound. The use of $\sum_a w_a\le1$ is correct, and no lower bound on the smallest positive weight is needed.
The componentwise continuity argument also covers fully pinned coordinates: their magnetizations converge to one because
$$
0\le1-q_a^+(y)\le1-y_a.
$$
Thus compactness of the feasible set legitimately establishes attainment of $\mathrm{OPT}$.
The separate accuracy conversion,
$$
|M_z(x)-M^+(x)|\le(12\Delta)^{1/4},
$$
follows from the same inequalities with the stated constant.
The positive-bias perturbation supplies the hypotheses needed for differentiation.
For every unpinned coordinate, the objective derivative is positive at zero and tends to negative infinity at one. Thus the maximizing free magnetization lies strictly inside $(0,1)$ and satisfies the displayed stationarity equation.
The Jacobian $J$ is correct. The calculation of $q-Jq$ is also correct, including the treatment of pinned coordinates. The displayed scalar derivative verifies the strict positivity needed to obtain
$$
\|J\|_q<1.
$$
Consequently, the Neumann series exists and is entrywise nonnegative.
The implicit-function theorem is applicable in the interior of the control cube: the equilibrium equations are smooth there and their derivative with respect to $q$ is invertible. Continuity of the maximizing branch identifies the local solution with the equilibrium being studied.
Both derivative formulas are correct. In particular:
Repeated-coordinate second derivatives are included, so the argument establishes diminishing returns even when two items later affect the same control coordinate.
Integration gives monotonicity and the stated finite-increment diminishing-returns inequality in the interior. The boundary approximation preserves coordinate ordering and scales the increment consistently, so continuity extends both conclusions to the whole cube.
Finally, the perturbation changes the objective uniformly by at most $\lambda$. The stated bound of $2\lambda$ on the original-objective gap is valid, and the accuracy conversion proves convergence of the perturbed magnetizations. Passing to the limit therefore establishes the required properties for the original biases, including cases with zero magnetizations or singular unperturbed linearization.
The lemma’s geometric and numerical arguments are valid.
The point $z_0$ has the claimed distance from the box boundary, and the chosen radius fits inside that margin. Both Lipschitz estimates are correct, so the good sublevel set contains the required ball.
The approximate-gradient cuts preserve that sublevel set under the contradiction assumption. The gradient error contributes at most $\zeta/8$ to the relevant inner product. The zero-gradient stopping case also has the claimed objective accuracy.
The central-cut ellipsoid formulas, containment calculation, volume ratio, logarithmic expansion, and spectral bounds are correct for $n\ge2$.
The rational rounding argument correctly maintains containment. In particular, the matrix rounding and added diagonal term ensure
$$
P'\preceq S\preceq(1+\theta)P',
$$
while the center error is absorbed by the subsequent inflation. The lower spectral bound is sufficient throughout the prescribed number of updates.
The inflation-adjusted volume decrease is valid. The chosen update count makes the final volume strictly smaller than that of the preserved radius-$r$ ball, producing the required contradiction.
Selecting the recorded center with the smallest approximate objective gives the stated $2\zeta$ accuracy. The one-dimensional interval version has the same preserved-sublevel argument.
The bit-complexity discussion adequately controls matrix magnitudes, denominators, intermediate arithmetic, square-root precision, and oracle-query lengths. None of the updates requires an unbounded-precision exact irrational computation.
The clipping estimates are correct. The entropy modulus follows from the increasing magnitude of its derivative and the displayed binary-entropy bounds. Its use after clipping yields precisely the stated fourth-root loss.
The selected $\rho$ makes the clipping loss at most $\Delta/2$ and requires only polynomially many encoding bits.
The gradient formula includes the self-interaction contribution correctly. The proposed rational $H$ bounds the Euclidean gradient norm on the truncated box and satisfies the numerical lemma’s requirements.
The logarithm series has geometrically decreasing tails after normalization. Together with rational approximations to square roots and polynomially bounded separation from singularities, this provides the required value and gradient oracles.
The numerical lemma contributes another objective loss of at most $\Delta/2$. With
$$
\Delta=\frac{\eta^4}{192},
$$
the magnetization conversion gives error $\eta/2$, leaving the stated allowance for numerical evaluation of the final square roots and sum. Clamping preserves the error bound.
The fully pinned case is explicitly handled. Fixing rounding and tie choices correctly makes the approximate oracle a well-defined deterministic set function.
The case $B=0$ is settled correctly. For $B>0$, the uniform control proves
$$
\mathrm{OPT}\ge B.
$$
This lower bound is sufficient for converting additive numerical losses into the final multiplicative guarantee.
Both restrictions on $\delta$ are used correctly: together they bound the rounding loss by $\epsilon B/4$. Downward rounding preserves feasibility, including coordinates originally equal to one.
The binary-item construction represents every rounded control exactly using $N=\tau p$ items. Every subset remains inside the control cube. Fractional diminishing returns establishes submodularity even for multiple items associated with the same type.
Rounding an optimal continuous control gives the stated lower bound on $V$. Evaluations of infeasible item sets legitimately use the previously established extension $M^+$.
The correction in Section 8 makes $g$ exactly nonnegative, monotone, and submodular despite the evaluation errors.
The minimum correction increment cancels the worst possible monotonicity error. For incomparable sets, its submodularity surplus is $4\eta ab$, which compensates for the worst four-value error. Comparable sets cancel identically. The uniform comparison bounds between $g$ and $f$ are also correct.
The cited theorem permits a nonnegative, nondecreasing submodular function with nonzero value at the empty set, and gives the stated guarantee with $O(N^5)$ evaluations. Its algorithm uses finite enumeration and greedy comparisons. These match the prover’s application. [Sviridenko’s paper](https://thibaut.horel.org/submodularity/papers/sviridenko2004.pdf)
Positive rational costs can be scaled to integers with polynomial encoding length. Exact rational evaluations of $g$ allow the required comparisons in polynomial bit time. Including the empty set covers instances with no feasible nonempty set.
The error arithmetic is correct:
$$
(\alpha+1+2N^2)\eta\le\frac{\epsilon B}{4}.
$$
Combining this loss with discretization yields the claimed approximation, using $B\le\mathrm{OPT}$. The output control is rational and exactly feasible.
The number of items, precision requirements, oracle running times, and knapsack operations are polynomial in the stated input parameters. The construction does not require a quantitative stability gap.
No blocking issue remains.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.