# Counterexamples against all odds

What are some examples of conjectures proved to be true generically (i.e. there is a dense $$G_{\delta}$$ of objects that affirm the conjecture) but are nevertheless false?

Also, it would be cool to see examples where the conjecture was proved true with probability 1, but was nevertheless false.

Of course one can manufacture statements from the spaces themselves, but I'm mostly interested in actual conjectures from contemporary mathematics whose resolution exhibited this pattern.

I am curious about this situation because sometimes, although we cannot find them easily, the "counterexample space" for a given conjecture may be quite large, yet inaccessible due to the limitations of existing techniques. For example, Tsirelson's conjecture and the Connes Embedding Conjecture were recently proven false, and although we cannot yet concretely construct a counterexample I see no reason to believe that counterexamples will necessarily be terribly rare objects...once the techniques are available to construct them. (These may be fighting words.)

The present question inquires about a distinct situation where it has been proved that a randomly selected object will not provide a counterexample. As dire as this sounds, the situation may be advantageous in that the construction of a counterexample may have to be much more surgical, and so one may see more clearly a way to build one. I'm wondering if my intuition about this is valid, based on recent history.

The question is just a passing curiosity, really, but I think someone may have a good story or two that will educate.

• Many things are true generically... e.g. the “conjecture” ‘all algebraic varieties are smooth’ would satisfy your condition. Aug 7, 2020 at 22:25
• Every real number is irrational. :p Aug 7, 2020 at 22:28
• @ElliotG every real number is rational Aug 7, 2020 at 22:29
• Right! I'm interested in situations where there was a reticent conjecture, someone proved its holding generically, and then the conjecture was ultimately false, most likely by a targeted construction. For example, the "conjecture" you mention above could be blown up by coming up with a single example of a non-smooth variety. I am curious if history contains other kinds of plot twists... Aug 7, 2020 at 22:31
• Alas, both examples with rational and irrational numbers fail: the first is not true generically, the second never was a conjecture. Aug 8, 2020 at 14:21

The most famous example is the so-called Riemann-Hilbert problem, which has a long and complicated history which I don't explain in detail. As it happens Hilbert's own formulation was not very exact, this was rather a program of research than an exact formulation with a yes/no answer. This was Problem 21 in his famous list. Hilbert believed that the question has a positive answer, and even that he solved it.

The most common version of the problem was whether there exists a Fuchsian system, that is a differential equation of the form $$w'=A(z)w=\left(\sum_{j=1}^m\frac{A_j}{z-a_j}\right)w$$ on the Riemann sphere, with arbitrary prescribed singularities $$a_j$$ and prescribed monodromy representation. Here $$A_j$$ are constant $$n\times n$$ matrices, $$w$$ is a solution vector, and $$w'=dw/dz$$.

It was solved for $$A$$ in general position by Josip Plemelj in 1908, who obtained a positive answer, and for a long time it was assumed that the statement is true in general. It is true in dimension $$2$$, and it is true in higher dimensions under various very mild conditions which are violated on the set of large codimension. For example, the answer is positive if at least one $$A_j$$ is diagonalizable. However in 1989 Andrei Bolibrukh constructed a $$3\times 3$$ counterexample with $$m=4$$. Such counterexamples exist for every $$n\geq 3$$.

Bolibrukh, A. A. The Riemann-Hilbert problem on the complex projective line. (Russian) Mat. Zametki 46 (1989), no. 3, 118–120.

Let $$S$$ be a finite set of (reduced) points in the projective plane and let $$I$$ be the (saturated) homogeneous ideal of $$S$$. Recall that $$I^{(m)}$$ is the $$m$$th symbolic power of $$I$$, consisting of polynomials that vanish to order at least $$m$$ at each point of $$S$$ (in characteristic $$0$$). Evidently the ordinary power $$I^m$$ satisfies $$I^m \subseteq I^{(m)}$$. This is just the statement that if each one of $$F_1,\dotsc,F_m$$ vanishes at a point $$P$$, then every $$(m-1)$$th derivative of the product $$F_1 \dotsm F_m$$ vanishes there also. In fact if $$n \geq m$$, then $$I^n \subseteq I^{(m)}$$. Conversely, if $$I^n \subseteq I^{(m)}$$, then $$n \geq m$$. So there's a pretty simple classification for when ordinary powers are contained in symbolic powers.

