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

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.

Turing machines (1937) and Boolean circuits: the primary models for digital computers.

Universal Quantum computers, and quantum Turing machines (Deutsch, 1985).

The ring of Gaussian integers Z[i] is a fundamental example of a ring of integers extending Z. Many early results in number theory were motivated by understanding and generalizing properties exhibited by Z[i] and its relationship with Z.

The Riemann zeta function is the fundamental example of a Dirichlet L-series. It is central in analytic number theory.

• (I think we had it this example before.) – Gil Kalai Jan 13 '10 at 19:59
• Ah, I see it now in the real and complex analysis section. It seems a curious omission in the number theory section, as well as the modular function $j(\tau)$ or the Dedekind eta function. Some of my suggestions for this question are not designed to be new examples to many mathematicians. They indicate that I think those examples are fundamental, which might not be as obvious to mathematicians outside those fields. – Douglas Zare Jan 14 '10 at 9:21
• Explaining how examples already mentioned are fundamental can be very useful! Note that you can freely edit existing answers. – Gil Kalai Jan 15 '10 at 8:40
• Actually, I can't edit them. – Douglas Zare Jan 15 '10 at 9:41

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.

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.

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

The Möbius strip or Möbius band (a surface with only one side and only one boundary component).

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

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.

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

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.

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.

The Alexander polynomial in knot theory.

Borromean rings

Borromean rings are important in several places. For example, they appear in computations of homotopy groups of the 2-sphere, where they corresponds to the Hopf fibration.

The pseudo-arc in continuum theory.

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?

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.

Schwarzschild metric as a prototype of black hole was a fundamental example in the development of General Relativity (for instance, it is often referred to when "defending" the ADM mass as a natural concept of mass in General Relativity).

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

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

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 surely) 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.

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.

I presented the emerging list of examples over my blog and several people suggested a few more examples. I will mention them together:

Tom LaGatta proposed to add the percolation model (1854), John Sidles made several suggestions and in particular proposed several examples from Control theory such as the Nyquist criteria, Christian Blatter proposed adding the Peano curve, and Mark Meckes proposed adding the fundamental Banach spaces L_p/l_p and C(K).

Joe Malkevich proposed several basic examples of games in addition to the prisoner dilemma (chicken, chain store game, and centipede) and the Gale-Shapley model of two-sided market model (the model in the famous Gale-Shapley stable marriage theorem). I thought that we should probably add a basic economic model of exchange markets (like the Arrow-Debreu model).

I also thought the configurations of Desargues and Pappus should be added.

There was also some critique on the classification of examples, and an interesting suggestion By Michael Nielsen that "Distilled and expanded, it could form the basis for an excellent book. Perhaps: 'Examples from the book'." (This refers to Aigner and Ziegler's book "Proofs from the book". (In fact, a similar idea by Ziegler and me have motivated the question itsef.)