# Fundamental Examples

It is not unusual that a single example or a very few shape an entire mathematical discipline. Can you give examples for such examples? (One example, or few, per post, please)

I'd love to learn about further basic or central examples and I think such examples serve as good invitations to various areas. (Which is why a bounty was offered.)

To make this question and the various examples a more useful source there is a designated answer to point out connections between the various examples we collected.

In order to make it a more useful source, I list all the answers in categories, and added (for most) a date and (for 2/5) a link to the answer which often offers more details. (~year means approximate year, *year means a year when an older example becomes central in view of some discovery, year? means that I am not sure if this is the correct year and ? means that I do not know the date. Please edit and correct.) Of course, if you see some important example missing, add it!

Logic and foundations: $\aleph_\omega$ (~1890), Russell's paradox (1901), Halting problem (1936), Goedel constructible universe L (1938), McKinsey formula in modal logic (~1941), 3SAT (*1970), The theory of Algebraically closed fields (ACF) (?),

Physics: Brachistochrone problem (1696), Ising model (1925), The harmonic oscillator,(?) Dirac's delta function (1927), Heisenberg model of 1-D chain of spin 1/2 atoms, (~1928), Feynman path integral (1948),

Real and Complex Analysis: Harmonic series (14th Cen.) {and Riemann zeta function (1859)}, the Gamma function (1720), li(x), The elliptic integral that launched Riemann surfaces (*1854?), Chebyshev polynomials (?1854) punctured open set in C^n (Hartog's theorem *1906 ?)

Partial differential equations: Laplace equation (1773), the heat equation, wave equation, Navier-Stokes equation (1822),KdV equations (1877),

Functional analysis: Unilateral shift, The spaces $\ell_p$, $L_p$ and $C(k)$, Tsirelson spaces (1974), Cuntz algebra,

Algebra: Polynomials (ancient?), Z (ancient?) and Z/6Z (Middle Ages?), symmetric and alternating groups (*1832), Gaussian integers ($Z[\sqrt -1]$) (1832), $Z[\sqrt(-5)]$,$su_3$ ($su_2)$, full matrix ring over a ring, $\operatorname{SL}_2(\mathbb{Z})$ and SU(2), quaternions (1843), p-adic numbers (1897), Young tableaux (1900) and Schur polynomials, cyclotomic fields, Hopf algebras (1941) Fischer-Griess monster (1973), Heisenberg group, ADE-classification (and Dynkin diagrams), Prufer p-groups,

Number Theory: conics and pythagorean triples (ancient), Fermat equation (1637), Riemann zeta function (1859) elliptic curves, transcendental numbers, Fermat hypersurfaces,

Probability: Normal distribution (1733), Brownian motion (1827), The percolation model (1957), The Gaussian Orthogonal Ensemble, the Gaussian Unitary Ensemble, and the Gaussian Symplectic Ensemble, SLE (1999),

Dynamics: Logistic map (1845?), Smale's horseshoe map(1960). Mandelbrot set (1978/80) (Julia set), cat map, (Anosov diffeomorphism)

Geometry: Platonic solids (ancient), the Euclidean ball (ancient), The configuration of 27 lines on a cubic surface, The configurations of Desargues and Pappus, construction of regular heptadecagon (*1796), Hyperbolic geometry (1830), Reuleaux triangle (19th century), Fano plane (early 20th century ??), cyclic polytopes (1902), Delaunay triangulation (1934) Leech lattice (1965), Penrose tiling (1974), noncommutative torus, cone of positive semidefinite matrices, the associahedron (1961)

Topology: Spheres, Figure-eight knot (ancient), trefoil knot (ancient?) (Borromean rings (ancient?)), the torus (ancient?), Mobius strip (1858), Cantor set (1883), Projective spaces (complex, real, quanterionic..), Poincare dodecahedral sphere (1904), Homotopy group of spheres, Alexander polynomial (1923), Hopf fibration (1931), The standard embedding of the torus in R^3 (*1934 in Morse theory), pseudo-arcs (1948), Discrete metric spaces, Sorgenfrey line, Complex projective space, the cotangent bundle (?), The Grassmannian variety,homotopy group of spheres (*1951), Milnor exotic spheres (1965)

Graph theory: The seven bridges of Koenigsberg (1735), Petersen Graph (1886), two edge-colorings of K_6 (Ramsey's theorem 1930), K_33 and K_5 (Kuratowski's theorem 1930), Tutte graph (1946), Margulis's expanders (1973) and Ramanujan graphs (1986),

Combinatorics: tic-tac-toe (ancient Egypt(?)) (The game of nim (ancient China(?))), Pascal's triangle (China and Europe 17th), Catalan numbers (18th century), (Fibonacci sequence (12th century; probably ancient), Kirkman's schoolgirl problem (1850), surreal numbers (1969), alternating sign matrices (1982)

Algorithms and Computer Science: Newton Raphson method (17th century), Turing machine (1937), RSA (1977), universal quantum computer (1985)

Social Science: Prisoner's dilemma (1950) (and also the chicken game, chain store game, and centipede game), the model of exchange economy, second price auction (1961)

Statistics: the Lady Tasting Tea (?1920), Agricultural Field Experiments (Randomized Block Design, Analysis of Variance) (?1920), Neyman-Pearson lemma (?1930), Decision Theory (?1940), the Likelihood Function (?1920), Bootstrapping (?1975)

-
I think that this should be community wiki. – Loop Space Nov 11 '09 at 7:55
@Jose: Hard to say exactly. My instinct is that the kind of answers that this question will garner are those that didn't involve much actual thought, and the votes up or down will be more an assessment of whether the voter liked the example rather than whether the voter liked the answer (which, ideally, should contain an explanation of why that example shaped the discipline); both of these indicate that the answerers should not gain reputation for their answers, hence community wiki. – Loop Space Nov 11 '09 at 9:50
I've hit this with the wiki hammer. – Scott Morrison Nov 11 '09 at 19:34
I can't imagine a counterexample to the following rule: Any question whose purpose is to produce a sorted list of resources (i.e. the question includes, or should include, "one per post please") should be community wiki. – Anton Geraschenko Nov 12 '09 at 8:03
Why does this question have a bounty anyway? – Kevin H. Lin Nov 21 '09 at 17:33

In modal logic there is a particularly simple formula, called McKinsey formula: ◻⋄p→⋄◻p. It is so simple, yet it defines a frame property which cannot be expressed in first-order logic.

Also, with the right selection of other formulas, it gives rise to frame incompleteness examples (logics that are consistent, but are not logics of any class of frames whatsoever).

-

the Fischer-Griess Monster.

see:

http://en.wikipedia.org/wiki/Monster_group

-

Poincare dodecahedral sphere, the 1904 example of a homology sphere was fundamental for the discovery of the fundamental group, and have led to the statement of the Poincare conjecture.

-

SLE - stochastic Loewner evolution (or Schramm-Loewner evolution) is a one parameter class of random planar curves. These random curves depend on a real parameter kappa, they are (almost suely) simple curves when kappa is at most 4, they fill the plane when kappa is at least 8. They are related to many planar stochastic models. Look here for more pictures.

-

While the group of permutations (and permutation matrices) is probably too fundamental to be included, a mysterious, with much more yet to be understood generalization called alternating sign matrices are important in modern combinatorics. Those are square matrices with entries 1, 0 and -1 so that the non zero entries in each row and column alternate in sign and sum up tp one. There is a simple correspondence between alternating sign matrices and monotone triangles.

-

RSA

(From the Wikipedia article) In cryptography, RSA (which stands for Rivest, Shamir and Adleman) is an algorithm for public-key cryptography. It is the first algorithm known to be suitable for signing as well as encryption, and was one of the first great advances in public key cryptography. RSA is widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys and the use of up-to-date implementations.

-

The Alexander polynomial in knot theory.

-
-

Hyperbolic toral automorphisms (viz. the cat map and its generalizations) are the fundamental examples of Anosov diffeomorphisms, and their suspensions are the fundamental examples of Anosov flows. This is because they are "structurally stable", i.e. small perturbations preserve the Anosov property and any Anosov diffeomorphism on a torus is topologically conjugate to a hyperbolic toral automorphism. I am actually not even aware of any other concrete examples of Anosov dynamics other than those derived from geodesic flows on hyperbolic spaces.

-

I think polynomials are one of the greatest inventions of humankind. Not only are they extremely flexible and come up in so many domains of math, but they've lead to interesting breakthroughs. For example, trying to find a closed formed solution to the quintic polynomial lead Galois to develop groups, right?

-

Within the category of algorithms and computer science, I would say Conway's "The Game of Life", where binary, two dimensional structures may evolve, requiring not much than an initial state.

http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life

Cellular automatons have spawn practically a branch of computer science on its own right, and has deep connections with dynamical systems and some types of fractals as well, like Sierpinsky's triangle, using rule 90 (in Mathematica):

ArrayPlot[CellularAutomaton[90, {{1}, 0}, 50]] This commands embeds the running of the Rule 90 for 50 steps, from a single 1 on a background of zeros, and then displays Sierpinsky's triangle.

Also, celullar automatons, inspired on the Game of Life, have met their usage as well to study pseudo-randomness, or artificial music (see Stephen Wolfram's work, for example).

-

The cyclic polytope in the study of convex polytopes in high dimensions.

It is the convex hull of n points on the moment curve (t,t^2,t^3,...,t^d). It is simplicial and has the property that every [d/2] points form a face. (So, for example, in 4 dimension every two vertices form an edge.)

-
Its boundary also has the greatest number of faces of each dimension among d-1-dimensional simplicial spheres on n vertices. (This is the upper bound theorem.) – Hugh Thomas Nov 15 '09 at 17:22

The cone of positive semidefinite matrices is a fundamental example of a convex cone which is important in convexity and for convex and semidefinite programming.

The Reuleaux triangle is the first and most famous example of a set of constant width other than the circle (or ball in higher dimensions).

-
The determinant of symmetric matrix is a fundamental example of hyperbolic polynomial (it is hyperbolic with respect to any positive definite matrix). – Petya Mar 15 '10 at 4:56

Tic-Tac-Toe tends to be the starting example in combinatorial game theory, just because it's simple enough to depict the entire tree on one page yet can still be used to illustrate the standard definitions and notation.

-
yes, perhaps along with nim. – Gil Kalai Nov 21 '09 at 21:07
xkcd.com/832 – kjetil b halvorsen Sep 16 '15 at 12:51

The Newton-Raphson method. A method for finding successively better approximations to the zeroes of a real-valued function. See also this link.

-

The Prüfer p-group is a noteworthy example in the theory of Infinite Abelian Groups. (Answer by J. H. S.)

-

The Ising model (1925)

-

The symmetric and alternating groups are fundamental examples in group theory, representation theory, and combinatorics.

-

The gamma function is a fundamental example of an interesting function defined only on the integers which has an analytic (meromorphic) continuation to the whole complex plane. This ability to extend an interesting, seemingly discrete function to a complex differentiable function motivates a lot of later material.

-

The irrational rotation on the torus $\mathbb{T^2}$: $T_t (z,w) = (e^{2 \pi i \alpha }z, e^{2 \pi i \beta} w)$, where $\alpha, \beta \in \mathbb{R}, \frac{\alpha}{\beta} \notin \mathbb{Q}$. It is perhaps the first nontrivial example of an ergodic dynamical system. By considering its orbits $t \mapsto T_t (z,w)$, one gets examples of one-to-one immersions (with dense image) which are not embeddings, immersed submanifolds which are not closed/regular submanifolds, Lie subgroups which are not closed subgroups, non-Hausdorff quotient space and similar phenomena.

-

In combinatorics there are very simple basic graphs from which a whole lot of theory came. For example the complete graphs $K_5$ and $K_{3,3}$ which alone provide the ground level for any non-planar graph according to Kuratowski's theorem. Another simple graph that gave rise to a huge amount of theory is Petersen's graph, which I like to think as the graph whose vertices are the ten two-element subsets of $\{1,2,3,4,5\}$, and for which two such vertices are connected iff they are disjoint.

A link for Kuratowski's theorem is http://en.wikipedia.org/wiki/Kuratowski's_theorem

-

In $C^*$-algebras, the Cuntz Algebra is a fundamental example of a separable unital $C^*$-algebra. Its appearance has reshaped much of the theory of $C^*$-algebras.

-
You probably want to say something about it being simple and infinite and nuclear, as well... – Yemon Choi Nov 22 '09 at 14:10

The image of a torus embedded in $\mathbb{R}^3$ tilted on its side is the fundamental example of Morse Theory. In some sense it shows why you should "believe" all of the Morse lemmas before you sit down to prove them.

-

I think the question of whether or not $li(x) := \int_{2}^{x} \frac{dt}{\ln(t)}$ was contained in $\mathbb{C}\left(x, \ln\left(x\right)\right)$ spawned the field of galois theory of differential equations. One key question in this field, is what sort of extensions arise from adjoining solutions to a differential equation with coefficients in some ring (for example $\mathbb{C}(x)$?

In the case of the original question it can be posed as what extension arises from the differential equation $$\ln(x)y' = 1?$$

This field developed in parallel to galois theory of number fields (and other algebraic geometry, and arithmetic geometry). A good reference for the field is the aptly titled "Galois Theory of Linear Differential Equations" by Marius Van der Put and Michael Singer.

-
In case it is not clear why this function is interesting, it is asymptotic to $\pi(x)$, the number of primes less than x. – Ben Weiss Nov 24 '09 at 5:44
This reminds me that we did not include any number in our list. Probably pi and e are too fundamental, but the Euler constant could be a candidate. – Gil Kalai Nov 24 '09 at 6:05
The question of whether li(x) is contained in C(x,ln(x)) reduces at once to the transcendence of ln(x) over C(x), which is easy to prove. So perhaps you mean the question of whether li(x) is an elementary function. Questions similar to this were indeed the root of Liouville's theory of elementary integrals. – lhf Nov 25 '09 at 1:31

Some of the examples above have indeed shaped whole "disciplines" but others, as striking as they are, are less sweeping in scope.

For me, a very important and thought provoking example, and historically important for a variety of reasons is the Tutte graph. This graph shows a 3-valent 3-polytopal graph which has no hamiltonian circuit. This example, in particular, doomed attempts to prove the 4-color theorem based on ideas related to hamiltonian circuits.

http://en.wikipedia.org/wiki/Tutte_graph

http://mathworld.wolfram.com/TuttesGraph.html

It inspired a great variety of conjectures and work related to hamiltonian circuits for polytopes.

-
A very nice example. It is true that the examples vary in terms of importance and also in terms of how large we understand the concept of an "example". – Gil Kalai Dec 6 '09 at 6:49

The Sorgenfrey line is an example that has motivated a lot of research in general topology, mostly generalized metric properties and ordered space theory. It's an example of a hereditary normal space with non-normal square, it is separable, Lindelöf, first countable, but not second countable; a generalized ordered space that is not orderable, and many more.

-

The rational parametrization of the locus of the equation $X^2+Y^2=1$ by $(\frac{t^2-1}{t^2+1},\frac{2t}{t^2+1})$. It can be viewed geometrically by taking a line that intersects the unit circle at one rational point and then considering all possible (rational) slopes of the line (including infinity), which are in correspondence with (rational) points of the circle. This is the most basic example of using a geometric idea to find solutions to a diophantine equation, and it leads to very deep mathematics.

-
It's also a nice way to prove the trigonometric change of variable formulas with $t=\tan(\alpha/2)$. When I saw those in high-school, I believe we used brute force instead! – Thierry Zell Apr 18 '11 at 18:44

Motivated by Amit Kumar Gupta's answer about the continuum hypothesis, let me add an example that is less natural but has inspired an amazing amount of set theory, namely Suslin's Hypothesis. This conjecture, proposed in 1920 and now known to be independent of ZFC, says that the real line with its usual ordering relation is characterized up to isomorphism by the following properties:

• dense linear order without endpoints

• Dedekind-complete

• No uncountable family of pairwise disjoint open intervals.

The point of the conjecture is that it was proved much earlier by Cantor that one gets a characterization of $\mathbb R$ if one puts in place of the last property the stronger statement that there is a countable dense set. So Suslin is simply asking whether one can weaken this separability assumption to the third property in the list above (often called the "countable chain condition"). I can't claim that this question is anywhere near as natural as the continuum hypothesis, but what makes it important (in my opinion) is its impact on the development of set theory. The fact that Suslin's hypothesis is false in Gödel's constructible universe $L$ was one of the first applications (and probably a major motivation, though I don't actually know that) for Jensen's theory of the fine structure of $L$, a theory that has grown tremendously as a component of the inner model program in contemporary set theory. The fact that Suslin's hypothesis is consistent with ZFC was the initial application and the motivation for the theory of iterated forcing, now a central tool in set theory. It also provided the occasion for the invention of Martin's axiom. That axiom and the combinatorial principles isolated by Jensen from the fine structure of $L$ have become standard tools for proving independence results without explicitly referring to forcing or to $L$.

-

The Lorenz system of ordinary differential equations: $$\dot x=\sigma(y-x)$$ $$\dot y = rx-y-xz$$ $$\dot z = xy-bz$$ ($\sigma$, $r$, $b$ are parameters) is a good example in dynamical system. It is an example of a deterministic system displaying chaotic behaviour. Also the Lorenz attractor. Date: 1963.

-