Research proof index

If G is a polynomial generator, then G is zero-evading with error the maximum of the total degrees of the individual polynomials divided by the size of the smallest evaluation sets S i. Remark 3.20, the version of the statement in the brackets [BCGM25]. Note: Remark 3.20 provides two ways of viewing a polynomial generator as a zero-evading generator...

Law of Total Probability (Partitioning an Event) The probability of an event f r occurring can be calculated by summing the probabilities of two disjoint cases: 1. f r occurs AND g r occurs. 2. f r occurs AND g r does NOT occur. Good to be used with Pr_multi_let_equiv_single_let

Monotonicity of Probability If event A (defined by predicate f) implies event B (defined by predicate g) for all outcomes r, then the probability of A is less than or equal to the probability of B.

Probability of a nonzero polynomial evaluating to zero over a uniform product distribution is at most d / m, where d bounds the total degree and m bounds below the cardinality of each factor. This bridges schwartz_zippel_counting with the probability formulation.

Helper lemma for probability marginalization. Pr_{ (x, y) ← D₁ × D₂ }[ P x ] = Pr_{ x ← D₁ }[ P x ]

Schwartz-Zippel Lemma (Probability Form): For a non-zero multivariate polynomial P of total degree at most d over a finite field L, the probability that P(r) evaluates to 0 for a uniformly random r is at most d / |L|.