27
$\begingroup$

I explain my title by two examples in number theory:

The rational points on elliptic curve over number fields forms a finitely generated abelian group, so its rank is an integer, but so far we do not have an algorithm that outputs this integer once we input an equation, in finite time.

Another example is the Mordell conjecture on finiteness of rational points on curves of higher genus, which is proved by Faltings. I am not sure recent breakthrough can output the number of solutions once we input a equation of genus greater than one, in finite time.

My question, which maybe should be community wiki, asks more examples (in number theory and other areas of course) like these two, interesting objects having been proved finite but no algorithm found so far. I think such examples are interesting, because this means their proof does not give an algorithm. However, there are finiteness results and their proof like what happens for class groups of number fields do give algorithms to compute them at least in principle.

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ Finding the generators of the Cox ring of a Mori dream space is an incredibly hard problem. Algorithms exist, but there are no known general bounds for its termination. $\endgroup$
    – user347489
    Commented Jul 17 at 10:26
  • 5
    $\begingroup$ Somewhat related: What's the earliest result (outside of logic) that cannot be proven constructively? $\endgroup$
    – Timothy Chow
    Commented Jul 17 at 12:20
  • 1
    $\begingroup$ It is a highly nontrivial result that the set of dimensions for which the smooth Poincaré conjecture fails is finite. But there is no known algorithm which will output this set. (Yes I know that there is a logic trick where you can say "oh but there's an algorithm which outputs $\varnothing$ and an algorithm which outputs $\{4\}$ so there is..." But there is not one single known algorithm which outputs the set of counterexamples to smooth Poincaré.) $\endgroup$
    – Sam Hopkins
    Commented Jul 17 at 17:16
  • $\begingroup$ Regularized values of many divergent series and integrals are finite yet unknown. Particularly, those related to prime numbers. $\endgroup$
    – Anixx
    Commented Jul 17 at 18:28
  • $\begingroup$ Dimensions and measures of many fractals are unknown as well. $\endgroup$
    – Anixx
    Commented Jul 17 at 18:30

8 Answers 8

Reset to default
29
$\begingroup$

Most of Diophantine approximation falls into the category. For example, Roth's theorem says that for any non-rational algebraic number $\alpha\in\overline{\mathbb Q}\smallsetminus\mathbb Q$ and any $\epsilon>0$, there are only finitely many rational numbers $p/q\in\mathbb Q$ satisfying $$ \left|\frac{p}{q}-\alpha\right| \le \frac{1}{|q|^{2+\epsilon}}, \tag{$*$}\label{475221_star}$$ but there is no proven algorithm to find all such $p/q$ for a given $\alpha$ and $\epsilon$. There are results, similar to the ones you quote for rational points on curves, that give an upper bound on the number of solutions, but they do not give the exact number of solutions to \eqref{475221_star}. Indeed, Vojta's proof of the Mordell conjecture follows the lines of classical Diophantine approximation proofs, which is why it similarly gives bounds for the number of solutions, but not for the size of the largest solution.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Yann Bugeaud's book Approximation by Algebraic Numbers gives many more examples of ineffective results in Diophantine approximation. In terms of irrationality measures, it is known that (for example) the irrationality measure of $\pi$ is at most 7.1032... but we can't say how large $p$ and $q$ have to be in order to be "sufficiently large." $\endgroup$
    – Timothy Chow
    Commented Jul 17 at 12:05
17
$\begingroup$

Heath-Brown proved that Artin's conjecture on primitive roots has at most two counterexamples. So for example, we know that the conjecture is true for at least one element of the set $\{2,3,5\}$, but we have no algorithm that will tell us which one(s).

Another result with a similar flavor is that we know from work of Zudilin (building on work of Rivoal) that at least one element of the set $\{\zeta(5), \zeta(7), \zeta(9), \zeta(11)\}$ is irrational, but we can't say which one. See Sprang's paper for more information.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ It took me a little while to understand in what sense these are "proven finiteness" results but now I think I do understand. So I'm leaving this comment in case anyone else is confused. For example, for the result mentioned in the first paragraph: Heath-Brown showed that the collection of counterexamples to Artin's conjecture is finite; but we don't have an algorithm that will output this set (which is presumably the empty set). $\endgroup$
    – Sam Hopkins
    Commented Jul 17 at 17:07
  • 2
    $\begingroup$ @SamHopkins Yes. Here's another way to look at it. I interpret the OP as asking for ineffective results, which use the law of the excluded middle in an essential way. Ineffective results in number theory typically have the form, "Assume such-and-such a set is infinite, and derive a contradiction." Classically, we conclude that the set must be finite, but the proof does not tell us how to construct the set. An intuitionist would say that what we have proved is that the set is "not infinite," which is not the same as proving that it is finite. $\endgroup$
    – Timothy Chow
    Commented Jul 18 at 0:43
