OctoInformBeta

OpenAI preprint, September 2026 · Section 2. An extremal weight and its cross-mass bound

Lemma 2.1: Stationary coordinates and an exact identity for the potential gap

The graph potential has a global maximizer.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let G=(V,E)G=(V,E) be a finite simple graph. The variational problem assigns real weights to vertices and couples a logarithmic vertex contribution with a penalty for weight on adjacent vertices.

A real vertex weight ww on GG is a function w:V→ℝw:V\to\mathbb R. The neighborhood NG(v)N_G(v) of a vertex vv is the set of vertices adjacent to vv.✦ The vertex mass w(S)w(S) of a set S⊆VS\subseteq V and the neighborhood mass w(NG(v))w(N_G(v)) are the sums in (1): w(S)=∑u∈Swu,w(NG(v))=∑u∈NG(v)wu.w(S)=\sum_{u\in S}w_u, \qquad w(N_G(v))=\sum_{u\in N_G(v)}w_u.(1)

For vertex sets S,D⊆VS,D\subseteq V, the cross mass ew(S,D)e_w(S,D) is the ordered edge sum in (2); the sets SS and DD may overlap: ew(S,D)=∑u∈S∑v∈D{u,v}∈Ewuwv.e_w(S,D)=\sum_{u\in S}\ \sum_{\substack{v\in D\\ \{u,v\}\in E}}w_uw_v.(2)✦ The unordered edge mass MG(w)M_G(w) is the sum of endpoint products over unordered edges, as in (3): MG(w)=∑{u,v}∈Ewuwv=12ew(V,V).M_G(w)=\sum_{\{u,v\}\in E}w_uw_v=\frac12 e_w(V,V).(3)✦

The vertex potential ϕ:ℝ→ℝ\phi:\mathbb R\to\mathbb R and the graph potential FG:ℝV→ℝF_G:\mathbb R^V\to\mathbb R are the functions in (4). All logarithms are natural, with the convention 0log⁡0=00\log0=0: ϕ(t)={t(1−log⁡|t|),t≠0,0,t=0,FG(w)=∑v∈Vϕ(wv)−MG(w).\phi(t)= \begin{cases} t(1-\log|t|),&t\ne0,\\ 0,&t=0, \end{cases} \qquad F_G(w)=\sum_{v\in V}\phi(w_v)-M_G(w).(4) An optimizer ww for GG is a real vertex weight that is nonnegative at every vertex and satisfies (5): FG(q)≤FG(w)for every q∈[0,∞)V.F_G(q)\le F_G(w) \qquad\text{for every }q\in[0,\infty)^V.(5)

The Claim

Theorem 1. Let GG be a finite simple graph. Then there exists a real vertex weight w that is an optimizer for G.\text{there exists a real vertex weight $w$ that is an optimizer for $G$.}(6)✦ Let ww be an optimizer for GG. For every vertex v∈Vv\in V, 0<wv≤1,log⁡(1/wv)=w(NG(v)).0<w_v\le1, \qquad \log(1/w_v)=w(N_G(v)).(7)✦ For every nonnegative real vertex weight qq, 0≤FG(w)−FG(q)=∑v∈V(qvlog⁡(qv/wv)−qv+wv)+MG(q−w).0\le F_G(w)-F_G(q) =\sum_{v\in V}\bigl(q_v\log(q_v/w_v)-q_v+w_v\bigr)+M_G(q-w).(8)✦

In the paper, the result reads: for every nonempty finite simple graph GG, FGF_G attains its maximum, every maximizer ww has wv>0w_v>0, log⁡(1/wv)=w(NG(v))\log(1/w_v)=w(N_G(v)) and wv≤1w_v\le1 for every v∈Vv\in V, and every nonnegative real weight qq satisfies 0≤FG(w)−FG(q)=∑v∈V(qvlog⁡(qv/wv)−qv+wv)+MG(q−w)0\le F_G(w)-F_G(q)=\sum_{v\in V}(q_v\log(q_v/w_v)-q_v+w_v)+M_G(q-w), where the summand is wvw_v when qv=0q_v=0.

What Is Checked

The assertions (6), (7) and (8) are stated over finite simple graphs and real vertex weights, with competitor weights qq restricted to be nonnegative.