# Prove that a counterexample exists without knowing one

I strive to find a statement $S(n)$ with $n \in N$ that can be proven to be not generally true despite the fact that noone knows a counterexample, i.e. it holds true for all $n$ ever tested so far. Any help?

-
Ramsey theory comes to mind. –  Asaf Karagila Mar 13 '14 at 14:59
It may be a little off topic, but I think of the proof that there are $a,b\notin \Bbb Q$ such as $a^b\in\Bbb Q$, considering $\left(\sqrt{2}^{\sqrt{2}}\right)^\sqrt{2}$ –  mookid Mar 13 '14 at 15:02
@mookid: Try $a=e$, $b=\log 2$. –  Henning Makholm Mar 13 '14 at 15:04
I can't very easily prove that $\log 2\notin\Bbb Q$ (even if I can do so for $e$). Now the statement "noone knows a counterexample" is vague. –  mookid Mar 13 '14 at 15:07
I believe there was a proof that a universal turing machine exists, quite some time before somebody actually constructed one. I can't seem to find it now though. –  Cruncher Mar 14 '14 at 13:41

According the Wikipedia article on Skewes' number, there is no explicit value $x$ known (yet) for which $\pi(x)\gt\text{li}(x)$. (There are, however, candidate values, and there are ranges within which counterexamples are known to lie, so this may not be what the OP is after.)

Another example along the same lines is the Mertens conjecture.

A somewhat silly example would be the statement "$(100!)!+n+2$ is composite." It's clear that $S(n)$ is true for all "small" values of $n\in\mathbb{N}$, and it's clear that it's false in general, but I'd be willing to bet a small sum of money that no counterexample will be found in the next $100!$ years....

(Note: I edited in a "$+2$" to make sure that my silly $S(n)$ is clearly true for $n=0$ and $1$ as well as other "small" values of $n$.)

-
Counterexample to silly: n = (100!)! How shall I collect the small sum? –  Joshua Mar 13 '14 at 17:32
@Joshua That's not much of a counterexample: if that's the value of n, then the expression is clearly composite because it factors as 2((100!)!). –  amalloy Mar 13 '14 at 18:49
Who would be there give your bet after $100!$ years? :p –  Sawarnik Mar 13 '14 at 19:02
n = (-1 * (100!)!) + 1 ;) –  Xynariz Mar 13 '14 at 20:26
@Xynariz, we're looking for counterexamples in $\mathbb{N}$, not $\mathbb{Z}$. –  Barry Cipra Mar 13 '14 at 20:43

Statement: "There are no primes greater than $2^{60,000,000}$". No known counter-example. Counter example must exist since the set of primes is infinite (Euclid).

-

Assume some enumeration of all formulas in first-order peano arithmetic, and let $S(n)$ be the statement

The $n$-th formula is not provable in, but consistent with, first-order peano arithmetic, and isn't any of the known such formulas $\mathcal{F}$."

Assuming that the set of known such formulas $\mathcal{F}$ is recursive (meaning that for any given formula, one can decide whether it is in $\mathcal{F}$ or not), there is always such a formula. Otherwise, there would be a recursive and complete extension of PA, which contradicts the incompleteness theorem.

Update: According to this, recursive can be relaxed to recursively enumerable in the above. Thus, "knowing" a counter-example doesn't need to imply that, given a formula, we can decide whether it is a known counter-example. Instead, it's sufficient that there be an algorithm which produces these counter-examples one by one, which seems like a very natural definition for "knowing a counter-example". We then know that there must always be counter-examples that the algorithm does not generate.

