52
$\begingroup$

I am pretty distant from anything analytic, including analytic number theory but I decided to read the Wikipedia page on the Riemann hypothesis (current revision) and there is some pretty interesting stuff there:

Some consequences of the RH are also consequences of its negation, and are thus theorems. In their discussion of the Hecke, Deuring, Mordell, Heilbronn theorem, (Ireland & Rosen 1990, p. 359) say

The method of proof here is truly amazing. If the generalized Riemann hypothesis is true, then the theorem is true. If the generalized Riemann hypothesis is false, then the theorem is true. Thus, the theorem is true!!

What is surprising is that both a statement and its negation are useful for proving the same theorem.

Do similar situations arise with other major, notorious conjectures in mathematics? I only care about algebraic geometry and algebraic number theory for the most part but I guess it will make little sense to have such questions devoted to each area of mathematics so post whatever you've got.

To give an initial direction: are there any interesting statements one can prove assuming both some hard conjecture about motives (e.g. motivic $t$-structure, the standard conjectures, Hodge/Tate conjectures) and its negation?

$\endgroup$
  • 6
    $\begingroup$ @SamHopkins I personally think that this question is not related to the one you have linked to and that this question is not nearly vague enough to be closed as "unclear". Opinions differ I guess. $\endgroup$ – user141414 Jun 3 at 13:34
  • 6
  • 4
    $\begingroup$ One would have to see the actual proof I guess, but in this abstract description, nothing seems even remotely "truly amazing" to me. Rather, it sounds like doing an argument by distinguishing various (in this case, two) cases. $\endgroup$ – Christian Remling Jun 3 at 21:51
  • 2
    $\begingroup$ @Cutthewood My excuses, of course I like these arguments too, and I didn't mean to diminish their content. Just saying the form " A implies X and not A implies X as well" is not so strange $\endgroup$ – Pietro Majer Jun 3 at 22:31
  • 6
    $\begingroup$ @Michael: I think the difference is that, in your example, we know that the hypothesis $p = 4k+1$ is true for some $p$ and false for others, and so we really need both cases to prove the theorem for all $p$. In OP's example, the hypothesis is either universally true or universally false (there's no free variable like $p$), and hence one of the cases is completely unnecessary to treat, but we don't know which one. $\endgroup$ – Nate Eldredge Jun 4 at 18:19
27
$\begingroup$

I think this is much less surprising today. It's not uncommon to argue that a statement about some structures is true because one can decompose structures into random-like and structured parts ('structure and randomness'), and in either case get to the desired conclusion. Usually one is trying to prove that a certain statement is true for a whole class of structures by this method; there is no one special structure for which we really want to prove it. Take Roth's theorem as an example: we want to prove any positive-density set of integers in $N$ (for some large $N$) contains a three-term AP. We can do this if the set looks random (small Fourier coefficients) easily enough, but if the set does not look random, then there is a large Fourier coefficient, so the set looks structured, namely it has a noticeably larger density on some long AP than on $[N]$. But then we can pass to the AP and iterate this argument.

It just happens that when we try to prove things about the primes, we really only want to know about the one structure, contained in a class of structures with prime-like properties (which might not have more than one member, depending on the properties used in the proof). But the proof method is still to show that the whole class of structures satisfies the desired conclusion.

In this case (G)RH is a statement that the primes behave in some random-like way, in a fairly strong quantitative sense. And so its negation is the assertion of some structure beyond the obvious - which of course can be useful.

Of course, if you want to find other examples of theorems which you can prove by appealing to some major open problem being either true or false, you should probably have some reason why either outcome helps. Quite a few major open problems (or major theorems) can be read as some kind of quasirandomness statement, and for that there is a reason why the conjecture failing might be useful, so in principle there should be a decent list of possible candidates.

$\endgroup$
  • $\begingroup$ I guess the Hodge conjecture could be interpreted as saying "there are many algebraic cycles" or maybe "algebra controls topology" (feel free to bash me for such a formulation). Would be pretty fun is there was a similar example in this setting. $\endgroup$ – user141414 Jun 3 at 15:54
60
$\begingroup$

Theorem. The Stone-Čech compactification of the real line contains $2^\mathfrak c$ topologically distinct continua.

Here a continuum is defined to be a compact connected Hausdorff space. $2^\mathfrak c$ is easily seen to be an upper bound in the problem.

The proof was divided into two parts:

Case 1: The Continuum Hypothesis fails ($\mathfrak c>\omega_1$).

Dow, Alan, Some set-theory, Stone-Čech, and $F$-spaces, Topology Appl. 158, No. 14, 1749-1755 (2011).

Case 2: The Continuum Hypothesis holds ($\mathfrak c\leq\omega_1$).

Dow, Alan; Hart, Klaas Pieter, On subcontinua and continuous images of $\beta \mathbb{R} \setminus \mathbb{R}$, Topology Appl. 195, 93-106 (2015).

The assumptions $\neg$CH and CH are critical to the constructions. Also the types of continua constructed are very different in Case 1 vs Case 2. In fact, all continua of the type constructed for Case 1 are homeomorphic under CH.

This is the only theorem I know of which was proved using CH in this way. What's especially interesting is that both cases are necessary to this proof because CH and $\neg$CH are each consistent with ZFC. This may be different from the use of RH and $\neg$RH, or some other conjecture and its negation. If the conjecture is eventually proved, for instance, then you could throw away the other half of your proof.

$\endgroup$
  • 1
    $\begingroup$ I recognise that Stone-Čech fellow! $\endgroup$ – Daron Jun 5 at 17:32
32
$\begingroup$

This paper proves the existence of an essentially-deterministic algorithm for the following problem:

Input: an integer $n$

Output: An $n$-bit prime.

