# What is the smallest unknown natural number?

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.

• 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! Jun 7, 2015 at 12:06
• @AsafKaragila: No. :) Jun 7, 2015 at 12:07
• The smallest infinitely often occurring prime gap. Most likely that's $2$, but we don't know yet. Jun 7, 2015 at 12:07
• @AsafKaragila, such a gap is known to exist and the best unconditional upper bound I know is 246. See arxiv.org/abs/1409.8361 Jun 7, 2015 at 12:14
• 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. Jun 8, 2015 at 20:18

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

• 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! :-) Jun 7, 2015 at 12:48
• If Elliott–Halberstam conjecture is true, the bound can be lowered to $6$ (see this video). Jun 7, 2015 at 15:44
• @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.
– MCT
Jun 7, 2015 at 17:35
• @Soke And of course Zhang explicitly says that his goal is not to optimize the bound, just prove finiteness. Jun 8, 2015 at 7:40
• Since the question was about the smallest unknown integer, please take that number and divide by 2 :-) Oct 24, 2015 at 23:29

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$: (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$: 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\}$. de Grey, Aubrey DNJ. "The chromatic number of the plane is at least $5$." arXiv:1804.02385 (2018).

• 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. Jun 8, 2015 at 0:08
• That the result depends on the axiom of choice is really surprising to me. Whodathunkit! Jun 9, 2015 at 2:57
• Cute that Warring's problem $G(3)$ is also in $\{4,5,6,7\}$. Jun 11, 2015 at 11:48
• @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?
– MJD
Jun 11, 2015 at 13:51
• @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. Jun 25, 2015 at 7:29

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

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

• 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.
– bof
Jun 7, 2015 at 12:19
• @bof Graham's number is no longer the best upper bound for that problem. Jun 8, 2015 at 13:54

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\}$.

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.

• This is also an interesting one, because it is from set theory, and not from number theory like most here. Jun 11, 2015 at 11:43

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$

• The value is conjectured to be 1, but is it known to be finite? If yes, is there a bound? Jun 7, 2015 at 19:41
• @JoonasIlmavirta If there were a (reasonable) bound, then one could prove Collatz. Jun 8, 2015 at 7:41
• @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. Jun 8, 2015 at 14:32
• That's a fair point. Jun 8, 2015 at 14:41
• Also, if it's not $1$ it is very large, given the work done on it. Jun 9, 2015 at 3:27

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.

• 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. Jun 10, 2015 at 4:28
• @user26486 No this is a variant. See en.wikipedia.org/wiki/Waring's_problem Jun 10, 2015 at 12:53
• 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. Jun 11, 2015 at 11:02
• @user26486 fixed Jun 11, 2015 at 11:38

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.

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.

• Of course, most likely they are all irrational, but we aren't close to proving that. Sep 15, 2015 at 23:21

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.

• Is this known to be finite?
– JiK
Jun 8, 2015 at 9:38
• @JiK: Not known. Jun 8, 2015 at 10:05

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

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

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

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