65
$\begingroup$

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?

$\endgroup$
19
  • 8
    $\begingroup$ Before the end of 19th century, all continuous functions "encountered in mathematical literature" were piecewise differentiable. If you mean examples of such situation, the list will be almost infinite. $\endgroup$ Jul 26, 2021 at 19:35
  • 17
    $\begingroup$ A whole lot of conjectures have been been proven! Reading Godel, you could imagine a world where most interesting statements people come up with just don't have proofs or disproofs, let alone ones understandable by humans. Part of this could be selection bias (we don't study areas that are intractable) but I think we've also gotten lucky. $\endgroup$ Jul 26, 2021 at 19:47
  • 6
    $\begingroup$ @AlexMine "Category sense" often refers to the fact that some sets are of first or second category in Baire sense, these days more commonly known as meager and nonmeager. It is unrelated to category theory. $\endgroup$
    – Wojowu
    Jul 26, 2021 at 19:56
  • 7
    $\begingroup$ There are a huge number of examples in the literature in which extremely pathological behavior is proved to be "typical in the Baire category sense" -- differentiability behavior (in many different ways) of functions belonging to various spaces of functions, sequential convergence and summation behavior (in many different ways) of sequences belonging to various spaces of sequences, topological or geometrical or other behavior (in many different ways) of sets belonging to various hyperspaces of sets (compact, convex, continua, ...), etc. (continued) $\endgroup$ Jul 27, 2021 at 14:14
  • 4
    $\begingroup$ I think one way of understanding this is that many of these pathological behaviors can be viewed as certain types of regularity behavior that "natural examples" tend not to have. By regularity, I'm thinking of a kind of simplicity of structure that in certain ways is not very sensitive to perturbations, somewhat like continuous analogs of discrete phenomena. As a possibly over-simplistic example, consider the complexity of addition and multiplication of natural numbers as compared to addition and multiplication of transfinite (cardinal) numbers. $\endgroup$ Jul 27, 2021 at 14:28

21 Answers 21

50
$\begingroup$

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.

$\endgroup$
14
  • 20
    $\begingroup$ In the same vein, most finite partially ordered sets have height two (i.e., longest chain of cardinality three) by ams.org/journals/tran/1975-205-00/S0002-9947-1975-0369090-9, not at all like the ones occurring "naturally." $\endgroup$ Jul 27, 2021 at 0:32
  • 14
    $\begingroup$ Or most semigroups have a zero and the product of any three elements are zero but nobody ever considers these $\endgroup$ Jul 27, 2021 at 2:00
  • 6
    $\begingroup$ @Kvothe I understand your frustration, but "p-group" is standard terminology in abstract algebra which is freely used on this site. It is a group in which each element has order $p^k$, or equivalently for finite groups, a group of order $p^n$. $\endgroup$ Jul 28, 2021 at 10:24
  • 6
    $\begingroup$ @Kvothe I've added a link to p-group. (It would not have occurred to me though that p-group needed to be defined since it is a pretty standard abstract algebra term which I would think would be standard in the undergrad math curriculum.) $\endgroup$
    – JoshuaZ
    Jul 28, 2021 at 11:39
  • 3
    $\begingroup$ Well, most groups are conjectured to be not just $2$-groups, but also class-$2$ nilpotent. I’d say that that’s indeed a fairly strong “well-behavedness” condition, just short of being abelian, and the fact that they are formed as an extension of $(C_2)^n$ by $(C_2)^m$ does make their structure rather more boring than general finite groups (even though it still leaves room for them to be messy enough). $\endgroup$ Jul 29, 2021 at 15:15