There's no obvious reason that $$I^{(m)} \subset I^n$$ should ever hold for any $$m$$ and $$n$$, beyond the trivial $$n=1$$, $$m \geq 1$$. However, following work of Swanson, the containment $$I^{(2n)} \subseteq I^n$$ was shown around 2000 or 2001 by Ein-Lazarsfeld-Smith, using asymptotic multiplier ideals, and also by Hochster-Huneke, using tight closure methods. More generally, for ideals of height $$h$$ (on smooth varieties), $$I^{(hn)} \subseteq I^n$$ holds; for points in the plane the height is $$2$$.

It's not the case, though, that if $$I^{(m)} \subseteq I^n$$, it must be $$m \geq 2n$$ (or $$hn$$). For example, complete intersections have $$I^{(m)} \subseteq I^n$$ as soon as $$m \geq n$$. One can show that if $$I^{(cn)} \subseteq I^n$$ for all $$I$$ and all $$n$$, then it must be $$c \geq h$$. But what about small values of $$n$$, or subleading terms, that is $$m = hn + o(n)$$?

In particular Huneke asked whether the containment $$I^{(4)} \subseteq I^2$$ could be improved to $$I^{(3)} \subseteq I^2$$. You can check computationally and it works for lots of examples, so there's some plausibility. This was very much a question, but some people (not including Huneke) started calling it "Huneke's conjecture".

Around 2010, Bocci-Harbourne showed that $$I^{(3)} \subseteq I^2$$ holds for points in general position. That's a dense $$G_\delta$$: "general position" means it holds on a Zariski open, dense subset of the $$(\mathbb{P}^2)^k$$ that parametrizes sets of $$k$$ points in the plane (ignoring order and collisions of points). (On the other hand, this is very much like "all algebraic varieties are smooth".)

But, around 2013, a counterexample was found by Dumnicki-Szemberg-Tutaj-Gasińka. It's a collection of $$12$$ points and easy to verify, once you know what to try. It was even a previously known arrangement of points (a dual Hesse arrangement).

Since then people have found families of counterexamples, counterexamples in higher dimension, higher-dimensional counterexamples consisting of positive-dimensional components (instead of points), and so on; they look for families where $$m=cn$$ works with $$1 \leq c < h$$... You can find literature on this with keywords like "containment problem for symbolic powers", resurgence, and Waldschmidt constant.

