104
$\begingroup$

There are several unknown numbers in mathematics, such as optimal constants in some inequalities. Often it is enough to some estimates for these numbers from above and below, but finding the exact values is also interesting. There are situations where such unknown numbers are necessarily natural numbers, for example in Ramsey theory. For example, we know that there is a smallest integer $n$ such that any graph with $n$ vertices contains a complete or an independent subgraph of 10 vertices, but we don't know the exact value of $n$.

What kinds of unknown small (less than 100, say) integers are there? What are the smallest unknown constants which are known to be integers? Or, more rigorously, what is the smallest upper bound for an unknown but definable number that is known to be an integer?

I know that asking for the smallest unknown integer is ill-defined since we do not know the exact values. The more rigorous version of the question is well-posed, but I do not want to keep anyone from offering interesting examples even if they are clearly not going to win the race for the lowest upper bound.

An answer should contain a definition of an integer quantity (or a family of them) and known lower and upper bounds (both of which should be integers, not infinite). Conjectures about the actual value are also welcome. I have given one example below to give an idea of what I'm looking for.

$\endgroup$
  • 84
    $\begingroup$ Will you be satisfied with $\begin{cases} 0 & \text{RH is true}\\ 1 & \text{RH is false}\end{cases}$? You can't go smaller than that, by the way! So it's provably the smallest possible case! $\endgroup$ – Asaf Karagila Jun 7 '15 at 12:06
  • 17
    $\begingroup$ @AsafKaragila: No. :) $\endgroup$ – Joonas Ilmavirta Jun 7 '15 at 12:07
  • 42
    $\begingroup$ The smallest infinitely often occurring prime gap. Most likely that's $2$, but we don't know yet. $\endgroup$ – Daniel Fischer Jun 7 '15 at 12:07
  • 8
    $\begingroup$ @AsafKaragila, such a gap is known to exist and the best unconditional upper bound I know is 246. See arxiv.org/abs/1409.8361 $\endgroup$ – Joonas Ilmavirta Jun 7 '15 at 12:14
  • 27
    $\begingroup$ Obviously it's the answer to the question "What is the smallest unknown natural number?" The answer to this question is unknown, by definition, and it is known to be a natural number, also by definition. And while in general, for two unknown numbers you cannot say which one is smaller, for this specific problem we know, again by definition, that it is the smallest. $\endgroup$ – celtschk Jun 8 '15 at 20:18

15 Answers 15

121
$\begingroup$

The smallest infinitely often occurring prime gap, or

$$\liminf_{n\to\infty}\; (p_{n+1} - p_n)$$

is unknown as of now. Most likely, it is $2$, but the twin prime conjecture has not yet been settled.

Due to the work of Yitang Zhang and subsequent improvements by others (notably James Maynard and Terence Tao), we know that some prime gaps occur infinitely often. Zhang proved that gaps not larger than 70 million occur infinitely often, and the improvements lowered the bound to $246$ (perhaps there have been recent further improvements I'm not aware of).

$\endgroup$
  • 72
    $\begingroup$ The improvement from $70{,}000{,}000$ to $246$ is impressive; but the improvement from infinity to $70{,}000{,}000$ is ever so slightly more impressive! :-) $\endgroup$ – Asaf Karagila Jun 7 '15 at 12:48
  • 3
    $\begingroup$ If Elliott–Halberstam conjecture is true, the bound can be lowered to $6$ (see this video). $\endgroup$ – user26486 Jun 7 '15 at 15:44
  • 54
    $\begingroup$ @GlenO Well that's not really fair. Yitang Zhang's paper set forth a new tool which allowed the problem of the Twin Prime Conjecture to be solved - previously we had no idea how to solve it at all. That was the focus of his paper, which is why he had the absurdly large starting point of $70,000,000$ (as such papers commonly do). Further decreasing of that bound is all work that only exists thanks to his pioneering. $\endgroup$ – MCT Jun 7 '15 at 17:35
  • 14
    $\begingroup$ @Soke And of course Zhang explicitly says that his goal is not to optimize the bound, just prove finiteness. $\endgroup$ – Kimball Jun 8 '15 at 7:40
  • 2
    $\begingroup$ @Soke: I know literally nothing on the subject, but all the impressions I got from reading what knowledgeable people had to say, was that it was a particularly surprising result because no new tools were used. Yiitang Zhang just squeezed the known methods down and got this bound. $\endgroup$ – Asaf Karagila Jun 9 '15 at 20:48
