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 ; this lemma bounds how many zeros a polynomial over can have.
Fix a prime and a finite set , and let be a polynomial with coefficients in in the variables , . A point of is a function , which assigns a value to each variable, and there are points. How many of them can be zeros of , when is nonzero of total degree at most a natural number ? The Schwartz-Zippel lemma answers this, and the library states its answer over as a proportion and as a count.
The Zero Set
The zero set of a polynomial over in the variables , , is the set of points of at which vanishes: (1)β¦
The Claim
Theorem 1. Let be a prime, a finite set and a natural number, and let be a nonzero polynomial over in the variables , , of total degree at most . Then the proportion of zeros of among the points of satisfies (2)β¦ and their number satisfies (3)β¦
In the paper, the result reads: if is nonzero of total degree at most , with prime, and are independent and uniform in , then , where and stands for .
For independent uniform values , , the probability that vanishes at is the proportion on the left of (2).
What Is Checked
The claim is stated over the zero set of (1), for a prime and a nonzero polynomial over in the variables of a finite set , of total degree at most .