A strongly universal hash family makes every ordered pair of outputs equally likely: for distinct inputs and arbitrary specified outputs ,
Thus the two outputs are independent random variables, each with the uniform distribution on a finite set. Adding the equal ordered pairs gives collision probability , so the family is also a universal hash family.
Here is a completely enumerable example. In the finite field , take the affine functions , using modular arithmetic modulo . Choose and as independent random variables, each with the uniform distribution on a finite set of all five finite field elements , including . There are equally likely hash functions. For , the ordered pair is . For instance gives ; gives . Every prescribed occurs exactly once, at .
Figure 1.
Enumerating all affine hash functions over the finite field with five elements
. Each cell shows the unique coefficient pair (a,b) producing the displayed outputs at 0 and 1. Removing a = 0 deletes the diagonal and leaves dependent outputs despite uniform individual values. Details.
Each row contains five choices, so each individual output has probability . Each cell has probability , and the five diagonal cells give collision probability . For any distinct , the same conclusion follows from and : a nonzero finite field element has a unique inverse. This is the beauty of the construction: two small random coefficients provide exact pair balance without choosing five unrelated values.
The example uses equal-sized input and output sets to make every choice visible; it illustrates the family definitions rather than compression. In a larger input set, a hash function cannot avoid all collisions into five buckets. What a universal hash family controls is the fraction of its members that collide on each fixed pair, rather than the existence of any collision anywhere.
Restricting to leaves permutations with zero collision probability for distinct inputs. Individual outputs remain uniform, but given , the four values other than each have conditional probability and has zero. Hence these outputs are not independent random variables: this is a universal hash family but not a strongly universal hash family. Finally, the full -member example contains five constant functions, with immediately visible collisions. Its pair guarantee concerns a random choice of hash function, and makes no claim of cryptographic collision resistance.
Swap 2026-10-31
Exchange two stored values while preserving all others. For an array, a temporary value implements x := a[i]; a[i] := a[j]; a[j] := x. For distinct indices this uses two element reads and two element writes. The operation is an involution, and its permutation is a transposition.
Sylvester matrix Created 2026-10-14 Updated 2026-10-18
For polynomials of polynomial degrees , the Sylvester matrix has shifted coefficient rows of followed by shifted rows of , using descending-power order. It is a square matrix of size . Its transpose represents the linear map with , ; its determinant is the resultant.
For an original parameter example, choose and . Then
The two lists of coefficients become three rows because is multiplied by both and . Thus the common-root parameter values are and . At , the resultant is , so the two polynomials have no common root.
Figure 1.
A Sylvester matrix tests when a moving root of a polynomial coincides with a fixed one
. Original example , . Left: the vertical dashed line marks the root of a polynomial of ; it does not make zero. Right: the same test for all parameters is the function graph of the resultant . A crossing between two arbitrary function curves would not suffice: both values must be zero. Details.
One can verify the certificate without any determinant expansion:
For , division by gives a Bézout's identity for polynomials. At , the identity instead becomes a nontrivial cancellation between multiples of two polynomials sharing the polynomial factor .
The general proof needs only a short linear algebra outline. A common polynomial factor gives a nonzero cancelling pair within the degree bounds, making the Sylvester matrix singular. Conversely, if are coprime polynomials and , then divides ; the bound forces and then . Thus the linear map has zero kernel of a linear map exactly in the coprime case. Over an algebraic closure, a nonconstant common polynomial factor is equivalent to a common root.
In 1840, James Joseph Sylvester described forming the shifted coefficient rows and taking a signed sum of products selected by permutations. In modern notation, this is the Sylvester matrix and its determinant. The construction turns the nonlinear common-root of a polynomial question into linear algebra. His paper's word derivatives concerns elimination, rather than the formal derivative used below.[ref]
Symmetric group Created 2026-09-24 Updated 2026-11-05
The symmetric group is the group of all bijections of an -element set, with multiplication given by function composition. There are such permutations, since one chooses the images successively in ways.
For , composition is not commutative: but the reversed product is , applying the rightmost permutation first. Every permutation decomposes into disjoint cycles and into transpositions. By Cayley's theorem, every finite group embeds in some symmetric group, so permutation actions provide a universal concrete model of finite group operations.
A permutation of order two is a product of disjoint transpositions. Its conjugacy class has the displayed size. For , equality with the transposition class requires . The left side grows strictly with . At , its ratio to the right side is one only for ; at it jumps from below to above one between and , and for it is already greater than one. Thus degree six is the only possible exceptional degree for an group automorphism not preserving transpositions.
Symmetric tensor 2026-10-06
A symmetric tensor is unchanged by every permutation of its slots. A symmetric second-rank tensor is the rank-two case; symmetry for higher rank requires invariance under every such slot exchange.
Take the four-point set
the vertices of a polygon of a rectangle whose side lengths are four and two. Three choices of structure give three different symmetry groups on these same points.
As an unstructured set, has all permutations as symmetries, forming the symmetric group . If Euclidean distance is part of the data, the allowed maps are only the identity, a half-turn rotation, and the reflections across the two coordinate axes. They form a Klein four-group of group order four. To see that nothing is missing, fix the image of one vertex of a polygon: its three other distances, , , and , are distinct, so they uniquely determine the images of the remaining vertices.
Preserving affine structure permits more. The affine map
cycles all four points of . It sends a horizontal side of length four to a vertical side of length two, so it is not an isometry. Yet it preserves the rectangle's vertex set and all affine combinations among those points.
Figure 1.
An affine symmetry preserves these four points while changing a side's Euclidean length
. Original example . The orange side of length four on the left is sent to the orange side of length two on the right. The point labels track the map for this illustration; they are not additional fixed labels imposed on the underlying four-point object. Details.
Let and let be the square's quarter-turn rotation. Then
Conjugating every square symmetry by gives eight affine maps preserving . This group isomorphism makes the affine symmetry group a dihedral group, although some of its maps do not preserve the original Euclidean distances. There are no further affine symmetries: an affine map preserves the common midpoint of the diagonals, so it must preserve opposite pairs. The image of one vertex has four choices and the image of an adjacent vertex has two; those choices determine the map through three noncollinear points.
Thus
An arbitrary permutation need not be an affine map. For example, exchanging the two top vertices while fixing the two bottom vertices sends the common diagonal midpoint to two different points, which no single affine map can do. The phrase "the symmetry of these points" becomes unambiguous only after stating which structure matters.
Symmetry group Created 2026-10-14 Updated 2026-10-14
A symmetry group collects bijections of an object to itself that preserve a specified structure in both directions, with function composition as the operation. For a geometric object one may require Euclidean distances to be preserved, giving an isometry group; for a graph, one preserves adjacency, giving a graph automorphism group. For an unstructured finite set, every permutation is allowed. The structure to be preserved is part of the definition.
For a square with its usual geometric structure, the symmetry group consists of four rotations and four reflections. These form the dihedral group of group order eight. The existing group action example shows how its eight elements move the vertices of a polygon; changing the object to its edges or a marked configuration changes the group action being studied.[ref]
Specifying the preserved data makes it possible to test a proposed symmetry exactly. After the preserved data are declared, function composition, the identity map, and inverse maps automatically preserve them too. Symmetry transformations therefore form a group, and questions about equivalent configurations become questions about group orbits, stabilizer subgroups, and group homomorphisms. This supplies reusable mathematics for comparing many different kinds of objects.
A divided difference depends on the chosen interpolation nodes and their data, but is unchanged by any permutation of those same interpolation nodes. The explicit sum in divided difference makes this visible: a permutation merely rearranges its summands.[ref]
There is also a short explanation using Lagrange cardinal polynomials. The coefficient of in the th Lagrange cardinal polynomial is . Taking that coefficient in their weighted sum gives exactly the explicit divided difference formula. Since polynomial interpolation has a unique answer for a fixed set of distinct interpolation nodes, this coefficient cannot depend on their ordering. If the interpolation polynomial has polynomial degree below , the coefficient is zero.
For the four-point example in divided difference table, every ordering gives third divided difference . This does not make every Newton polynomial coefficient invariant: whereas , because these use different pairs of interpolation nodes. Even at second order, and use different triples. The node order in Newton interpolation determines which subsets occur along the top row.
Symplectic quotient of the binary subset module Created 2026-10-14 Updated 2026-11-05
Let be even and let be the vector subspace of even-weight vectors. Its dot product is an alternating bilinear form, since on . The orthogonal complement of in is spanned by the all-one vector , which lies in . Consequently the radical of a bilinear form on is , and
is a nondegenerate symplectic vector space of dimension . The symmetric group acts by coordinate permutations, preserving this alternating bilinear form.
At , this group action is faithful. A weight-two vector and its complement have weights two and four, so a permutation fixing its quotient class must fix that two-element subset itself. Fixing every two-element subset forces the identity. The resulting embedding is an isomorphism, because the symplectic group over a finite field order formula gives .
For the unitary group with , the third tensor power of its defining representation decomposes as displayed. The first two summands have highest weights and and dimensions and . The mixed summand has highest weight and dimension . In the three-dimensional weight space spanned by permutations of , the vectors killed by all positive root vectors have coefficient sum zero, giving multiplicity two. For , the exterior cube vanishes and .
The proper rotational tetrahedral symmetry group is , acting by even permutations of the vertices. Its conjugacy classes consist of the identity, the three half-turns about opposite-edge midpoint axes, four rotations through about outward-pointing vertex axes, and their four inverses. A 3-cycle has a three-element centralizer, so its class has size . Conjugating it to its inverse would require an odd permutation on its three moved vertices, so the two orientations form different classes in even though they lie in one class in .
For a number-conserving Gaussian pairing state, six permutations give this expression. Each transposition has sign , positive for bosons and negative for fermions; the two three-cycles have positive sign for either statistics. Equivalently it is the permanent or determinant of the three-by-three one-body density matrix. For bosonic number states, repeated-mode factorial corrections must be included instead of assuming that Wick theorem.
Topological order Created 2026-10-14 Updated 2026-11-05
A topological order of a finite directed graph is a sequence containing every vertex exactly once, with
Thus every directed edge points forward in the list. Equivalently, a bijection assigning positions satisfies for every directed edge . A topological ordering names the same kind of list. [ref]
The toy directed acyclic graph has exactly five topological orders: , , , , and . These lists were checked by enumerating all permutations and retaining precisely those satisfying all five directed edge inequalities. Every list ends with , since all other tasks have a directed path to publication. A topological order need not put adjacent entries next to one another in the directed graph: and are consecutive in without a directed edge between them.
A directed cycle would force the impossible chain of position inequalities . In the toy example, adding requires review before publication and publication before review, so there are no topological orders. Together with the construction in topological sorting, this proves that a finite directed graph admits a topological order if and only if it is a directed acyclic graph. The empty directed graph has the empty sequence as its topological order.
There is also a useful connection to partial orders: define when or there is a directed path from to . For a directed acyclic graph, this reachability relation is a partial order, and its linear extensions are exactly the topological orders. The directed acyclic graph specifies which pairs must be ordered; a topological order chooses positions for all the remaining pairs.
Top-to-random card shuffle Created 2026-10-03 Updated 2026-11-05
The Top-to-random card shuffle removes the top card and inserts it in one of the positions uniformly. Its Stationary distribution is uniform on permutations. Each move is the inverse of a move of the Random-to-top card shuffle, so these chains are time reversals under that Stationary distribution.
In this group-walk setting they also have the same total variation mixing profile. Starting from the identity permutation, a random-to-top path multiplies independent identically distributed increments . The top-to-random increments have their inverse law. Reversing the order of an iid list leaves its joint law unchanged, so the product of inverse increments has the law of . Inversion is a bijection preserving the uniform distribution; it therefore preserves total variation distance to that distribution. Translation symmetry makes the distance independent of the starting permutation.
Consequently top-to-random shares the cutoff scale and order- window of random-to-top. The group symmetry is essential to this argument: time reversal alone does not give equality of worst-case total variation profiles for arbitrary Markov chains.
Trace computation of Specht module dimension Created 2026-10-07 Updated 2026-11-05
Right multiplication by on the group algebra is an idempotent with image . Every diagonal entry in the permutation basis is the coefficient of the identity in , namely . Thus its rank equals its trace, giving . Triangular standard-tableau ideals and the Robinson–Schensted correspondence identify this dimension with the standard-tableau count.
Left multiplication of a permutation by a transposition swaps the two target labels . If they occur in different cycles, becomes the single cycle . If they occur in the same cycle, that formula reverses and splits the cycle in two. All other cycles are unchanged, so the total number of cycles, including fixed points, decreases or increases by exactly one. Empty intermediate lists yield one-cycles and require no exceptional case.
Transposition (permutation) Created 2026-09-28 Updated 2026-10-14
A transposition is a permutation that exchanges two elements and fixes every other element. Every transposition has order two.
A transposition is a cyclic permutation of length two.
A uniform random permutation of distinct objects gives each of the permutations the same probability. Restricting the order to any fixed subset gives a uniform ordering on that subset. Relative ranks encode such a permutation bijectively by independent choices of an insertion position.
Unit modulo n Created 2026-09-29 Updated 2026-10-14
For a positive integer modulus , a residue class is a unit when it has a modular multiplicative inverse: some integer satisfies . Modulo twelve, the units are exactly
In particular, five is its own modular inverse, since . Multiplying all twelve residue classes by five gives a permutation; multiplying the outputs by five recovers the inputs. By contrast, multiplying by six gives only zero and six, with six inputs for each output. It cannot be reversed.
Figure 1.
Multiplication by five permutes all twelve residue classes, whereas multiplication by six merges distinct inputs
. Details.
In general, the exact criterion is
For the forward direction, implies every common divisor of divides one. Conversely, if their greatest common divisor is one, Bézout's identity supplies , so is a modular inverse. The extended Euclidean algorithm computes these coefficients. The units form the unit group under multiplication. [ref]
Multiplicative cancellation while keeping the same integer modulus is valid for a unit modulo n: from , multiply by a modular inverse of to get . A nonunit cannot be cancelled as a general rule. For example, , yet . Thus division by six cannot undo this multiplication; solving a linear congruence instead keeps track of all possible classes.
This distinction marks the boundary between commutative rings and fields. Modulo a prime number , every nonzero residue class is a unit, so is a finite field. Modulo twelve it is a commutative ring with zero divisors, and is not a field. For , the sole class satisfies and is a unit; this one-element zero ring is not a field. [ref]