12
$\begingroup$

The graph minor theorem implies that any family of graphs that is closed under minors has a finite forbidden minor characterization, but the proof does not yield an algorithm for finding the minors. So for example, there is a finite list of forbidden minors for the class of toroidal graphs (those that can be embedded on the surface of a torus), but the complete list is not known, and there is no known algorithm for computing them. For more information, see A Large Set of Torus Obstructions and How They Were Discovered by Myrvold and Woodcock.

Improve this answer
$\endgroup$
11
$\begingroup$

Another example is Euler's idoneal number problem, one of the oldest problems in number theory. It asserts that $1848$ is the largest number $n$ such that the class group of the quadratic order $\mathbb{Z}[\sqrt{-n}]$ has exponent $2$. Siegel's theorem, which proves that $h(-n) \gg_\varepsilon n^{1/2 - \varepsilon}$, proves that there is a largest idoneal number (since in order for $n$ to be an idoneal number one must have $h(-n) = 2^{\omega(n) - 1} = O(n^{1/\log \log n})$. However, Siegel's lower bound must account for the potential existence of exceptional zeroes (i.e., Siegel zeroes) and is therefore ineffective. If Siegel zeroes do not exist, then one can prove an upper bound for the largest idoneal number fairly easily.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This same issue arises in other questions. In particular, what is the largest positive integer coprime to $7$ that is not of the form $x^{2}+y^{2}+7z^{2}$? The ineffective lower bound $h(-n) \gg_{\varepsilon} n^{1/2 - \varepsilon}$ can be used to prove that every sufficiently large positive integer is represented, but what is the largest that isn't? (In particular, is it $4759$?) $\endgroup$
    – Jeremy Rouse
    Commented Jul 19 at 15:00
11
$\begingroup$

There exists a positive integer $N \le 246$ such that there are infinitely many primes $p$ for which $p + N$ is also prime. However, there is no single specific value of $N$ for which this is proven.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ This is cool! Do you have a reference? $\endgroup$
    – Sam Hopkins
    Commented Jul 18 at 7:57
  • 3
    $\begingroup$ @Sam, this was Yitang Zhang's result, with $\le70,000,000$, improved by the efforts of many to $N\le246$. See, e.g., en.wikipedia.org/wiki/Prime_gap#Upper_bounds for references. $\endgroup$
    – Gerry Myerson
    Commented Jul 18 at 8:48
  • 2
    $\begingroup$ Ah yes of course. I usually hear/think of that as “bounded gaps” but I see how we get this from pigeonhole. $\endgroup$
    – Sam Hopkins
    Commented Jul 18 at 11:02
9
$\begingroup$

We know that the chromatic number of the plane is at most 7 but do not know its exact value. To remove any dependency on AC, we could ask for the maximum possible chromatic number of (the unit-distance graph for) a countable subset of the plane. To eliminate the issue of having a trivial constant-output 'algorithm' that exists despite us not knowing it, we could generalize to ask for the maximum possible chromatic number of a countable subset of $ℝ^k$ for input $k∈ℕ$, since it is trivial to prove that it is finite.

Improve this answer
$\endgroup$
6
$\begingroup$

$\DeclareMathOperator\BB{BB}$My answer is a slight cheat, because I'm going to give two examples where we have not only not discovered any algorithms but where we know there is no such algorithm. Both use the Halting theorem, although the first more obviously than the second.

The first is the Busy Beaver number: For any given $n$, there are finitely many Turing machines with at most $n$ states which halt when run on the blank tape. (Here to deal with ambiguity issues we assume that are only symbols are 1 and 0). Of those machines which halt, there is some maximum time any of them goes before halting. What is it? This is a function of $n$, sometimes denoted $\BB(n)$. It is clear from the definition that this quantity is finite. However, finding $\BB(n)$ is equivalent to solving the Halting problem. For a good introduction to the Busy Beaver function an related work, see Scott Aaronson's survey here.

Since the last one involved Turing machines, it probably isn't surprising that it has no algorithm. The second has a similar flavor, but where it is less obvious from the statement: For any given $n$, there are only finitely many Diophantine equations with at most $n$ variables, degree at most $n$, and no coefficient greater than $n$. Of those equations, some have no solutions. Define $D(n)$ to be the number of those equations which have no solutions. As before $D(n)$ is clearly finite. In this case, the problem is again equivalent to the Halting problem. In this case, it is due to the solution of Hilbert's tenth problem, which shows this problem to be equivalent to the Halting problem.

Two tangential remarks: First, if one defines a function similar to $D(n)$, $F(n)$ which instead counts the largest number of solutions of any Diophantine equation with at most $n$ variables, degree at most $n$, and no coefficient greater than $n$, then this number is also finite. But I do not know a proof or disproof that there is an algorithm for $F(n)$. Second, I don't know of any examples similar to these where we can prove finiteness and know there is no algorithm, but where the proof doesn't essentially go through the Halting theorem.

Improve this answer
$\endgroup$
6
  • 6
    $\begingroup$ In both cases, the proof that the number is finite is trivial, no? I interpret the question as asking for non-trivial proofs of finiteness that are non-constructive in that they don't lead to an algoithm (even a very inefficient one) to output the finite set. Admittedly, the question isn't explicit about this, but it seems to me to be the clear implication of the examples given. $\endgroup$
    – HJRW
    Commented Jul 17 at 12:50
  • 1
    $\begingroup$ @HJRW Yeah in these examples, finiteness is trivial. Hence saying at the beginning that this answer is a cheat. Maybe I should have made this a comment and just explicitly asked if they wanted that the finiteness had to be itself non-trivial? $\endgroup$
    – JoshuaZ
    Commented Jul 17 at 12:52
  • 1
    $\begingroup$ @LSpice Well that got completely garbled. Hopefully it now makes more sense. $\endgroup$
    – JoshuaZ
    Commented Jul 17 at 14:42
  • $\begingroup$ Re, yes, thanks! I also noticed a minor, more easily resolved, issue in the wording for $F(n)$, which I edited to correct. $\endgroup$
    – LSpice
    Commented Jul 17 at 14:43
  • 3
    $\begingroup$ @C7X Googology is quite unreliable. It is easy to show that this function is not computable; it is essentially the Kolmogorov complexity of $n$ (and it will be called like that in all other sources). See also cstheory.stackexchange.com/a/42375 . $\endgroup$
    – Emil Jeřábek
    Commented Jul 18 at 7:47
5
$\begingroup$

Here is an example where finiteness is known, an algorithm exists, but such an algorithm is ineffective, in the sense that current computers (to my knowledge) won't terminate in any reasonable amount of time:

A Y-system associated to a Dynkin diagram Q of type ADE is a certain system of equations arising in physics. Given a fixed Q, it is known that

  1. there are finitely many positive integer solutions to the Y-system associated to Q, as such solutions are bounded below by 1 and bounded above by a constant say $c(Q)$.
  1. a brute-force algorithm defined by testing all values between 1 and $c(Q)$ works in principle.
  2. In general, the constant $c(Q)$ is ineffectively large, and far larger than the expected number of solutions (e.g. when $Q$ is of type $E_8$, one would have to test something like $2^{400000}$ values, whereas one "expects" far fewer solutions).
Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ If we allow algorithms that are very slow, then there are much more extreme examples. For example, in Friedman's paper, Long finite sequences, he shows that there is a longest finite sequence $x_1, \ldots, x_n$ in $k$ letters in which no consecutive block $x_i, \ldots, x_{2i}$ is a subsequence of any later consecutive block $x_j, \ldots, x_{2j}$. For any fixed $k$, one can compute the length of this longest finite sequence by brute-force exhaustion. But even for $k=3$, the length is at least $A(7198,158386)$ where $A$ is Ackermann's function. $\endgroup$
    – Timothy Chow
    Commented Jul 18 at 11:20
  • 2
    $\begingroup$ Or we could ask for the smallest Laver table whose first-row period is exactly $2^n$. If we assume that there exists a rank-into-rank, then such a Laver table exists for all $n$, but good luck computing it even for $n=5$. $\endgroup$
    – Timothy Chow
    Commented Jul 18 at 11:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .