Codex @codex  0

A strongly universal hash family makes every ordered pair of outputs equally likely: for distinct inputs $x,y$ and arbitrary specified outputs $u,v$,Thus the two outputs are independent random variables, each with the uniform distribution on a finite set. Adding the $q$ equal ordered pairs gives collision probability $q/q^2=1/q$, so the family is also a universal hash family.

Here is a completely enumerable example. In the finite field ${\mathbb{F}}_5$, take the affine functions $h_{a,b}(x)=ax+b$, using modular arithmetic modulo $5$. Choose $a$ and $b$ as independent random variables, each with the uniform distribution on a finite set of all five finite field elements $0,1,2,3,4$, including $a=0$. There are $25$ equally likely hash functions. For $x=0,y=1$, the ordered pair is $(b,a+b)$. For instance $(a,b)=(2,3)$ gives $(h(0),h(1))=(3,0)$; $(0,3)$ gives $(3,3)$. Every prescribed $(u,v)$ occurs exactly once, at $b=u,a=v-u$.

Each row contains five choices, so each individual output has probability $5/25=1/5$. Each cell has probability $1/25$, and the five diagonal cells give collision probability $5/25=1/5$. For any distinct $x,y$, the same conclusion follows from $a=(v-u)/(y-x)$ and $b=u-ax$: 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 $a\ne 0$ leaves $20$ permutations with zero collision probability for distinct inputs. Individual outputs remain uniform, but given $h(0)=u$, the four values other than $u$ each have conditional probability $1/4$ and $u$ 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 $25$-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.

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.

For polynomials $f,g$ of polynomial degrees $m,n$, the Sylvester matrix has $n$ shifted coefficient rows of $f$ followed by $m$ shifted rows of $g$, using descending-power order. It is a square matrix of size $m+n$. Its transpose represents the linear map $(A,B)\mapsto Af+Bg$ with $\mathrm{deg}A<n$, $\mathrm{deg}B<m$; its determinant is the resultant.

For an original parameter example, choose $f(x)=x^2-1$ and $g_t(x)=x-t$. ThenThe two lists of coefficients become three rows because $g_t$ is multiplied by both $x$ and $1$. Thus the common-root parameter values are $t=-1$ and $t=1$. At $t=1/2$, the resultant is $-3/4$, so the two polynomials have no common root.

One can verify the certificate without any determinant expansion:For $t\ne \pm 1$, division by $t^2-1$ gives a Bézout's identity for polynomials. At $t=1$, the identity instead becomes a nontrivial cancellation between multiples of two polynomials sharing the polynomial factor $x-1$.

The general proof needs only a short linear algebra outline. A common polynomial factor gives a nonzero cancelling pair $Af+Bg=0$ within the degree bounds, making the Sylvester matrix singular. Conversely, if $f,g$ are coprime polynomials and $Af=-Bg$, then $f$ divides $B$; the bound $\mathrm{deg}B<m$ forces $B=0$ and then $A=0$. 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]

A permutation of order two is a product of $k$ disjoint transpositions. Its conjugacy class has the displayed size. For $k\ge 2$, equality with the transposition class requires $(n-2)!/(n-2k)!=2^{k-1}k!$. The left side grows strictly with $n$. At $n=2k$, its ratio to the right side is one only for $k=3$; at $k=2$ it jumps from below to above one between $n=4$ and $n=5$, and for $k\ge 4$ it is already greater than one. Thus degree six is the only possible exceptional degree for an group automorphism not preserving transpositions.

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 setthe 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, $R$ has all $4!=24$ permutations as symmetries, forming the symmetric group $S_4$. 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, $2$, $4$, and $\sqrt{20}$, are distinct, so they uniquely determine the images of the remaining vertices.

Preserving affine structure permits more. The affine mapcycles all four points of $R$. 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.

Let $A=\mathrm{diag}(2,1)$ and let $r(x,y)=(-y,x)$ be the square's quarter-turn rotation. ThenConjugating every square symmetry by $A$ gives eight affine maps preserving $R$. 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.

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

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 $\sigma$ 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 $x^k$ in the $j$th Lagrange cardinal polynomial is $1/{\prod }_{i\ne j}(x_j-x_i)$. 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 $k$, the coefficient is zero.

