[Math] Examples of ubiquitous objects that are hard to find

co.combinatoricscomputational complexityexamples

I've been wrestling with a certain research problem for a few years now, and I wonder if it's an instance of a more general problem with other important instances. I'll first describe a general formulation of the problem, and then I'll reveal my particular instance.

Let $S_n$ denote a set of objects of size $n$. I am interested in subsets $G_n\subseteq S_n$ with two properties:

  1. There are natural probability distributions on $S_n$ for which a random member lands in $G_n$ with high probability, so $G_n$ is ubiquitous in some sense.

  2. It seems rather difficult (and it might be impossible) to efficiently construct a member of $G_n$ along with a certificate of its membership which can be verified in polynomial time.

Question: Do you have an example of $G_n$ which satisfies both of these?

Here's my example: Let $S_n$ denote the set of real $m\times n$ matrices with $1\leq m\leq n$, fix a constant $C>0$, and say $\Phi\in G_n$ if the following holds for each $k$ satisfying $m\geq Ck\log(n/k)$: If $x\in\mathbb{R}^n$ has $k$ nonzero entries, then

$$\frac{1}{2}\|x\|^2\leq\|\Phi x\|^2\leq\frac{3}{2}\|x\|^2.$$

(This is essentially what it means for $\Phi$ to satisfy the restricted isometry property.) In this case, $G_n$ satisfies 1 above (provided $C$ is sufficiently large) by considering matrices with iid subgaussian entries. The fact that $G_n$ is plagued with 2 above is the subject of this blog entry by Terry Tao.

Best Answer

(I learned about this from a recent expository talk of Chris Fraser.)

Hilbert's seventeenth problem asks

Given a multivariate polynomial that takes only non-negative values over the reals, can it be represented as a sum of squares of rational functions?

It was resolved, in the affirmative, by Emil Artin in 1927. At the time he posed this question, Hilbert had already showed that the use of rational functions here is necessary: there exist nonnegative polynomials which cannot be expressed as a sum of squares of polynomials. But Hilbert's proof of the existence of such a polynomial was nonconstructive and it was not until Motzkin in 1967 that a specific example of such a polynomial was found (using the AM-GM inequality; see the linked Wikipedia article for the specific polyomial, which actually is not too big).

In fact, there is a precise sense (see https://arxiv.org/abs/math/0309130) in which, as the number of variables tends to infinity, the proportion of nonnegative polynomials which are sums of squares of polynomials tends to zero. Hence, even though it took 40+ years to find a specific example of a nonnegative polynomial that's not a sum of squares, "almost all" nonnegative polynomials would've worked.

Related Question