OctoInformBeta

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

Proposition 4.2 [Directions with nonvanishing evaluations]: For a large prime pp, u=⌈2hDh/θ⌉u = \lceil 2hD_h/\theta\rceil directions in 𝔽pr\mathbb{F}_p^r where each nonzero form of degree hh needs at most θu\theta u deletions

Directions on which no nonzero form vanishes after few deletions.

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

This proposition is a step in the counterexamples to the duality conjecture for metric entropy, in their part on finite-field partitions and separated rows. Let pp be a prime, rr and hh positive integers, and E=𝔽prE = \mathbb{F}_p^r. The question is whether a single list of directions t1,…,tu∈Et_1, \dots, t_u \in E, its length uu fixed by rr, hh and a real 0<θ<10 < \theta < 1 before pp is chosen, serves every nonzero symmetric hh-linear form ZZ on EE at once: after at most θu\theta u directions are deleted, the deleted ones depending on ZZ, the form should be nonzero at every hh-tuple of the remaining directions, repeated directions allowed. For h=1h = 1 it asks for uu vectors of EE of which at most θu\theta u lie in any one hyperplane through the origin.

Symmetric Forms and Directions

A point vv of EE is a function on {1,…,r}\{1, \dots, r\} with values in 𝔽p\mathbb{F}_p, and [u][u] denotes {1,…,u}\{1, \dots, u\}. A symmetric form ZZ of degree jj on EE, an element of Sym⁡j(E*)\operatorname{Sym}^j(E^*), is the symmetric jj-linear map Ej→𝔽pE^j \to \mathbb{F}_p given by a coefficient cm∈𝔽pc_m \in \mathbb{F}_p for each multiset mm of jj indices from {1,…,r}\{1, \dots, r\}: Z(v1,…,vj)=∑a1,…,aj=1rc{{a1,…,aj}}v1(a1)⋯vj(aj),Z(v_1, \dots, v_j) = \sum_{a_1, \dots, a_j = 1}^{r} c_{\{\!\{a_1, \dots, a_j\}\!\}}\, v_1(a_1) \cdots v_j(a_j),(1) where {{a1,…,aj}}\{\!\{a_1, \dots, a_j\}\!\} is the multiset of the indices. The number of such multisets, and so the dimension of Sym⁡j(E*)\operatorname{Sym}^j(E^*), is Dj=(r+j−1j).D_j = \binom{r + j - 1}{j}.(2)✦

The number of directions attached to rr, hh and a real θ>0\theta > 0 is the integer u=⌈hwθ⌉,w=2Dh.u = \Bigl\lceil \frac{h w}{\theta} \Bigr\rceil, \qquad w = 2 D_h.(3)✦

The Claim

Theorem 1. Let pp be a prime, rr and hh positive integers, 0<θ<10 < \theta < 1, and uu the number of directions (3). Suppose p>hp > h and p>h2u2hp > h^2 u^{2h}. Then there are directions t1,…,tu∈Et_1, \dots, t_u \in E such that every nonzero symmetric form ZZ of degree hh on EE has a nonempty set T⊆[u]T \subseteq [u] with |[u]\T|≤θuandZ(ti1,…,tih)≠0 for all (i1,…,ih)∈Th.|[u] \setminus T| \le \theta u \quad\text{and}\quad Z(t_{i_1}, \dots, t_{i_h}) \neq 0 \ \text{ for all } (i_1, \dots, i_h) \in T^h.(4)✦ More generally, for a real θ<1\theta < 1 and a positive integer uu satisfying hw≤θu,h<p,h2u2h<ph w \le \theta u, \qquad h < p, \qquad h^2 u^{2h} < p(5)✦ in place of (3) and the bounds on pp, there are directions t1,…,tu∈Et_1, \dots, t_u \in E with the same property.

In the paper, the result reads: for 0<θ<10 < \theta < 1, positive integers rr and hh, w=2Dhw = 2D_h, u=⌈hw/θ⌉u = \lceil hw/\theta \rceil and a prime p>max⁡{h,h2u2h}p > \max\{h, h^2 u^{2h}\}, there are t1,…,tu∈𝔽prt_1, \dots, t_u \in \mathbb{F}_p^r such that for every nonzero Z∈Sym⁡h(E*)Z \in \operatorname{Sym}^h(E^*) some T⊆[u]T \subseteq [u] with |[u]\T|≤θu|[u] \setminus T| \le \theta u has Z(ti1,…,tih)≠0Z(t_{i_1}, \dots, t_{i_h}) \neq 0 for all (i1,…,ih)∈Th(i_1, \dots, i_h) \in T^h, repeated indices allowed.

