Situations where “naturally occurring” mathematical objects behave very differently from “typical” ones

Question

I am looking for examples of the following situation in mathematics:

• every object of type $X$ encountered in the mathematical literature, except when specifically attempting to construct counterexamples to this, satisfies a certain property $P$ (and, furthermore, this is not a vacuous statement: examples of objects of type $X$ abound);

• it is known that not every object of type $X$ satisfies $P$, or even better, that “most” do not;

• no clear explanation for this phenomenon exists (such as “constructing a counterexample to $P$ requires the axiom of choice”).

This is often presented in a succinct way by saying that “natural”, or “naturally occurring” objects of type $X$ appear to satisfy $P$, and there is disagreement as to whether “natural” has any meaning or whether there is any mystery to be explained.

Here are some examples or example candidates which come to my mind (perhaps not matching exactly what I described, but close enough to be interesting and, I hope, illustrate what I mean), I am hoping that more can be provided:

• The Turing degree of any “natural” undecidable but semi-decidable (i.e., recursively enumerable but not recursive) decision problem appears to be $\mathbf{0}'$ (the degree of the Halting problem): it is known (by the Friedberg–Muchnik theorem) that there are many other possibilities, but somehow they never seem to appear “naturally”.

• The linearity phenomenon of consistency strength of “natural” logical theories, which J. D. Hamkins recently gave a talk about (Naturality in mathematics and the hierarchy of consistency strength), challenging whether this is correct or even whether “naturality” makes any sense.

• Are there "natural" sequences with "exotic" growth rates? What metatheorems are there guaranteeing "elementary" growth rates? concerning the growth rate of “natural” sequences, which inspired the present question.

• The fact that the digits of irrational numbers that we encounter when not trying to construct a counterexample to this (e.g., $e$, $\pi$, $\sqrt{2}$…) experimentally appear to be equidistributed, a property which is indeed true of “most” real numbers in the sense of Lebesgue measure (i.e., a random real is normal in every base: those which are are a set of full measure) but not of “most” real numbers in the category sense (i.e., a generic real is not normal in any base: those which are are a meager set).

What other examples can you give of the “most $X$ do not satisfy $P$, but those that we actually encounter in real life always do (and the reason is unclear)” phenomenon?

Answer 1

Most finite groups empirically are 2-groups (in the sense of being a p-group with $p=2$ not in the other sense of the word). There are a lot of them. Conjecturally almost all finite groups are 2-groups. That is it is conjectured that if you count all groups up to isomorphism with at most $n$ elements, then the fraction of those which are 2-groups goes to 1 as n goes to infinity. In practice, while we often encounter small 2-groups and a few specific 2-groups like $(Z/(2Z))^k$, when dealing with "largish" finite groups all these weird 2-groups don't seem to often show up.

Answer 2

Almost all real numbers are uncomputable, yet almost every real number used in math is computable.

--

Edit: Note that this does not meet all the criteria of the question, as clear explanations exist both for why almost all real numbers are not computable and for why almost all real numbers found in the mathematical literature are computable.

Answer 3

Thanks to Boris Tsirelson, we know that not all infinite-dimensional Banach spaces contain either $c_0$ or $\ell_p$ for some $p\in [1,\infty)$. But all known counterexamples are constructed in a particular inductive way, and all spaces that "occur in nature" do contain $c_0$ or $\ell_p$, sometimes (as in the case of Orlicz spaces) for non-trivial reasons.

Answer 4

The example mentioned in a comment by Martin M. W. seems worth posting as an answer. Naturally occurring theorems and conjectures tend not to be unprovable (relative to one of the standard axiomatic systems), but there are results showing that in some sense, "most" true statements are unprovable. For example, the paper Is complexity a source of incompleteness? by Cristian S. Calude and Helmut Jürgensen sets up a framework in which they can prove that

the probability that a true sentence of length $n$ is provable in the theory tends to zero when $n$ tends to infinity, while the probability that a sentence of length $n$ is true is strictly positive.

[EDIT: David Speyer has pointed out that the paper by Calude and Jürgensen seems to be wrong. One recent discussion of whether "most" statements are unprovable is the paper Revisiting Chaitin’s Incompleteness Theorem by Christopher Porter.]

It is not clear why natural unprovable statements seem to be so rare. Harvey Friedman believes that as our understanding of mathematics increases, incompleteness will crop up increasingly often, and he has worked very hard to find natural unprovable statements.

