Additive combinatorics Created 2026-09-24 Updated 2026-10-13
Additive combinatorics studies how the cardinalities and sumset representation functions of sumsets reveal structure in finite sets contained in abelian groups. Write the group operation as addition: the ambient abelian group may be the integers , a finite cyclic group, or another abelian group. The same definitions apply, but the ambient group changes which bounds are possible.
The basic experiment is to add every ordered pair of members of a finite set. The sumset records the distinct answers; the sumset representation function records how often each answer occurs; the additive energy counts coincidences between those answers. An arithmetic progression produces many repeated sums, so its sumset grows slowly and its additive energy is relatively large. The doubling constant measures that growth relative to the original cardinality.
The examples below compare the arithmetic progression with the more spread-out integer set . Their four members give sixteen ordered pairs in each case, but different numbers of distinct sums. This small comparison illustrates the definitions; it does not establish a claim about arbitrarily large sets. For a systematic introduction, see Tao and Vu's author page for Additive Combinatorics, with free sample chapters on sum set estimates and additive geometry.
Additive energy Created 2026-09-24 Updated 2026-10-13
The additive energy of a finite set in an abelian group counts additive quadruples, with order and repeated members allowed:
At a fixed sum , independently choosing two of its ordered pairs gives additive quadruples. Thus additive energy weights heavily represented sums more strongly than the cardinality of the sumset does.
For and , the sumset representation functions give
The arithmetic progression has additional coincidences such as . The set still has coincidences forced by commutativity, including , so its additive energy is not merely the sixteen identical-pair comparisons.
The same additive energy can be counted using the difference set. Define . The identity is equivalent to , and the coordinate rearrangement is a bijection. Consequently
For , the difference counts from through are again . For , the zero difference has four representations and each of the twelve nonzero differences has one, giving . The sumset representation functions for sums and differences can look different while their squared totals agree.
For every nonempty finite set in an abelian group ,
The lower bound follows from the Cauchy-Schwarz inequality and the total sumset representation function count:
For the upper bound, any three members determine at most one fourth member of an additive quadruple. See Yufei Zhao's MIT lecture 25, pages 1-3, for representation counts and the energy bounds.
In the two integer examples, the lower bounds are and , and the upper bound is . For the subgroup of , each element of has three sum representations, so and both bounds are equalities.
For nonempty , dividing additive energy by gives a relative measure between and one. Small doubling constant therefore forces relatively large additive energy. A converse requires care: the Balog-Szemerédi-Gowers theorem extracts a large subset with small doubling constant, rather than asserting that all of has small doubling constant.
For a directed graph, store in for the edge . The reverse edge is separate and is stored only if it exists. Consequently, list length is outdegree, not indegree, and each directed edge contributes one entry in total. An incoming-list index is additional storage.[ref]
Orient the seven edges of our example from earlier to later labels. The resulting directed graph has
There are now seven entries, with outdegrees . In particular, needs an empty list even though it is reached from : incoming edges do not make 's outgoing list nonempty. Replacing each directed edge by an undirected graph connection would lose this distinction.
Our running simple graph excludes self-loops and repeated edges. If those restrictions are relaxed, specify how the adjacency list encodes them. Here an undirected self-loop at contributes two copies of to , matching its contribution of two to the degree of a vertex. A directed self-loop contributes one copy, and one each to outdegree and indegree. Distinct parallel edges retain distinct entries; a multigraph's list length can therefore exceed its number of distinct neighbours.[ref][ref]
For example, add one undirected self-loop at to the seven-edge example. Its list becomes , the vertex degree of becomes four, and the total entry count becomes sixteen for eight edges. If an application instead stores a self-loop once, it must account for its doubled undirected vertex degree separately. In a weighted graph, an entry can be an ordered pair meaning destination and weight ; the weight belongs to the edge, not to the destination vertex.
An almost strongly universal hash family relaxes the exact ordered pair balance of a strongly universal hash family. In the convention used here, choose with the uniform distribution on a finite set from a family with possible outputs. Every individual output remains uniform, and for every distinct pair of inputs and every specified ordered pair of outputs ,
Equivalently, the conditional probability is at most . This asks how predictable a second output can become after the first is known.
For , strongly universal hash families give : learning one output leaves each specified second output with conditional probability . A looser guarantee permits a specified ordered pair to have probability as large as , while each individual output still has probability . Summing over the five equal ordered pairs bounds the collision probability by , rather than the required of a universal hash family. Thus an almost strongly universal hash family need not be a universal hash family. Necessarily , because the conditional probabilities sum to one; equality recovers a strongly universal hash family. This relaxation is useful in Wegman–Carter authentication, where efficiency can be traded against a quantified forgery bound within a complete message authentication protocol.
Binary tree Created 2026-10-13 Updated 2026-10-14
A binary tree, in the data structure convention used here, is a rooted tree in which each vertex has zero, one or two children in a rooted tree, occupying distinct left and right positions. A single left child and a single right child give different binary trees. A vertex with no children in a rooted tree is called a leaf. An empty binary tree has no root of a tree and is also allowed as a storage case. [ref]
For example, give the root of a tree label , its left child label and its right child label . Attach as the left and right children in a rooted tree of , and as those of . This binary tree has seven vertices, six edges, and height of a binary tree : a longest downward graph path contains two edges. The binary search tree lookup illustration below shows this shape alongside the binary tree consisting only of successive right children , whose height of a binary tree is .
Left and right positions specify an ordered shape, not a numerical total order on stored labels. Swapping labels and in the first example still gives a binary tree, but destroys the binary search tree property. Nor must a binary tree be balanced: the right-child chain is just as valid. The same shape convention supports a binary heap, a Huffman code, or a binary search tree, each with its own additional rules. The useful idea is to describe two smaller subtrees at each vertex, making structural recursion natural.
For a precise recursive description, a finite binary tree is either empty or a root of a tree carrying a value together with an ordered pair of disjoint smaller binary trees. The entries of this ordered pair are its left and right subtrees, each of which may be empty. Thus two binary tree child slots exist even when fewer than two children in a rooted tree exist; an empty slot does not denote an extra vertex. This decomposition is the basis of structural recursion.[ref]
Figure 1.
Left and right binary tree child slots distinguish shapes even with just one child
. Solid circles are vertices; outlined squares mark empty binary tree child slots. The first two binary trees differ only in the occupied slot at . The last two have the same four labels but different height of a binary tree. Details.
In the four-vertex mixed example, has left child and right child , while has only a right child . Count its vertices by structural recursion: the empty binary tree contributes zero and each nonempty binary tree contributes one plus the counts of its left and right subtrees. Thus contributes , and contributes . The same decomposition computes height of a binary tree, supports inorder traversal, and supplies short proofs by structural induction. It separates shape from the values stored in a data structure.
Ignoring values, let count finite binary tree shapes with vertices, retaining left and right slots and counting the empty shape once. Splitting at the root of a tree gives the recurrence relation
For each left subtree size , choose its shape and the right subtree shape independently. This yields the Catalan numbers: , , and . The two shapes at are exactly the left-only and right-only examples. Forgetting the slot distinction would change the counting problem.
Catalan number Created 2026-09-24 Updated 2026-10-14
The Catalan number counts Dyck paths with semilength of a Dyck path . For a nonnegative integer ,
The count includes the empty path. Of the paths with three up steps and three down steps, exactly five stay at nonnegative height. Their shapes and balanced parentheses encodings appear below.[ref]
Figure 1.
All five Dyck paths of semilength three and their balanced parentheses encodings
. Original enumeration of six-step up/down paths with nonnegative prefix heights. An up step encodes an opening parenthesis and a down step a closing one. Each panel shows one distinct string; no path shape or illustration is copied from a source. Details.
The useful connection is a shared decomposition. A Dyck path splits uniquely at its first-return decomposition of a Dyck path; a binary tree splits at its root into left and right subtrees; a binary parenthesization splits at its last operation. Each removes one outer unit and leaves an ordered pair of smaller objects. The resulting Catalan recurrence lets one count several different structures with the same calculation. A count of five does not mean the structures are physically identical: a bijection supplies the precise translation between them.
Combinatorics Created 2026-09-24 Updated 2026-10-13
Combinatorics studies discrete structures through counting, construction, and extremal questions. Its objects include subsets, permutations, graphs, and set partitions. The question is often easy to ask: how many teams can we choose, how many arrangements avoid a collision, or how few connections are enough? The challenge is to organize the possibilities so that every permitted object is counted exactly as intended.
For example, choosing two people from five gives ten teams. Choosing a captain and deputy from those same five gives twenty assignments. The difference is whether order is part of the object: a team is a subset, while the two named roles distinguish an ordered pair. The binomial coefficient and the rule of product encode these two counting problems. Choosing the right objects comes before manipulating a formula.
The beauty is that a change of viewpoint can turn enumeration into an explanation. Double counting connects two descriptions of one collection; Pascal's identity splits a selection into cases; the inclusion-exclusion principle repairs overlapping counts. These methods also supply exact finite models for probability and help measure the possibilities an algorithm must handle. Richard Stanley's textbook introduces the subject through counting questions and then develops these general tools. [ref]
Converse relation 2026-10-31
Reversing every ordered pair of a binary relation. Swapping the two components is its own inverse and therefore preserves distinctness of a representation by a list of distinct pairs.
Conway Game of Life 2026-10-13
Conway's Game of Life is a cellular automaton in which a simple local rule produces patterns that remain still, pulse, or travel across a square grid. Choose the starting pattern; after that there are no player decisions. The Life blinker and Life glider below make the surprise concrete: the rule mentions only births and survival, yet repeated applications create a clock and a moving shape.
The standard board is infinite, with cells at ordered pairs of integers. At generation let be for a live cell and for a dead cell. Count all eight cells sharing an edge or a corner, excluding the center itself:
The local Boolean function defining the next generation is
This is the rule B3/S23: a dead cell is born with exactly three live neighbors; a live cell survives with exactly two or three. A live cell with zero or one, or with four through eight, dies. A dead cell with two stays dead. All counts and center states come from generation : this is a synchronous update, even if an algorithm computes its cells one at a time.[ref]
In particular, the two births in the Life blinker do not help any other cell survive until the following generation. Writing each answer over its old value and then reading that new value for another count changes the rule. The simplest correct algorithm reads one array and writes the next generation into a second array; swap their roles after the entire step. The one-row in-place Life update achieves the same rule with less auxiliary storage by preserving the old values that later counts still need.
A finite implementation must specify its boundary convention. Holding all cells outside the rectangle permanently dead can destroy a Life glider when it reaches the edge. Wrapping neighbor coordinates from one edge to the opposite edge allows interaction with patterns on the other side. Neither convention is the infinite board. The figures display finite windows into an infinite board initially dead everywhere except the stated live cells; the windows do not impose walls.
Conway's Game of Life illustrates emergence in a precise, modest sense: the Life glider's motion is a collective pattern derived from local birth and death, without a motion command. It has deterministic evolution; visually surprising behavior introduces no random choices. Nor do the words "alive" and "dead" make it an experimentally validated model of biology. The beauty is that the same rule yields a stable four-cell square, the Life blinker, and the Life glider: three qualitatively different behaviors from a handful of cells.
For the stable square, take the live set . Each live cell has three live neighbors, and every dead cell has at most two. The next generation is identical: this configuration is a fixed point of the global update function. In contrast, the Life blinker returns after two generations, and the Life glider returns only after allowing a translation.
The patterns are useful as small, exact checks of an algorithm: the square checks survival without births, the Life blinker checks births and deaths in one simultaneous step, and the Life glider checks several steps and diagonal neighbors. More elaborate constructions can encode data and assemble Boolean circuits; Johnston and Greene develop constructions that simulate arbitrary computation in their chapter 9. This is a statement about suitably designed patterns with enough space and time, not a claim that every starting pattern computes something useful or that a fixed finite board has unlimited computer memory.[ref]
Martin Gardner introduced Conway's Game of Life to his Scientific American readers in October 1970, reporting that Conway selected the rules after experimentation with patterns. The aim was sustained, varied behavior rather than immediate extinction or trivially demonstrable unlimited growth. These were mathematical explorations of chosen rules.[ref]
Gardner's hands-on procedure is still a useful experiment: place black counters for the current live cells; mark doomed counters by stacking another black counter; mark births with white counters; finish checking before removing the doomed stacks and turning white counters black. Count only the original black occupants. Repeat with three adjacent counters to obtain the Life blinker, then with the five coordinates of the Life glider. Recording each generation tests whether the procedure implements the rule; it does not measure a natural population.[ref]
Difference set Created 2026-09-24 Updated 2026-10-13
For finite sets in an abelian group , their difference set is
Here is the additive inverse in . The difference set records possible displacements from a member of to a member of ; it is distinct from the set difference .
For the integer sets and ,
The positive differences for are , each obtained once; reversing each ordered pair supplies the corresponding negative difference. Every nonempty finite set has , with representations . Swapping the members of an ordered pair also shows . In the cyclic group , the subgroup satisfies as well as .
Dirichlet convolution Created 2026-09-24 Updated 2026-11-05
The Dirichlet convolution of arithmetic functions is the arithmetic function
In the first sum, runs over the positive integer divisors of ; the second uses ordered pairs of positive integers whose product is . Both sums are finite. Each pair contributes one weight from and one from , so Dirichlet convolution combines information attached to complementary factors. It turns a divisor sum into an operation on arithmetic functions. [ref]
For the six ordered pairs are . The constant-one arithmetic function gives one per pair, while the identity arithmetic function weights the first factor by its size:
Here is the divisor function and is the sum-of-divisors function. By comparison, the pointwise product of arithmetic functions gives and .
Figure 1.
Six ordered pairs of positive integers with product 12 contribute to Dirichlet convolution: one per pair for the divisor function, or the first factor for the sum-of-divisors function
. Details.
Commutativity follows by swapping the two entries of every ordered pair. Associativity follows by reindexing either grouping over the same ordered tuples of three positive integers:
For example, counts ordered tuples of three positive integers with product . Distribute the two occurrences of the prime factor among three entries in ways, and the one occurrence of the prime factor in ways. These binomial coefficients are the stars and bars counts of exponent choices in the nonnegative integers; prime factorization therefore gives such tuples. Directly, the same Dirichlet convolution is .
The Identity for Dirichlet convolution is , and the Möbius function reverses a divisor sum because . This makes Dirichlet convolution useful both for counting factorizations and for recovering an arithmetic function from its divisor sum.
Dirichlet hyperbola method Created 2026-09-24 Updated 2026-10-14
The Dirichlet hyperbola method turns a long summation over a Dirichlet convolution into two short ones by covering the lattice points below a hyperbola with two overlapping strips. Its simplest application is an exact count: for a positive integer , every positive integer divisor of corresponds to the ordered pair . Thus the divisor summatory function counts precisely the ordered pairs of positive integers with :
Here is the divisor function, and the floor function gives the number of allowed values of for each . The axes are excluded, while points on are included.
Set , using the floor function and the positive square root. Every counted pair has or . Otherwise . The first strip contains points; swapping the two coordinates gives the same count for the second. Their overlap contains all pairs with , since . The inclusion-exclusion principle therefore gives the exact identity
The subtraction is for the whole overlap square, rather than only the diagonal. The same Dirichlet hyperbola method identity holds for real , with and . [ref]
Figure 1.
The Dirichlet hyperbola method counts 35 positive lattice points with : two strips of 22 points overlap in a square of nine points
. Details.
A subgroup of the graph automorphism group acts distance-transitively when it is transitive on the ordered pairs of vertices at each fixed graph distance. Thus two vertex pairs at the same distance can be matched by one automorphism from that subgroup. Existence of such a subgroup implies that the full automorphism group has the same property, making the graph a distance-transitive graph. The specified subgroup need not be the entire automorphism group.
Divisor function Created 2026-09-24 Updated 2026-11-05
The divisor function counts the positive integer divisors of a positive integer . In particular , because has just one positive integer divisor. More generally the notation gives and the sum-of-divisors function . Thus the divisor function counts the positive integer divisors, while adds their sizes. [ref]
If the prime factorization is with distinct prime numbers and positive exponents , then
The short proof is a count: each positive integer divisor has a unique form , where . There are choices at each prime number, and choosing them gives every positive integer divisor exactly once. For there are no prime factors and the product is .
For , choose and to obtain . The six values are ; sorted, the positive integer divisors are . Therefore . The diagram makes the independent exponent choices visible.
Figure 1.
The prime factorization gives a three-by-two array of positive integer divisors , so the divisor function has
. Details.
This count is useful because a known prime factorization gives without testing every smaller positive integer for divisibility. It also proves the divisor function is a multiplicative function: coprime integers have disjoint prime factors, so their exponent choices combine. For example , but , so it is not a completely multiplicative function. Equivalently, under Dirichlet convolution, counting ordered pairs of positive integers whose product is .
The divisor summatory function adds the divisor function up to a cutoff . It counts all ordered pairs of positive integers whose product is at most . For , the twelve individual divisor function values are
Counting columns of lattice points instead gives . The Dirichlet hyperbola method needs only the first three column counts:
The arithmetic work of the Dirichlet hyperbola method is much smaller even though the answer is identical.
This is useful for elementary averages: individual divisor function values fluctuate, but their summation has the regular behavior given by the divisor summatory asymptotic. Dividing that estimate by a positive integer gives
where is the natural logarithm, is the Euler--Mascheroni constant, and uses big O notation. This describes an average, rather than an estimate for every individual divisor function value. [ref]
Double counting establishes an identity by computing the cardinality of the same finite set in two ways. The useful step is to identify exactly what the members of that collection are; an algebraic equality then records two legitimate ways to organize them.
Take the ordered pairs where is a -element subset of an -element set and is marked. Choosing first gives pairs. Choosing first leaves members to choose from the other , giving . Hence
For five people and two-person teams, both counts give : ten teams with two choices of a marked member, or five choices of that member with four choices of a teammate. The identity is explained by the bijection between these descriptions, rather than merely verified through factorials.
Elementary outcome Created 2026-10-14 Updated 2026-10-25
An elementary outcome is one member of the sample space. For the ordered two-toss model, is one outcome; it contains both toss results. By contrast, “at least one head” is an event containing three outcomes. The outcome and the singleton set are different objects: when that singleton is measurable, the notation gives its probability. In the finite model below, every subset is measurable.
The word elementary refers to the chosen level of detail. An outcome can be an ordered pair, a sequence, or an entire realization of a point process. A random variable then extracts a numerical feature of that outcome; the window count of a point process is one example.
Empty-set cases for Cartesian projections Created 2026-10-07 Updated 2026-11-05
For the coordinate projection map , let denote the other factor. Then is surjective exactly when is the empty set or is nonempty. If is nonempty, a preimage of one chosen element requires an element of , and that same element provides a preimage for every element of .
The projection map is injective exactly when is the empty set or has at most one element. When contains an element and contains two distinct elements, the corresponding distinct ordered pairs have the same projection. With at most one omitted coordinate available, two pairs with the same retained coordinate must agree.
These conditions include the cases with the empty set as the domain of a function. In particular, a surjection onto an empty Cartesian product need not induce a surjection onto a nonempty factor: the empty function onto is surjective, while the resulting empty function into is not.
Finite modification of the identity on the real line Created 2026-10-07 Updated 2026-11-05
A finite modification of the identity on the real line is a function agreeing with the identity map outside a finite set. For example, changing only to gives such a function; both and then map to , so a finite modification need not be a bijection.
Sorting the exceptional set gives a unique finite record of ordered pairs . Real-number pairing by separated digits encodes every fixed-length record in , and placing length- records in disjoint intervals gives an injection into the real line. Include the zero-length record for the unchanged identity map. Conversely, prescribing and for gives distinct functions for distinct real numbers . The Cantor-Schröder-Bernstein theorem therefore shows that all such finite modifications have the same cardinality as the real line.
Forcing name rank 2026-10-06
The ordinal assigned recursively by . It measures dependency on subnames and justifies generic evaluation by recursion. The ordinary rank of a set also accounts for the coding of the ordered pairs and the forcing conditions; it need not equal this dependency rank of a set.