OctoInformBeta

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

Lemma 4.1 [Polynomial zero bound]: When the total degree is at most dd, the zeros make up at most a fraction d/pd/p of all assignments of the variables

A nonzero polynomial of low degree over 𝔽p\mathbb{F}_p has few zeros.

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

The counterexamples to the duality conjecture for metric entropy have a part on finite-field partitions and separated rows, which works over a prime field 𝔽p\mathbb{F}_p; this lemma bounds how many zeros a polynomial over 𝔽p\mathbb{F}_p can have.

Fix a prime pp and a finite set VV, and let PP be a polynomial with coefficients in 𝔽p\mathbb{F}_p in the variables zvz_v, v∈Vv \in V. A point of 𝔽pV\mathbb{F}_p^V is a function V→𝔽pV \to \mathbb{F}_p, which assigns a value to each variable, and there are p|V|p^{|V|} points. How many of them can be zeros of PP, when PP is nonzero of total degree at most a natural number dd? The Schwartz-Zippel lemma answers this, and the library states its answer over 𝔽p\mathbb{F}_p as a proportion and as a count.

The Zero Set

The zero set Z(P)Z(P) of a polynomial PP over 𝔽p\mathbb{F}_p in the variables zvz_v, v∈Vv \in V, is the set of points of 𝔽pV\mathbb{F}_p^V at which PP vanishes: Z(P)={zβˆˆπ”½pV:P(z)=0}.Z(P) = \{\, z \in \mathbb{F}_p^V : P(z) = 0 \,\}.(1)✦

The Claim

Theorem 1. Let pp be a prime, VV a finite set and dd a natural number, and let PP be a nonzero polynomial over 𝔽p\mathbb{F}_p in the variables zvz_v, v∈Vv \in V, of total degree at most dd. Then the proportion of zeros of PP among the points of 𝔽pV\mathbb{F}_p^V satisfies |Z(P)|p|V|≀dp,\frac{|Z(P)|}{p^{|V|}} \le \frac{d}{p},(2)✦ and their number satisfies p|Z(P)|≀dp|V|.p\,|Z(P)| \le d\,p^{|V|}.(3)✦

In the paper, the result reads: if Pβˆˆπ”½p[z1,…,zk]P \in \mathbb{F}_p[z_1, \dots, z_k] is nonzero of total degree at most dd, with pp prime, and U1,…,UkU_1, \dots, U_k are independent and uniform in 𝔽p\mathbb{F}_p, then Pr⁡(P(U)=0)≀d/p\Pr(P(U) = 0) \le d/p, where U=(U1,…,Uk)U = (U_1, \dots, U_k) and kk stands for |V||V|.

For independent uniform values Uvβˆˆπ”½pU_v \in \mathbb{F}_p, v∈Vv \in V, the probability that PP vanishes at UU is the proportion on the left of (2).

What Is Checked

The claim is stated over the zero set Z(P)Z(P) of (1), for a prime pp and a nonzero polynomial PP over 𝔽p\mathbb{F}_p in the variables of a finite set VV, of total degree at most dd.