Answer 5

If a Banach space is reflexive, this trivially implies that it has an isomorphism with its bi-dual. In general, the converse is not true, i.e. a space can be isomorphic to its bi-dual without being reflexive and students are usually warned to never make that mistake. Nevertheless, the only example of such a space that I know of is a specifically constructed counterexample.

Answer 6

A relatively low-level example: most functions encountered in introductory to mid-level calculus are either continuous or at most non-continuous at a countable number of points. However it is easy to construct functions where this does not hold. Likewise for differentiability.

Answer 7

1. In practice, subsets of $\mathbb{R}$ encountered in analysis tend to be measurable, but not all subsets of $\mathbb{R}$ need be measurable, and in fact are not by the Axiom of choice.

2. In practice, properties of natural numbers encountered in number theory are arithmetical (expressible in the language of Peano arithmetic), but of course one can easily conjure up non-arithmetical ones.

3. Most mathematical statements occuring in practice can be expressed as set-theoretic formulas of very low logical complexity, typically having at most one alternation of unbounded quantifiers on the outside.

Answer 8

In mathematics, the binary operations of most algebraic structures one is interested in, are associative. It is more common that such operations are not commutative but only seldom is one confronted with structures which are non-associative.

One of the first examples we usually learn about are groups which have an associative (but not necessarily commutative) operation. More generally, the composition of morphisms in categories are demanded to be associative.

So the natural operations are the associative ones and one may be led to believe that this is also the typical case. At least this was my belief in my freshman year until someone showed me otherwise in response to a blog entry I wrote about this topic. He coded Cayley tables for sets of small orders and checked how often these are associative or commutative. (I learned the following results from wordpress user "Herr Fessa".)

• Number of associative operations: By OEIS/A023814 there are $$(a_n)_n = (1, 1, 8, 113, 3492, 183732, 17061118, \dots)$$ associative binary operations for $n = 0,1,2,\dots$.
• Number of commutative operations: As commutative binary operations are given by Cayley tables symmetric about the diagonal, there are precisely $b_n = n^{\frac{n(n+1)}{2}}$ such operations.

For comparison: For $n = 5$ there are $183732$ associative operations and $298023223876953125$ commutative ones.

Answer 9

There are lots of statements of this kind involving deformation theory: roughly, "natural" objects tend to have fewer deformations than general ones. A subphenomenon here is formality. Derived algebra objects over fields of characteristic zero that occur in nature (for example operads that occur in nature) tend to be formal.

Answer 10

For this answer, let us just work with $T_{0}$-spaces to avoid trivialities.

There exists regular spaces that are not completely regular, and in point-free topology, there exists regular frames that are not completely regular (frames are the point-free topological spaces). Furthermore, one can say that most regular spaces are not completely regular and that most regular frames are not completely regular depending on one's definition of mostness. However, I have not encountered any "naturally occurring" regular space or regular frame that is not completely regular.

The distinction between regularity and complete regularity is of philosophical importance. In general topology, there is a distinction between the "good spaces" that are used in analysis (such as manifolds, complete metric spaces, or even locally convex topological vector spaces) and the "bad spaces" (such as the cofinite topology, the Zariski topology, and non-Hausdorff spaces) (I put the word "bad" in quotes because I personally find these "bad" topological spaces to be quite interesting). One should therefore ask if there is an axiom that provides the dividing line between the "bad spaces" and the "good spaces".

In the past, I used to believe that complete regularity was the main separation axiom between the bad spaces and the good spaces, but now I think that there are just as good reasons to believe that regularity is the main separation axiom that distinguishes between the "bad spaces" and the "good spaces". In fact, regularity may be one cutoff between the "bad spaces" and the "good spaces" while complete regularity may be another cutoff, and there are only two distinct cutoffs because there are regular spaces that are not completely regular. Since regularity and complete regularity are different, the dividing line between "bad spaces" and "good spaces" may be a blur that spreads from regularity to complete regularity rather than a definite axiom.

Examples of regular spaces which are not completely regular.

This paper by Mysior gives a quite simple example of a regular space that is not completely regular. This question also gives examples of regular spaces that are not completely regular.

Regularity and complete regularity are good axioms

Unlike Hausdorffness, regularity and complete regularity both extend seamlessly to point-free topology. Regularity behaves slightly better in this regard since the regularity axiom is a first order formula. Both regularity and complete regularity are very well-behaved in both general and point-free topology. They are both closed under taking products, subspaces, and sublocales in point-free topology.