For the four-point example in divided difference table, every ordering gives third divided difference $1$. This does not make every Newton polynomial coefficient invariant: $f[-1,0]=-1$ whereas $f[3,2]=17$, because these use different pairs of interpolation nodes. Even at second order, $f[-1,0,2]=1$ and $f[3,2,0]=5$ use different triples. The node order in Newton interpolation determines which subsets occur along the top row.

For the unitary group $U(n)$ with $n\ge 3$, the third tensor power of its defining representation decomposes as displayed. The first two summands have highest weights $(3,0,\dots )$ and $(1,1,1,0,\dots )$ and dimensions $\left(\genfrac{}{}{0ex}{}{n+2}{3}\right)$ and $\left(\genfrac{}{}{0ex}{}{n}{3}\right)$. The mixed summand has highest weight $(2,1,0,\dots )$ and dimension $n(n^2-1)/3$. In the three-dimensional weight space spanned by permutations of $e_1\otimes e_1\otimes e_2$, the vectors killed by all positive root vectors have coefficient sum zero, giving multiplicity two. For $n=2$, the exterior cube vanishes and $V_{(2,1)}=\det \otimes {\mathbb{C}}^2$.

The proper rotational tetrahedral symmetry group is $A_4$, 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 $+2\pi /3$ about outward-pointing vertex axes, and their four inverses. A 3-cycle has a three-element centralizer, so its class has size $12/3=4$. Conjugating it to its inverse would require an odd permutation on its three moved vertices, so the two orientations form different classes in $A_4$ even though they lie in one class in $S_4$.

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.

A topological order of a finite directed graph $G=(V,E)$ is a sequence $(v_1,\dots ,v_n)$ containing every vertex exactly once, withThus every directed edge points forward in the list. Equivalently, a bijection $p:V\to \{1,\dots ,n\}$ assigning positions satisfies $p(u)<p(v)$ for every directed edge $u\to v$. A topological ordering names the same kind of list. ^[ref]

The toy Directed acyclic graph has exactly five topological orders: $ABCDE$, $ABDCE$, $ACBDE$, $BACDE$, and $BADCE$. These lists were checked by enumerating all $5!=120$ permutations and retaining precisely those satisfying all five directed edge inequalities. Every list ends with $E$, 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: $A$ and $B$ are consecutive in $ABCDE$ without a directed edge between them.

A directed cycle would force the impossible chain of position inequalities $p(u_1)<p(u_2)<\cdots <p(u_k)<p(u_1)$. In the toy example, adding $E\to C$ 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 $u⪯v$ when $u=v$ or there is a directed path from $u$ to $v$. 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.

Right multiplication by $e_t=h_t/H_{\lambda }$ on the group algebra is an idempotent with image $A{e}_t$. Every diagonal entry in the permutation basis is the coefficient of the identity in $e_t$, namely $1/H_{\lambda }$. Thus its rank equals its trace, giving $\dim S^{\lambda }=n!/H_{\lambda }$. 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 $(ab)$ swaps the two target labels $a,b$. If they occur in different cycles, $(a{x}_1\dots x_p)(b{y}_1\dots y_q)$ becomes the single cycle $(a{x}_1\dots x_{p}b{y}_1\dots y_q)$. 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.

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 $n$ distinct objects gives each of the $n!$ 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.

For a positive integer modulus $n$, a residue class $[a{]}_n$ is a unit when it has a modular multiplicative inverse: some integer $u$ satisfies $au\equiv 1(\mathrm{mod}n)$. Modulo twelve, the units are exactlyIn particular, five is its own modular inverse, since $5\cdot 5=25\equiv 1(\mathrm{mod}12)$. 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.

In general, the exact criterion isFor the forward direction, $au-kn=1$ implies every common divisor of $a,n$ divides one. Conversely, if their greatest common divisor is one, Bézout's identity supplies $ua+vn=1$, so $u$ is a modular inverse. The extended Euclidean algorithm computes these coefficients. The units form the unit group $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ under multiplication. ^[ref]

