OctoInformBeta

OpenAI preprint, September 2026 · §6. A common sampling schedule

The schedule, checkpoints and the terminal time t*: Forward kernels, the common schedule with its block lengths and offset NN, exact starts, and residues of displacements modulo πp\pi_p or π‾p\bar\pi_p

Random sampling times from difference transitions and a uniform offset.

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 z0,z1,…z_0, z_1, \dots be a walk in ℤ[i]\mathbb{Z}[i], to be read not at a fixed time but at a random one. The random time is built in stages: a stage started at time aa moves forward by a random advance of bounded size whose law may depend on aa, and the next stage starts where it stops. In the common schedule every stage but the last is a difference transition, driven by the differences between the points the walk visits just ahead of the current time, and the last stage adds a uniform random offset. If the stages start at time aa and end at time tt, what is observed is the residue of the displacement zt−zaz_t - z_a modulo a Gaussian prime π\pi of norm pp, or modulo its conjugate π‾\bar\pi, for a prime p≡1(mod⁡4)p \equiv 1 \pmod 4.

Laws and Difference Transitions

A law on a finite set XX is a function μ\mu from XX to the nonnegative reals with ∑x∈Xμ(x)=1\sum_{x \in X} \mu(x) = 1.✦ Given a law μ\mu on XX and, for each x∈Xx \in X, a law ν(⋅∣x)\nu(\cdot \mid x) on a finite set YY, the joint law of μ\mu and ν\nu is the law on X×YX \times Y with mass μ(x)ν(y∣x)\mu(x)\,\nu(y \mid x) at (x,y)(x, y): the law of the pair obtained by drawing xx from μ\mu and then yy from ν(⋅∣x)\nu(\cdot \mid x).✦ The pushforward of μ\mu along a map f:X→Yf \colon X \to Y is the law on YY that gives each point the total mass of its preimage under ff.✦ The uniform law on a nonempty finite set XX is the law on XX that gives every point mass 1/|X|1/|X|; the point mass at x∈Xx \in X is the law on XX that gives xx mass 11 and every other point mass 00. A time law PP of last time L∈ℕL \in \mathbb{N} is a law on {0,1,…,L}\{0, 1, \dots, L\}, the law of a random time at most LL.✦

Fix a walk zz, a time aa and n∈ℕn \in \mathbb{N}. The segment of length nn from aa is the set E={za,za+1,…,za+n}E = \{z_a, z_{a+1}, \dots, z_{a+n}\} of the points visited at times a,…,a+na, \dots, a + n✦, and its difference set E−EE - E is the set of all differences w−w′w - w' with w,w′∈Ew, w' \in E✦. For each d∈E−Ed \in E - E, a pair (ud,vd)(u_d, v_d) of advances in {0,…,n}\{0, \dots, n\} with za+ud−za+vd=dz_{a+u_d} - z_{a+v_d} = d is chosen once and for all.✦ The difference pair law is the law of (ud,vd)(u_d, v_d) when dd is drawn uniformly from E−EE - E.✦ The difference transition of window nn at aa draws this pair and, independently, a fair coin, and advances by udu_d on heads and by vdv_d on tails; its law Δn,a\Delta_{n,a} on {0,…,n}\{0, \dots, n\} is Δn,a(t)=#{d∈E−E:ud=t}+#{d∈E−E:vd=t}2|E−E|.\Delta_{n,a}(t) = \frac{\#\{d \in E - E : u_d = t\} + \#\{d \in E - E : v_d = t\}}{2\,|E - E|}.(1)✦

Block Lengths