The case for complete regularity as the cutoff.

A space is completely regular if and only if it can be embedded into a cube $[0,1]^{I}$ for some set $I$.

A space is completely regular if and only if it can be endowed with a compatible uniformity.

A space is completely regular if and only if it can be endowed with a compatible proximity.

The case for regularity as the cutoff.

A space $X$ is regular if and only if a filter $\mathcal{F}$ converges to a point $x_{0}$ precisely when the filter generated by $\{\overline{R}\mid R\in\mathcal{F}\}$ also converges to $x_{0}$.

There are several inequivalent ways of interpreting a topological space or frame in a forcing extension (or more generally, a larger model of ZFC). In any case, given a regular space $X$, if the forcing extension $V[G]$ collapses enough cardinals, then the interpretation of $X$ in $V[G]$ will be both regular and second countable.

A frame $L$ is regular if and only if there exists a frame $M$ such that the frame coproduct $L\oplus M$ is paracompact.

Answer 11

It is worthwhile to mention the Von Neumann conjecture for locally compact groups under "every object of type X encountered in the mathematical literature, except when specifically attempting to construct counterexamples to this, satisfies a certain property P"

At around 1930, Von Neumann introduced the definition of amenable groups. It was believed until 1980 that a group is non-amenable if and only if it contains a subgroup isomorphic to $\mathbb{F}_2$. In 1950s, M.M. Day attached Von Neumann's name to this famous conjecture. The version of Von Neumann's conjecture for locally compact groups is as follows: a locally compact group is non-amenable if and only if it contains a topological subgroup isomorphic to $\mathbb{F}_2$, the free group on two generators with discrete topology. It was not disproven until 1980, at which year, the Tarski monster was shown to be a non-amenable group that does not contain a subgroup isomorphic to $\mathbb{F}_2$.

The conjecture still holds for connected Lie groups and (more generally) almost connected locally compact groups. $G$ is said to be almost connected if the factor group $G/G_e$ is compact, where $G_e$ is the connected component of the identity $e\in G$.

Answer 12

I think this is common in algebraic geometry too. For example while most curves have dimension of their Brill--Noether space given exactly by the Brill--Noether number $\rho$ (thanks to the Brill--Noether Theorem of Griffiths and Harris), it is hard in practice to write down any particular curve which does.

(This is also an answer to the linked "finding hay in a haystack" question.)

EDIT: And I should say why this shows the non-generic but "natural" curves are "better behaved" is because it means their Brill--Noether spaces are larger than you would expect, i.e., these curves have more "representations" (maps into projective space) than you would guess.

Answer 13

Essentially all naturally occurring large categories are complete and cocomplete. The "only" counterexample (in the sense of, say, categories met by a typical undergraduate) is the category of fields. A "random" large category, if such a thing were to exist, has no reason to have any limits or colimits at all, though.

Essentially all naturally occurring large categories are locally presentable, or certainly at least accessible. The "only" counterexample, in the same sense, is the category of topological spaces. Again, a "random" large category should not be controlled by a small set.

Answer 14

Most polynomial algorithms we know have polynomial bounds of a low degree and with small coefficients.

One could say that this is easy to explain: These are the algorithms we especially look for, because they are the most useful ones. But on the other hand, why there are so many "useful" polynomial algorithms is not so clear.

Answer 15

One approach to formalizing any kind of "genericity" (my forcing background is showing here) is as follows. Intuitively, a generic object should avoid all "small" sets (where "small" is something we already have an idea about - e.g. meager, null, etc.). Of course this will be impossible since every singleton will be small, so instead we get a gradation of genericity notions - where each one amounts to "avoids all "small" sets which are "simply definable"" for some appropriate notion of simple definability. For example, considering randomness we start with the intuition that a random real avoids every null set, and wind up with notions like "avoids every "computably describable" null set" (or more precisely, "passes every computable Martin-Lof test").

Once we make this shift we get, as hoped for, that the set of non-generic objects is itself a small set. Consequently, insofar as naturally-occurring things are simply definable this entire perspective is predicated on the idea that naturally-occurring objects shouldn't be typical.

The fascinating thing, then, is that these "typical-but-unnatural" objects wind up actually being useful to us in serious ways - this is where forcing especially comes into play. So even though in one sense this is a cheating response to your question, I don't think it's actually inappropriate since there's real content here.

