MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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) eliptic curves, transendental 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 Desrague 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 (mid 19th 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)

-
I think that this should be community wiki. – Andrew Stacey Nov 11 2009 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. – Andrew Stacey Nov 11 2009 at 9:50
I've hit this with the wiki hammer. – Scott Morrison Nov 11 2009 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 2009 at 8:03
Why does this question have a bounty anyway? – Kevin Lin Nov 21 2009 at 17:33

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

-

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

-

Gödel's Constructible Universe, L, is the fundamental example of inner model theory. L was the first inner model, and is the minimal one. One could argue that the point of inner model theory is to build L-like models that do things L cannot.

-

Theory of Algebraically Closed Fields (ACF for short) is an important example in Model Theory. This was a motivation example to develop theory of stable and simple theories (leading, eventually, to a beautiful proof of Mordell-Lang conjecture by Ehud Hrushovski).

-

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 Newton-Raphson method. A method for finding successively better approximations to the zeroes of a real-valued function. See also this link.

-

The Ising model (1925)

-

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

-

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?

-

I think the seven bridges of Koenigsberg initiated a lot of modern discrete mathematics.

-

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

-
yes, perhaps along with nim. – Gil Kalai Nov 21 2009 at 21:07

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.

-

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.

-

Two unrelated examples: The configuration of 27 lines on a cubic surface ; (See also here and here) The regular heptadecagon (17 sides polygon) and its geometric construction.

-

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.

-

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.

-

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

-

Ravi Vakil gives interesting examples in algebraic geometry: "The existence of some of these pathologies is common knowledge'', but I had never known what they were.".

-

Margulis's expanders: This class of 8 regular graphs is the first explicit example for a family of expanders. The vertices are pairs of integer modulo m, the neighbors of (x,y) are (x+y,y), (x-y,y), (x,y+x), (x,y-x), (x+y+1,y), (x-y+1,y), (x, y+x+1), (x,y-x+1). All operations are modulo m.

Expanders were first doscovered and constucted probabilistically by Pinsker. The Ramanujan graphs of Lubotzky, Philips and Sarnak are expanders with extremely good properties. This paper by Hoory, Linial and Wigderson contains much more information.

-

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.

-

Although this may fall foul of the criticism that it perhaps it has not shaped a subject yet, I'll give it the benefit of the doubt that it may still shape a future subject. In a way the answer touches two answers already given: the Platonic solids and also the quaternions.

I am talking about the ADE classification, which appears in the theory of Lie algebras, finite subgroups of $SU(2)$ (McKay correspondence), representation theory of quivers (Gabriel's theorem), singularity theory (Du Val), classification of conformal field theories,...

-

The arithmetics of conics with pythagorean triples is since long been used as toy model for the beautifull combination of arithmetics, analysis and geometry in the study of algebraic curves, but Lemmermeyer's "Conics - a Poor Man's Elliptic Curves" and his subsequent arxiv articles pushes the "toy" into the direction of a "fundamental example" for some fascinating issues.

-

Spheres (of various dimensions) are the fundamental examples of (compact) Riemannian manifolds (or even Alexandrov spaces) of curvature > 0. Several major theorems of Riemannian geometry were motivated by the question of how to recognize a sphere. Most recently this culminated in Brendle and Schoen's proof of the differentiable sphere theorem.

-

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 2009 at 6:49

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

-
-