Let n be a positive integer, A_1,dots, A_n be symmetric positive semidefinite matrices, and let lVert,·,rVert be the spectral norm. For m≤ n, compare the average of all ordered products with the average of ordered products having distinct indices. Recht-Ré conjecture. For every m≤ n, frac1n^mlVert∑_1≤ j_1,…,j_m≤ n A_j_1… A_j_mrVert≥frac(n-m)!n!lVert∑_substack1≤ j_1,…,j_m≤ n,j_1,…,j_m distinct A_j_1… A_j_mrVert. This inequality was proposed to compare with-replacement and without-replacement sampling, but the paper shows that it is false as stated, including a counterexample for m=5.

Recht-Ré conjecture for noncommutative arithmetic-geometric means

About 12 years old · traced to 2014

Let $n$ be a positive integer, $A_1,\dots, A_n$ be symmetric positive semidefinite matrices, and let $\lVert\,\cdot\,\rVert$ be the spectral norm. For $m\leq n$ , compare the average of all ordered products with the average of ordered products having distinct indices. Recht-Ré conjecture. For every $m\leq n$ ,

\frac{1}{n^m}\left\lVert\sum_{1\leq j_1,\dots,j_m\leq n} A_{j_1}\cdots A_{j_m}\right\rVert\geq\frac{(n-m)!}{n!}\left\lVert\sum_{\substack{1\leq j_1,\dots,j_m\leq n,\j_1,\dots,j_m\ \text{distinct}}} A_{j_1}\cdots A_{j_m}\right\rVert.

This inequality was proposed to compare with-replacement and without-replacement sampling, but the paper shows that it is false as stated, including a counterexample for $m=5$ .

References

Primary source

Zehua Lai and Lek-Heng Lim, “Recht-Ré Noncommutative Arithmetic-Geometric Mean Conjecture is False”, arXiv:2006.01510 (2020).

Additional references

2 papers in this index state this conjecture (2014–2020). The statement above is taken from the most recent of them; the others are arXiv:1411.0333.

Posted 1 month ago

Progress summary

Refreshed 4 weeks ago

Claimed solved

A 2020 paper reports that the proposed inequality fails in a five-factor case, but the supplied record contains no independent verification.

Recht and Ré proposed the comparison for sampling with and without replacement. The exact conjecture is reported false in general, although the published computational argument does not exhibit explicit matrices.

Known results

The inequality holds for $m=2$ and $m=3$ for arbitrary $n$ .
Earlier work established the relevant $n=2$ case and a special $n=3$ case.

June 2020 counterexample claim

On June 2, 2020, Zehua Lai and Lek-Heng Lim's paper Recht–Ré Noncommutative Arithmetic-Geometric Mean Conjecture is False reduced the problem to a semidefinite program and reported, for $m=n=5$ , an optimum near $144.6488$ , above the conjectured value $5!=120$ . They claim this proves existence of violating positive semidefinite matrices, but their method supplies neither explicit matrices nor the minimum counterexample dimension; $m=4$ remains open in the stated generality.

Current status (as of September 2026): The conjecture is claimed false through the $m=n=5$ semidefinite-program computation, while explicit counterexamples, independent verification, and the remaining refined questions are unresolved.

Sources

No solutions have been posted yet.