What are some things we can prove they must exist, but have no idea what they are?

Question

What are some things we can prove they must exist, but have no idea what they are?

Examples I can think of:

• Values of the Busy beaver function: It is a well-defined function, but not computable.
• It had been long known that there must be self-replicating patterns in Conway's Game of Life, but the first such pattern has only been discovered in 2010
• By the Well-ordering theorem under the assumptions of the axiom of choice, every set admits a well-ordering. (See also Is there a known well ordering of the reals?)

Answer 1

Take objects which existence proof uses the axiom of choice, e.g:

• Each vector space has a basis (the standard existence proof uses Zorn's lemma). How does a concrete basis of $C[a,b]$ look like? What about $\mathbb R$ as a $\mathbb Q$-vector space?
• Ultrafilter, which are used in the construction of the hyperreals: Does the sequence $(0,1,0,1,0,1,\ldots)$ represent $0$ or $1$? The answer to this question depends on the chosen ultrafilter, but its existence proof uses the axiom of choice...

Well defined numbers for which only estimations are currently known:

• Ramsey numbers.

Answer 2

There are a number of games, like Hex and Chomp, for which it is easy to prove a first player win by strategy stealing but we do not generally know the winning strategy.

Answer 3

Not sure if this satisfies the requirement that we "have no idea what they are", but the extremely strange Mill's constant seems worth mentioning here: There is supposed to be some real number $r>0$ with the property that the integer part of $$r^{3^n}$$ is prime for every natural $n$. It is not known if $r$ is rational and as far as I know not even a numerical approximation of $r$ is possible without assuming the Riemann hypothesis.

Source: Wikipedia

Answer 4

Collisions in cryptographic hashes must exist due to the pigeonhole principle. Although some collisions have been found for some hash functions, we "have no idea what they are" in the sense that they aren't readily calculated.

Answer 5

(1) From the set-theory axiom system called ZFC we can prove that the set of reals has a cardinal number $\mathfrak{c}$. But, assuming that ZFC is consistent, we don't know what $\mathfrak{c}$ is: it cannot be proven or disproven from ZFC that $\mathfrak{c}$ is the least uncountable cardinal, or the second or even the $\mathfrak{c}$-th.

(2) Perhaps someone else can help with this one, as I forget the references and the details: a unique positive real r, whose decimal digits have a certain property. It was easily shown that $0<r<2$ but impossible to prove or disprove that $r<1$ or $r=1$ or $r>1$.

Answer 6

The leading (decimal) digit of the ludicrously huge number $TREE(3)$. (See https://cp4space.wordpress.com/2012/12/19/fast-growing-2/ and http://www.cs.nyu.edu/pipermail/fom/2006-March/010279.html.)

---

OK, one might object "But that's an absolutely uninteresting object!" That may be; I'd argue, though, that it is meta-interesting in the following sense. The problem

Determine the leading digit of $TREE(n)$

is, I think, likely to be extremely hard - I would bet my entire life savings that it is not in $P$, $NP$, $EXP$, . . . or really any reasonable complexity class at all, simply because in order to compute it we seem to have to compute $TREE(n)$. But as far as I know, proving that we need to do this (let alone making clear what we mean by this) is galactically out of reach, and I would be extremely surprised if I lived to see even a proof that the problem is not linear-time computable.

So I'd argue that the leading digits of such huge numbers are interesting as a class, even if individually they're a bit pointless, because they represent a really weird kind of intractable computation.

Answer 7

A partition of the 3D ball into 5 distinct pieces such that, through only translations and rotations, the pieces can be moved and reassembled into two balls, each of equal size to the original.

This is the Banach-Tarski paradox. The existence of such a partition depends on the axiom of choice, so in particuar there is no way to say exactly what the partition looks like, other than the fact that one exists.

Answer 8

The functions given by the Riemann mapping theorem.

A simply connected region can be mapped bijectively and holomorphically onto the open unit disk. Take some slightly weird shape, say, a square with 4 half-circles attached to the sides, and it is likely there is no nice description on how this map looks like.

Similarly, there are a lot of such examples when dealing with unique solutions to differential equations.

Answer 9

1. A function $\mathcal{G}(n)$ that, for each positive integer $n$, gives the length of the Goodstein sequence for $n$. We know such a function is well-defined and finite for all $n \in \mathbb Z^+$, but the function values get so large for small $n$ that it is difficult to compute.
2. Moser's worm problem for a convex set. Blaschke's selection theorem guarantees a solution exists but we don't know what it looks like.
3. Waring's problem of computing $g(n)$ and $G(n)$.

Answer 10

ZFC proves that there exists a well-ordering of the real numbers. (Many such, in fact.)

Nobody has a clue what one is like.

Answer 11

What is the least infinitely repeating prime gap? See the recent work by Zhang, et. al.

Answer 12

Many problems that are just computationally hard. Only about 40 or so Mersenne primes are known (not a very good example, because there is no proof they are infinite, so we might know all of them. ).

Take the sequence of primes p where the gap between p and the next larger prime is larger than any earlier gap between consecutive prime numbers.

These two are borderline hard; we can make progress (find the next Mersenne prime, find the next larger gap between consecutive primes), but it takes a huge amount of processing power.

A hard one: Find a set of k consecutive integers which contains more prime numbers than the set of k integers from 2 to k+1. (It is known that such a set must have more than 2000 elements, and its elements would be huge).

Let pi(n) = floor (pi x $10^n$). List the complete factorisation, with proof, of pi(n) for 1 ≤ n ≤ $10^6$. (I think such a list could be checked for correctness by computer in a reasonable amount of time; creating it would be absolutely impossible - it would for example require factoring many numbers of several hundred thousand digits).

Answer 13

It can be proved, for instance,that $x^2+x+1$ is irreducible in $\mathbb F_p[x]$ for $p=29$ which gives two "irrational" elements (the two roots of the polynomial) in a quadratic extension of $\mathbb F_{29}$.

What kind of object is each of these two roots? Absolutely non idea.

And for all finite field there are in general infinitely many of these "irrationals" which are in no way similar to the algebraic numbers.

Answer 14

There are many examples of objects whose existence can be proven using Probability Theory. One example is the existence of matrices with the restricted isometry property: https://en.wikipedia.org/wiki/Restricted_isometry_property. If one wants matrices of certain dimensions, the only known way to construct them is to create matrices at random using a certain process. And the probability that they do have the RIP property is so high that from an engineering standpoint, they can actually be used as such. But knowing for certain if a matrix is RIP is NP-hard.

Answer 15

How would a basis for $\mathbb R$ as a field over $\mathbb Q$ look like? By the axiom of choice we know one must exist, but I have no idea how it would look. It would be quite odd, as it must be large enough so that every real number can be expressed as a finite sum of its elements, but it must be small enough to be linearly independent.

---

For a simpler example, what would be a basis for $\mathbb F_2^\mathbb N$?

Answer 16

The constant in the Berry-Esseen theorem:

If we have a bunch of i.i.d. random variables $(X_j)_{j\geq 1}$ with a finite third moment, that is $E[|X_j|^3]<\infty$ (and thus they also have some mean $\mu$ and variance $\sigma^2$), then we can prove without too much trouble that their scaled average, $A_n := \frac{(\sum_{j=1}^n X_j)-n\mu}{\sigma \sqrt{n}}$ converges in distribution to the standard normal distribution $\mathcal{N}(0,1)$. This is just a weak version of the Central Limit Theorem. (The first few sections of this Wikipedia article give a list of CLTs that assume less)

Denote $A_n$'s cumulative distribution function as $G_n(x)$, and call the standard normal's CDF $\Phi(x).$

We can prove that for any sample size $n$, then $$\sup_x |G_n(x)-\Phi(x)|\leq c \cdot \frac{E\{|X|^3\}}{\sigma^3\sqrt{n}},$$ for some universal $c>0.$

As of 2012 we know $c < 0.4748$ (at the time the book was published it was $c<0.7975$), but that's our best guess.

The CLT tells us that $A_n$ will get close to the normal distribution, eventually as $n$ gets large. The Berry-Esseen theorem tells us how close it is guaranteed to get, for any $n$ you specify.

Or at least, it's supposed to, we just don't know precisely how well. This is interesting because a strange constant no one has seen before pops out of seemingly nowhere, given only routine conditions.

Answer 17

I'm suprised that the following two haven't shown up:

• What is the smallest Riesel number?
• What is the smallest Sierpiński number?

In both cases we know they exist because they are smaller than or equal to 509,203 and 78,557 respectively.

Answer 18

Let $C$ denote the standard Cantor set. And $$r+C=\{x+r\mid x\in C\},\,\forall r\in\Bbb R$$ By Baire Category Theorem we know that there surely exist values of $r$ (in fact, they are even dense in $\Bbb R$) such that $r+C$ doesn't contain any rational number, however we have little idea of any concrete example.