52
$\begingroup$

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?)
$\endgroup$
  • 5
    $\begingroup$ A number normal in every base (even only normal in two different bases). $\endgroup$ – Did Sep 26 '15 at 23:15
  • 5
    $\begingroup$ en.wikipedia.org/wiki/Chaitin%27s_constant ? $\endgroup$ – Chappers Sep 26 '15 at 23:21
  • 4
    $\begingroup$ Usually anything proven to exist but not constructed using Zorn's lemma. $\endgroup$ – Pedro Tamaroff Sep 26 '15 at 23:25
  • 6
    $\begingroup$ @Did Actually we know lots of explicit examples of absolutely normal numbers, see math.berkeley.edu/~slaman/papers/poly.pdf. We don't know any natural examples, but then, we don't know any natural examples exist, either. Actually, the first explicit example was given by Turing, way back in the 1930s. $\endgroup$ – Noah Schweber Sep 27 '15 at 2:21
  • 2
    $\begingroup$ @Did If you read more than the first sentence, you will see that "satisfactory" is evidently being used to mean "reasonably efficiently computable" and that the paper claims to describe a computational procedure that explicitly finds such a number, taking slightly more than quadratic time to find a given number of its bits. It explicitly cites Turing's construction and explains that they find it unsatisfactory because it takes doubly-exponential time to find a given number of bits. $\endgroup$ – Gareth McCaughan Sep 28 '15 at 12:54

18 Answers 18

47
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Can we have a citation for this weird thing? $\endgroup$ – Chappers Sep 27 '15 at 0:13
  • 2
    $\begingroup$ E.g. en.wikipedia.org/wiki/Mills%27_constant $\endgroup$ – Damian Reding Sep 27 '15 at 0:17
  • 7
    $\begingroup$ It is easy to calculate other real numbers with the same "strange" property as $r$. The only thing making this one hard to compute is the requirement that the number be as small as possible. $\endgroup$ – ASCII Advocate Sep 29 '15 at 0:19
  • 2
    $\begingroup$ You sir, made my day. That is absolutely amazing. $\endgroup$ – Frank Conry Sep 29 '15 at 3:09
  • 1
    $\begingroup$ @Frank The magic quickly disappears once you understand how it works. Then it appears rather trivial and not very interesting. That it seems like magic to many readers is probably because related topics are not normally covered in elementary number theory courses, so are little-known. $\endgroup$ – Bill Dubuque Sep 29 '15 at 3:44
28
$\begingroup$

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.

$\endgroup$
  • 10
    $\begingroup$ This isn't exactly an example. Hex and Chomp are finite, so we know the winning strategy "search all possible game trees for a winning strategy". When people say we don't know the winning strategy, they mean something like "we don't know an efficient strategy", or "we don't know an insightful strategy", but we don't know that such strategies necessarily exist. $\endgroup$ – Henry Sep 27 '15 at 23:02
  • 5
    $\begingroup$ @Henry: Then by similar logic, we know the winning or drawing strategy for either white or black in the game of chess (i.e. "search the game tree"). But I don't think most AI researchers would agree with that statement. You don't know the strategy until you can show me a perfectly played game of chess (or hex or chomp or whatever). $\endgroup$ – Kevin Sep 28 '15 at 14:33
  • 6
    $\begingroup$ @Kevin: There are two (or more) plausible things you could mean by a winning strategy---you could mean "any computable strategy", or you could only allow strategies which are "fast", "practical", or "perspicacious". My complaint is that this example is having it both ways: "we have a proof that a computable strategy exists, but have no example of a practical strategy at all". But "we proved there's an A, but can't find a B!" isn't surprising; it's just that the statement is obscured by the ambiguity of "winning strategy". $\endgroup$ – Henry Sep 28 '15 at 15:34
  • $\begingroup$ @Henry: To me, a strategy describes what move should be played at any given point in the game. "Search the game tree" is not a legal chess (or hex etc.) move. So we don't know any winning strategy. $\endgroup$ – Kevin Sep 28 '15 at 15:37
  • $\begingroup$ @Kevin: Please note that I'm not making a claim about what "winning strategy" means, only about consistency of meaning in Ross' example. Regarding your definition, what does "describe" mean? Presumably the player is allowed to do some kind of calculations before making their move. (Those calculations not being legal moves themselves seems beside the point.) Since you want to reject the "search game trees" strategy, presumably that's an improper calculation for some reason. But then how do you know that there's any strategy for Hex or Chomp which has only proper calculations? $\endgroup$ – Henry Sep 28 '15 at 16:07
24
$\begingroup$

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:

