OctoInformBeta

OpenAI preprint, September 2026 · §2. Constructing the signed walk · §2.1

§2.1 (setting): diagonal Dirichlet energy, eq. (dirichlet-energy), and the bound (all-diagonal-energy): A symmetric convex body KK is good when its compressed heat operators have norm at least e−∑ivi/20000e^{-\sum_i v_i/20000} for every weight vv

Convex bodies that diagonal heat flow drains slowly.

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

Given vectors u0,…,uN−1u_0, \dots, u_{N-1} in ℝd\mathbb{R}^d, balancing with signed prefix sums asks for signs εi∈{−1,1}\varepsilon_i \in \{-1, 1\} that keep every prefix ∑i<kεiui\sum_{i<k} \varepsilon_i u_i, for k≤Nk \le N, inside a fixed convex body. The construction of the signed walk is set in a coefficient space ℝι\mathbb{R}^\iota, the Euclidean space with one coordinate for each element of a finite index set ι\iota, around a convex body KK there that Gaussian steps leave only slowly.

How slowly is measured by heat flow with a diagonal covariance. For a weight v=(vi)i∈ιv = (v_i)_{i \in \iota} with every vi≥0v_i \ge 0, smooth a function supported in KK by the centered Gaussian whose coordinates are independent with variances viv_i, then cut the result back to KK. The question is how large a share of its L2L^2 norm a function can keep through these two steps as the total variance ∑ivi\sum_i v_i grows.

Heat Operators on L2L^2

Let (X,μ)(X, \mu) be a measure space and L2(μ)L^2(\mu) the space of complex square-integrable functions on XX. For a measurable function m:X→ℂm : X \to \mathbb{C} with |m|≤C|m| \le C almost everywhere, the multiplication operator MmM_m is the bounded operator f↦mff \mapsto mf on L2(μ)L^2(\mu).✦ The mask PDP_D of a measurable set D⊆XD \subseteq X is the multiplication operator by the indicator of DD: PDf=𝟏Df.P_D f = \mathbf{1}_D f.(1)✦

A function f∈L2(μ)f \in L^2(\mu) is supported on a set D⊆XD \subseteq X when it vanishes almost everywhere outside DD, and L2(D)L^2(D) is the set of these functions: L2(D)={f∈L2(μ):f(x)=0 for almost every x∉D}.L^2(D) = \{ f \in L^2(\mu) : f(x) = 0 \text{ for almost every } x \notin D \}.(2)✦

Now let EE be a Euclidean space with Lebesgue measure, and ℱ:f↦fˆ\mathcal{F} : f \mapsto \hat f the Fourier transform, an isometry of L2(E)L^2(E) onto itself. For a measurable function m:E→ℝm : E \to \mathbb{R} with |m|≤1|m| \le 1, the Fourier multiplier with symbol mm is the operator Tm=ℱ−1Mmℱ.T_m = \mathcal{F}^{-1} M_m \mathcal{F}.(3)✦ The heat operator of a measurable function w:E→ℝw : E \to \mathbb{R} with w≥0w \ge 0 is the Fourier multiplier with symbol e−we^{-w}, Hw=Te−w,H_w = T_{e^{-w}},(4)✦ and its compression to a measurable set D⊆ED \subseteq E is the operator HwD=PDHwPD.H^D_w = P_D H_w P_D.(5)✦

For a function w:E→ℝw : E \to \mathbb{R}, the heat energy of f∈L2(E)f \in L^2(E) is ℰw(f)=∫E(1−e−w(ξ))|fˆ(ξ)|2dξ,\mathcal{E}_w(f) = \int_E \bigl(1 - e^{-w(\xi)}\bigr) \, |\hat f(\xi)|^2 \, d\xi,(6)✦ the analogue, for the heat operator HwH_w, of a Dirichlet form.

On the coefficient space ℝι\mathbb{R}^\iota, a weight is a family v=(vi)i∈ιv = (v_i)_{i \in \iota} of reals vi≥0v_i \ge 0, and the Gaussian symbol of vv is the function σv(ξ)=12∑i∈ιvi(2πξi)2,ξ∈ℝι.\sigma_v(\xi) = \frac{1}{2} \sum_{i \in \iota} v_i \, (2\pi \xi_i)^2, \qquad \xi \in \mathbb{R}^\iota.(7)✦

The Definition

Definition 1. Let D⊆ℝιD \subseteq \mathbb{R}^\iota be a measurable set and cc a real number. The set DD satisfies the diagonal energy bound with constant cc when, for every weight vv, the compression to DD of the heat operator of the Gaussian symbol has operator norm on L2(ℝι)L^2(\mathbb{R}^\iota) ∥HσvD∥≥exp⁡(−c2∑i∈ιvi).\bigl\| H^D_{\sigma_v} \bigr\| \ge \exp\Bigl( -\frac{c}{2} \sum_{i \in \iota} v_i \Bigr).(8)✦ A good convex body is a set K⊆ℝιK \subseteq \mathbb{R}^\iota that is nonempty, open, bounded, convex and centrally symmetric, and that satisfies the diagonal energy bound with constant 1/100001/10000: −K=K,∥HσvK∥≥exp⁡(−120000∑i∈ιvi) for every weight v.-K = K, \qquad \bigl\| H^K_{\sigma_v} \bigr\| \ge \exp\Bigl( -\frac{1}{20000} \sum_{i \in \iota} v_i \Bigr) \text{ for every weight } v.(9)✦

In the paper, the result reads: for a bounded open convex set DD and a positive definite diagonal matrix QQ, the diagonal Dirichlet energy is λQ(D)=inf⁡{∫D⟨Q∇g,∇g⟩/∫Dg2:0≠g∈H01(D)}\lambda_Q(D) = \inf \{ \int_D \langle Q \nabla g, \nabla g \rangle / \int_D g^2 : 0 \ne g \in H^1_0(D) \}, the constants are κ=1/100\kappa = 1/100 and δ=1/4\delta = 1/4, and the body KK is required to satisfy λQ(K)≤κ2tr⁡Q\lambda_Q(K) \le \kappa^2 \operatorname{tr} Q for every such QQ. Writing Q=diag⁡(v)Q = \operatorname{diag}(v), so that tr⁡Q=∑ivi\operatorname{tr} Q = \sum_i v_i, the bound (8) takes the place of the condition λQ(D)≤ctr⁡Q\lambda_Q(D) \le c \operatorname{tr} Q, with c=κ2c = \kappa^2 for a good convex body.

What Is Checked

The diagonal energy bound and good convex bodies are stated over the coefficient space ℝι\mathbb{R}^\iota with Lebesgue measure and the space L2(ℝι)L^2(\mathbb{R}^\iota) with its Fourier transform, through the mask (1), the heat operator (4) with its compression (5), and the Gaussian symbol (7).

About these constructions the library proves that the Gaussian symbol is nonnegative✦, and that for a measurable mm with |m|≤C|m| \le C almost everywhere and any f∈L2(μ)f \in L^2(\mu) the product mfmf lies in L2(μ)L^2(\mu)✦ with ∥mf∥≤C∥f∥\|mf\| \le C \|f\|✦.