34
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ This is equivalent to Timothy Chow's answer :) $\endgroup$ Jul 28, 2021 at 12:03
  • 1
    $\begingroup$ I see a clear explanation for this phenomenon: We are interested in computing numbers! Often we develop new mathematics in order to compute more. So it is no surprise that the numbers occurring in our mathematics are mostly computable numbers. $\endgroup$
    – user44143
    Jul 28, 2021 at 17:06
  • 2
    $\begingroup$ @darijgrinberg Can you expand on how they are equivalent? This isn't obvious to me. $\endgroup$
    – JoshuaZ
    Jul 28, 2021 at 17:16
  • 1
    $\begingroup$ Yeah, in hindsight I should have rather said "This is not very surprising given Timothy Chow's answer". $\endgroup$ Jul 28, 2021 at 20:25
  • 1
    $\begingroup$ @MattF No it's not surprising that mathematician mostly use computable numbers. I don't think the OP required the result to be surprising. Although, back in the 19th c. a lot of people were surprised to learn that that most numbers were incomputable (although they didn't use that term). I'm still entirely comfortable with the idea. $\endgroup$ Aug 11, 2021 at 19:03
32
$\begingroup$

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.

$\endgroup$
27
$\begingroup$

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.

$\endgroup$
13
  • 10
    $\begingroup$ Surely our notion of "naturality" of mathematical statements is shaped by our experience of mathematics, which tends to push it in the direction of statements that are not just provable, but can actually be proved by our existing techniques? Specifically, I think our mathematical aesthetic evolves to select for statements that are provable, but where a proof is very hard to find. $\endgroup$
    – Will Sawin
    Jul 26, 2021 at 23:33
  • 3
    $\begingroup$ It's not yet clear if there are many natural unprovable statements - the only thing we know is that there aren't many natural statements that we know how to prove are unprovable. This statement is not as mysterious, as we don't have nearly as many techniques available for proving statements unprovable in number theory as we do in, say, set theory. Certainly it's still pretty mysterious, though. $\endgroup$
    – Will Sawin
    Jul 26, 2021 at 23:35
  • 3
    $\begingroup$ @WillSawin I agree with your points. But note: ZF is much stronger than PA. A priori, we might expect that many theorems that can be stated in the first-order language of arithmetic and that can be proved in ZF would be unprovable in PA. But this seems not to be the case. "Natural" arithmetical theorems of ZF almost always turn out to be provable in PA (case study: Fermat's last theorem); it's not the case that we have lots of arithmetical theorems of ZF sitting around that we suspect are unprovable in PA but just can't prove that they're unprovable in PA. $\endgroup$ Jul 27, 2021 at 2:45
  • 8
    $\begingroup$ Regarding the Calude and Jurgensen paper: We've discussed this before and it seems wrong to me; see my post here mathoverflow.net/questions/4454/… . I've never been able to understand why I am wrong. @TimothyChow, you know a lot more logic than I do, can you help? $\endgroup$ Jul 27, 2021 at 11:20
  • 4
    $\begingroup$ I'll point out that my counterargument also involves an example of the phenomenon in this question. I point out that a positive density of grammatical mathematical sentences are of the form "$1=1$ or S", yet mathematicians spend almost no time trying to prove such sentences. This fact is not very mysterious, though... $\endgroup$ Jul 29, 2021 at 13:23
24
$\begingroup$

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.

$\endgroup$
1
24
$\begingroup$

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.

$\endgroup$
6
  • 15
    $\begingroup$ Moreover, there are $2^{2^{\aleph_0}}$ functions from $\mathbb{R}$ to $\mathbb{R}$, but only $2^{\aleph_0}$ of them are continuous. (Because a continuous function is determined by its values on the rational numbers.) So, in a very simple sense, almost all functions are discontinuous. $\endgroup$ Jul 27, 2021 at 13:56
  • $\begingroup$ How many continuous real functions are nowhere differentiable? $\endgroup$
    – Stef
    Jul 27, 2021 at 15:32
  • 5
    $\begingroup$ @Stef Continuous functions originating from the same point have a relatively natural measure on them, in the form of Brownian motion (Wiener measure). Under that measure, almost all the continuous functions are nowhere differentiable. $\endgroup$
    – Buzz
    Jul 27, 2021 at 16:16
  • 1
    $\begingroup$ @Stef See the math.SE question, 'Amount' of nowhere-differentiable functions in C([0,1])?. $\endgroup$ Jul 28, 2021 at 2:20
  • 1
    $\begingroup$ @Timothy Chow (and others who might be interested): For a lot about the type of nondifferentiability behavior that "most" continuous functions have, see my answer to Generic Elements of a Set. $\endgroup$ Jul 28, 2021 at 16:13
20
$\begingroup$
  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.

$\endgroup$
2
  • 13
    $\begingroup$ Your first example doesn't really work as such because I explicitly ruled out the case when we have a simple explanation like “a counterexample can't be constructed without the axiom of choice”. But you can replace “measurable” by “Borel” and it works (and also ties nicely with the second). $\endgroup$
    – Gro-Tsen
    Jul 26, 2021 at 23:06
  • $\begingroup$ Goof point, I was a bit sloppy there with regards to the criteria. $\endgroup$ Jul 27, 2021 at 7:14
16
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ Students of Lie algebras are out there making sure that some non-associative operations are studied. (Also students of exceptional groups who think of $\mathsf G_2$ via automorphisms of the octonions.) $\endgroup$
    – LSpice
    Jan 8, 2022 at 17:42
  • 1
    $\begingroup$ Personally, I'm quite interested in subtraction, which is notoriously nonassociative. $\endgroup$ Jul 25, 2022 at 2:09
13
$\begingroup$

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.

$\endgroup$
1
  • 17
    $\begingroup$ This sounds very interesting, but could you mention some examples accessible to a non-deformation theorist? $\endgroup$
    – LSpice
    Jul 26, 2021 at 20:11
12
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ What's the case for regular spaces being the cutoff, rather than completely regular? $\endgroup$
    – arsmath
    Jul 26, 2021 at 21:32
  • 1
    $\begingroup$ I edited my answer to give a case for regularity and a case for complete regularity. The regular spaces will become completely regular (and much more) in forcing extensions, and the for every regular frame $L$, there is another frame $M$ where $L\oplus M$ is paracompact. $\endgroup$ Jul 26, 2021 at 22:13
  • $\begingroup$ It would be helpful to also mention an example of a regular not completely regular space. Or at least explain what comprises the difference. $\endgroup$ Jul 27, 2021 at 5:04
10
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Does "the conjecture still holds" mean that it is known to be true, or just not known to be false? $\endgroup$
    – LSpice
    Aug 25, 2023 at 2:07
  • $\begingroup$ @LSpice For clarity, please allow me to group in steps: (a) for a normal subgroup $H$, $G$ is amen. iff $H$ & $G/H$ are amen.. If $G/G_e$ compact (so amenable), then $G$ amen. iff $G_e$ amen. (b) By the structure theorem, there exists a compact normal subgroup $K$ such that $L:=G_e/K$ is a connected Lie group. By (a), $G_e$ is amen. iff $L=G_e/K$ is amen.. (c) Let $S$ be the solvable radical of $L$. $S$ is always amen.. If the semisimple $L/S$ is compact, it is always amenable. If not compact, it must contain a topologically isomorphic copy of $\mathbb{F}_2$. $\endgroup$
    – Onur Oktay
    Aug 26, 2023 at 5:38
  • $\begingroup$ Putting all together, an almost connected $G$ is amenable iff $L/S$ doesn't contain a copy of $\mathbb{F}_2$. Since the space is limited, there are a few gaps in this outline. For instance, it doesn't tell how to lift copies of $\mathbb{F}_2$ to $G$ from $L/S$. $\endgroup$
    – Onur Oktay
    Aug 26, 2023 at 5:50
10
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ This may be related to the 'rigidity'/'lack of deformations' or 'extra symmetries' which have also been mentioned... $\endgroup$ Jul 27, 2021 at 14:47
  • 2
    $\begingroup$ In fact, since the moduli space of curves of genus greater than 24 is not unirationa, it would seem that l one can only find the generic point "formally" since the co-ordinates of the parameter space cannot be chosen to be algebraically independent of each other. $\endgroup$
    – Kapil
    Jul 27, 2021 at 15:12
9
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ Not true of the homotopy category of spaces! Probably most other homotopy categories as well. $\endgroup$
    – Jeff Strom
    Jul 26, 2021 at 22:27
  • 4
    $\begingroup$ @JeffStrom Certainly, those are the next most natural examples. I think I can sneak by with asserting that they're not met by the typical undergraduate, though! Those also give another property that holds in all but one counterexample, too: concreteness. And it's interesting to observe that they tend to have locally presentable models in the background, whether as model categories or $\infty$-categories--an exception that proves the rule, I think, whereas Top is just a real exception. $\endgroup$ Jul 26, 2021 at 22:29
  • $\begingroup$ The "typical" condition also protects this statement from having the category of schemes as a counterexample. $\endgroup$
    – Will Sawin
    Jul 26, 2021 at 23:40
  • 1
    $\begingroup$ @willSawin Yes, I suppose schemes are a fair example too, though of course there are a lot of proposals for not working in that category, an urge which gets at the explanation of my observation. $\endgroup$ Jul 27, 2021 at 3:08
  • $\begingroup$ Actually I do not agree to both of the statements made here. Many naturally occuring categories are not (co)complete and not locally presentable, also very basic examples already (manifolds for example). Besides, there is always the trick to consider subcategories of nice objects, e.g. the category of Noetherian rings, which behaves badly. See also the 3rd cond. in the question. $\endgroup$ Aug 2, 2021 at 17:57
8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ It should be mentioned that by the time hierarchy theorem, we have that $P \supsetneq TIME(n^3)$ (or $TIME(n^k)$ for any finite $k$), which is a priori a possible explanation for this. So there are problems that require $n^{100}$ time, but known examples are highly artificial. $\endgroup$ Aug 9, 2021 at 20:28
  • $\begingroup$ See cstheory.stackexchange.com/questions/6660/… for an interesting discussion of polynomial-time algorithms with huge exponents. $\endgroup$
    – Guntram
    Aug 18, 2021 at 14:04
7
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ @ChristianChapman The various hardness results for linear codes (NP hardness of the Nearest Codeword problem and minimum distance problems) would suggest that the problem is nature, not thought. $\endgroup$ Jul 29, 2021 at 6:33
  • $\begingroup$ Mark, in general Nearest Codeword is more difficult than decoding with an error rate guarantee. $\endgroup$ Jul 29, 2021 at 11:16
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.