OctoInformBeta

OpenAI preprint, September 2026 · §2. Families of directions

Lemma 2.1: Explicit bounds on the dimension mm also suffice, and pivoted direction families exist for sufficiently large mm

Existence of direction families for sufficiently large dimension.

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

Consider choosing finite families of vectors in ℝm\mathbb{R}^m as projection directions. Such collections must control the lengths and pairwise independence of the vectors within each family while regulating their averages and extreme inner products against arbitrary test vectors. The question is whether collections meeting these quantitative requirements exist for sufficiently large mm or under explicit dimension inequalities, and whether every coordinate of every vector can also be kept bounded away from zero.

Direction Families

Letting KK be a nonnegative integer and EE a real inner-product space, the empirical covariance Cov⁡(x,v)\operatorname{Cov}(x, v) of a family x=(x1,…,xK)∈EKx = (x_1, \dots, x_K) \in E^K at a vector v∈Ev \in E is the real number defined by (1): Cov⁡(x,v)=1K∑i=1K⟨v,xi⟩2.\operatorname{Cov}(x, v) = \frac{1}{K} \sum_{i=1}^K \langle v, x_i \rangle^2.(1)✦

In a real inner-product space EE, for any nonnegative integer KK, the empirical sine transform Φ(x,w)\Phi(x, w) of a family x=(x1,…,xK)∈EKx = (x_1, \dots, x_K) \in E^K at w∈Ew \in E is the vector in EE defined by (2): Φ(x,w)=1K∑i=1Ksin⁡⟨xi,w⟩xi.\Phi(x, w) = \frac{1}{K} \sum_{i=1}^K \sin\langle x_i, w \rangle\, x_i.(2)✦

Given a real inner-product space EE and a nonnegative integer KK, the bad projection set ℬK(q,v)\mathcal{B}_K(q, v) associated with a real threshold qq and a vector v∈Ev \in E is the subset of EKE^K defined by (3): ℬK(q,v)={x=(x1,…,xK)∈EK:∃i∈{1,…,K},|⟨v,xi⟩|>q}.\mathcal{B}_K(q, v) = \bigl\{ x = (x_1, \dots, x_K) \in E^K : \exists i \in \{1, \dots, K\},\ |\langle v, x_i \rangle| > q \bigr\}.(3)✦

When AA is a subset of a set Ω\Omega and y=(y1,…,yK)∈ΩKy = (y_1, \dots, y_K) \in \Omega^K is a family indexed by a nonnegative integer KK, the number of bad samples ν(A,y)\nu(A, y) is the nonnegative integer defined by (4): ν(A,y)=|{s∈{1,…,K}:ys∈A}|.\nu(A, y) = \bigl|\{ s \in \{1, \dots, K\} : y_s \in A \}\bigr|.(4)✦

With mm a nonnegative integer, S=m3S = m^3, and N=m6N = m^6, a direction family gg in dimension mm is a collection (gs,i)1≤s≤S,1≤i≤N(g_{s,i})_{1 \le s \le S,\, 1 \le i \le N} of vectors in ℝm\mathbb{R}^m, where g=(g1,…,gS)g = (g_1, \dots, g_S) with gs=(gs,1,…,gs,N)∈(ℝm)Ng_s = (g_{s,1}, \dots, g_{s,N}) \in (\mathbb{R}^m)^N, satisfying the five conditions (5): m2≤∥gs,i∥≤2m(1≤s≤S,1≤i≤N),gs,a≠tgs,b(1≤s≤S,1≤a,b≤N,a≠b,t∈ℝ),12≤Cov⁡(gs,v)≤2(1≤s≤S,v∈ℝm,∥v∥=1),∥Φ(gs,w)−e−∥w∥2/2w∥≤2m(1≤s≤S,w∈ℝm,∥w∥≤m42),ν(ℬN(11log⁡m,v),g)≤S2(v∈ℝm,∥v∥=1).\begin{aligned} \frac{\sqrt{m}}{2} &\le \|g_{s,i}\| \le 2\sqrt{m} && (1 \le s \le S,\ 1 \le i \le N), \\ g_{s,a} &\neq t\, g_{s,b} && (1 \le s \le S,\ 1 \le a, b \le N,\ a \neq b,\ t \in \mathbb{R}), \\ \frac{1}{2} &\le \operatorname{Cov}(g_s, v) \le 2 && (1 \le s \le S,\ v \in \mathbb{R}^m,\ \|v\| = 1), \\ \bigl\|\Phi(g_s, w) - e^{-\|w\|^2/2} w\bigr\| &\le \frac{2}{\sqrt{m}} && (1 \le s \le S,\ w \in \mathbb{R}^m,\ \|w\| \le m^{42}), \\ \nu\bigl(\mathcal{B}_N(11\sqrt{\log m}, v),\, g\bigr) &\le \frac{S}{2} && (v \in \mathbb{R}^m,\ \|v\| = 1). \end{aligned}(5)✦