-
This is a really good answer indeed, although I can't imagine how to explain it to someone with an average level of mathematical knowledge. What I really like about this one anyway (correct me if I'm wrong) is that, unlike some of the other ones, this is still guaranteed to be a valid answer in 100! and more years, if someone is there to read it. –  GOTO 0 Mar 14 '14 at 8:48
This seems shady. Without being told what $\cal{F}$ is, how can we give you a counterexample? Seems like letting $S(n)$ be the statement "$n$ isn't the largest prime factor of $p$" works just as well. There's always a value for $n$ that makes $S(n)$ false, but obviously I can't tell you what it is without knowing $p$. –  mjqxxxx Mar 15 '14 at 4:15
@mjqxxxx The point is, there are many non-provable but consistent formulas. You don't need to know $\mathcal{F}$ to find non-provable but consistent formulas. The point of $\mathcal{F}$ is to fullfill the requirement that there are no known counter-examples. Because whenever you find one (or even infinitely many, so long as there's an algorithm that tells for a particular formula wheter or not it's a counter-example), just just add it to $\mathcal{F}$, and due to the incompleteness theorem you know that there'll be more (which you don't know yet) –  fgp Mar 15 '14 at 13:46
@GOTO0 Yeah, that was the idea - giving an answer where any counter-example that is found can simply be added to a list of exceptions, keeping the answer correct. Although I cheated a bit, because I do require the set to be recursive - yet one could conceivably know a recursively enumberable set of counter-example (i.e., you can generate a never-ending list of counter-examples, but cannot decide in finite time that a particular formua is not a counter-example). I believe that my answer stays correct even if you replace "recursive" by "recuresively enumberable", but I didnt really check –  fgp Mar 15 '14 at 13:58

Let $S(n)\equiv$ "$n$ appears only finitely many times in the decimal development of $\pi$". We know that certainly this cannot be true for all $n$. We also know that at least two counterexamples are in $\{1,2,3,4,5,6,7,8,9,0\}$ but we don't know any counterexample.

Of course this relies, as other answers, on facts that are still unknown (no number can be tested before answering: which are the numbers that appear infinitely many times in the development of $\pi$?) So, strictly speaking, it is not a new answer, but I think is nice.

-
Hmm, I even suppose this is false for all of the digits here. –  Paŭlo Ebermann Mar 15 '14 at 10:53

Define $k$ to be 42 if the Riemann Hypothesis is true, and 108 if it is false.

Now consider $S(n) \equiv n\ne k$.

Alternatively consider $S(n)$ to be "$n$ is larger than $\mathit{BB}(100)$ which is the longest running time of a terminating two-symbol Turing machine with 100 states when started on an empty tape".

-
Not the twin prime conjecture? :-) –  Asaf Karagila Mar 13 '14 at 15:02
this cannot be tested fof $n=42$ –  user126154 Mar 13 '14 at 15:03
@user126154: Yet, nobody knows a counterexample. –  Henning Makholm Mar 13 '14 at 15:05
@user126154: Then define $k$ as the square of the number of quarks in the visible universe if RH is true; and the cube of the same number if RH is false. –  Asaf Karagila Mar 13 '14 at 15:07
@HenningMakholm and Asaf, I think user126154 is interpreting the OP's question as referring to statements $S$ that can be definitively settled (e.g., by some finite computation) for any given value of $n$. –  Barry Cipra Mar 13 '14 at 15:24

The BPSW primality test seems like a good example. 34 years after the probabilistic primality test was described, in daily use in many math packages, we still haven't found a counterexample (even to the weaker versions), and we know from exhaustive testing there are none below 2^64. Pomerance has a 1984 paper which gives a heuristic argument showing we expect infinitely many counterexamples to exist. Various authors have constructed lists of primes where the product of some subset is very likely to be a counterexample (the search spaces are enormous however).

-

If we require that $S(n)$ must be decidable by a known algorithm, then how about:

$S(n)$ iff either there is a comparison-based sorting strategy for $16$ elements that uses at most $n-1$ comparisons, or every comparison-based sorting strategy for $16$ elements uses at least $n+1$ comparisons in the worst case.

This can be determined simply by by enumerating strategies, and clearly there is exactly one counterexample, but it is not known what it is.

In fact it is known that the counterexample is either 45 or 46.

-
This is fascinating. Do you have a link to further information? –  trichoplax Apr 18 '14 at 9:51
@githubphagocyte: The best I can find right away is A036604 and links therein, in particular this paper which is the newest reference I know stating the problem is still open. –  Henning Makholm Apr 18 '14 at 17:36
There's far more to it than I expected for just 16 elements. Thanks for the links! –  trichoplax Apr 19 '14 at 13:21

Accepting the axiom of choice, for $n\ge1$ let $$S(n) := \mathbb{R}^n \;\text{ has no well-ordering}".$$

I believe it's provable that a well-orering of $\mathbb{R}$ cannot be constructed, although the axiom of choice indicates it exists.

-
You have to be a Platonist to accept this as a good example. –  Asaf Karagila Mar 13 '14 at 16:40
Accepting the axiom of choice, your $S(n)$ can be proved to be false for every $n$. So $n=1$ is a known counterexample. (And $n=0$ is a counterexample even without the axiom of choice). –  Henning Makholm Mar 13 '14 at 16:54
@HenningMakholm Yes, but can you show the counterexample? –  Jeff Snider Mar 13 '14 at 16:56
@AsafKaragila I don't know if your comment is in good humor or a serious criticism. I like the simple purity of this example. –  Jeff Snider Mar 13 '14 at 16:58
@Jeff: But the "counterexample" in the OP means the $n$ for which $S(n)$ is false. And we certainly know such an $n$, namely $n=1$ (or $n=42$ or whatever you like). –  Henning Makholm Mar 13 '14 at 17:10

