Examples of ubiquitous objects that are hard to find?

Question

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.

Answer 1

(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.

Answer 2

Almost all real numbers are undefinable (http://en.wikipedia.org/wiki/Definable_real_number). But it's (by definition) impossible to write down any formula naming any specific undefinable real, much less issue a checkable certificate for a given one.

Answer 3

Metric number theory, diophantine approximation, and the probabilistic method provides many such examples.

Example 1: It is known that for almost all real numbers (all except a set of Lebesgue measure zero), the denominator of the $n$-th convergent $q_n$ satisfies $\lim_{n \rightarrow \infty} q_n^{1/n} = \exp(\pi^2/(12 \log 2))$. However, as noted in my question here, it seems difficult to produce many examples. Standard numbers such as $\pi$ or any algebraic number of degree larger than 2 are conjectured to have this property, but it cannot be proved.

Example 2: Any example generated by the (infinite) probabilistic method of Erdos. For instance, it is known that there exists a subset $B \subset \mathbb{N}$ with the property that every sufficiently large number $n$ may be written as a sum of at most 2 elements of $B$, and that the representation function $R(n)$ of the number of ways of writing $n$ as a sum of at most two elements of $B$ satisfies $R(n) = \Theta(\log n)$. To date, no explicit example of such a $B$ is known.

Example 3: Similar to example 2, it is known that a suitable random set satisfies the result of the Gauss circle problem, but it not known whether the squares themselves have that property.

Example 4: In my question asking for whether one can prove the existence or non-existence of curves of low degrees on algebraic varieties of higher dimension, the answer received is that it's doable in 'general' surfaces, but very hard to do for any specific variety.

Answer 4

A random pair of elements of $\mathop{SL}(n, \mathbb{Z})$ (where random is defined by taking a generating set, and picking two random long words) almost certainly (meaning, with probability approaching $1$ exponentially fast in the length of the words) generates a Zariski dense free subgroup (the "free" part is a result of Richard Aoun). The Zariski density part can be confirmed/denied in polynomial time. However, checking that the group is free is almost certainly (in some philosophical sense) undecidable for $n>2.$

Answer 5

Some examples may be found in Noga Alon's Nonconstructive Proofs in Combinatorics.

I have a remark about your second condition, which talks about the difficulty/impossibility of constructing a member along with a certificate. There are at least two distinct cases here: (a) verifying the validity of the object is hard even if it is found; (b) the object is hard to find but once it is found then its validity is easy to verify.

For (a), as someone else mentioned, an example is to find a graph on $n$ vertices that contains neither a clique nor an independent set of size $2 \log_2 n$.

For (b), examples are harder to come by, because if something is ubiquitous and easy to recognize when you've found it then you can just try generating random examples until you hit on one. For this not to work, one has to weaken the definition of "with high probability." An example that I learned from Noga Alon was to find a 16-regular multigraph on $n$ vertices whose second largest eigenvalue is less than 8. The existence of these follows from a highly sophisticated probabilistic argument by Joel Friedman, but I believe no construction is known. Nonconstructive existence proofs using the local lemma are another potential source of examples, since the probabilities involved can be exponentially small, though many of these objects can now be constructed efficiently using the breakthrough work of Moser and Tardos.

Answer 6

Gromov's random groups probably provide examples of the phenomenon you describe. The idea is to construct a group by fixing a number of generators and randomly choose relations in some specified way. A number of counter-examples to hard conjectures related to geometric group theory (such as the Baum-Connes conjecture with coefficients) have been shown to exsit recently by arguing that a random group is a counter-example with positive probability. But in many cases it is not known how to verify that a specific group (i.e. a specific set of relations) has the desired property.

Answer 7

Explicit tensors or polynomials of general rank.

The Waring rank of a general polynomial (meaning, general coefficients), in a given number of variables and of a given degree, has been known since 1995 (work of Alexander-Hirschowitz). A random polynomial has this general rank with probability $1$ (with respect to any reasonable meaning of “random polynomial”). But there’s no known way to get an explicit polynomial of general rank beyond some small cases. Nor is there any good way to check if a given polynomial indeed has general rank.

Fixing a degree $d$ and letting the number of variables grow, the general rank is a polynomial of degree $d-1$ (after finitely many exceptional cases). There’s no known explicit sequence of polynomials $p_n$, of degree $d$ in $n$ variables, with rank growing with order $n^{d-1}$ (ignore $d=2$). (Elementary symmetric polynomials of odd degree achieve order $n^{(d-1)/2}$.)

I believe all of this holds as well for tensors, with the exception that in most tensor products the general rank isn’t known yet.

Answer 8

Every $n\times n$ matrix with integer entries and all row sums and all column sums equal ("semi-magic square") can be written as an integer linear combination of at most $n^2-2n+2$ permutation matrices. Almost all such matrices can't be written as integer linear combinations of fewer permutation matrices – the ones that can be so written form a finite union of lower dimensional sets. Yet it's not so easy to find, say, a $4\times4$ integer matrix with, say, two- or three-digit entries that can't be written as an integer linear combination of nine or fewer permutation matrices.