For reals gg and xx and for j∈ℕj \in \mathbb{N}, the band scale is Sj=g2jxS_j = g^{2j} x✦, and the band length is ℓj(g,x)=⌊egSj⌋=⌊exp⁡(g2j+1x)⌋.\ell_j(g, x) = \big\lfloor e^{g S_j} \big\rfloor = \big\lfloor \exp\big(g^{2j+1} x\big) \big\rfloor.(2)✦ Lists of lengths are written side by side, juxtaposition being concatenation. For a real α\alpha and j∈ℕj \in \mathbb{N}, the top block Tα(j)T_\alpha(j) is the list ℓ0(g,2jα),…,ℓ19(g,2jα)\ell_0(g, 2^j \alpha), \dots, \ell_{19}(g, 2^j \alpha) of twenty band lengths at the top parameter g=10−6g = 10^{-6}✦; for a finite set J⊂ℕJ \subset \mathbb{N}, the top blocks Tα(J)T_\alpha(J) are the concatenation of the Tα(j)T_\alpha(j), j∈Jj \in J, in decreasing order of jj✦. An accurate block takes m∈ℕm \in \mathbb{N} and a real cc: Am(c)A_m(c) is the list ℓ0(gm,ecem),…,ℓ4m2−1(gm,ecem)\ell_0(g_m, e^{c e^m}), \dots, \ell_{4m^2 - 1}(g_m, e^{c e^m}) of 4m24m^2 band lengths on the accurate grid gm=e−m2g_m = e^{-m^2}.✦

Signed Factors

A split prime sieve 𝒫\mathcal{P} is a finite set of rational primes p≡1(mod⁡4)p \equiv 1 \pmod 4 together with, for each p∈𝒫p \in \mathcal{P}, a Gaussian prime πp\pi_p of norm pp.✦ Its primes are enumerated once and for all as p0,…,pr−1p_0, \dots, p_{r-1}, where r=|𝒫|r = |\mathcal{P}|.✦ A signed index ι=(σ,k)\iota = (\sigma, k) of 𝒫\mathcal{P} is a pair of a sign pattern σ=(σ0,…,σr−1)∈{+,−}r\sigma = (\sigma_0, \dots, \sigma_{r-1}) \in \{+, -\}^r and a position k∈{0,…,r−1}k \in \{0, \dots, r - 1\}.✦ The prime of a signed index ι=(σ,k)\iota = (\sigma, k) of 𝒫\mathcal{P} is pkp_k, and its signed factor πι\pi_\iota is πpk\pi_{p_k} when σk=+\sigma_k = + and the conjugate π‾pk\bar\pi_{p_k} when σk=−\sigma_k = -✦. The residue ring at ι\iota is the quotient ℤ[i]/(πι)\mathbb{Z}[i]/(\pi_\iota) of ℤ[i]\mathbb{Z}[i] by the multiples of πι\pi_\iota✦, and the residue map sends w∈ℤ[i]w \in \mathbb{Z}[i] to its class wmod⁡πιw \bmod \pi_\iota✦.

The Definition

