<p>$
\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 <a href="http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma">Scwartz-Zippel lemma</a> may be the only practical way to verify the identity.</p>

<p>For an example of the univariate case, check this <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/brute.pdf">article</a> 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 &lt; j, \pi(i) &gt; \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) &lt; \pi(i)\}$ . Zeilberger proves that, for all $n$, the covariance of the two statistics is</p>

<p>$$
\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$. </p>

CC BY-SA 3.0
2014-03-06T21:56:38.513Z
Thanks, that's a lovely article.  I quite like the moral.
Geoffrey Irving
CC BY-SA 3.0
2014-03-06T21:07:09.653Z
2014-03-06T21:07:09.653Z
Sasho Nikolov
<p>I think <a href="https://arxiv.org/pdf/1610.07430" rel="nofollow noreferrer">this paper</a> 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 &quot;high probability assurance&quot; of that fact.</p>
<p>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”.</p>

CC BY-SA 4.0
2024-10-29T13:53:26.357Z
2024-10-29T13:53:26.357Z
James Bell-Clark
<p>There are plenty of situations where a randomized "proof" is much easier than a deterministic proof, the canonical example being polynomial identity testing.  </p>

<p><strong>Question</strong>: Are there any natural mathematical "theorems" where a randomized proof is known but a deterministic proof is not?</p>

<p>By a "randomized proof" of a statement $P$ I mean that</p>

<ol>
<li><p>There is a randomized algorithm that takes an input $n &gt; 0$ and if $P$ is false produces a deterministic proof of $\neg P$ with probability at least $1-2^{-n}$.</p></li>
<li><p>Someone has run the algorithm for, say, $n = 100$, and not disproved the theorem.</p></li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2014-03-06T01:58:49.153Z
@Kaveh: Thanks for the category corrections.  I wasn't sure what to put it under.
Geoffrey Irving
CC BY-SA 3.0
2014-03-06T04:06:52.117Z
for a long time primality testing in P fit this category until early 2000s when AKS PTime algorithm discovered
vzn
CC BY-SA 3.0
2014-03-06T04:13:54.833Z
It is true that "Integer <n> is prime" once generated a large number of theorems satisfying the definition, but that I am looking for examples that aren't simply large instances of $BPP-P$ problems.
Geoffrey Irving
CC BY-SA 3.0
2014-03-06T17:52:02.260Z
another direction, studying "derandomization" literature (looking for good survey also). wasnt the relatively recent (award winning) [Reingold theorem](http://en.wikipedia.org/wiki/SL_(complexity)) also a case of this (again prior to the proof)?
vzn
CC BY-SA 3.0
2014-03-06T18:01:08.813Z
Well any problem with a deterministic proof resting on the ERH (like Primes used to be) would have this property
Suresh Venkat
CC BY-SA 3.0
2014-03-06T19:05:21.933Z
I am sorry to say but I don't think your question makes sense, as there cannot be any such statements, natural or not. You write that N is a prime used to be a good example but (of course) there has always been a deterministic proof as well for primality, just a bit longer. I also cannot imagine how you would define the success probability of an algorithm that is supposed to disprove one fix statement. Maybe you want to ask for an efficient proof for a class of problems (i.e., the input would be P and n and the statement P(n)) but then we arrive to complexity theory and the definition of BPP.
domotorp
CC BY-SA 3.0
2014-03-06T21:54:13.667Z
domotorp: It is true that (assuming the algorithm uses a bounded number of random bits) any such randomized proof can be derandomized with some performance cost.  However, I am asking about examples where the performance cost is high enough that the deterministic proof has not been run to date, while the randomized proof has.  I believe the definitions make sense in this context.
Geoffrey Irving
CC BY-SA 3.0
2014-03-06T21:58:14.473Z
Suresh: Do you mean that ERH has such a randomized proof?  ERH can be used to derandomize Miller, but I'm not sure how this generalizes to all statements conditional on ERH.
Geoffrey Irving
<lo.logic><randomness><randomized-algorithms><proofs>
Natural theorems proven only "to high probability"?
Geoffrey Irving
# Natural theorems proven only "to high probability"?

(Asked by: username_0 on 2014-03-06)

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.

**Tags:** lo.logic, randomness, randomized-algorithms, proofs
> **Comments:**
> **username_0**: @Kaveh: Thanks for the category corrections.  I wasn't sure what to put it under.  
> **username_1**: for a long time primality testing in P fit this category until early 2000s when AKS PTime algorithm discovered  
> **username_0**: It is true that "Integer <n> is prime" once generated a large number of theorems satisfying the definition, but that I am looking for examples that aren't simply large instances of $BPP-P$ problems.  
> **username_1**: another direction, studying "derandomization" literature (looking for good survey also). wasnt the relatively recent (award winning) [Reingold theorem](http://en.wikipedia.org/wiki/SL_(complexity)) also a case of this (again prior to the proof)?  
> **username_2**: Well any problem with a deterministic proof resting on the ERH (like Primes used to be) would have this property  
> **username_3**: I am sorry to say but I don't think your question makes sense, as there cannot be any such statements, natural or not. You write that N is a prime used to be a good example but (of course) there has always been a deterministic proof as well for primality, just a bit longer. I also cannot imagine how you would define the success probability of an algorithm that is supposed to disprove one fix statement. Maybe you want to ask for an efficient proof for a class of problems (i.e., the input would be P and n and the statement P(n)) but then we arrive to complexity theory and the definition of BPP.  
> **username_0**: domotorp: It is true that (assuming the algorithm uses a bounded number of random bits) any such randomized proof can be derandomized with some performance cost.  However, I am asking about examples where the performance cost is high enough that the deterministic proof has not been run to date, while the randomized proof has.  I believe the definitions make sense in this context.  
> **username_0**: Suresh: Do you mean that ERH has such a randomized proof?  ERH can be used to derandomize Miller, but I'm not sure how this generalizes to all statements conditional on ERH.  

---

## 2 answers

### Answer by username_4 on 2014-03-06. Score: 6

$
\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](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma) may be the only practical way to verify the identity.

For an example of the univariate case, check this [article](http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/brute.pdf) 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$.

> **Comments:**
> **username_0**: Thanks, that's a lovely article.  I quite like the moral.  

---

### Answer by username_5 on 2024-10-29. Score: 4

I think [this paper](https://arxiv.org/pdf/1610.07430) 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”.


---

