11
$\begingroup$

In 2020, András Faragó claimed to have proved that NP = RP (discussion; v1 of the paper); the paper was later retracted due to a counterexample to theorem 1.

A few days ago, Faragó posted another claimed proof to the arXiv. Perhaps, given the first attempt, less attention will be paid to this second paper, but I still wonder whether any similar (or dissimilar) problems have been found.

$\endgroup$
4
  • 5
    $\begingroup$ Ancient Greeks had a story that is pertinent to this situation. $\endgroup$ Dec 29, 2023 at 8:55
  • 3
    $\begingroup$ The expression “Note that our sampling algorithm (if correct) has extremely surprising consequences” (emphasis mine) is not exactly inviting confidence. $\endgroup$ Dec 29, 2023 at 13:30
  • 4
    $\begingroup$ Well, the author made a mistake once. Maybe he is just trying to be modest :) $\endgroup$ Dec 29, 2023 at 18:52
  • $\begingroup$ To anybody wondering why the preprint was not retracted: I wrote to Faragó, but I believe he must have been quite ill by that point, and it seems that he has now, sadly, died. $\endgroup$ Feb 6 at 18:58

1 Answer 1

15
$\begingroup$

It seems to me that Theorem 1 in the paper is false for essentially the same reasons as the Peres example showed in the last version.

Theorem 1 seems to say the following, at least in a special case. Let $S$ be some finite domain and let $H\subset S$ denote some subset. Let $X$ be a random $n\times n$ array with entries in $S$ with the property that each $X_{i,j}$ has some fixed marginal distribution $\mathcal{D}$ on $S$ such that $H$ has positive probability, and let $\alpha$ denote the conditional distribution of $X_{i,j}$ obtained by conditioning on $X_{i,j}\in H$ (which is well-defined since $H$ has positive probability). Moreover, suppose that the entries of the matrix are jointly independent across rows (but the entries within a row need not be independent). An $H$-perfect matching of $X$ (Def. 5) is a bijection $\sigma:[n]\to [n]$ such that $X_{i,\sigma(i)}\in H$ for all $i\in [n]$. Let $M(X)$ denote the (random, possibly empty) set of $H$-perfect matchings of $X$.

Theorem 1 appears to claim that, under just these assumptions, conditioned on $X$ having a $H$-perfect matching, the distribution of $(X_{1,\tau(1)},\ldots,X_{n,\tau(n)})$ factorizes as a product measure over $\alpha$, where $\tau$ is chosen uniformly at random among all $H$-perfect matchings of $X$. That is, for any $(x_1,\ldots,x_n)\in H^n$, \begin{equation*} \Pr_{\tau\sim \mathsf{U}[M(X)]}\left(X_{i,\tau(i)}=x_i,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right)=\prod_{i=1}^n \alpha(x_i), \end{equation*} where $\mathsf{U}[M(X)]$ is the uniform distribution over $H$-perfect matchings in $X$.

For a counterexample, just take Peres' example verbatim. Let $S=\{1,2,3\}$ and $H=\{1,2\}$. For each row of $X$ independently, with probability $1/2$, sample the entries of the row i.i.d. uniformly $1$ or $2$, and with probability $1/2$, sample the entries of the row i.i.d. uniformly $1$ or $3$. Call the first situation $A$ and the second situation $B$. The marginal law of each $X_{i,j}$ is clearly $1$ with probability $1/2$ and $2$ or $3$ with probability $1/4$ each. The conditional law $\alpha$ of $X_{i,j}$ given $X_{i,j}\in H$ is $X_{i,j}=1$ with probability $2/3$ and $X_{i,j}=2$ with probability $1/3$.

Let's compute \begin{equation*} \Pr_{\tau\sim \mathsf{U}[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right). \end{equation*} Theorem 1 appears to claim that this should be $\alpha(2)^n=(1/3)^n$.

It's easy to see that that the probability $M(X)\neq \emptyset$ is $1-o(1)$ by comparison with the probability that a random bipartite graph with $1/2$ edge probability has a perfect matching via the obvious coupling. Now, we have \begin{equation*} \Pr_{\tau\sim \mathsf{U}[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right)=\Pr_{\tau\sim U[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\,\land\, \text{all rows sampled via $A$}\bigg\vert M(X)\neq \emptyset\right). \end{equation*} This holds simply because if all entries in any perfect matching are $2$, all rows must have been sampled according to situation $A$. We thus have \begin{equation*} \Pr_{\tau\sim \mathsf{U}[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\,\land\, \text{all rows sampled via $A$}\bigg\vert M(X)\neq \emptyset\right)=\Pr_{\tau\sim U[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via $A$}\,\land\,M(X)\neq \emptyset\right)\cdot\Pr\left(\text{all rows sampled via $A$}\vert M(X)\neq \emptyset\right). \end{equation*} For the second factor, by Bayes' rule, we have \begin{equation*} \Pr\left(\text{all rows sampled via $A$}\vert M(X)\neq \emptyset\right)= \frac{\Pr\left(\text{all rows sampled via $A$}\right)}{\Pr(M(X)\neq \emptyset)}=\frac{1+o(1)}{2^n}, \end{equation*} since the event that all rows are sampled via $A$ implies there exists a $H$-perfect matching. For the first factor, note that \begin{equation*} \Pr_{\tau\sim U[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via $A$}\,\land\,M(X)\neq \emptyset\right)=\Pr_{\tau\sim U[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via $A$}\right), \end{equation*} since again, the event that all rows are sampled via $A$ implies the existence of $H$-perfect matchings. In fact, all perfect matchings are valid if $A$ occurs since necessarily every entry is in $H$ by construction. But given $A$ occurs for every row, the joint law of all entries of the matrix is i.i.d. uniform over $1$ or $2$, independent of the choice of uniform random matching. So we have \begin{equation*} \Pr_{\tau\sim U[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via $A$}\right)=\frac{1}{2^n}. \end{equation*} Putting it together, we find that $\Pr_{\tau\sim \mathsf{U}[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right)=\frac{1+o(1)}{4^n}\ll \frac{1}{3^n}$.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you; I shall accept this answer once I’ve read it more closely. $\endgroup$ Jan 1 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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