OctoInformBeta

OpenAI preprint, September 2026 · §4. Entropy enrichment from a forward segment

Lemma 4.1: Self-avoiding segments of nn steps at most DD lie in rectangles of area between n/9n/9 and 2max⁡(D,K4D)|E−E|2\max(D,K_{4D})\,|E-E|, EE the segment’s points

Differences of a walk segment bound the area it spans.

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

Take a self-avoiding walk z0,z1,…z_0, z_1, \dots in ℤ[i]\mathbb Z[i], a sequence of distinct Gaussian integers, and a forward segment z0,…,znz_0, \dots, z_n of it whose n≥1n \ge 1 steps have length at most DD. Its points form a set EE of n+1n + 1 Gaussian integers, and the question is how many distinct differences x−yx - y with x,y∈Ex, y \in E such a set must have. The region the segment covers may be a thin strip of length about DnDn or a disc of radius about n\sqrt n, and its size is measured by the area of a rectangle containing the segment.

The same comparison has a form for two finite walks from 00 with steps at most DD, one ending at aa and one at bb: how large must a set of Gaussian integers be that contains every difference of a point of the first walk and a point of the second, against the area of the parallelogram spanned by aa and bb? This is the setting of a discrete Sperner lemma for rectangles. Part (c) of Theorem 1, stated below, is its form for three points of one segment spanning a triangle.

Differences, Lattice Balls and Rectangles

For a finite set EE of Gaussian integers, the difference set E−EE - E is the finite set E−E={x−y:x,y∈E}E - E = \{\, x - y : x, y \in E \,\}(1)✦ of Gaussian integers, and |E−E||E - E| is its number of elements.

The point set EE of the segment z0,…,znz_0, \dots, z_n of length n≥0n \ge 0 of a sequence z0,z1,…z_0, z_1, \dots of Gaussian integers is the set {z0,z1,…,zn}\{z_0, z_1, \dots, z_n\} of its first n+1n + 1 terms.✦

For a real number DD, the lattice ball of radius DD is the finite set of Gaussian integers at distance at most DD from 00 in ℂ\mathbb C, and KDK_D is its number of elements: KD=|{u∈ℤ[i]:|u|≤D}|.K_D = \bigl|\{\, u \in \mathbb Z[i] : |u| \le D \,\}\bigr|.(2)✦

The determinant det⁡(a,b)\det(a, b) of Gaussian integers aa and bb is the integer det⁡(a,b)=Re⁡aIm⁡b−Im⁡aRe⁡b;\det(a, b) = \operatorname{Re} a \operatorname{Im} b - \operatorname{Im} a \operatorname{Re} b;(3) its absolute value is the area of the parallelogram spanned by aa and bb, and it vanishes exactly when 00, aa and bb lie on a line.

An oriented rectangle of length R≥0R \ge 0 and half-width W≥0W \ge 0 is a subset of ℂ\mathbb C of the form {p∈ℂ:0≤Re⁡(e(p−c))≤R,|Im⁡(e(p−c))|≤W}\{\, p \in \mathbb C : 0 \le \operatorname{Re}\bigl(e(p - c)\bigr) \le R,\ \bigl|\operatorname{Im}\bigl(e(p - c)\bigr)\bigr| \le W \,\}(4) with c,e∈ℂc, e \in \mathbb C and |e|=1|e| = 1.

The Claim

Theorem 1. (a) Let D≥1D \ge 1 be a real number and n≥1n \ge 1 an integer, let z0,z1,…z_0, z_1, \dots be a self-avoiding walk in ℤ[i]\mathbb Z[i] with |zt+1−zt|≤D|z_{t+1} - z_t| \le D for t<nt < n, and let E={z0,…,zn}E = \{z_0, \dots, z_n\}. Then there are real numbers RR and WW with 1≤W≤R1 \le W \le R and an oriented rectangle of length RR and half-width WW containing EE such that n≤18RW,RW≤D2n2,RW≤max⁡(D,K4D)|E−E|.n \le 18RW, \qquad RW \le D^2 n^2, \qquad RW \le \max(D, K_{4D})\,|E - E|.(5)✦

(b) Let D≥0D \ge 0 be a real number, n,m≥1n, m \ge 1 integers and a,ba, b Gaussian integers with det⁡(a,b)≠0\det(a, b) \ne 0, and let v0,…,vnv_0, \dots, v_n and w0,…,wmw_0, \dots, w_m be finite walks in ℤ[i]\mathbb Z[i] with steps at most DD, from v0=0v_0 = 0 to vn=av_n = a and from w0=0w_0 = 0 to wm=bw_m = b. If FF is a finite set of Gaussian integers containing vi−wjv_i - w_j for all i<ni < n and j<mj < m, then |det⁡(a,b)|≤K4D|F|.|\det(a, b)| \le K_{4D}\,|F|.(6)✦

(c) Let D≥0D \ge 0 be a real number and n≥0n \ge 0 an integer, let z0,z1,…z_0, z_1, \dots be a sequence of Gaussian integers with |zt+1−zt|≤D|z_{t+1} - z_t| \le D for t<nt < n, and let E={z0,…,zn}E = \{z_0, \dots, z_n\}. If i,j,k≤ni, j, k \le n and det⁡(zj−zi,zk−zi)≠0\det(z_j - z_i, z_k - z_i) \ne 0, then |det⁡(zj−zi,zk−zi)|≤K4D|E−E|.|\det(z_j - z_i, z_k - z_i)| \le K_{4D}\,|E - E|.(7)✦

In the paper, the result reads: if EE is the set of points of a segment of n≥1n \ge 1 steps of the walk, RR its diameter and WW the larger of 11 and the maximal distance of a point of EE from a diameter line, then A=RWA = RW satisfies cn≤A≤D2n2cn \le A \le D^2 n^2 and |E−E|≥cDA|E - E| \ge c_D A, with c>0c > 0 absolute and cD>0c_D > 0 depending only on DD.

Part (a) takes for RR and WW the length and half-width of a rectangle containing the segment, in place of the diameter and the distance from a diameter line, and gives c=1/18c = 1/18 and cD=1/max⁡(D,K4D)c_D = 1/\max(D, K_{4D}).

What Is Checked

The claim is stated over sequences of Gaussian integers with distances taken in ℂ\mathbb C, the point set {z0,…,zn}\{z_0, \dots, z_n\} of a segment, the difference set (1), the lattice ball of radius 4D4D with its K4DK_{4D} elements (2), the determinant (3) and the oriented rectangles (4).