11
$\begingroup$

My experience seems to be that quite often "generic" mathematical objects tend to be either extremely well behaved or structured, or at the opposite extreme are as unstructured as possible.

For example, random finite graphs have good expansion properties but actually constructing explicit families of expanders is quite challenging. There are a number of theorems that state that generic finitely generated subgroups of certain classes of topological groups are free.

On the other extreme, nearly all finite groups are (believed to be) $2$-groups (even $2$-step solvable), which is in some sense as unstructured as a finite group can be (in particular, I think nobody feels one can classify them up to isomorphism). Generic finite semigroups are (believed to be) $3$-nilpotent, meaning they have a multiplicative zero and the product of any $3$ elements is $0$. This again would indicate that the generic object is highly non-structured.

I am interested in other examples in different areas of mathematics of this phenomenon of generic objects being unreasonably structured or simply unreasonable.

As usual for big list questions, please provide one example per answer.

$\endgroup$
6
  • $\begingroup$ I am particularly interested in nontrivial examples from a math viewpoint. Eg almost all numbers are transcendental would be a less interesting example. $\endgroup$ May 7, 2014 at 15:00
  • 1
    $\begingroup$ The dichotomy between "highly structured" and "highly random" is at the heart of additive combinatorics: or at least I have heard this slogan tossed around a lot! $\endgroup$ May 7, 2014 at 15:11
  • 1
    $\begingroup$ Would "Almost all continuous functions are nowhere differentiable" (in either the sense of category or measure) be an example of the kind you are looking for? Maybe that again is too trivial. Or, "Almost all numbers are normal"? $\endgroup$ May 7, 2014 at 16:28
  • $\begingroup$ @Nate, they are better in some sense than transcendental numbers, but of course the deeper the math involved the more interesting. $\endgroup$ May 7, 2014 at 17:51
  • $\begingroup$ alas interesting idea but probably too broad when undecidable problems are taken into acct (undecidability is quite rampant). also, fractals. also, Collatz conjecture related to integer iterative/dynamic equations. $\endgroup$
    – vzn
    May 7, 2014 at 20:18

8 Answers 8

9
$\begingroup$

Generic Turing machine programs are unreasonable: the computation head will fall off the beginning of the tape.

Basically, the situation is that on the usual one-way infinite tape model, a random program causes a random-walk behavior for the head position, and consequently by Polya's recurrence theorem, it follows that almost all Turing machine programs lead eventually to the situation where the head attempts to move left from the left-most cell, causing the head to fall off the beginning of the tape. Indeed, almost all programs do this before repeating a state. This is not difficult to see, if you think about what a random program line in a huge program will do: write something random, randomly go left or right, and pick a random new state. If the states have not yet repeated, then exactly half of the programs go left and half go right from whatever configuration you're at.

$\endgroup$
8
  • 1
    $\begingroup$ @JoelHamkins, does this not depend on the model of Turing machine? What happens with two-way infinite tapes? $\endgroup$ May 7, 2014 at 19:09
  • $\begingroup$ Yes, as we discuss in the paper, the argument is for the one-way infinite tape models. With two-way infinite tapes, if you allow many halt states, then almost all programs halt very quickly. But if you have a two-way infinite tape and only one halt state, then the best known currently is that proportion $1/e^2$ of all Turing machines fail to halt, for trivial reasons. $\endgroup$ May 7, 2014 at 19:13
  • $\begingroup$ You might expand upon this briefly. Just looking at the linked abstract, I get the impression that with probability 1 you can tell if a program will stop in polynomial time, in polynomial time. This might mean that with high probability P is equal to NP. Gerhard "Or Most Programs Are Garbage" Paseman, 2014.05.07 $\endgroup$ May 7, 2014 at 19:14
  • $\begingroup$ @GerhardPaseman thanks for the advice; I have added some explanation. $\endgroup$ May 7, 2014 at 19:19
  • 1
    $\begingroup$ I think the mentions of P and NP here in regard to the paper may lead to confusion, so let me clarify the matter. The result we prove is that there is a measure-one set of TM programs on which the halting problem is trivial, so trivial that it can be decided in polynomial time (even linear time). This has nothing to do with whether the programs themselves operate in P or NP. But in fact, a corollary of the proof of the result is that almost all programs compute a function with finite domain, using the particular TM formalism of that paper. $\endgroup$ May 14, 2014 at 13:02
6
$\begingroup$

The phenomenon of concentration of measure produces many examples wherein a randomly chosen object has an unexpected property with high probability. A classical example is the Johnson-Lindenstrauss lemma, which asserts that given any small number $\epsilon$, integers $N >> n >> k$, and $k$ points in $\mathbb{R}^N$, a randomly chosen linear map $\mathbb{R}^N \to \mathbb{R}^n$ will distort the pairwise distances between the $k$ points by no more than a factor of $1-\epsilon$ with very high probability.

$\endgroup$
1
  • $\begingroup$ I am very happy to have been told about this result! $\endgroup$ Jun 25, 2014 at 14:01
5
$\begingroup$

Their are many such examples in the theory of finite dimensional Banach spaces. Suppose that $X$ is an $n$ dimensional Banach space. If you take a random subspace of dimension $k$, then for some values of $k$ (in particular, if $k$ is of order at most $\log n$), you get a subspace whose norm is a small distortion of a Euclidean norm. In fact, $k$ can even be proportional to $n$ if $X=\ell_p^n$ with $1\le p \le 2$. On the other hand, sometimes you you get a very bad space if $k$ is large. For example, if $X= \ell_p^n$, $2< p \le \infty$, the random subspace of proportional dimensional does not have any good basis (technically, the unconditional constant of any basis is large).

$\endgroup$
3
$\begingroup$

The set of umbilics of infinite curvature of a "typical" convex body in $\mathbb{R}^n$ has measure zero, but is dense and uncountable.

Here "typical" is in the sense of Baire category: the subset of convex bodies with this property is "comeager."

Schneider, Rolf. "Curvatures of typical convex bodies—The complete picture." Proc. Amer. Math. Soc., (PDF download link).

There are several properties of typical convex bodies that are somewhat counterintuitive.

$\endgroup$
2
$\begingroup$

Gabriel proved that generic finite dimensional algebras have finite representation type. This is surprisingly structured.

$\endgroup$
2
$\begingroup$

Atiyah and Hirzebruch proved that if a compact connected Lie group acts smoothly and nontrivially on a compact spin manifold of dimension $4k$ then the $\hat{A}$-genus vanishes. By calculations with the spin bordism group, there is a sense in which a "generic spin manifold" of dimension $4k$ has nonvanishing $\hat{A}$-genus (at least for $k > 1$ - not sure if anything weird happens in dimension $4$), so the conclusion is that a generic compact spin manifold of dimension $4k$ has only discrete symmetries.

By contrast, while many (but not all) of the basic examples of compact manifolds one encounters in everyday life are spin, most have some sort of continuous symmetry (indeed, quite a few are homogeneous spaces).

$\endgroup$
0
1
$\begingroup$

There is a tendency for Baire-generic self-adjoint operators on a separable Hilbert space to exhibit purely singular continuous spectrum. An enjoyable reference which contains precise theorems in this vein is the following:

B. Simon, Operators with Singular Continuous Spectrum: I. General Operators, Annals of Mathematics, 141 (1995) 131-145.

$\endgroup$
-1
$\begingroup$

Given the initial state (assumed not to be at the origin) of a Brownian motion in $\mathbb{R}^2$, and the angular component of the process in polar coordinates, one can deduce the entire trajectory of the process. See Rogers and Williams' book "Diffusions, Markov Processes and Martingales" for a proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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