d4-conf-sagt-2012-0017 (d4-conf-sagt-2012-0017)

Given two types of equal mass, each with belief \(1/2\), and symmetric cross-type interaction \(J_{AB}=J_{BA}=2\), let \(F_\beta\) be the stated mean-field free energy. Given rational \(\beta\), rational boxes isolating two distinct local minima \(q^-,q^+\in[0,1]^2\), and additive error \(\epsilon>0\), compute an additive-\(\epsilon\) approximation to the minimum, over continuous paths joining those minima, of the maximum \(F_\beta\) along the path minus the lower endpoint value.

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible types. Here \(\tau=2\), the number of available opinions is \(m=2\), and the types \(A,B\) each have mass \(1/2\) and belief \(1/2\).
Let \(q_a\in[0,1]\) be the fraction of type \(a\) expressing opinion \(1\). There are no within-type interactions, and \(J_{AB}=J_{BA}=2\); each unordered interaction is counted once.
Define \(h(u)=u\log u+(1-u)\log(1-u)\), using natural logarithms and \(0\log0=0\), and \(F_\beta(q)=\frac14+\frac12[q_A(1-q_B)+q_B(1-q_A)]+\frac{h(q_A)+h(q_B)}{2\beta}\).
The input consists of binary rationals \(\beta>0\), \(0<\epsilon<1\), and two disjoint closed rational boxes in \([0,1]^2\), each promised to contain exactly one local minimum of \(F_\beta\), denoted \(q^-\) and \(q^+\). Let \(L\) be the total input bit length.
Define \(\Delta_\beta=\inf_{\gamma}\max_{t\in[0,1]}F_\beta(\gamma(t))-\min\{F_\beta(q^-),F_\beta(q^+)\}\), where \(\gamma:[0,1]\to[0,1]^2\) is continuous with \(\gamma(0)=q^-\) and \(\gamma(1)=q^+\).

Is computing an additive-\(\epsilon\) approximation to \(\Delta_\beta\) possible in time polynomial in \(m,\tau,L\), or is this promised approximation problem NP-hard?