Which runs in time sub-exponential in $n$ for infinitely many inputs.

On a high level the argument works as follows:

  1. Suppose a certain kind of pseudo-random generator exists. Then we can derive an algorithm to compute the above.
  2. Suppose that kind of pseudo-random generator does not exist. Then we have a collapse of complexity classes $\mathsf{PSPACE} = \mathsf{ZPP}$ which then implies some circuit lower bounds, which in turn yields a pseudo-random generator with the desired properties.
$\endgroup$
  • $\begingroup$ is the existence of a pseudo-random generator hard? $\endgroup$ – user141414 Jun 3 at 19:56
  • 6
    $\begingroup$ Yes -- no one knows how to unconditionally prove the existence of such things. For most kinds of pseudo-random generator, their existence is stronger than $P \neq NP$. $\endgroup$ – Izaak Meckler Jun 3 at 19:59
  • 6
    $\begingroup$ This is indeed an intriguing result, however, the algorithm only runs in time subexponential in $n$ rather than polynomial, and it does not work on all inputs $n$, but only for some infinite subset. $\endgroup$ – Emil Jeřábek supports Monica Jun 4 at 10:05
  • $\begingroup$ Thanks Emil -- amended. $\endgroup$ – Izaak Meckler Jun 6 at 5:31
  • 1
    $\begingroup$ Please, what does essentially-deterministic mean? $\endgroup$ – Hilder Vítor Lima Pereira Jun 6 at 12:56
26
$\begingroup$

Here is a baby answer.

Theorem: There exist two irrational numbers $p,q$ such that $p^q$ is rational.

Proof: In case $\sqrt 2^{\sqrt 2}$ is rational we can take $p=q=\sqrt 2$.

Otherwise take $p= \sqrt 2^{\sqrt 2}$ and $q=\sqrt 2$. We have $p^q = \big(\sqrt 2^{\sqrt 2}\big)^{\sqrt 2} = \sqrt 2^{\sqrt 2 \cdot \sqrt 2} = \sqrt 2^2=2$ is rational.

$\endgroup$
  • 2
    $\begingroup$ This was the first example that came to my mind. I wonder if the commenters sceptical about the "truly amazing"ness of the example in the original post really find this one (which is accessible to any mathematician) to be just an ordinary proof, with nothing special about it (in a psychological, not rigorous, sense). $\endgroup$ – LSpice Jun 5 at 19:17
  • 3
    $\begingroup$ @LSpice I find it to be disappointing for an almost opposite reason as D.S. Lipham. A simple cardinality argument gives the theorem. It's like this "Thm: There is a room in my house without my dog in it. Prf: If my dog is not in the kitchen, we are done. If my dog is in the kitchen, then my dog is begging for food scraps in the kitchen, which means my dog is not in the bedroom, so we are done." Better to say I have four rooms in my house and one dog. $\endgroup$ – Will Sawin Jun 6 at 5:46
  • 2
    $\begingroup$ @D.S.Lipham the proof above is much easier than the proof that $\sqrt{2}^\sqrt{2}$ is irrational, so there is still something quite nice and elegant about it. I do agree that knowing about this more explicit result spoils the magic a bit. It’s also worth pointing out that p=e, q=log(2) gives another explicit way of proving the theorem being claimed (and I believe that the irrationality of log(2) is much easier to prove than irrationality of $\sqrt{2}^\sqrt{2}$. The irrationality of e is a trivial result of course.) $\endgroup$ – Dan Romik Jun 6 at 7:36
  • 2
    $\begingroup$ @WillSawin what cardinality argument did you have in mind? $\endgroup$ – D.S. Lipham Jun 6 at 8:22
  • 2
    $\begingroup$ @D.S.Lipham Fix any positive rational number $a$ and take $p=a^{1/q}$ for $q$ in $\mathbb R$. We have only countably many rational $q$, and only countably many $q$ with $p$ rational, because $a^{1/q}$ is an invertible function. So there must be (uncountably many!) irrational pairs with this property. $\endgroup$ – Will Sawin Jun 6 at 14:01
11
$\begingroup$

Every proof by contradiction can be seen as following the template identified in the theorem.

Namely, when we've proved a statement $S$ by contradiction, then $S$ follows from $S$ and also from $\neg S$.

$\endgroup$
  • 12
    $\begingroup$ I do not see how this addresses the question. The question specifically asked about "major, notorious conjectures in mathematics". A somewhat subjective definition but you probably agree that not every statement $S$ belongs to that category. Actually, now that I think of it $S$ would simultaneously have to be proven and to be a conjecture so I think this answer deserves some further clarification. $\endgroup$ – user141414 Jun 3 at 15:25
  • 4
    $\begingroup$ I took the central phenomenon of your question to be the situation where one statement follows from another and also from its negation. While that might seem unusual or even amazing, as you say, the point of my answer is that actually this happens quite frequently in mathematics. $\endgroup$ – Joel David Hamkins Jun 3 at 15:28
  • $\begingroup$ I appreciate your shift of perspective. It is actually pretty interesting. Still, you addressed a very different question. If I could downvote, I would (but I also thank you for this insight, even if it was not presented in the appropriate place!). $\endgroup$ – user141414 Jun 3 at 15:35
  • 3
    $\begingroup$ I do not think that the proof structure being discussed by the question asker follows your pattern. Their pattern is [(P) --> (Q)] and [(not P) --> (Q)] therefore, (Q). That is standard proof by cases. You did something different. $\endgroup$ – Toothpick Anemone Jun 4 at 20:15
  • 7
    $\begingroup$ @ToothpickAnemone - The answer was following (a special case of) the pattern posed in the question, not vice versa. Joel has explored the special case of P = Q. $\endgroup$ – Jirka Hanika Jun 4 at 21:43

Your Answer

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