OctoInformBeta

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

Proposition 2.1 [Signs with adaptive shifts]: Whatever the shifts |qi|≤1/4|q_i| \le 1/4, each depending on the current point, signs εi∈{−1,1}\varepsilon_i \in \{-1, 1\} end the walk from the origin in the domain

Signs bring walks with small adaptive shifts into good domains.

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 ι\iota be a finite set of coordinates and K⊂ℝιK \subset \mathbb{R}^\iota a convex body. A walk starts at the origin and makes nn moves: at step i=0,…,n−1i = 0, \dots, n-1 it goes from its current point xx to x+(qi(x)+εi)ejix + (q_i(x) + \varepsilon_i)\, e_{j_i}, where ji∈ιj_i \in \iota is the direction of the move, the shift qi(x)q_i(x) is imposed and has absolute value at most 1/41/4, and the sign εi∈{−1,1}\varepsilon_i \in \{-1, 1\} is ours. The question is for which bodies the signs can be chosen, whatever the shifts, so that the walk ends in KK.

The library answers it for good domains, a class of symmetric convex bodies defined through the heat semigroup, and states the answer also for walks started at any point of the backward domain of KK, the set obtained from KK by pulling it back along the directions of the moves.

Good Domains

The space of the walk is ℝι\mathbb{R}^\iota, the Euclidean space of real vectors indexed by the finite set ι\iota, with coordinate vectors eke_k for k∈ιk \in \iota; on it, ℱ\mathcal{F} is the Fourier transform of the space L2(ℝι)L^2(\mathbb{R}^\iota) of complex square-integrable functions.

For a measure μ\mu and a measurable function mm with |m|≤C|m| \le C almost everywhere, the multiplication operator MmM_m is the bounded linear operator on L2(μ)L^2(\mu) that sends ff to mfmf.✦ For a measurable set DD, we write 1D1_D also for multiplication by the indicator of DD.✦

The Fourier multiplier with a measurable symbol m:ℝι→ℝm \colon \mathbb{R}^\iota \to \mathbb{R}, |m|≤1|m| \le 1, is the operator ℱ−1Mmℱ\mathcal{F}^{-1} M_m \mathcal{F} on L2(ℝι)L^2(\mathbb{R}^\iota).✦ The heat operator HwH_w of a measurable function w≥0w \ge 0 on ℝι\mathbb{R}^\iota is the Fourier multiplier with symbol e−we^{-w}✦, and its compression to a measurable set D⊂ℝιD \subset \mathbb{R}^\iota is the operator 1DHw1D1_D H_w 1_D✦.

For a weight v∈[0,∞)ιv \in [0, \infty)^\iota, the Gaussian symbol σv\sigma_v is the function on ℝι\mathbb{R}^\iota given by σv(ξ)=12∑k∈ιvk(2πξk)2.\sigma_v(\xi) = \frac{1}{2} \sum_{k \in \iota} v_k \, (2\pi \xi_k)^2 .(1)✦

A measurable set D⊂ℝιD \subset \mathbb{R}^\iota satisfies the diagonal heat bound with constant cc if, for every weight v∈[0,∞)ιv \in [0, \infty)^\iota, the compressed heat operator has operator norm on L2(ℝι)L^2(\mathbb{R}^\iota) ∥1DHσv1D∥≥exp⁡(−c2∑k∈ιvk).\bigl\| 1_D H_{\sigma_v} 1_D \bigr\| \ge \exp\Bigl( -\frac{c}{2} \sum_{k \in \iota} v_k \Bigr).(2)✦

A good domain is a subset KK of ℝι\mathbb{R}^\iota that is nonempty, open, bounded, convex and centrally symmetric (−x∈K-x \in K for every x∈Kx \in K), and satisfies the diagonal heat bound (2) with constant c=κ2c = \kappa^2, where κ=1/100\kappa = 1/100.✦

The Signed Walk