Definition 1. A forward kernel KK of bound M∈ℕM \in \mathbb{N} is a family of laws KaK_a on the advances 0,1,…,M0, 1, \dots, M, one for each time a∈ℕa \in \mathbb{N}: Ka(t)≥0(0≤t≤M),∑t=0MKa(t)=1(a∈ℕ).K_a(t) \ge 0 \quad (0 \le t \le M), \qquad \sum_{t=0}^{M} K_a(t) = 1 \qquad (a \in \mathbb{N}).(3)✦ Two forward kernels KK and RR, of bounds MM and M′M', compose to the forward kernel KRKR of bound M+M′M + M' that advances from aa by uu drawn from KaK_a and then by vv drawn from Ra+uR_{a+u}: (KR)a(t)=∑u+v=tu≤M,v≤M′Ka(u)Ra+u(v),0≤t≤M+M′.(KR)_a(t) = \sum_{\substack{u + v = t \\ u \le M,\ v \le M'}} K_a(u)\, R_{a+u}(v), \qquad 0 \le t \le M + M'.(4)✦ The uniform offset kernel UNU_N, for N∈ℕN \in \mathbb{N}, is the forward kernel of bound NN with the uniform law at every time: (UN)a(t)=1N+1,0≤t≤N,a∈ℕ.(U_N)_a(t) = \frac{1}{N + 1}, \qquad 0 \le t \le N,\ a \in \mathbb{N}.(5)✦ Given a walk zz, the difference kernel Δn\Delta_n of window n∈ℕn \in \mathbb{N} is the forward kernel of bound nn whose law at each time aa is Δn,a\Delta_{n,a} of (1).✦ The common schedule of zz with segment lengths n1,…,nkn_1, \dots, n_k and offset NN is the forward kernel C(n1,…,nk;N)C(n_1, \dots, n_k; N) defined by recursion on the list: C(;N)=UN,C(n1,n2,…,nk;N)=Δn1C(n2,…,nk;N).C(\,; N) = U_N, \qquad C(n_1, n_2, \dots, n_k; N) = \Delta_{n_1}\, C(n_2, \dots, n_k; N).(6)✦ A time law PP of last time LL, advanced by a forward kernel KK of bound MM, gives the time law PKPK of last time L+ML + M, the law of b+tb + t with bb drawn from PP and then tt from KbK_b: (PK)(s)=∑b+t=sb≤L,t≤MP(b)Kb(t),0≤s≤L+M.(PK)(s) = \sum_{\substack{b + t = s \\ b \le L,\ t \le M}} P(b)\, K_b(t), \qquad 0 \le s \le L + M.(7)✦ The exact start at a∈ℕa \in \mathbb{N} is the time law δa\delta_a of last time aa, the point mass at aa: δa(a)=1,δa(s)=0(0≤s<a).\delta_a(a) = 1, \qquad \delta_a(s) = 0 \quad (0 \le s < a).(8)✦ A checkpoint is a time a∈ℕa \in \mathbb{N} at which the schedule is started exactly, from the exact start δa\delta_a. The terminal time t*t^* of the common schedule started at a checkpoint aa is the random time of law δaC(n1,…,nk;N)\delta_a\, C(n_1, \dots, n_k; N).

A concrete schedule is given by a real α\alpha, natural numbers mm and WW, and a finite set J(w)⊂ℕJ(w) \subset \mathbb{N} for each w<Ww < W. The schedule has WW windows, indexed by w<Ww < W. Window ww contributes the block Tα(J(w))Am(100w/4)T_\alpha(J(w))\, A_m(100^w/4), and the common block list BB of the concrete schedule runs through the windows from w=W−1w = W - 1 down to w=0w = 0 and ends with Am(1/20)A_m(1/20): B=Tα(J(W−1))Am(100W−14)⋯Tα(J(0))Am(14)Am(120).B = T_\alpha(J(W-1))\, A_m\big(\tfrac{100^{W-1}}{4}\big) \cdots T_\alpha(J(0))\, A_m\big(\tfrac{1}{4}\big)\, A_m\big(\tfrac{1}{20}\big).(9)✦ The offset NW,mN_{W,m} of the concrete schedule is the window smoothing length NW,m=⌈exp⁡(20⋅100Wem)⌉.N_{W,m} = \big\lceil \exp\big(20 \cdot 100^W e^m\big) \big\rceil.(10)✦ The relative residue law ρa,ι\rho_{a,\iota} of a forward kernel KK of bound MM, a split prime sieve 𝒫\mathcal{P}, a walk zz, a time aa and a signed index ι\iota of 𝒫\mathcal{P} is the law on ℤ[i]/(πι)\mathbb{Z}[i]/(\pi_\iota) of the class of the displacement za+t−zaz_{a+t} - z_a modulo πι\pi_\iota, with tt drawn from KaK_a: ρa,ι(ξ)=∑0≤t≤M(za+t−za)mod⁡πι=ξKa(t),ξ∈ℤ[i]/(πι).\rho_{a,\iota}(\xi) = \sum_{\substack{0 \le t \le M \\ (z_{a+t} - z_a) \bmod \pi_\iota = \xi}} K_a(t), \qquad \xi \in \mathbb{Z}[i]/(\pi_\iota).(11)✦

In the paper, the result reads: the terminal time t*t^* is reached by transitions of Lemma 4.3 at decreasing scales, in three bands per window, followed by one independent uniform offset in {0,…,N−1}\{0, \dots, N - 1\}, with exact starts at checkpoints.

What Is Checked

The definitions are stated over laws on finite sets, a walk zz in ℤ[i]\mathbb{Z}[i] with the difference sets of its segments and a chosen pair of advances for each difference, the band lengths (2) with their real parameters, and a split prime sieve with its signed indices, signed factors and residue rings. About these constructions the library proves that every element of the difference set of a segment {z0,…,zn}\{z_0, \dots, z_n\} is a difference zu−zvz_u - z_v with u,v∈{0,…,n}u, v \in \{0, \dots, n\}, the fact on which the choice of the pairs (ud,vd)(u_d, v_d) rests.✦