Why wasn't the counterexample found earlier? For one thing, it's a bit of a niche subject. The space of arrangements of $$12$$ points is $$24$$-dimensional (and nobody knew whether $$12$$ was the right number of points). And finally, the counterexample is not over the rationals (it's over $$\mathbb{Q}[\omega]$$, $$\omega$$ a cube root of unity), which means there's an extra step needed to enter it into Macaulay2. In hindsight that might seem a bit trivial, but this counterexample wasn't going to be found by just guessing random field extensions and guessing some points.

Sorry for rambling on. I think that algebraic geometry must have many versions of this story, where something was known to hold generally (meaning, on a Zariski open, dense set), conjectured to hold universally, but found to have counterexamples. This particular story is a favorite for me just because it relates to the motivation for my thesis problem. (I studied the multiplier ideals that appeared in the Ein-Lazarsfeld-Smith proof.)

George Andrews and Cristina Ballantine's 2019 Almost partition identities builds on classical results to prove that various pairs of integer partition statistics are equal asymptotically 100% of the time yet are not equal infinitely often. One example:

The total number of parts in all self-conjugate partitions of $$n$$ = the number of partitions of $$n$$ in which no odd part is repeated and there is exactly one even part (possibly repeated)

is true for almost all $$n$$. Yet equality fails infinitely often and the error grows without bound.

This may not satisfy your question, though, since no one ever claimed that the statistics were always equal---they skipped that step.

• This list if examples may be started with "the number of partitions of $n$ onto an even number of distinct parts equals to the number of partitions of $n$ onto an odd number of distinct parts", with exceptions being pentagonal numbers $n=k(3k\pm 1)/2$, due to Euler himself. Well, this of course never was a conjecture. Aug 8, 2020 at 13:51
• @FedorPetrov Yes, and they start from that in the article. I was trying to satisfy the "contemporary" part of the question, at least. Aug 8, 2020 at 14:12

(More of a comment than an answer, I suspect, but anyway…)

There are a bunch of results in graph theory that have to make exceptions for the Petersen graph, how do you rank that kind of counterexample? It's very far from unknown, you only have to remember to check it. And remarkably, it often stands as the only counterexample, so the theorem proper only has to include an exception.

Edit: An analogy, to help readers not familiar with graph theory get the gist of the situation: it's a bit like basic arithmetic, where you every now and then have to remember to exclude zero (e.g. "for all nonzero $$a$$ the equation $$ax=b$$ has a unique solution"), except that the thing you're making an exception for is more like $$\dfrac{1+\sqrt{19}}{5}$$ — complicated enough that most people having been shown the example and then asked to recreate it from memory will get it wrong. And it is the same exception in a bunch of unrelated theorems.

Edit 2: Examples of particular results provided in comment by @aorq. In each statement, the * means "except one particular graph".

Theorems:

• Every* connected vertex-transitive graph of order 2p is Hamiltonian.
• Every* bipartite Kneser graph is Hamiltonian.
• Every* generalized Petersen graph has a 1-factorization and chromatic index 3.

Conjectures:

• Every* bridgeless cubic graph admits a 2-bisection.
• Every* connected Kneser graph is Hamiltonian.
• Every* cyclically 4-edge connected cubic graphs has an even cycle double cover.
• Every* connected metacirculant is Hamiltonian.
• Every* connected strongly regular graph is Hamiltonian.
• Every* bridgeless cubic graphs has circular chromatic index at most 7/2.
• This might work in the context in the question if there is a natural sample space of graphs for which a particular statement is true with probability one but the Peterson graph belongs to a set of measure zero. However, you can see how such constructions might be reverse engineered so that they are in essence like the "every number is irrational" example... Aug 8, 2020 at 13:37
• @JonBannon, turning the set of graphs into a sample space is Standard Operating Procedure in probabilistic graph theory, but probably not in the way you seem to seek; maybe I'll turn that into another (not-quite-)answer. However, why require a set to have measure zero – doesn't that tend to exclude countable mathematics from consideration? In the results under consideration in my answer, the set of counterexamples has cardinality one, which should be as good as it gets. Aug 8, 2020 at 15:35
• Sure, Lars. Whatever is natural to an area is fine with me! Asymptotically probability zero may be nice in the discrete setting, maybe. Aug 8, 2020 at 15:43
• I'd like this answer more if it gave even one example of a result for which the Petersen graph is the only counterexample ("$G$ is not isomorphic to the Petersen graph" doesn't count). Aug 8, 2020 at 23:50
• Known: Every* connected vertex-transitive graph of order 2p is Hamiltonian. Every* bipartite Kneser graph is Hamiltonian. Every* generalized Petersen graph has a 1-factorization and chromatic index 3. Open: Every* bridgeless cubic graph admits a 2-bisection. Every* connected Kneser graph is Hamiltonian. Every* cyclically 4-edge connected cubic graphs has an even cycle double cover. Every* connected metacirculant is Hamiltonian. Every* connected strongly regular graph is Hamiltonian. Every* bridgeless cubic graphs has circular chromatic index at most 7/2. [* = except a certain graph.]
– aorq
Aug 9, 2020 at 3:21

