15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Kaveh: Thanks for the category corrections. I wasn't sure what to put it under. $\endgroup$ – Geoffrey Irving Mar 6 '14 at 1:58
  • 1
    $\begingroup$ another direction, studying "derandomization" literature (looking for good survey also). wasnt the relatively recent (award winning) Reingold theorem also a case of this (again prior to the proof)? $\endgroup$ – vzn Mar 6 '14 at 17:52
  • 1
    $\begingroup$ Well any problem with a deterministic proof resting on the ERH (like Primes used to be) would have this property $\endgroup$ – Suresh Venkat Mar 6 '14 at 18:01
  • 1
    $\begingroup$ 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. $\endgroup$ – domotorp Mar 6 '14 at 19:05
  • 2
    $\begingroup$ 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. $\endgroup$ – Geoffrey Irving Mar 6 '14 at 21:54
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks, that's a lovely article. I quite like the moral. $\endgroup$ – Geoffrey Irving Mar 6 '14 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.