# 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. Mar 13, 2014 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}$ Mar 13, 2014 at 15:02
• @mookid: Try $a=e$, $b=\log 2$. Mar 13, 2014 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. Mar 13, 2014 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. Mar 14, 2014 at 13:41

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

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? Mar 13, 2014 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!)!). Mar 13, 2014 at 18:49
• Who would be there give your bet after $100!$ years? :p Mar 13, 2014 at 19:02
• n = (-1 * (100!)!) + 1 ;) Mar 13, 2014 at 20:26
• @Xynariz, we're looking for counterexamples in $\mathbb{N}$, not $\mathbb{Z}$. Mar 13, 2014 at 20:43

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. Mar 14, 2014 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$. Mar 15, 2014 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, 2014 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, 2014 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. Mar 15, 2014 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 "There is a two-symbol Turing machine with 100 states that runs for at least $n$ steps when started on an empty tape, but eventually terminates".

• Not the twin prime conjecture? :-) Mar 13, 2014 at 15:02
• this cannot be tested fof $n=42$ Mar 13, 2014 at 15:03
• @user126154: Yet, nobody knows a counterexample. Mar 13, 2014 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. Mar 13, 2014 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$. Mar 13, 2014 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? Apr 18, 2014 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. Apr 18, 2014 at 17:36
• There's far more to it than I expected for just 16 elements. Thanks for the links! Apr 19, 2014 at 13:21

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.

"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? Mar 15, 2014 at 10:59
• @PaŭloEbermann Yes. It is a property of continuous functions. Mar 16, 2014 at 18:14

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. Mar 14, 2014 at 13:26

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$. Mar 15, 2014 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. Mar 15, 2014 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. Mar 15, 2014 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.) Mar 15, 2014 at 4:44
• But this isn't related to some property of natural numbers, is it? Mar 15, 2014 at 11:01

"$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. Mar 15, 2014 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, 2014 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. Mar 15, 2014 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, 2014 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.) Apr 17, 2014 at 11:46