Natural theorems proven only "to high probability"?

Question

There are plenty of situations where a randomized "proof" is much easier than a deterministic proof, the canonical example being polynomial identity testing.

Question: Are there any natural mathematical "theorems" where a randomized proof is known but a deterministic proof is not?

By a "randomized proof" of a statement $P$ I mean that

1. There is a randomized algorithm that takes an input $n > 0$ and if $P$ is false produces a deterministic proof of $\neg P$ with probability at least $1-2^{-n}$.

2. Someone has run the algorithm for, say, $n = 100$, and not disproved the theorem.

It's easy to generate non-natural statements that fit: just pick a large instance of any problem where only an efficient randomized algorithm is known. However, although there a lot of mathematical theorems with "lots of numerical evidence", such as the Riemann hypothesis, I don't know of any with rigorous randomized evidence of the above form.

Answer 1

$ \DeclareMathOperator{\inv}{inv} \DeclareMathOperator{\maj}{maj} $ This is not an example of what you are asking for, but it suggests how such an example can come about. Some combinatorial identities can be encoded as identities about polynomials of bounded degree $d$. If the polynomials are univariate, to prove the identity it is enough to verify it on $d+1$ points. However, if the polynomials are multivariate, and the degree is at least moderately large, the Scwartz-Zippel lemma may be the only practical way to verify the identity.

For an example of the univariate case, check this article by Zeilberger, resolving a question of Knuth. He proves a statement about statistics of permutations. For a permutation $\pi \in S_n$, let $\inv(\pi)$ be the number $|\{(i, j): i < j, \pi(i) > \pi(j)\}|$ of inversions of $\pi$, and let the major index $\maj(\pi)$ of $\pi$ be the sum of all integers in the set $\{i: \pi(i+1) < \pi(i)\}$ . Zeilberger proves that, for all $n$, the covariance of the two statistics is

$$ \mathbb{E}[(\inv(\pi) - \mathbb{E}[\inv(\pi)])\cdot(\maj(\pi) - \mathbb{E}[\maj(\pi)])] = \frac{1}{4}{n \choose 2}, $$ where all expectations are over a uniformly random $\pi$ in $S_n$. Zeilberger's proof is just a computer verification for $n \in \{1, 2, 3, 4, 5\}$, and an observation that the statement is equivalent to an identity between polynomials in $n$ of degree at most $4$.

Answer 2

I think this paper contains an example of what you are after. Though the error in the random process is two-sided, that is even if the statement were false this approach would only give a "high probability assurance" of that fact.

Claims 2.3 and 2.4 in that paper are natural (non-parametraized) statements about the subject at hand. The authors do not provide proofs (presumably not for lack of trying to some degree, given they prove multiple other results in the paper) however they do reduce the truth of those claims to bounds on high dimensional integrals, which they then check using Monte Carlo methods and confirm “with high probability”.