24
$\begingroup$

Although any theorem (or true conjecture) can be computationally checked, many long-standing open problems have been computational verified for very large values. For example, the Collatz Conjecture and Fermat's Last Theorem (before it was proven) were computationally verified by large scale computation programs. Not only have these calculations been carried out, but there is a lengthy history of improving the bound for which these calculations have been carried out until.

What are other problems (not necessarily from number theory) have been similarly verified for values up to some large bound, and how high have they been checked? Specifically I’m interested in cases where is an established history of computationally verifying the problem up to larger and larger bounds.

I’m interested both in the current cutting edge and the history of the computation.

$\endgroup$
  • 6
    $\begingroup$ I suppose you are specifically interested in open problems? The Collatz conjecture has been checked up to values on the order of $87\cdot 2^{60}$. $\endgroup$ – JMoravitz Aug 6 '18 at 20:30
  • 1
    $\begingroup$ @JMoravitz Most examples are conjectures, though I think this did happen for FLT before it was solved. That example is still interesting to me. $\endgroup$ – Stella Biderman Aug 6 '18 at 20:38
  • 4
    $\begingroup$ Although not particularly impressive of a number at first glance, the Union-closed sets conjecture is known to be true for all sets of size up to 46. When you realize that there are $2^{46}$ subsets in the power set and $2^{2^{46}}$ possible families of subsets (ignoring the closed under union property) it becomes more exciting. I'm not sure how it was verified up to $46$, whether it was from computer assistance or not, but it is still an interesting open problem. $\endgroup$ – JMoravitz Aug 6 '18 at 20:38
  • 1
    $\begingroup$ Legendre's conjecture? $\endgroup$ – Bram28 Aug 6 '18 at 20:52
  • 3
    $\begingroup$ I've voted to close as too broad. Testing problems numerically is generally pretty easy compared to proving them, so pretty much any open problem about the natural numbers will have been checked. This is not to say that there is not a great deal of expertise that goes into checking things numerically, or that certain problems are not more amenable than others to such testing, but without anything more precise than 'large values', it's difficult to find anything to narrow down this list at all beyond 'all open problems'. $\endgroup$ – John Gowers Aug 6 '18 at 20:55
25
$\begingroup$

The nonexistence of Fermat primes beyond $65537$ has been verified, as far as I know, to $2^{2^{32}}+1$. Thereby, we have identified the last constructible regular prime-sided polygon up to a point far beyond where any such construction could be carried out. (Based on current theories of quantum gravity, a regular polygon having the shortest possible side length and "only" $2^{2^8}+1$ sides would not fit in the known Universe.)

It was, of course, Euler who first killed Fermat's conjecture that $2^{2^n}+1$ is prime for all natural numbers $n$, by disproving it for $n=5$. Now the opposite conjecture is in vogue, and it has been verified up to $n=32$. Testing of Fermat numbers for primality can be accomplished by Pepin's Test, a stronger form of Fermat's Little Theorem whereby a Fermat number $M\ge 5$ is prime iff $3^{(M-1)/2}\equiv -1 \bmod M$. Because Pepin's test does not directly identify factors when the number is composite, $2^{2^n}+1$ has no known factors, despite being certified composite, for $n=20$ and $n=24$.

See here for a more thorough discussion of Fermat numbers.

$\endgroup$
  • $\begingroup$ That’s a super cool note about Fermat primes. $\endgroup$ – Stella Biderman Aug 6 '18 at 20:58
  • 6
    $\begingroup$ Funnily enough, C programmers have a completely different name for $2^{2^5} + 1$, namely UINT_MAX + 2. (You do need to cast it properly or else it rolls over.) $\endgroup$ – Kevin Aug 7 '18 at 7:01
  • $\begingroup$ @Kevin In the embedded world, 16-bit ints are still not uncommon. $\endgroup$ – Daniel Fischer Aug 7 '18 at 10:04
  • $\begingroup$ @Kevin: I feel that when you add an abritrary value to a constant that it kind of stops being a name. UINT_MAX is a significant named number. UINT_MAX+k is just any number you want.... $\endgroup$ – Chris Aug 7 '18 at 16:04
  • $\begingroup$ @Chris: But this way we have twin composite numbers! Isn't that neat? $\endgroup$ – Kevin Aug 7 '18 at 16:12
18
$\begingroup$

Whether or not there exist any odd perfect numbers is an open problem. Numbers up to $10^{1500}$ have been checked (as of $2012$) without any success.