For discrete binary opinion games on \(K_{r,r}\), suitable beliefs and weights give logit mixing time \(t_{\mathrm{mix}}\ge e^{\beta\Theta(\mathrm{CW})}/(2r)\) for \(\beta\ge C/r\), with an absolute sufficiently large constant \(C\); this is a mixing-time bound. [Ferraioli–Goldberg–Ventre](https://www.cs.ox.ac.uk/people/paul.goldberg/papers/fgv-tcs16.pdf)
Macroscopic limits of two-population Curie–Weiss dynamics are known; the search located no complexity classification for the precise promised barrier-approximation problem above. [Collet](https://arxiv.org/abs/1406.4044)

Result

The promised problem is polynomial-time solvable in the ordinary bit model. Below is an exact formula for the barrier and a deterministic algorithm computing it to additive error \(\epsilon\) in time polynomial in \(L\). Since \(m=\tau=2\), this is polynomial in \(m,\tau,L\).

1. Classifying the local minima

Introduce coordinates \(x=2q_A-1\), \(y=2q_B-1\), and define \(g(x)=h((1+x)/2)\). The objective becomes

\(\displaystyle \widetilde F_\beta(x,y)=\frac12-\frac{xy}{4}+\frac{g(x)+g(y)}{2\beta},\qquad (x,y)\in[-1,1]^2.\)

The function \(g\) is even, and on \((-1,1)\),

\(\displaystyle g'(x)=\operatorname{arctanh}x,\qquad g''(x)=\frac{1}{1-x^2},\qquad g(0)=-\log 2.\)

There are no boundary local minima. Indeed, move any boundary coordinate \(q_a\) inward by \(\delta>0\). The interaction term changes by at most \(\delta/2\) in absolute value. The entropy contribution changes by \(h(\delta)/(2\beta)\), and

\(\displaystyle \frac{h(\delta)}{\delta}=\log\delta+\frac{1-\delta}{\delta}\log(1-\delta)\longrightarrow-\infty.\)

Thus the total objective decreases for sufficiently small \(\delta\).

Consequently every local minimum is an interior stationary point. Write \(k=\beta/2\). The stationary equations are

\(\displaystyle \operatorname{arctanh}x=ky,\qquad \operatorname{arctanh}y=kx.\)

They force \(x=y\): if \(x>y\), monotonicity of \(\operatorname{arctanh}\) gives \(\operatorname{arctanh}x>\operatorname{arctanh}y\), whereas the equations give the opposite inequality. The case \(x<y\) is identical.

For \(0<t<1\), define

\(\displaystyle f(t)=\frac{\operatorname{arctanh}t}{t}=\int_0^1\frac{dv}{1-t^2v^2}.\)

This integral shows that \(f\) is strictly increasing. Moreover, \(f(0+)=1\) and \(f(1-)=+\infty\).

If \(\beta\le 2\), the only stationary point is \((0,0)\). There can therefore be at most one local minimum, contradicting the promise of two minima in disjoint boxes. Hence every promised input satisfies \(\beta>2\).

For \(\beta>2\), there is a unique \(s\in(0,1)\) satisfying

\(\displaystyle f(s)=k,\qquad\text{equivalently}\qquad \operatorname{arctanh}s=\frac{\beta s}{2}.\)

The stationary points are exactly \((0,0)\), \((s,s)\), and \((-s,-s)\).

At either nonzero stationary point, the Hessian eigenvalues are

\(\displaystyle \lambda_\pm=\frac{1}{2\beta(1-s^2)}\pm\frac14.\)

Both are positive because

\(\displaystyle \frac{\beta}{2}=f(s)=\int_0^1\frac{dv}{1-s^2v^2}<\frac{1}{1-s^2}.\)

Thus \((s,s)\) and \((-s,-s)\) are strict local minima. At \((0,0)\), the Hessian eigenvalue in the diagonal direction is \(1/(2\beta)-1/4<0\), so this point is not a local minimum.

Therefore the promised minima, in either labeling, are precisely

\(\displaystyle \left(\frac{1-s}{2},\frac{1-s}{2}\right)\quad\text{and}\quad\left(\frac{1+s}{2},\frac{1+s}{2}\right).\)

Their energies are equal. In particular, the boxes need not be used beyond their promise.

2. Computing the exact path barrier

Set

\(\displaystyle C_\beta=\widetilde F_\beta(0,0)=\frac12-\frac{\log 2}{\beta}.\)

Every continuous path between \((-s,-s)\) and \((s,s)\) crosses the line \(x+y=0\), by the intermediate value theorem. On that line, evenness of \(g\) gives

\(\displaystyle \widetilde F_\beta(x,-x)=\frac12+\frac{x^2}{4}+\frac{g(x)}{\beta}\ge\frac12-\frac{\log 2}{\beta}=C_\beta.\)

Here \(g(x)\ge g(0)=-\log 2\), since \(g'(x)=\operatorname{arctanh}x\). Thus every admissible path has maximum energy at least \(C_\beta\).

For the matching upper bound, use the diagonal path. Define

\(\displaystyle \phi_\beta(u)=\widetilde F_\beta(u,u)=\frac12-\frac{u^2}{4}+\frac{g(u)}{\beta}.\)

For \(0<u<s\),

\(\displaystyle \phi_\beta'(u)=\frac{u}{\beta}\bigl(f(u)-k\bigr)<0.\)

Since \(\phi_\beta\) is even, its maximum on \([-s,s]\) is \(\phi_\beta(0)=C_\beta\). The diagonal path therefore attains the lower bound.

Consequently,

\(\displaystyle \boxed{\Delta_\beta=C_\beta-\phi_\beta(s)=\frac{s^2}{4}-\frac{g(s)+\log 2}{\beta}.}\)

This is an exact characterization of the requested barrier.

3. A polynomial-time approximation algorithm

It remains to justify polynomial bit complexity. In particular, we must avoid exact comparisons between transcendental quantities.

3.1 Rational logarithms can be approximated efficiently

For a positive rational \(z\) of bit length \(b\), an approximation to \(\log z\) with error at most \(2^{-p}\) can be computed in time polynomial in \(b+p\).

Here is a direct construction. Choose an integer \(e\) such that \(w=z2^{-e}\in[1,2)\). Then \(|e|=O(b)\). Put \(v=(w-1)/(w+1)\), so \(0\le v<1/3\), and use

\(\displaystyle \log w=2\sum_{j=0}^{\infty}\frac{v^{2j+1}}{2j+1}.\)

The remainder after \(M\) terms is bounded by

\(\displaystyle 2\sum_{j=M}^{\infty}\frac{v^{2j+1}}{2j+1}\le\frac{2v^{2M+1}}{(2M+1)(1-v^2)}\le 3^{-2M}.\)

The same bound applies to the corresponding expansion of \(\log 2\), where \(v=1/3\). Therefore \(\log z=e\log 2+\log w\) is approximated to the required accuracy using \(M=O(p+\log(b+1))\) terms. Exact rational arithmetic on these finite sums has polynomial bit complexity: both the number of operations and the lengths of the intermediate numerators and denominators are polynomial in \(b+p\).

3.2 Bisection with certified errors

Let \(\eta=\epsilon/16\). Maintain a bracket \([a,b]\subseteq[0,1]\) containing \(s\), initially \([0,1]\).

At its midpoint \(t\), compute a rational \(\widehat f(t)\) satisfying

\(\displaystyle |\widehat f(t)-f(t)|\le\eta.\)

Use these rules:

• If \(\widehat f(t)+\eta<k\), replace \(a\) by \(t\).
• If \(\widehat f(t)-\eta>k\), replace \(b\) by \(t\).
• Otherwise, stop and use \(t\).

The two bracket updates are valid by strict monotonicity of \(f\).

If the algorithm stops in the third case, then \(|f(t)-k|\le2\eta\). For every \(u\) between \(t\) and \(s\), monotonicity and \(f(s)=k\) imply \(|f(u)-k|\le2\eta\). Hence

\(\displaystyle |\phi_\beta'(u)|=\frac{u}{\beta}|f(u)-k|\le\frac{2\eta}{\beta}.\)

Integrating over an interval of length at most one gives

\(\displaystyle |\phi_\beta(t)-\phi_\beta(s)|\le\frac{2\eta}{\beta}<\eta=\frac{\epsilon}{16}.\)

Thus an uncertain comparison already provides sufficient accuracy in the minimum’s value, regardless of the root’s conditioning.

3.3 Bounding the number of iterations

We also need a stopping guarantee when every comparison is certified.

For \(u,v\in[0,1]\) with \(|u-v|\le\delta\le1\), monotonicity of \(g'\) yields

\(\displaystyle |g(u)-g(v)|\le\int_{1-\delta}^1\operatorname{arctanh}z\,dz\le\frac{\delta}{2}\left(\log\frac{2}{\delta}+1\right).\)

The last inequality follows from \(\operatorname{arctanh}z\le\frac12\log(2/(1-z))\). Since \(\beta>2\),

\(\displaystyle |\phi_\beta(u)-\phi_\beta(v)|\le\frac{\delta}{2}+\frac{\delta}{4}\left(\log\frac{2}{\delta}+1\right).\)

Let \(K\) be the least integer with \(2^{-K}\le\epsilon\), and perform at most \(N=2K+8\) bisection steps. If there is no early stop, take the final bracket’s midpoint \(t\). Then \(|t-s|\le2^{-N}\), and the preceding bound gives

\(\displaystyle |\phi_\beta(t)-\phi_\beta(s)|\le\frac{2^{-N}(N+4)}4\le\frac{\epsilon}{64}.\)

For the final inequality, use \(N=2K+8\), \(2K+12\le16\cdot2^K\), and \(2^{-K}\le\epsilon\).

Thus, in either stopping case, the selected rational \(t\) satisfies

\(\displaystyle |\phi_\beta(t)-\phi_\beta(s)|\le\frac{\epsilon}{16}.\)

3.4 Evaluating the barrier and checking complexity

Evaluate

\(\displaystyle D(t)=\frac{t^2}{4}-\frac{g(t)+\log 2}{\beta}.\)

Approximate each logarithm used in \(g(t)\), and \(\log 2\), to error at most \(\epsilon/16\). The coefficients in \(g(t)\) are nonnegative and sum to one, so its evaluation error is at most \(\epsilon/16\). The resulting rational output \(\widehat D\) therefore satisfies

\(\displaystyle |\widehat D-D(t)|\le\frac{\epsilon}{8\beta}<\frac{\epsilon}{16}.\)

Combining the evaluation and optimization errors,

\(\displaystyle |\widehat D-\Delta_\beta|\le|\widehat D-D(t)|+|\phi_\beta(t)-\phi_\beta(s)|<\frac{\epsilon}{8}<\epsilon.\)

Finally, \(K=O(L)\), because \(\epsilon\) is an explicitly encoded binary rational. There are \(O(L)\) iterations, and every midpoint has \(O(L)\) bits. To approximate

\(\displaystyle f(t)=\frac{1}{2t}\log\frac{1+t}{1-t}\)

within \(\eta\), it suffices to approximate the logarithm within \(2t\eta\). Each tested midpoint satisfies \(t\ge2^{-N}\), so the required number of precision bits is \(O(N+\log(1/\epsilon))=O(L)\). All logarithm arguments and rational comparisons likewise have polynomial bit length.

The entire algorithm therefore runs in polynomial time in \(L\), including when \(\beta\) is extremely close to \(2\) or very large.

4. Scope of the conclusion

This settles the precise promised problem with \(m=\tau=2\); it does not classify barrier computation when these parameters vary.

The supplied [Ferraioli–Goldberg–Ventre paper](https://www.cs.ox.ac.uk/people/paul.goldberg/papers/fgv-tcs16.pdf) studies convergence and mixing times of discrete opinion dynamics, while [Collet](https://arxiv.org/abs/1406.4044) studies a macroscopic limit of a bipartite Curie–Weiss model. A mixing-time lower bound does not establish computational hardness of evaluating this barrier. Here the explicit barrier formula and the certified numerical algorithm establish polynomial-time solvability.

⟨structured verdict parsed — rendered above⟩

The prover resolves the promised problem correctly: the barrier admits the stated exact formula, and the proposed algorithm approximates it in polynomial bit complexity. I found no mathematical errors or gaps requiring clarification.

• Coordinate transformation and derivatives

Substituting \(q_A=(1+x)/2\) and \(q_B=(1+y)/2\) gives
\[ \widetilde F_\beta(x,y)=\frac12-\frac{xy}{4}+\frac{g(x)+g(y)}{2\beta}. \]
The constant and interaction coefficient are correct. The stated identities for \(g'\), \(g''\), and \(g(0)\) are also correct on their specified domains.

• Exclusion of boundary local minima

Moving one boundary coordinate inward by \(\delta\) changes the interaction term by at most \(\delta/2\). Its entropy changes from zero to \(h(\delta)\), whether the coordinate originally equals zero or one.

The displayed limit \(h(\delta)/\delta\to-\infty\) therefore proves that the objective decreases for sufficiently small positive \(\delta\), for every fixed finite \(\beta>0\). This covers edges and corners and excludes local minima relative to the closed square.

• Stationary points and the implication of the promise

The stationary equations have the correct coefficients:
\[ \operatorname{arctanh}x=ky,\qquad \operatorname{arctanh}y=kx,\qquad k=\beta/2. \]
Since \(k>0\), the monotonicity argument forcing \(x=y\) is valid.

The integral representation of \(f(t)\) is correct for \(0<t<1\). It establishes strict monotonicity, and the stated endpoint limits establish the asserted root count. Oddness of \(\operatorname{arctanh}\) supplies the corresponding negative root.

When \(\beta\le2\), there is only one possible local minimum because there is only one stationary point and no boundary local minima. The disjoint boxes promised to contain local minima consequently force \(\beta>2\). No classification of the degenerate stationary point at \(\beta=2\) is needed for this implication.

• Classification of the nonzero stationary points

The Hessian eigenvalues are correctly computed as
\[ \frac{1}{2\beta(1-s^2)}\pm\frac14. \]
The strict integral inequality gives
\[ \frac{\beta}{2}<\frac{1}{1-s^2}, \]
which makes the smaller eigenvalue positive. Thus both nonzero stationary points are strict local minima.

At the origin, the diagonal eigenvalue is negative for \(\beta>2\), excluding a local minimum there. Combined with the preceding exhaustive stationary-point classification, this proves that the promised boxes identify exactly the two stated minima. Their equal energies follow from simultaneous sign symmetry.

• Lower bound on every path

Along any admissible continuous path, \(x+y\) changes sign between the endpoints. The intermediate value theorem applies and forces a crossing of \(x+y=0\).

On that line,
\[ \widetilde F_\beta(x,-x) =\frac12+\frac{x^2}{4}+\frac{g(x)}{\beta} \ge C_\beta. \]
The inequality \(g(x)\ge g(0)\) holds throughout the closed interval by the stated derivative and continuity at the endpoints. Hence every path has maximum energy at least \(C_\beta\).

• Matching path and exact barrier

The derivative
\[ \phi_\beta'(u)=\frac{u}{\beta}\bigl(f(u)-k\bigr) \]
is correct. Strict monotonicity of \(f\) makes it negative on \(0<u<s\). Evenness then places the maximum of the diagonal path at zero.

This path attains the lower bound, so the minimax energy is exactly \(C_\beta\). Subtracting the common minimum energy gives precisely
\[ \Delta_\beta =\frac{s^2}{4}-\frac{g(s)+\log2}{\beta}. \]

• Polynomial-time logarithm evaluation

The scaling \(z=2^e w\), with \(1\le w<2\), has \(|e|=O(b)\). The logarithmic series and its remainder bound are correct, including the use of \(v=1/3\) for \(\log2\).

Taking \(M=O(p+\log(b+1))\) controls the error after multiplication by \(e\). Exact rational evaluation has polynomial complexity: the number of terms is polynomial, and the numerator and denominator lengths remain polynomial in \(b+p\). The argument establishes the claimed logarithm subroutine without relying on an unstated computational theorem.

• Certified bisection and uncertain comparisons

Both certified update rules preserve the root bracket.

If neither update applies, the approximation guarantee implies \(|f(t)-k|\le2\eta\). Monotonicity bounds the same residual throughout the interval between \(t\) and \(s\). Integrating the resulting derivative bound yields
\[ |\phi_\beta(t)-\phi_\beta(s)| \le\frac{2\eta}{\beta}<\eta. \]
This argument controls the minimum’s value without assuming a well-conditioned root. All points in this integration interval lie strictly between zero and one.

• Iteration bound and constants

The entropy modulus bound is valid: \(g'\) is nonnegative and increasing on \([0,1)\), so an interval of length at most \(\delta\) has its largest integral adjacent to one. The logarithmic upper bound remains integrable there.

The quadratic term contributes at most \(\delta/2\), and \(\beta>2\) gives the stated total modulus.

With \(\delta=2^{-N}\), its bound is at most
\[ \frac{2^{-N}(N+4)}4. \]
For \(N=2K+8\), the cited inequality \(2K+12\le16\cdot2^K\) holds for every \(K\ge1\), the range guaranteed by \(0<\epsilon<1\). It gives the claimed bound \(\epsilon/64\). Thus the fixed iteration cap is sufficient.

• Final evaluation and total bit complexity

Every selected midpoint lies strictly inside \((0,1)\), so the final logarithm arguments are positive. The coefficients in \(g(t)\) are nonnegative and sum to one, making the stated evaluation-error bound valid.

Since \(D(t)=C_\beta-\phi_\beta(t)\), the optimization error transfers directly to the barrier estimate. Combining the two errors establishes the promised additive accuracy.

For explicit binary rational input, \(K=O(L)\). Tested midpoints have polynomial bit length and satisfy the stated lower bound on \(t\), so approximating the logarithm to error \(2t\eta\) requires only \(O(L)\) precision bits. The final midpoint and its logarithm arguments also have \(O(L)\) bit length. Rational arithmetic involving \(\beta\) remains polynomial even when its numerical value is large. The complexity claim is therefore justified.

• Scope and cited context

The conclusion applies to the fixed promised instance family with \(m=\tau=2\); it does not assert a classification for varying dimensions. The descriptions of the supplied papers agree with their stated subjects: [Ferraioli–Goldberg–Ventre](https://www.cs.ox.ac.uk/people/paul.goldberg/papers/fgv-tcs16.pdf) study discrete opinion dynamics and mixing, while [Collet](https://arxiv.org/abs/1406.4044) studies macroscopic limits of a bipartite Curie–Weiss model. Neither paper is used as a mathematical premise in the barrier proof.

Required repair or clarification: none.

⟨structured verdict parsed — rendered above⟩