70
$\begingroup$

The chromatic number $\chi$ of the plane satisfies $4 \le \chi \le 7$, i.e., $\chi \in \{4,5,6,7\}$. The problem is known as the Hadwiger-Nelson problem:

What is the minimum number of colors needed to color the plane such that no two points separated by a distance of exactly $1$ are assigned the same color?

The coloring below, due to John Isbell, shows that $\chi \le 7$:


          7-colors
          (Image from mathpuzzle.com. The circles shown have unit radius.)


And the 4-colorability of the unit-distance graph, the Moser Spindle, shows that $\chi \ge 4$:


          Moser Spindle with 4 colors on nodes
Update (16 Apr 2018): Aubrey de Grey constructed a unit-distance graph of $1567$ vertices that has chromatic number $5$. See this post by Adam Goucher. This improves on the Moser spindle, and so now we know that $\chi \ge 5$, i.e., now $\chi \in \{5,6,7\}$.


      5colors
      de Grey, Aubrey DNJ. "The chromatic number of the plane is at least $5$." arXiv:1804.02385 (2018).


$\endgroup$
  • 16
    $\begingroup$ There is evidence the answer depends on the Axiom of Choice: Shelah, Saharon, and Alexander Soifer. "Axiom of choice and chromatic number of the plane." Journal of Combinatorial Theory, Series A 103.2 (2003): 387-391. $\endgroup$ – Joseph O'Rourke Jun 8 '15 at 0:08
  • 10
    $\begingroup$ That the result depends on the axiom of choice is really surprising to me. Whodathunkit! $\endgroup$ – Cameron Williams Jun 9 '15 at 2:57
  • 1
    $\begingroup$ Cute that Warring's problem $G(3)$ is also in $\{4,5,6,7\}$. $\endgroup$ – Joseph O'Rourke Jun 11 '15 at 11:48
  • 3
    $\begingroup$ @CameronWilliams There is a theorem of Erdős that a certain infinite graph coloring problem is equivalent to the negation of the continuum hypothesis; details are at What is a simple example of an unprovable statement? $\endgroup$ – MJD Jun 11 '15 at 13:51
  • 1
    $\begingroup$ @JosephO'Rourke: If it depends on it, say if it's true only if choice holds, I suppose that then means the problem is kicked into the realm of non-constructive statements? That would be a bummer. $\endgroup$ – Nikolaj-K Jun 25 '15 at 7:29
40
$\begingroup$

How about the concrete problem of understanding how many (non-intersecting) spheres can touch another sphere in low dimensions? This is known as the kissing number problem, and it is open in dimension $5$.

In dimension $2$, the kissing number is $6$, given by the hexagonal tiling of the plane: dimension2

In dimension $3$, the kissing number is $12$, which is given by spheres at the vertices of the icosahedron. Note that there is actually so much extra space in dimension $3$ that we can swap any two spheres by continuous movement that leaves all the spheres non-intersecting and touching the central sphere. In dimension $4$ the optimal kissing number configuration has $24$ spheres, given by the vertices of the $24$-cell.

As for dimension $5$, all that is known is that it is at least $40$ and at most $44$. In fact the only other dimensions for which we know the value of the kissing number problem are $8$ and $24$, and this is due to the extraordinary symmetries of the $E_8$ and Leech lattices.

$\endgroup$
38
$\begingroup$

Ramsey numbers give the smallest sizes of graphs that ensure that certain kinds of subgroups of a given size can always be found. More specifically, $R(k,l)$ is the smallest integer such that any graph with at least so many vertices contains a complete subgraph of $k$ vertices or an independent subgraph of $l$ vertices.

Some small values are known, but there are surprisingly small unknown ones. For example:

  • $36\leq R(4,6)\leq41$
  • $43\leq R(5,5)\leq48$1

The Electronic Journal of Combinatorics has a dynamical survey of small Ramsey numbers which you can consult for more details and newest bounds.


1 At the time of writing this answer the limit was $49$. Vigleik Angeltveit and Brendan D. McKay released a preprint on March 26, 2017, proving $R(5,5)\leq 48$. The value has been updated in the dynamical survey as well. If there are changes to the relevant numbers in the survey, feel free to edit. (Other sources for updates can also be mentioned, but I will restrict the listed numbers to the values of the survey for consistence.)

