Is there any conjecture that has been proved to be solvable/provable but whose direct solution/proof is not yet known?

Question

In mathematics, is there any conjecture about the existence of an object that was proven to exist but that has not been explicitly constructed to this day? Here object could be any mathematical object, such as a number, function, algorithm, or even proof.

Answer 1

It is known that there is an even integer $n\le246$ such that there are infinitely many primes $p$ such that the next prime is $p+n$, but there is no specific $n$ which has been proved to work (although everyone believes that every even $n\ge2$ actually works).

Answer 2

I am not sure this answers your question but it seems to come close. The Wikipedia article Skewes number states

In number theory, Skewes's number is any of several extremely large numbers used by the South African mathematician Stanley Skewes as upper bounds for the smallest natural number $x$ for which $\, \pi(x) > \textrm{li}(x) \,$ where $\pi$ is the prime-counting function and $\, \textrm{li} \,$ is the logarithmic integral function.

It further states that

All numerical evidence then available seemed to suggest that $\, \pi(x) \,$ was always less than $\, \textrm{li}(x). \,$ Littlewood's proof did not, however, exhibit a concrete such number $x$.

The problem is that even though the existence of the number $x$ has been proven, we only know huge upper bounds on the first such number.

Perhaps a better example is from the Wikipedia article Ramsey theory where

Problems in Ramsey theory typically ask a question of the form: "how many elements of some structure must there be to guarantee that a particular property will hold?"

These Ramsey numbers have the property that

Results in Ramsey theory typically have two primary characteristics. Firstly, they are non-constructive: they may show that some structure exists, but they give no process for finding this structure (other than brute-force search). For instance, the pigeonhole principle is of this form. Secondly, while Ramsey theory results do say that sufficiently large objects must necessarily contain a given structure, often the proof of these results requires these objects to be enormously large – bounds that grow exponentially, or even as fast as the Ackermann function are not uncommon.

Thus, in theory, some of these enumerative numbers exist but they are too huge to write explicitly. In other cases, there exist small bounds but it is very hard to narrow the bounds.

Answer 3

It's known that no matter the size of the board, the first player has a winning strategy in Chomp, but an explicit winning strategy is only known for smallish boards.

Answer 4

Well, this might be an example of what you are asking for:

Take the question "are there irrational numbers $a,b$ such that $a^b$ is rational?"

A quick way to see that there are is to consider $\alpha =\sqrt 2^ {\sqrt 2}$.

Either $\alpha$ is rational or irrational. If it is rational, then we are done. If it is irrational then consider $\alpha^{\sqrt 2}=2$. Either way, we can find an example.

To be sure, it is possible (though quite difficult) to show that $\alpha$ is irrational and there are other ways to get direct examples (such as $e^{\ln 2}$) that settle the problem . But this indirect proof is so simple it is, I think, worth study.

Answer 5

Define the following number:

$$K = \begin{cases} 1, & \text{if Riemann Hypothesis is true} \\ 0, & \text{if it is false} \end{cases}$$

Since the Riemann Hypothesis is either true or false, the above constant $K$ is well-defined, mathematically. It is one specific number. But no one knows whether it is 0 or 1 (because knowing it means knowing the answer to the hypothesis).

I know this example is very artificial, but nevertheless I thought it was interesting to share - basically any unsolved problem in mathematics can be converted in an object that certainly exists but knowing what it is becomes equivalent to solving the problem itself in the first place.

Answer 6

There are sentences, called Parikh sentences for which there are short proofs that the sentence is provable but all proofs are very long. My discussion is based on page 17 of Noson Yanofsky's arXiv article A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points. He constructs a sentence $\mathcal{C}_{n}$ that says, "I do not have a proof of myself that is shorter than $n$. Then choose a large $n$, say $P!$, where $P$ is a reasonable estimate of the number of electrons in the observable universe.

In the above article Yanofsky states his discussion is based on R. Parikh's Existence and Feasiblity in Arithmetic.

Answer 7

Not every mathematical object can be explicitly constructed. For example, there are uncountably many real numbers, but only countably many finite strings in a given finite alphabet (let's say ASCII). An explicit construction of a real number is a finite ASCII string, and by definition it can only construct at most one real number, so that leaves uncountably many real numbers that can't be explicitly constructed.

Answer 8

One could say that for many problems that are NP hard, it is often known that the solution exists, but (in many cases) we don't have the computational power to evaluate it exactly, so we use algorithms that we hope are close to the optimal solution.

Probably one of the most commonly known NP hard problems is the traveling salesman. In this problem, we want to find the shortest route connecting a set of nodes. Clearly, a solution does exist; in fact, it's really easy to consider a finite set of candidate solutions, one of which must have the shortest route.

The problem is that generally speaking, this finite set we need to consider is still very large, and we must evaluate the length on the routes for each element in these sets to obtain the answer. Simplistic approaches result in a set of size $O(n!)$. Reading through the wikipedia page on the problem, it seems that there are methods that reduce this to $O(n^2 2^n)$. Note that this means the human race does not have enough computational power to solve this problem for a couple hundred nodes within our lifetime [citation needed].

But a solution must exist!

Answer 9

Maybe the Picard–Lindelöf theorem is what you are looking for. It is an existence theorem for solutions of differential equations and it uses the Banach fixed point theorem. It basically says, under certain conditions differential equations have a unique solution. But to find the solution for any given differential equation is rather hard (and not alway possible).

Answer 10

It is known that the game of Hex cannot end in a draw (visually this makes sense, either there is a path side to side or up and down). This implies that the first player has a winning strategy since the first player can always 'steal' the second player's strategy. However, an explicit strategy is only known for very small boards.

Answer 11

stackzebra posted an answer, which has been deleted by a moderator. It's a very simple answer, but, I think, a good one, so I'm going to post it (in a modified form) here:

It has been proved that there is a prime greater than $10^{10^{100}}$ – indeed, Euclid proved that there are infinitely many such primes – but no example has ever been given. The largest known primes are as infinitesimals compared to this number.