OctoInformBeta

OpenAI preprint, September 2026 · §2. A graph of large distance classes · §2

§2 (setting): fiber systems and their sampling laws: A uniform edge can be drawn fiber first or target first, and circles of rich pairs in the plane form a fiber system

Fiber systems and two ways to sample an edge.

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 set PP of nn points in the plane and pin one of them, xx. The other points of PP lie on circles centered at xx, one for each distance from xx to a point of PP, and the pinned distance problem asks how few of these circles a pin can have. The circles that carry many points of PP are the large distance classes at xx, and the second section of the source builds from them a directed graph on PP: an edge runs from each pin to every point of each of its large classes.

Such a graph is a union of fibers, a fiber being one large class read as a set of targets with the pin as their source. Its edges are drawn at random, uniformly, and the question is how a uniform edge can be reached from the pieces: a fiber first and a target on it next, or the target first and a source next. The library sets this up for an abstract fiber system on a finite vertex set, together with its uniform laws, and the planar fiber system of large distance classes is one of them.

Rich Pairs

The plane is ℝ2\mathbb{R}^2 with the Euclidean norm and distance.✦ For a finite set PP in the plane and points xx and yy of the plane, the points at equal distance are the points of PP other than xx whose distance to xx equals ∥y−x∥\|y-x\|✦, and the pinned distance multiplicity kP(x,y)k_P(x,y) is their number: kP(x,y)=|{z∈P\{x}:∥z−x∥=∥y−x∥}|.k_P(x,y) = \bigl|\{z \in P \setminus \{x\} : \|z-x\| = \|y-x\|\}\bigr|.(1)✦

For a real number ss and n=|P|n = |P|, a rich pair of PP at exponent ss is an ordered pair of distinct points of PP with multiplicity at least nsn^{s}, and ℛs(P)\mathcal{R}_s(P) denotes the set of rich pairs of PP at exponent ss: ℛs(P)={(x,y)∈P×P:x≠y,kP(x,y)≥ns}.\mathcal{R}_s(P) = \{(x,y) \in P \times P : x \neq y,\ k_P(x,y) \ge n^{s}\}.(2) The set ℐs(P)\mathcal{I}_s(P) of fiber indices of PP at exponent ss consists of the pairs (x,r)(x, r) of a point xx of PP and a radius rr such that r=∥y−x∥r = \|y-x\| for some rich pair (x,y)(x,y) of PP at exponent ss: ℐs(P)={(x,∥y−x∥):(x,y)∈ℛs(P)}.\mathcal{I}_s(P) = \{(x, \|y-x\|) : (x,y) \in \mathcal{R}_s(P)\}.(3)

The Claim

Definition 1. Let VV and II be finite sets. A fiber system on VV indexed by II assigns to each index e∈Ie \in I a source xe∈Vx_e \in V and a target set Fe⊆VF_e \subseteq V such that, for all e,f∈Ie, f \in I, xe∉Fe,Fe∩Ff=∅ whenever e≠f and xe=xf.x_e \notin F_e, \qquad F_e \cap F_f = \emptyset \ \text{ whenever } e \neq f \text{ and } x_e = x_f.(4)✦

For a set C⊆VC \subseteq V and a real number KK, the size of a fiber ee in CC is |Fe∩C||F_e \cap C|✦, and the fiber is active at level KK in CC when xe∈Cx_e \in C and its size in CC exceeds KK.✦ A pair (x,y)(x,y) is an edge at level KK in CC when some fiber ee active at level KK in CC has xe=xx_e = x and y∈Fe∩Cy \in F_e \cap C✦; these pairs form the edge set EK(C)E_K(C).✦ The edge set of the fiber system is E=E−1(V)={(xe,y):e∈I,y∈Fe},E = E_{-1}(V) = \{(x_e, y) : e \in I,\ y \in F_e\},(5)✦ and its edge count is m=|E|.m = |E|.(6)✦ The edge law qq is the function on V×VV \times V that takes the value 1/m1/m on EE and 00 elsewhere: q(x,y)={1/mif (x,y)∈E,0otherwise.q(x,y) = \begin{cases} 1/m & \text{if } (x,y) \in E,\\ 0 & \text{otherwise.}\end{cases}(7) The weight of a fiber ee is we=|Fe|/mw_e = |F_e|/m.✦ The incoming neighbors of a vertex yy form the set N−(y)={x∈V:(x,y)∈E}N^-(y) = \{x \in V : (x,y) \in E\}✦, and the incoming weight of yy is w−(y)=|N−(y)|/mw^-(y) = |N^-(y)|/m.✦

For a finite subset BB of a set XX, the uniform law uBu_B on BB and the uniform law πB\pi_B on distinct ordered pairs of BB are the functions on XX and on X×XX \times X given by uB(x)={1/|B|if x∈B,0otherwise,u_B(x) = \begin{cases} 1/|B| & \text{if } x \in B,\\ 0 & \text{otherwise,}\end{cases}(8)✦ πB(x,y)={1|B|(|B|−1)if x,y∈B and x≠y,0otherwise.\pi_B(x,y) = \begin{cases} \dfrac{1}{|B|\,(|B|-1)} & \text{if } x, y \in B \text{ and } x \neq y,\\ 0 & \text{otherwise.}\end{cases}(9)✦ On a fiber system, α=uV\alpha = u_V is the uniform law on the vertices, π=πV\pi = \pi_V the uniform law on distinct ordered pairs of vertices, μe=uFe\mu_e = u_{F_e} the uniform law on the target set of ee and ρy=uN−(y)\rho_y = u_{N^-(y)} the uniform law on the incoming neighbors of yy.

For a finite set PP in the plane and a real number ss, the planar fiber system is the fiber system on PP indexed by ℐs(P)\mathcal{I}_s(P) with x(x,r)=x,F(x,r)={y∈P:∥y−x∥=r}.x_{(x,r)} = x, \qquad F_{(x,r)} = \{y \in P : \|y-x\| = r\}.(10)✦

Theorem 1. Let VV and II be finite sets and take a fiber system on VV indexed by II. For all vertices xx and yy in VV, ∑e∈I,xe=xweμe(y)=q(x,y)\sum_{e \in I,\ x_e = x} w_e\, \mu_e(y) = q(x,y)(11)✦ and w−(y)ρy(x)=q(x,y).w^-(y)\, \rho_y(x) = q(x,y).(12)✦

In the paper, the result reads: edges with the same source and the same squared distance form a fiber ee with source xex_e and target set FeF_e, where ke=|Fe|k_e = |F_e|; α\alpha is uniform on PP, π\pi uniform on distinct ordered pairs, qq uniform on the edge set EE with marginals qXq_X and qYq_Y, μe\mu_e uniform on FeF_e and ρy\rho_y uniform on the incoming neighbors of yy.

What Is Checked

The fiber system and everything built on it, through the identities (11) and (12), are stated over finite sets VV and II; the uniform laws (8) and (9) over a finite subset of an arbitrary set; and the planar fiber system (10) over a finite set PP in ℝ2\mathbb{R}^2 and a real number ss. The library also proves that the planar fiber system meets the two conditions of a fiber system: every radius of a fiber index is positive, so no pin lies among its own targets, and two distinct fibers with the same pin lie on circles of different radii, so their target sets are disjoint.