Prove that a counterexample exists without knowing one
Matthew Harrington 
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?
$\endgroup$ 612 Answers
$\begingroup$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).
$\endgroup$ $\begingroup$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$.)
$\endgroup$ 10 $\begingroup$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.
$\endgroup$ 4 $\begingroup$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.
$\endgroup$ 1 $\begingroup$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".
$\endgroup$ 5 $\begingroup$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).
$\endgroup$ $\begingroup$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.
$\endgroup$ 3 $\begingroup$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.
$\endgroup$ $\begingroup$"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.
$\endgroup$ 2 $\begingroup$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".
$\endgroup$ 1 $\begingroup$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.
$\endgroup$ 6 $\begingroup$"$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.
$\endgroup$ 5