"Prove that a counterexample exists without knowing one". The existence of continuous nowhere differentiable function can be proved without constructing one. In fact, a "typical" continuous function has this property.

-
This is not a property of natural numbers, is it? –  Paŭlo Ebermann Mar 15 '14 at 10:59
@PaŭloEbermann Yes. It is a property of continuous functions. –  vesszabo Mar 16 '14 at 18:14

Consider the false statement, "All numbers are algebraic." The set of algebraic numbers is countable, but $|\mathbb C|=2^{\aleph_0}>\aleph_0$. Therefore we know there are $2^{\aleph_0}$-many transcendental (i.e. non-algebraic) numbers without needing to identify any in particular. In this case, actual counterexamples, like $\pi$ and $e$, are obviously known, but it's difficult to prove that they are transcendental. This argument works as an easy non-constructive proof that counterexamples exist.

-
We can name $e$ and write down a formula that defines it uniquely. In particular, $e$ equals $\exp(1),$ where $\exp$ is the unique function $\mathbb{R} \rightarrow \mathbb{R}$ with $\exp' = \exp$ and $\exp(0)=1$. –  goblin Mar 15 '14 at 2:30
@user18921 It's not clear from that definition that $e$ is not algebraic, but regardless I don't think that was the point of this answer. He wasn't claiming that there are no known transcendental numbers. –  Daenerys Naharis Mar 15 '14 at 2:47
@Joseph the answer states that we cannot name a single transcendental number. This is blatantly false; take $e$ as a counterexample. But perhaps what he really meant is that we cannot explicitly define a single transcendental number. This is also blatanly false; define $e$ as $\exp(1)$. No matter how you slice or dice this answer, its simply wrong. –  goblin Mar 15 '14 at 2:52
@user18921 I didn't suggest that we don't know of any transcendental numbers. $\pi$ and $e$ are obvious examples, but it's difficult to prove that those particular numbers are transcendental. The point is that if you wanted to prove that some transcendental number exists, then it's sufficient to use this cardinality argument. (I altered the language of the answer to make this clearer.) –  Maxwell Mar 15 '14 at 4:44
But this isn't related to some property of natural numbers, is it? –  Paŭlo Ebermann Mar 15 '14 at 11:01

Are there any situations where we can prove that either A or B (or some element of a finite set) is a counterexample, but we don't know which one?

What about if the limit of some infinite sequence can be shown to be a counterexample, but we can't find the limit - as long as we know it exists. That would become philosophical. What does it mean to "know" a counterexample?

If I give you an arbitrary seventh degree polynomial P7, do we "know" it's smallest real root? Because that would be a counterexample to "P7 (x) != 0 for all x".

-
See Henning's answer. –  Asaf Karagila Mar 14 '14 at 13:26

"$n$ is composite" can be tested and proved relatively efficiently for large $n$ but finding a prime factor of a large composite number is a notoriously difficult computational problem.

-
And how is this a statement where noone knows a counterexample? $n = 5$ is one. –  Paŭlo Ebermann Mar 15 '14 at 10:58
Start from a large composite number, such as one of the RSA challenges. Copy the number into a program like Mathematica (IsPrime[] command) to get a probabilistic certificate that it is prime, or get an error-free non-random certificate using an implementation of the AKS polynomial-time primality test. Neither type of test will help in finding factors of $n$. –  zyx Mar 15 '14 at 11:55
Yes, your answer is a true fact, but it doesn't really answer the question. You might need to reword it to fit the question. –  Paŭlo Ebermann Mar 15 '14 at 12:03
Well, have a look in the Cunningham project tables of factors of $a^n - 1$ for small $a$ (such as $a=2$) and large $n$ and search for the letter "C", the first letter of the word "composite". Numbers like C564 indicate 564-digit factors that are known to be composite, but no factors (of the C564) are known. –  zyx Apr 17 '14 at 4:24
I think I understand what you mean ... So an example statement $S(n)$ as requested in the question would be "$n$ is not a non-trivial factor of C564". Could you put this into your answer? (Maybe with a link how to get C564, I didn't really succeed there.) –  Paŭlo Ebermann Apr 17 '14 at 11:46

There is no prime-generating polynomial with only $10$ variables, no matter how large its degree $n$.

In fact, it has been proven there exists one, and $n$ is in the order of $10^{45}$ but its value is not precisely known.

-