11

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.

Emil Jeřábek
  • 17,430
  • 3
  • 61
  • 90
Jiak Kantang
  • 123
  • 5

1 Answers1

15

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

Jason Gaitonde
  • 965
  • 6
  • 6