Answer 16

In the study of dynamical systems, there are many empirical rules that are valid for most systems people (in particular more applied ones) usually consider, but for which pathologic counterexamples exist.

For example, for most deterministic dynamics $X$, the following are equivalent:

• $X$ fulfils some definition of chaos.
• $X$ fulfils another definition of chaos.
• $X$ is bounded and the Lyapunov exponent of $X$ is positive.
• $X$ has a strange/fractal attractor (fractal dimension larger than topological dimension).
• $X$ passes any of the other empirical tests for chaos.

Yet there are pathological counterexamples to many of the equivalences, for example strange non-chaotic attractors. Being on the applied side, I cannot say much about how “typical” the counterexamples are and whether “simple” explanations exist except that we probably would not have differing definitions of chaos otherwise.

Answer 17

In information theory, the capacity of a memoryless channel is defined as the mutual information between the input and output distributions, maximized over all possible input symbol distributions. In fact, no known concrete family of codes has rate asymptotically approaching the capacity but a completely random family of codes, with symbols drawn randomly from a distribution that maximizes the mutual information between input and output distributions of the channel, does! Shannon published this in 1948.

Answer 18

Euclidean lattices of high density are generic and are very difficult to construct in large dimensions.

Answer 19

The structure of difference sets in additive combinatorics provides a curious example of this phenomenon. A specific instance is the following: unless specifically constructed to be a counterexample, if $A$ is a subset of $(\mathbb Z/2\mathbb Z)^d$ with $|A|> 0.01\cdot 2^d$ then the difference set $A - A:=\{a-a':a, a'\in A\}$ must contain a subgroup of index $K$ (independent of $d$ or $A$). The counterexamples, due independently to Igor Kriz and Imre Ruzsa, are spelled out explicitly in Theorem 9.4 of Ben Green's Finite Field Models in Arithmetic Combinatorics. Such constructions are often referred to as niveau sets.

What's curious is that niveau sets are, in some sense, the only known way to construct a dense subset $A$ of an abelian group $G$ where $A-A$ lacks some prescribed structure. Here are the instances I am aware of:

• Kriz's construction of a set of topological recurrence which is not a set of measurable recurrence. Discovered independently by Ruzsa.

• Forrest's example of a set of measurable recurrence which is not a set of strong recurrence (and McCutcheon's variant of Forrest's example).

• Green's version of niveau sets (Theorem 9.4): $A\subset (\mathbb Z/2\mathbb Z)^d$ where $|A|\approx (1/4)2^d$ and $A-A$ does not contain a subgroup of small index.

• Ruzsa's construction of dense sets $A\subset \{1,\dots,N\}$ where $A+A$ does not contain exceptionally long arithmetic progressions.

• Bourgain's example of subsets in $\mathbb T^d$ with Haar measure $m(A)\approx 1/2$ where $A-A$ does not contain a connected subgroup of $\mathbb T^d$. (Unpublished, to my knowledge.)

• Katznelson's examples of sets which are $k$-Bohr recurrent but not $(k+1)$-Bohr recurrent.

• Julia Wolf's construction of sets whose popular difference sets lack structure.

• My construction of a set $S\subset \mathbb Z$ where every translate of $S$ is a set of measurable recurrence and no translate of $S$ is a set of strong measurable recurrence.

• Ackelsberg's generalization of the above to countable abelian groups.

• My construction of a set dense in the Bohr topology of $\mathbb Z$ which is not a set of measurable recurrence.

While varying in many technical details, all of the above examples rely, in the same way, on the additive structure of Hamming balls in $(\mathbb Z/p\mathbb Z)^d$ for a fixed prime $p$ (usually $p=2$) and large $d$.

It would be very interesting to find a fundamentally different construction of a set $A$ where $A-A$ lacks some prescribed structure, or to prove that every such example comes from niveau sets.

Answer 20

Almost every deterministic stable system that we see in textbooks has some well-defined Lyapunov function. But in reality, it can be argued that for most stable systems, finding a Lyapunov function is either very hard or maybe impossible. It is not yet known whether the inverse of Lyapunov theorem is true, i.e. does a Lyapunov function, obtainable by a well-defined algorithm, exist for every stable system?

Answer 21

As a simple example up to a certain level of maths most of the rules of Euclidian geometry are assumed while they pertain to very few geometries.