OctoInformBeta

OpenAI preprint, September 2026 · §4. Finite-field partitions and separated rows · §4

Proposition 4.3 [Partitions with separated rows]: With contraction labels along the directions of Proposition 4.2, distinct forms in Symh(E*)\mathrm{Sym}^h(E^*) are more than hh apart in some admissible graph

Rows of distinct symmetric forms lie at sup distance one.

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

Proposition 4.3 concerns a finite matrix whose rows, points of ℝY\mathbb{R}^Y with the sup norm, are built from symmetric forms over a prime field. Its rows are indexed by the forms xx of degree h≥1h \ge 1 on E=𝔽prE = \mathbb{F}_p^r, where pp is a prime and rr the rank.✦ Each of uu directions ti∈Et_i \in E partitions these forms according to their contraction x(ti,⋅,…,⋅)x(t_i, \cdot, \dots, \cdot), and a set TT of directions links two forms when one of its directions puts them in the same part. A column belongs to a form zz and a set TT, and its entry at xx is a logarithmic cutoff, at radius hh, of the distance from xx to zz along these links. The proposition counts the rows and the possible contractions along each direction, and asks how far apart two distinct rows can be.

Forms and Contractions

Let KK be a field and rr a natural number. A symmetric form FF of degree jj on KrK^r is a family of coefficients Fs∈KF_s \in K, one for each multiset ss of jj indices from {1,…,r}\{1, \dots, r\}.✦ For a prime pp and E=𝔽prE = \mathbb{F}_p^r, these forms make up Symj(E*)\mathrm{Sym}^j(E^*), and the number of multisets indexing their coefficients is Dj=(r+j−1j).D_j = \binom{r + j - 1}{j}.(1)✦

A form FF of degree jj is evaluated at vectors v1,…,vj∈Krv^1, \dots, v^j \in K^r by F(v1,…,vj)=∑a∈{1,…,r}jF{a1,…,aj}va11⋯vajj,F(v^1, \dots, v^j) = \sum_{a \in \{1, \dots, r\}^j} F_{\{a_1, \dots, a_j\}} \, v^1_{a_1} \cdots v^j_{a_j},(2)✦ where {a1,…,aj}\{a_1, \dots, a_j\} is the multiset of the entries of aa and vbv_b is the coordinate of a vector vv at the index bb.

The contraction F(v,⋅,…,⋅)F(v, \cdot, \dots, \cdot) of a form FF of degree j+1j + 1 by a vector v∈Krv \in K^r is the form of degree jj whose coefficient on a multiset ss of jj indices is F(v,⋅,…,⋅)s=∑b=1rvbFs+b,F(v, \cdot, \dots, \cdot)_s = \sum_{b = 1}^{r} v_b \, F_{s + b},(3)✦ where s+bs + b is the multiset ss with one more copy of bb. Given directions ti∈Krt_i \in K^r, indexed by ii in an index set, the label of a form xx of degree h≥1h \ge 1 along tit_i is its contraction Li(x)=x(ti,⋅,…,⋅)L_i(x) = x(t_i, \cdot, \dots, \cdot), a form of degree h−1h - 1.✦

Partition Graphs and Profile Rows