$\endgroup$
  • 5
    $\begingroup$ +1 for mentioning Ramsey numbers. I could sit here all day and ask for the value of just about any Ramsey number while being sure that the value exists and that no one knows it. $\endgroup$ – Paddling Ghost Sep 28 '15 at 16:40
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Actually there is a really fast algorithm that computes the first digit of TREE(3). We just don't know that it computes the first digit of TREE(3) and in some strong proof system, there is probably no proof of any reasonable length of what the first digit of TREE(3) is. $\endgroup$ – Timothy Aug 18 '18 at 3:14
  • $\begingroup$ @Timothy The second part of my answer - which talks about formal complexity - is about $TREE(n)$ for arbitrary $n$, not just $TREE(3)$. That is, in the first part I mention that "the leading digit of $TREE(3)$" is something we know exists but don't know how to find; the point of the second part of my answer is that it seems plausible that the general function sending $n$ to the leading digit of $TREE(n)$ is actually rigorously complicated. $\endgroup$ – Noah Schweber Aug 18 '18 at 4:21
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Never heard this one stated where the number of pieces was 5. Does that imply that the new balls are made from 2 and 3 pieces each? $\endgroup$ – Jakob Sep 29 '15 at 13:23
  • 1
    $\begingroup$ @Jakob: Here is a good accessible explanation. $\endgroup$ – Kevin Sep 29 '15 at 15:29
13
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The twin prime conjecture says exactly what the smallest repeating gap is. This is not in the category of "exist but have no idea what they are". $\endgroup$ – ASCII Advocate Oct 5 '15 at 3:31
  • 1
    $\begingroup$ @ASCIIAdvocate, it's exactly that: a conjecture. It hasn't been proven yet. $\endgroup$ – kviiri Nov 30 '15 at 8:41
  • 1
    $\begingroup$ An extremely credible conjectured value (for the smallest gap) is not in the category of things that "exist but we have no idea what they are". @kviiri $\endgroup$ – ASCII Advocate Dec 1 '15 at 3:59
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Riemann mappings can be computed using circle packings. $\endgroup$ – ASCII Advocate Sep 29 '15 at 0:11
  • $\begingroup$ You mean approximated, I guess? $\endgroup$ – Per Alexandersson Sep 29 '15 at 0:42
  • 1
    $\begingroup$ Yes. What else could "compute" possibly mean here? $\endgroup$ – ASCII Advocate Sep 29 '15 at 4:38
7
$\begingroup$

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

$\endgroup$
5
$\begingroup$
  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)$.
$\endgroup$
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

Nobody has a clue what one is like.

$\endgroup$
  • 2
    $\begingroup$ There are many equivalent ways of stating the Axiom of Choice. Kunen's book simply states it as "Every set can be well-ordered." Kurt Godel showed that AC is consistent with the other axioms (ZF). The method of Forcing invented by Paul Cohen was used to show that the negation of AC is also consistent, and that is is consistent that R cannot be well-ordered.So if a well-ordering of R could be shown from ZF, then you can prove "1=0" from ZF, which would be most embarrassing to all of us. $\endgroup$ – DanielWainfleet Sep 27 '15 at 20:08
  • 2
    $\begingroup$ I didn't say ZF shows a well-ordering of R; I said ZFC shows it. $\endgroup$ – MJD Sep 27 '15 at 20:50
  • 1
    $\begingroup$ yes of course. I didn't contradict you.Nor did I mean to. $\endgroup$ – DanielWainfleet Sep 27 '15 at 23:06
  • 1
    $\begingroup$ This is a bit of an odd example, actually, because it is consistent that $\mathbb{R}$ does have a definable (specifically, $\Delta^1_2$) ordering. So, if e.g. we accept "$V=L$" as an axiom, we do know what this looks like. $\endgroup$ – Noah Schweber Sep 29 '15 at 2:07
  • $\begingroup$ I'm not sure it's necessarily true that no one has a clue what a well-ordering of R looks like. Some really good mathematicians might be able to figure out all sorts of complex properties that they can prove that all well-orderings of R have. $\endgroup$ – Timothy Aug 18 '18 at 3:26
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Could you elaborate a bit on the $\mathbb F_{29}$ problem? $\endgroup$ – YoTengoUnLCD Sep 30 '15 at 3:41
  • $\begingroup$ This is not the question about. However,at first try, I think in verify $f(x)\ne 0$ for the twenty nine elements of this field. Possible perhaps a more elegant way..... $\endgroup$ – Piquito Oct 1 '15 at 14:01
  • $\begingroup$ Maybe you have inquired about the "infinitely many": the algebraic cloture of $\mathbb F_p$ is the infinite union of all the finite fields $\mathbb F_{p^n}$ each of them being an extension of degree $n$ of $\mathbb F_p$. $\endgroup$ – Piquito Oct 1 '15 at 14:09
  • $\begingroup$ They're just $ \pm \sqrt{-3}$ by the quadratic formula. $\endgroup$ – Spooky Oct 4 '15 at 8:11
  • 1
    $\begingroup$ I do not think you dare to say "they're just" $\pm 1.732050808\sqrt{-1}$ but in the quadratic extension of $\mathbb F_{29}$ $\endgroup$ – Piquito Oct 4 '15 at 21:37
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.