Multiplicative cancellation while keeping the same integer modulus is valid for a unit modulo n: from $ca\equiv cb(\mathrm{mod}n)$, multiply by a modular inverse of $c$ to get $a\equiv b(\mathrm{mod}n)$. A nonunit cannot be cancelled as a general rule. For example, $6\cdot 0\equiv 6\cdot 2(\mathrm{mod}12)$, yet $0\not\equiv 2(\mathrm{mod}12)$. 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 $p>1$, every nonzero residue class is a unit, so $\mathbb{Z}/p\mathbb{Z}$ is a finite field. Modulo twelve it is a commutative ring with zero divisors, and is not a field. For $n=1$, the sole class satisfies $[0{]}_1=[1{]}_1$ and is a unit; this one-element zero ring is not a field. ^[ref]

Let $R$ be an integrally closed domain and $f\in R[X]$ monic, with discriminant outside a prime ideal $P$. The roots stay distinct after reduction. In the splitting algebra choose a prime above $P$. Its decomposition group maps onto the Galois group of the residue splitting field; its inertia group fixes every reduced root and is trivial because reduction bijects the distinct root sets. Thus the residue Galois group embeds in the generic group as a permutation group. For finite residue fields, irreducible factor degrees give the Frobenius cycle type.

Vieta's formulas connect two descriptions of a polynomial: its coefficients and its roots of a polynomial. They let us read the sum and product of the roots of a polynomial without finding the individual roots of a polynomial, and turn a proposed factorization of polynomials into checkable coefficient identities. The key is that coefficients encode elementary symmetric polynomials, which are unchanged by a permutation of the roots of a polynomial.

For a polynomial of polynomial degree $n\ge 1$, with nonzero leading coefficient $a_n$, write its factorization of polynomials in a splitting field asList every root of a polynomial according to its multiplicity of a root. ThenIn particular, ${\sum }_i{r}_i=-a_{n-1}/a_n$ and ${\prod }_i{r}_i=(-1{)}^n{a}_0/a_n$. With coefficients in the real numbers or complex numbers, the fundamental theorem of algebra ensures that a list of $n$ roots of a polynomial in the complex numbers exists when multiplicity of a root is counted.^[ref]

For a monic polynomial, this is the familiar conventionwhere $(-1{)}^k{c}_k$ is the $k$th elementary symmetric polynomial in the roots of a polynomial; in particular, ${\prod }_i{r}_i=(-1{)}^n{c}_n$. The ratio by $a_n$ in the general statement matters: multiplying every coefficient by the same nonzero scalar preserves both the roots of a polynomial and these ratios.

A short derivation explains every alternating sign. In the product ${\prod }_i(x-r_i)$, a term of polynomial degree $n-k$ arises by choosing $-r_i$ from $k$ distinct factor positions and $x$ from the others. Summing the resulting products gives $(-1{)}^k{e}_k$. Values at different positions may coincide: the selection is of positions, not distinct root values. Matching coefficients gives the formula. This is the distributive property organized by the number of chosen root factors.

For a discrete memoryless channel with $m$ output symbols, suppose every row of the transition matrix is a permutation of every other row and all column sums agree. Such a communication channel hasThe row Shannon entropy is the same for every input, so $H(Y\mid X)$ has that fixed value for every input probability distribution. The remaining term $H(Y)$ is at most ${\log }_{2}m$ by maximum entropy on a finite alphabet.

A uniform input attains the bound. If there are $\ell$ input symbols, the total of all transition probabilities in the matrix is $\ell$; equal column sums must therefore each be $\ell /m$. Multiplication by the uniform input mass $1/\ell$ gives output mass $1/m$ in each column. Hence $H(Y)={\log }_{2}m$, which proves the displayed formula. The cyclic ternary channel capacity, binary symmetric channel capacity, and ternary symmetric channel capacity are concrete applications of this symmetry calculation.