$\endgroup$
  • 2
    $\begingroup$ The combinatorial number for which Graham's number is an upper bound may be a good candidate for the smallest unknown number, assuming its true value is close to the lower bound. $\endgroup$ – bof Jun 7 '15 at 12:19
  • 6
    $\begingroup$ @bof Graham's number is no longer the best upper bound for that problem. $\endgroup$ – Eric Tressler Jun 8 '15 at 13:54
22
$\begingroup$

Consider the following problem:

Find the smallest $n$ such that every number $k\geq3n$ with the same parity as $n$ can be written as the sum of $n$ odd primes.

  • $n=1$ is trivially not true, because it states that every odd number is prime.
  • For $n=2$ it is the Goldbach Conjecture.
  • For $n=3$ it is the Weak Goldbach Conjecture, proven in 2013.

So the answer is in the set $\{2,3\}$.

$\endgroup$
12
$\begingroup$

Consider the value $$\max_{x \to \infty} \min \text{collatz}(x) . $$

Here, $\text{collatz}(x)$ for $x \in \mathbb{N}$ is defined as the set of generated numbers in the $3x + 1$-sequence in the Collatz conjecture when started from $x$.

Collatz conjecture is that $\max _{x \to \infty} \min \text{collatz}(x) = 1$

$\endgroup$
  • 8
    $\begingroup$ The value is conjectured to be 1, but is it known to be finite? If yes, is there a bound? $\endgroup$ – Joonas Ilmavirta Jun 7 '15 at 19:41
  • 2
    $\begingroup$ @JoonasIlmavirta If there were a (reasonable) bound, then one could prove Collatz. $\endgroup$ – Kimball Jun 8 '15 at 7:41
  • 7
    $\begingroup$ @Kimball, if it's not known to be finite, it's not necessarily a natural number. Therefore it's not exactly in the spirit of the question; if it was known to be a small integer, it would probably soon be known to be one. $\endgroup$ – Joonas Ilmavirta Jun 8 '15 at 14:32
  • $\begingroup$ That's a fair point. $\endgroup$ – Pål GD Jun 8 '15 at 14:41
  • $\begingroup$ Also, if it's not $1$ it is very large, given the work done on it. $\endgroup$ – Mark Hurd Jun 9 '15 at 3:27
9
$\begingroup$

How big is $2^{\aleph_\omega}$? ($\aleph_\omega$ is the $\omega$th uncountable cardinality.)

Of course, this question is well out of reach of ZFC, and certainly not about finite objects. However, Saharon Shelah showed that we can prove certain restrictions on this (and other) exponential quantities. In particular, he showed $$\text{If $2^{\aleph_k}<\aleph_\omega$ for every $k\in\omega$, then $2^{\aleph_\omega}<\aleph_{\omega_4}$.}$$

So far as I know the "4" is not known to be optimal, nor is there a good reason to believe it is apart from our inability to do better; see section 2 of Chapter IX of Shelah's book Cardinal Arithmetic, colorfully titled "Why the hell is it four?"

So here's an interesting unknown finite number:

What is the least $n$ such that ZFC proves: if $2^{\aleph_k}<\aleph_\omega$ for all $k\in\omega$, then $2^{\aleph_\omega}<\aleph_{\omega_n}$?

This may seem like a curiosity, but I think that computing this number - in particular, proving optimality, and reducing from 4 to something smaller if that's possible - would require fundamental advances in set theory.

$\endgroup$
  • 1
    $\begingroup$ See also my answer here. $\endgroup$ – Asaf Karagila Jun 11 '15 at 9:18
  • 3
    $\begingroup$ This is also an interesting one, because it is from set theory, and not from number theory like most here. $\endgroup$ – wythagoras Jun 11 '15 at 11:43
9
$\begingroup$

The value of $G(3)$ in the Waring's problem, or the upper bound to the number of cubes that are necessary to write a sufficiently large number.

Progress to this problem:

  • Every number that is 4 or 5 mod 9 needs 4 cubes.
  • It has been proven that 7 is enough by Linnik (1943).

Therefore $G(3)$ is a value form the set $\{4,5,6,7\}$.


Also, another thing related to Waring's problem:

What are the solutions to

