needle-in-the-haystack

A common problem in mathematics is to prove the existence and uniqueness of a solution, element, object in a category, etc. The typical approach for such a proof is to establish the existence of the solution, then determine the uniqueness. In instances like this, uniqueness is often proved by assuming there are two solutions and concluding they are indeed equal.

Needle-in-a-haystack Heuristic

An alternative and often more constructive approach is to prove uniqueness first, then prove existence – we call this the needle-in-the-haystack heuristic because it is much easier to find a needle in a haystack when you first prove you know where it will be if it is there at all.¹¹This terminology is due to F. R. Beyl

We give a basic example from elementary mathematics.

Proposition 1.

Two distinct non-parallel lines in a the $x y$ -plane intersect at exactly one point.

We pause to observe this is an existence and uniqueness question: a point of intersection must exist, and it must be unique. Because we care only about illustrating the heuristic we assume our meaning of lines excludes vertical lines, so each line is given by a function of the form $y=mx+b$ .

Proof.

Let $y_{1}=m_{1}x+b_{1}$ and $y_{2}=m_{2}x+b_{2}$ be distinct lines which are non-parallel; hence, $m_{1}\neq m_{2}$ . If $y_{1}=y_{2}$ for some $x$ then $m_{1}x+b_{1}=m_{2}x+b_{2}$ so $(m_{1}-m_{2})x=b_{2}-b_{1}$ . This leads to $\displaystyle x=\frac{b_{2}-b_{1}}{m_{1}-m_{2}}$ . Thus we have uniquely characterized any intersection point as the point $\displaystyle(x,y_{1}(x))$ , with $\displaystyle x=\frac{b_{2}-b_{1}}{m_{1}-m_{2}}$ , if an intersection exists.

To see that an intersection exists we appeal to the unique characterization.

y_{1}\left(\frac{b_{2}-b_{1}}{m_{1}-m_{2}}\right)=m_{1}\frac{b_{2}-b_{1}}{m_{1% }-m_{2}}+b_{1}=\frac{m_{1}b_{2}-m_{2}b_{1}}{m_{1}-m_{2}}=m_{2}\frac{b_{2}-b_{1% }}{m_{1}-m_{2}}+b_{2}=y_{2}\left(\frac{b_{2}-b_{1}}{m_{1}-m_{2}}\right).

∎

Remark 2.

After establishing a unique characterization of a solution it is often so convincing as to leave no need for the verification of the solution, so the existence stage of the proof may be omitted. [Indeed, a standard pre-calculus course would not hesitate to stop the proof at end of the uniqueness stage.]

If we chose to write the theorem in the traditional manner and introduce the existence first, then we would have begun with a rather unpredictable beginning:

Let $\displaystyle x=\frac{b_{2}-b_{1}}{m_{1}-m_{2}}$ .

Such an approach is no less logical but can leave a reader confused as to the reason these choices are being made.

Furthermore, to prove the uniqueness of a solution by means of assuming there are two solutions can be a misleading approach for some problems. For example, the intersection of $f(x)=x^{2}-8x$ with $g(x)=-3x-4$ is unique, but given two solutions $(x_{1},y_{1})$ , $(x_{2},y_{2})$ , it becomes rather difficult to conclude $(x_{1},y_{1})=(x_{2},y_{2})$ directly. With the needle-in-the-haystack heuristic one begins the proof by showing the only solution is $(4,-16)$ , if there is a solution. Thus we never compare two systems of equations in several variables.

When to use the heuristic

When an existence and uniqueness is claimed where there are accompanying equations or structures that must be satisfied by the solution, it is often possible to apply the heuristic. Often such problems can be worded as two sets intersecting at a single point. If the possible point of intersection is characterized before we know the intersection is non-empty, then we have an immediate candidate with which we may prove the intersection is non-empty.

When not to use the heuristic

There are, however, many examples where the traditional approach of establishing existence first is preferable. For instance, in a proof that every integer has a unique factorization, establishing some factorization exists is nearly trivial: choose a prime $p$ which divides $n$ , then by induction choose a prime factorization $q_{1}\cdots q_{s}$ of $n/p$ , and then $n=pq_{1}\cdots q_{s}$ is a prime factorization of $n$ . However, establishing the uniqueness of a prime factorization is a far more delicate matter.

The heuristic applies best when the definition of the solution, element, or object in question is not immediately presentable from the definition. When a definition provides a blue-print for establishing existence then the traditional method may be preferable.

Title	needle-in-the-haystack
Canonical name	Needleinthehaystack
Date of creation	2013-03-22 16:07:34
Last modified on	2013-03-22 16:07:34
Owner	Algeboy (12884)
Last modified by	Algeboy (12884)
Numerical id	10
Author	Algeboy (12884)
Entry type	Definition
Classification	msc 00A35