The signed walk from a point x∈ℝιx \in \mathbb{R}^\iota with directions j0,…,jn−1∈ιj_0, \dots, j_{n-1} \in \iota, shifts q0,…,qn−1:ℝι→ℝq_0, \dots, q_{n-1} \colon \mathbb{R}^\iota \to \mathbb{R} and real coefficients ε0,…,εn−1\varepsilon_0, \dots, \varepsilon_{n-1} is the sequence of points x(0)=xx^{(0)} = x and x(i+1)=x(i)+(qi(x(i))+εi)eji,0≤i<n;x^{(i+1)} = x^{(i)} + \bigl( q_i(x^{(i)}) + \varepsilon_i \bigr)\, e_{j_i}, \qquad 0 \le i < n;(3)✦ its endpoint is Wj,q,ε(x)=x(n)W_{j,q,\varepsilon}(x) = x^{(n)}.

The backward domains of a set K⊂ℝιK \subset \mathbb{R}^\iota along directions j0,…,jn−1j_0, \dots, j_{n-1} are the sets Kn=KK_n = K and Ki=Teji(Ki+1),i=n−1,…,0,K_i = T_{e_{j_i}}(K_{i+1}), \qquad i = n-1, \dots, 0,(4)✦ where, for a vector u∈ℝιu \in \mathbb{R}^\iota and a set L⊂ℝιL \subset \mathbb{R}^\iota, Tu(L)T_u(L) is the section domain of LL in the direction uu, the set of points of ℝι\mathbb{R}^\iota defined from LL and uu by the section construction, taken with parameters 5/25/2 and 11. The set K0K_0 is the backward domain of KK along j0,…,jn−1j_0, \dots, j_{n-1}.

The Claim

Theorem 1. Let K⊂ℝιK \subset \mathbb{R}^\iota be a good domain, let j0,…,jn−1∈ιj_0, \dots, j_{n-1} \in \iota be directions, and let q0,…,qn−1:ℝι→ℝq_0, \dots, q_{n-1} \colon \mathbb{R}^\iota \to \mathbb{R} be shifts with |qi(x)|≤1/4|q_i(x)| \le 1/4 for every ii and every x∈ℝιx \in \mathbb{R}^\iota. Then there are signs ε0,…,εn−1∈{−1,1}\varepsilon_0, \dots, \varepsilon_{n-1} \in \{-1, 1\} such that the signed walk (3) from the origin satisfies Wj,q,ε(0)∈K.W_{j,q,\varepsilon}(0) \in K .(5)✦ For every point xx of the backward domain K0K_0 of KK along j0,…,jn−1j_0, \dots, j_{n-1}, as in (4), there are likewise signs ε0,…,εn−1∈{−1,1}\varepsilon_0, \dots, \varepsilon_{n-1} \in \{-1, 1\} such that Wj,q,ε(x)∈K.W_{j,q,\varepsilon}(x) \in K .(6)✦

In the paper, the result reads: if K⊂ℝmK \subset \mathbb{R}^m is nonempty, bounded, open, convex and centrally symmetric with λQ(K)≤κ2tr⁡Q\lambda_Q(K) \le \kappa^2 \operatorname{tr} Q for every positive definite diagonal matrix QQ, where λQ\lambda_Q is the diagonal Dirichlet energy, if j1,…,jsj_1, \dots, j_s are ss distinct elements of {1,…,m}\{1, \dots, m\} and qiq_i are arbitrary functions ℝi−1→[−δ,δ]\mathbb{R}^{i-1} \to [-\delta, \delta] for a given bound δ\delta, then there are signs εi\varepsilon_i such that the walk x(0)=0x^{(0)} = 0, x(i)=x(i−1)+(qi(xj1(i−1),…,xji−1(i−1))+εi)ejix^{(i)} = x^{(i-1)} + \bigl( q_i(x^{(i-1)}_{j_1}, \dots, x^{(i-1)}_{j_{i-1}}) + \varepsilon_i \bigr) e_{j_i} has x(s)∈Kx^{(s)} \in K.

The box has the heat bound (2) with c=κ2c = \kappa^2 in place of the energy condition and δ=1/4\delta = 1/4, and it lets the directions repeat and each shift depend on the whole current point.

What Is Checked

The claim, (5) and (6), is stated over the signed walk (3), over good domains with their diagonal heat bound (2), built from the Gaussian symbol (1), the Fourier multiplier and multiplication by indicators, and over the backward domains (4).

About these constructions the library proves that the Gaussian symbol σv\sigma_v is nonnegative✦, and that multiplication by a measurable function bounded by CC maps L2(μ)L^2(\mu) into itself✦ with norm at most CC✦.