$$2^k\{(3/2)^k\}+\lfloor (3/2)^k \rfloor > 2^k$$

Here $\{\}$ denotes the fractional part. It is conjectured that there are no solutions. It has been proven that there are only finitely many solutions.

$\endgroup$
  • $\begingroup$ No, $g(3)$ is the upper bound of cubes needed to express an integer. It is known to be 9 (see Wikipedia). E.g. $g(2)=4$ by Lagrange's four-square theorem and the fact that not every integer can be a sum of $2$ or $3$ cubes. $\endgroup$ – user26486 Jun 10 '15 at 4:28
  • $\begingroup$ @user26486 No this is a variant. See en.wikipedia.org/wiki/Waring's_problem $\endgroup$ – wythagoras Jun 10 '15 at 12:53
  • $\begingroup$ Well yes, I should've looked at $G(3)$. But still, $G(3)$ is defined as the upper bound of cubes needed to express a sufficiently large number. Your definition of it is wrong. $\endgroup$ – user26486 Jun 11 '15 at 11:02
  • $\begingroup$ @user26486 fixed $\endgroup$ – wythagoras Jun 11 '15 at 11:38
7
$\begingroup$

The number of Fermat primes $F_n=2^{2^n}+1$.

One can easily check $F_0\to F_4$ are all primes. In history, it was conjectured that all these were prime. However, computational data shows that $F_5\to F_{30}$ are composite. Now it is conjectured that only the first $5$ are prime.

$\endgroup$
  • 8
    $\begingroup$ Is this known to be finite? $\endgroup$ – JiK Jun 8 '15 at 9:38
  • 6
    $\begingroup$ @JiK: Not known. $\endgroup$ – user21820 Jun 8 '15 at 10:05
7
$\begingroup$

Let me post another example.

What is the ninth solitary number?

It is known to be in the set $\{10,11\}$.

In fact, it is not know for any $k \geq 9$ what the $k$th solitary number is.

$\endgroup$
6
$\begingroup$

Which one of $\zeta (5),\zeta(7),\zeta(9),\zeta(11)$ is irrational. One of these were proven to be irrational, but it is not known which one out of the 4 are irrational.

$\endgroup$
  • 3
    $\begingroup$ Of course, most likely they are all irrational, but we aren't close to proving that. $\endgroup$ – Mario Carneiro Sep 15 '15 at 23:21
5
$\begingroup$

For any integer $N$, we can ask the following question: what is the smallest integer $k$ such that $\Sigma(k)>N$ (Busy Beaver function)? The answer is unknown for every $N\geq 4098$. For $N=4098$ the answer is either $5$ or $6$, and for, say, Graham's number, the answer is between $5$ and $22$.

$\endgroup$
5
$\begingroup$

Elliptic curves over $\mathbb Q$ of rank at least 28 are known, but their exact rank is not known.

$\endgroup$
1
$\begingroup$

As an alternative to unknown numbers that have a known "small" upper bound (e.g. $1$), or are otherwise likely to be small, here's one that is not very big but could (as far as we know) be fairly big, or not so big, or perhaps as small as $1$: $$\inf_{n\in\Bbb N}\left|\sum_{k=1}^{p+n}(-1)^k(p_{k+1}-p_k)\right|,$$where $p_k$ is the $k$th prime and $p=2^{57885161}-1$ is the largest known prime. (Here $p$ is chosen for ease of statement. Obviously there are numerous variations on this theme.)

$\endgroup$
0
$\begingroup$

The number $\pi$ has a very significant history and could be the ideal object of many problems about the first position in its decimal expansion in which a given property occurs:

In what position the following property occurs first?

1) two consecutive twin numbers of two digits (six possible couples)

2) the number 5 appears 5 consecutive times

3) the first square of ten digits

4) Nothing is known about which digit appears countless times however it is clear that at least one digit does. What is this digit?

Many other similar questions can be formulated. Note that, excepting 4), it is not obvious that there are corresponding answers but it is obvious also that their probability of existence is nonzero. A way to be sure of the existence of an answer is as follows:

The famous BBP Formula

enter image description here

gives the value of any position in the expansion of $\pi$ so one can looking for some interesting property in an advanced position and ask about the minimal position at which this occurs (it can be the discovered position, of course).

$\endgroup$

protected by davidlowryduda Jun 10 '15 at 2:43

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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