# Examples of ubiquitous objects that are hard to find?

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.

• That is extremely common situation in combinatorics and computer science. Many probabilistic method proofs give rise to such a situation. For example, we still do not know an explicit construction of Ramsey graphs with exponentially many vertices. – Boris Bukh Dec 30 '13 at 12:25
• Avi Widgerson even referred to the problem as that of "Finding Hay in the Haystack". – Boris Bukh Dec 30 '13 at 12:26
• For example mathcamp.org/2013/academics/week4blurbs-mc13.pdf (page 9/10, where it appears as "hay in a haystack"). – Noam D. Elkies Dec 30 '13 at 16:51

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.

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.

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

• I believe undecidability of freeness is still open for groups but for semigroups it is undecidable. – Benjamin Steinberg Dec 31 '13 at 21:50

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.

• I feel like (b) comes up quite a bit in complexity theory. Take any "hard" instance of an NP-complete problem whose answer is "yes" and try to find a certificate. For example, find a clique of size $n^\epsilon$ that the devil hid in an ER graph with $p=1/2$. – Dustin G. Mixon Dec 31 '13 at 11:00
• @Dustin: Yes, although these sorts of examples perhaps stretch the definition of "with high probability" a bit too far. The examples I mentioned at least have probabilistic proofs of existence. – Timothy Chow Dec 31 '13 at 18:09

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.