Let XX be a set with labelings LiL_i, indexed by ii in an index set, each mapping XX to a set of labels. For a set TT of indices, the partition graph GTG_T is the simple graph on XX in which two distinct points xx and x′x' are adjacent when Li(x)=Li(x′)L_i(x) = L_i(x') for some i∈Ti \in T.✦ A walk of length mm from xx to x′x' in GTG_T is a sequence x=x0,x1,…,xm=x′x = x_0, x_1, \dots, x_m = x' of points of XX with consecutive points adjacent. The graph distance dT(x,x′)d_T(x, x') is the least length of such a walk, and ∞\infty when there is none.✦

The cutoff profile of radius hh is the function φh\varphi_h on {0,1,2,…}∪{∞}\{0, 1, 2, \dots\} \cup \{\infty\} with φh(∞)=0\varphi_h(\infty) = 0 and, at a finite dd, φh(d)=max⁡(0,1−log⁡(d+1)log⁡(h+1)).\varphi_h(d) = \max\Bigl(0, \ 1 - \frac{\log(d + 1)}{\log(h + 1)}\Bigr).(4)

Now let XX be finite and 𝒯\mathcal{T} a finite family of finite sets of indices. The column index set is Y=X×𝒯Y = X \times \mathcal{T}✦, and the column gyg_y of y=(z,T)∈Yy = (z, T) \in Y is the real function on XX given by gy(x)=φh(dT(x,z)).g_y(x) = \varphi_h\bigl(d_T(x, z)\bigr).(5)✦ The profile row of a point x∈Xx \in X is the vector Rx=(gy(x))y∈YR_x = (g_y(x))_{y \in Y} of ℝY\mathbb{R}^Y, which carries the sup norm ∥v∥∞=max⁡y∈Y|vy|\|v\|_\infty = \max_{y \in Y} |v_y|.✦

For a real number θ\theta and a number uu of indices, an admissible set TT is a subset of [u]={1,…,u}[u] = \{1, \dots, u\} that misses at most θu\theta u indices; the admissible sets form the family 𝒯={T⊆[u]:|[u]\T|≤θu}.\mathcal{T} = \bigl\{T \subseteq [u] : |[u] \setminus T| \le \theta u\bigr\}.(6)✦

The Claim

Theorem 1. Let pp be a prime, E=𝔽prE = \mathbb{F}_p^r and h≥1h \ge 1, and let X=Symh(E*)X = \mathrm{Sym}^h(E^*) carry the labels L1,…,LuL_1, \dots, L_u along directions t1,…,tu∈Et_1, \dots, t_u \in E. Then |X|=pDh,|X| = p^{D_h},(7)✦ and each label takes at most pDh−1p^{D_{h-1}} values: |Li(X)|≤pDh−1(1≤i≤u).|L_i(X)| \le p^{D_{h-1}} \qquad (1 \le i \le u).(8)✦ If moreover the prime pp, the rank rr, the degree hh, the number uu of directions, the number θ\theta and the directions t1,…,tut_1, \dots, t_u are those of Proposition 4.2, then for any two distinct forms xx and x′x' in XX there is an admissible set T∈𝒯T \in \mathcal{T} with dT(x,x′)>h,d_T(x, x') > h,(9)✦ the rows of xx and x′x' satisfy ∥Rx−Rx′∥∞=1,\|R_x - R_{x'}\|_\infty = 1,(10)✦ and some column y∈Yy \in Y has |gy(x)−gy(x′)|=1.|g_y(x) - g_y(x')| = 1.(11)✦

In the paper, the result reads: with the parameters and directions of Proposition 4.2, X=Symh(E*)X = \mathrm{Sym}^h(E^*), Li(x)=x(ti,⋅,…,⋅)L_i(x) = x(t_i, \cdot, \dots, \cdot) and 𝒯={T⊆[u]:|[u]\T|≤θu}\mathcal{T} = \{T \subseteq [u] : |[u] \setminus T| \le \theta u\}, one has |X|=pDh|X| = p^{D_h}, each LiL_i has at most pDh−1p^{D_{h-1}} realized labels, every pair of distinct forms x,x′x, x' has some T∈𝒯T \in \mathcal{T} with dT(x,x′)>hd_T(x, x') > h, and the rows RxR_x of the matrix with columns indexed by Y=X×𝒯Y = X \times \mathcal{T} satisfy ∥Rx−Rx′∥∞=1\|R_x - R_{x'}\|_\infty = 1 for x≠x′x \ne x'.

What Is Checked

The claims (7) to (11) are stated over the forms of degree hh on 𝔽pr\mathbb{F}_p^r, given by their coefficients, with their labels by contraction along t1,…,tut_1, \dots, t_u, over the partition graphs GTG_T and their distances dTd_T for admissible TT, and over the rows and columns built from the cutoff profile φh\varphi_h on Y=X×𝒯Y = X \times \mathcal{T}.

The library also states two facts about these constructions in general. Let KK be any field, ti∈Krt_i \in K^r directions indexed by ii in any set, TT a nonempty finite set of indices, and xx, x′x' forms of degree h≥1h \ge 1 over KK whose difference vanishes at no hh directions from TT: (x′−x)(ta1,…,tah)≠0(x' - x)(t_{a_1}, \dots, t_{a_h}) \ne 0 whenever a1,…,ah∈Ta_1, \dots, a_h \in T. In the partition graph GTG_T of the labels by contraction, every walk ww from xx to x′x' then has length(w)>h,\mathrm{length}(w) > h,(12)✦ and the two forms satisfy dT(x,x′)>h.d_T(x, x') > h.(13)✦

For labelings LiL_i of a finite set XX, a finite family 𝒯\mathcal{T} of finite sets of indices and a radius h≥1h \ge 1, any two points xx, x′x' of XX with dT(x,x′)>hd_T(x, x') > h for some T∈𝒯T \in \mathcal{T} have ∥Rx−Rx′∥∞=1.\|R_x - R_{x'}\|_\infty = 1.(14)✦