The generic oracle hypothesis is false. In particular, $$\mathsf{IP}^G \ne \mathsf{PSPACE}^G$$ for a generic oracle $$G$$, but $$\mathsf{IP} = \mathsf{PSPACE}$$ in real life. Similarly, the random oracle hypothesis is false.

By the way, I gave this answer in response to a related MO question. There are a couple of other related MO questions, e.g., Heuristically false conjectures and Examples where physical heuristics led to incorrect answers.

It might be questionable if this example fits the bill, but in my opinion it does and it is a quite remarkable phenomenon.

The prime number theorem yields the asymptotic $$$$\pi(x+\Phi(x))-\pi(x) \sim \frac{\Phi(x)}{\log(x)},$$$$ as long as $$\Phi(x) \gg x$$. Now one might ask how small one is allowed to make $$\Phi(x)$$ so that this asymptotic remains true. For example Huxley showed that $$\Phi(x) = x^{\frac{7}{12}+\epsilon}$$ is admissible.

Assuming the Riemann hypothesis Selberg showed that the desired asymptotic holds for almost all $$x$$ as long as $$\frac{\Phi(x)}{\log(x)^2} \to \infty$$. It is natural to wonder if Selberg's result might be true without exception and it is here where the 'counterexamples against all odds' appear. Indeed Maier (in his paper 'primes in short intervals') showed the following: $$$$\liminf_{x\to\infty} \frac{\pi(x+\Phi(x))-\pi(x)}{\Phi(x)/\log(x)} < 1 < \limsup_{x\to\infty} \frac{\pi(x+\Phi(x))-\pi(x)}{\Phi(x)/\log(x)}$$$$ for $$\Phi(x) = \log(x)^B$$ with $$B>1$$. This shows the existence of exceptions in a quite spectacular manner.

Ursula Martin proved that when $$p$$ is prime, almost all finite $$p$$-groups have outer automorphism group a $$p$$-group, yet it follows from a Theorem of G. Glauberman that for any prime $$p > 3$$, and any (non-trivial) Sylow $$p$$-subgroup $$P$$ of a non-Abelian simple group $$G$$, it is never the case that $${\rm Out}(P)$$ is a $$p$$-group. Note also that by Burnside's $$p^{a}q^{b}$$-theorem, every non-Abelian finite simple group $$G$$ has order divisible by some prime $$p > 3$$.

Let $$\mathsf{A} = (A_1,\dots,A_m)$$ be a tuple of $$d \times d$$ matrices. The joint spectral radius (JSR) of $$\mathsf{A}$$ is $$\mathrm{JSR}(\mathsf{A}) := \lim_{n\to\infty} \sup_{i_1,\dots,i_n} \|A_{i_1} \dots A_{i_n}\|^{1/n}$$, where $$\|.\|$$ is any norm on $$\mathrm{Mat}(d\times d) = \mathbb{R}^{d^2}$$. The JSR was introduced by Rota and Strang in 1960. In the case of a single matrix ($$m=1$$), the JSR is equal to the spectral radius, that is, the biggest modulus of an eigenvalue of the matrix. For equivalent definitions of the JSR, see e.g. Jungers' monograph.

The finiteness conjecture of Lagarias and Wang (1995) asserted that for any tuple $$\mathsf{A} = (A_1,\dots,A_m)$$, there is a product $$A_{i_1} \dots A_{i_n}$$ of some finite length $$n$$ whose spectral radius is exactly equal to $$[\mathrm{JSR}(\mathsf{A})]^n$$. This conjecture was disproved in 2001 by Bousch and Mairesse. More counterexamples were constructed later, e.g. here, here, and here.

However, it is conjectured (see Conjecture 8 by Maesumi) that if $$m \ge 2$$ and $$d\ge 2$$, then the counterexamples to the finiteness conjecture form a subset of $$\mathbb{R}^{d^2m}$$ of zero Lebesgue measure, so the finiteness conjecture is almost always true. This conjecture is supported by numerical evidence (see e.g. here), but so far remains entirely open.