$\endgroup$
  • $\begingroup$ To see that there's "an established history of computationally verifying the problem," as the OP requested, I referred to oddperfect.org and Ochem and Rao's "Odd perfect numbers are greater than 10^1500." $\endgroup$ – Vectornaut Aug 8 '18 at 3:01
  • $\begingroup$ Ochem and Rao (unpublished) claims to have already pushed the computations to a lower bound of ${10}^{2000}$ for odd perfect numbers. (See their website.) $\endgroup$ – Jose Arnaldo Bebita-Dris Aug 8 '18 at 5:28
13
$\begingroup$

The Goldbach Conjecture has been verified up though $4\times 10^{18}$ by Oliviera e Silva (as of 2012). The history of these computations (13 previous records) can be found on Mathworld.

The Riemann Hypothesis has been verified through $10^{13}$ by X Gourdon (2004). The history of these computations can be found on Wikipedia.

The Union-closed Set Conjecture has been verified up to sets of size $46$ as well as for other special cases. The specific lower bound of size $46$ was found by Roberts and Simpson in 2010. The previous records were 18 (Sarvate and Renaud 1990) and 40 (Roberts 1992). Mathworld lists several other results that fail to beat Roberts 1992.

$\endgroup$
12
$\begingroup$

The Collatz conjecture, also called the $3x+1$ conjecture or Hail Stone sequence has been verified up to $87\times 2^{60}$ as of $2017$. More information can be found on Wikipedia.

$\endgroup$
  • 1
    $\begingroup$ Wikipedia lists two bounds, the current one and one from 1981. Would you happen to know if intermediary values have been calculated between 1981 and 2017? $\endgroup$ – Stella Biderman Aug 6 '18 at 20:55
  • 2
    $\begingroup$ "The 3x + 1 Problem and Its Generalizations". Amer. Math. Monthly. 92: 3–23. 1985. will provide a good amount of information about the problem and its history. $\endgroup$ – Mohammad Riazi-Kermani Aug 6 '18 at 21:36
9
$\begingroup$

Firoozbakht's conjecture states that, if $p_n$ is the $n$th prime numbers, then the sequence $\left(\sqrt[n]{p_n}\right)_{n\in\mathbb N}$ is strictly decreasing. It has never been proved, but it it has already been checked for the primes below $10^{19}$.

$\endgroup$
  • $\begingroup$ Do you have a source for this claim? I haven’t been able to find it, or any other computational results that didn’t get up to this bound $\endgroup$ – Stella Biderman Aug 6 '18 at 21:43
  • 3
    $\begingroup$ @StellaBiderman Please see here. $\endgroup$ – José Carlos Santos Aug 6 '18 at 21:45
7
$\begingroup$

Searching of solutions of the Diophantine equation

$$x^3+y^3+z^3=k$$

for small $k$ ($k<1000$) has been performed for $|x|,|y|,|z|$ up to $10^{15}$.

For $k<100$, solutions were not yet found for $k=33$ and $k=42$. For $k<1000$, there are 14 values without solution.


Edit: 33 has been cracked.

$\endgroup$
6
$\begingroup$
  • The Hadamard Conjecture states that a Hadamard matrix of order $4k$ should exist for every positive integer $k$. It has been numerically verified for all orders up to 668.
  • The Circulant Hadamard Conjecture posits that there are no circulant Hadamard matrices of order $>4$, and has been verified numerically for most values up to $10^4$.

If you allow liberal interpretation of "large values" as "high confidence", several of the Millennium Prize Problems provide examples.

  • The mass gap part of the Yang-Mills Existence and Mass Gap problem has been numerically verified using lattice QCD. To do this, you discretize space on a lattice and evaluate the spectrum of the Hamiltonian, and refining the computation is done by using a finer lattice. At this point the numerical evidence is so overwhelming that it's not really meaningful to ask "to what bound has it been checked?"; we "know" that the mass gap part of this problem is true--the only challenge is proving it rigorously. In the past, though, this sort of computation was at the very frontier of supercomputing, and there was a time when verifying the existence of a mass gap (and related phenomena) numerically was a major industry.
  • The origin of the Birch and Swinnerton-Dyer Conjecture was in number crunching on elliptic curves. The content of the conjecture is to rigorously prove certain trends which are observed numerically. I don't know how well those trends are now established numerically (but the linked Wikipedia article has plots showing roughly $10^6$ data points).
  • The Riemann Hypothesis has been verified numerically to something like ten trillion zeroes.

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