For a nonnegative integer mm with S=m3S = m^3 and N=m6N = m^6, a pivoted direction family gg in dimension mm is a direction family in dimension mm whose coordinate entries (gs,i)j(g_{s,i})_j satisfy (6): |(gs,i)j|>1m30(1≤s≤S,1≤i≤N,1≤j≤m).|(g_{s,i})_j| > \frac{1}{m^{30}} \qquad (1 \le s \le S,\ 1 \le i \le N,\ 1 \le j \le m).(6)✦

The Claim

Theorem 1. For every sufficiently large integer mm, there exists a direction family in dimension m.\text{there exists a direction family in dimension } m.(7)✦ Whenever an integer mm satisfies m≥106,log⁡m≥1,16e−m/12≤18m,2m9e−m/8+6m3e−m<1,\begin{aligned} m &\ge 10^6, & \log m &\ge 1, \\ 16 e^{-m/12} &\le \frac{1}{8m}, & 2m^9 e^{-m/8} + 6m^3 e^{-m} &< 1, \end{aligned}(8)✦ a direction family in dimension mm exists. With the coordinate pivot bound imposed, for all sufficiently large integers mm, there exists a pivoted direction family in dimension m.\text{there exists a pivoted direction family in dimension } m.(9)✦

In the paper, the result reads: there is an absolute constant CC such that, for every sufficiently large integer mm, with N=m6N = m^6 and S=m3S = m^3, there are vectors gs,i∈ℝmg_{s,i} \in \mathbb{R}^m (1≤s≤S1 \le s \le S, 1≤i≤N1 \le i \le N) such that (1) m/2≤∥gs,i∥≤2m\sqrt{m}/2 \le \|g_{s,i}\| \le 2\sqrt{m}, within each family ss the vectors have pairwise nonparallel directions, and every eigenvalue of N−1∑i=1Ngs,igs,iTN^{-1}\sum_{i=1}^N g_{s,i} g_{s,i}^T belongs to [1/2,2][1/2, 2]; (2) sup⁡∥w∥≤m42∥N−1∑i=1Ngs,isin⁡⟨gs,i,w⟩−we−∥w∥2/2∥≤2/m\sup_{\|w\| \le m^{42}} \bigl\| N^{-1}\sum_{i=1}^N g_{s,i} \sin\langle g_{s,i}, w\rangle - w e^{-\|w\|^2/2} \bigr\| \le 2/\sqrt{m}; and (3) for every unit vector v∈ℝmv \in \mathbb{R}^m, at least S/2S/2 of the indices ss satisfy max⁡1≤i≤N|⟨v,gs,i⟩|≤Clog⁡m\max_{1 \le i \le N} |\langle v, g_{s,i}\rangle| \le C\sqrt{\log m}. Whereas the paper uses an unspecified constant CC and eigenvalues of N−1∑i=1Ngs,igs,iTN^{-1}\sum_{i=1}^N g_{s,i} g_{s,i}^T, the library sets the projection constant to 1111 inside ℬN\mathcal{B}_N and ν\nu while writing the eigenvalue and sine bounds via Cov⁡(gs,v)\operatorname{Cov}(g_s, v) and Φ(gs,w)\Phi(g_s, w), and it pairs (7) with the explicit dimension claim (8) and the pivoted claim (9).

What Is Checked

The claims (7) and (9) are stated over direction families and pivoted direction families in dimension mm (built from empirical covariances, empirical sine transforms, bad projection sets, and numbers of bad samples) for sufficiently large nonnegative integers mm, whereas (8) is stated over direction families in dimension mm for any nonnegative integer mm meeting its four inequalities.