What Is Checked

The claim is stated over the prime field 𝔽p\mathbb{F}_p and E=𝔽prE = \mathbb{F}_p^r, the symmetric forms of degree hh on EE given by their coefficients on multisets and evaluated by (1), the dimension DhD_h of (2) and the number of directions uu of (3).

The diagonal polynomial of a symmetric form ZZ of degree hh with coefficients cmc_m is the polynomial in 𝔽p[X1,…,Xr]\mathbb{F}_p[X_1, \dots, X_r] PZ=∑b1,…,bh=1rc{{b1,…,bh}}Xb1⋯Xbh,P_Z = \sum_{b_1, \dots, b_h = 1}^{r} c_{\{\!\{b_1, \dots, b_h\}\!\}}\, X_{b_1} \cdots X_{b_h},(6)✦ whose value at x∈Ex \in E is Z(x,…,x)Z(x, \dots, x). Let p>hp > h and let ZZ be a nonzero symmetric form of degree hh on EE. Then PZ≠0P_Z \neq 0(7)✦ and its total degree is exactly hh: deg⁡PZ=h.\deg P_Z = h.(8)✦

On lists of directions, the uniform probability of a set A⊆EuA \subseteq E^u is Pr⁡(A)=|A|/|E|u\Pr(A) = |A| / |E|^u.✦ For a set B⊆EhB \subseteq E^h of hh-tuples of vectors and an index tuple a=(a1,…,ah)∈[u]ha = (a_1, \dots, a_h) \in [u]^h, the tuple event Aa(B)A_a(B) is the set of lists t∈Eut \in E^u with (ta1,…,tah)∈B(t_{a_1}, \dots, t_{a_h}) \in B.✦ The zero set of a symmetric form ZZ of degree hh on EE is VZ={(v1,…,vh)∈Eh:Z(v1,…,vh)=0}V_Z = \{(v_1, \dots, v_h) \in E^h : Z(v_1, \dots, v_h) = 0\}. Let p>hp > h, let ZZ be a nonzero symmetric form of degree hh on EE, and let a∈[u]ha \in [u]^h, repeated indices allowed. Then Pr⁡(Aa(VZ))≤hp.\Pr\bigl(A_a(V_Z)\bigr) \le \frac{h}{p}.(9)✦

For a positive integer DD and natural numbers hh, uu and pp with h2u2h<ph^2 u^{2h} < p, pDu2hD(hp)2D<1.p^D\, u^{2hD} \Bigl(\frac{h}{p}\Bigr)^{2D} < 1.(10)✦

The support of an hh-tuple a=(a1,…,ah)a = (a_1, \dots, a_h) of elements of a set UU is the set {a1,…,ah}\{a_1, \dots, a_h\} of its entries✦, and hh-tuples L1,…,LwL_1, \dots, L_w have pairwise disjoint supports when the supports of LiL_i and LjL_j are disjoint for all i≠ji \neq j.✦ Let EE be any finite set, pp, DD and ww any natural numbers, 𝒵\mathcal{Z} a finite set with at most pDp^D elements and, for each z∈𝒵z \in \mathcal{Z}, Bz⊆EhB_z \subseteq E^h a set of bad hh-tuples. If Pr⁡(Aa(Bz))≤hp for all z∈𝒵 and a∈[u]h,pDuhw(hp)w<1,\Pr\bigl(A_a(B_z)\bigr) \le \frac{h}{p} \ \text{ for all } z \in \mathcal{Z} \text{ and } a \in [u]^h, \qquad p^D u^{hw} \Bigl(\frac{h}{p}\Bigr)^{w} < 1,(11)✦ then there is a list t∈Eut \in E^u such that for every z∈𝒵z \in \mathcal{Z} and all index tuples L1,…,Lw∈[u]hL_1, \dots, L_w \in [u]^h with pairwise disjoint supports, at least one of the tuples (tLj(1),…,tLj(h))(t_{L_j(1)}, \dots, t_{L_j(h)}) lies outside BzB_z.

Let UU be a finite set, hh a positive integer, ww a natural number, and B⊆UhB \subseteq U^h a set of bad hh-tuples among which no ww have pairwise disjoint supports. Then there is a set T⊆UT \subseteq U with |U\T|≤h(w−1)andTh∩B=∅.|U \setminus T| \le h(w - 1) \quad\text{and}\quad T^h \cap B = \emptyset.(12)✦