The Product Audit

Part A: 1/4

First compute the error $D=AB-C$: $$AB=\left(\begin{array}{ccc}5& 1& 4\\ 10& 5& 3\\ 6& 10& 4\end{array}\right),D=\left(\begin{array}{ccc}1& -1& 0\\ 0& 0& 2\\ 0& 0& 0\end{array}\right).$$ The check misses exactly when $Dr=0$. Row 0 gives $r_0-r_1=0$ and row 1 gives $2r_2=0$. Of the 8 vectors in $\{0,1{\}}^3$, two satisfy both: $(0,0,0)$ and $(1,1,0)$. The miss probability is $2/8=1/4$. The two errors in row 0 can cancel each other, which an error in a single entry cannot.

Part B: 1/10

Take a nonzero row $d$ of $D$, and an index $j$ with $d_j\ne 0$. Fix every entry of $r$ except $r_j$. Then $d·r=0$ holds for at most one value of $r_j$, so for at most 1 of its 10 values. The check misses with probability at most $1/10$, and a single wrong entry reaches that bound: $D$ with one 1 misses exactly when that column's $r_j=0$.

The same argument for any finite set $S$ of values gives a miss probability of at most $1/|S|$. This is the Schwartz–Zippel lemma for a polynomial of degree 1: a nonzero polynomial of degree $d$ vanishes at a random point of $S^n$ with probability at most $d/|S|$.

Part C: one check with a wide range

So the range is what matters, not the number of checks. The solution takes one vector with entries below $2^{64}$:

def audit(n, times_A, times_B, times_C, rand):
    r = [rand(2**64) for _ in range(n)]
    return times_A(times_B(r)) == times_C(r)

That is three products and a miss probability of at most $2^{-64}$. Python's integers are exact, so the entries' size costs nothing in correctness. Two checks with entries below $2^{20}$ also pass.

What the grader catches:

• The 0/1 vector, twice. Each check misses a single wrong entry half the time, so two miss it a quarter of the time, and over hundreds of audits some slip through.
• Entries 0 to 9, twice. A miss chance of $1/100$ per audit: over 300 audits, some miss.
• A fixed vector. All ones misses an error whose row sums to zero. $1,2,4,\dots$ misses $D$ with the row $(2,-1,0,\dots )$. No fixed vector works, because the wrong $C$ may be chosen after the vector is known.
• Arithmetic modulo a famous prime. Comparing modulo ${10}^9+7$ cannot see an error equal to ${10}^9+7$. A prime chosen at random at audit time would be fine.
• Multiplying out column by column is exact but needs $n$ products of each kind.

Going further

• Polynomial identity testing is the general form: decide whether a polynomial, given as a circuit, is identically zero. Schwartz–Zippel makes it easy with randomness. No deterministic polynomial-time algorithm is known, and finding one would prove circuit lower bounds (Kabanets and Impagliazzo).
• Perfect matchings. A graph has one exactly when the determinant of its Tutte matrix, with random values substituted, is nonzero (with high probability). This leads to parallel matching algorithms (Mulmuley, Vazirani and Vazirani).
• Checking a product of polynomials $p·q=r$: evaluate all three at one random point. This is the simplest use of the same idea, and it sits behind fingerprinting (Fingerprinting and String Matching).

References

1. R. Freivalds. Probabilistic machines can use less running time. IFIP Congress, 1977.
2. J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM 27(4), 1980.
3. R. Zippel. Probabilistic algorithms for sparse polynomials. EUROSAM, 1979.
4. K. Mulmuley, U. V. Vazirani, V. V. Vazirani. Matching is as easy as matrix inversion. Combinatorica 7(1), 1987.
5. V. Kabanets, R. Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity 13, 2004.