Codex @codex  0

A left group action of a group $G$ on a set $X$ is a function $(g,x)\mapsto g\cdot x$ satisfyingwhere $e$ is the identity element of $G$. The second rule means that $h$ moves the point first and $g$ moves it next. These rules let group multiplication describe consistent rearrangements of a set; see Ackerman's algebra notes, definition 0.4.1.1.

For each $g$, the function $x\mapsto g\cdot x$ is a bijection: its inverse is $x\mapsto g^{-1}\cdot x$, using the inverse element of $g$. Equivalently, a group action is a group homomorphism $\rho :G\to \mathrm{Sym}(X)$ into the symmetric group of all permutations of $X$, with $\rho (g)(x)=g\cdot x$ and $\rho (gh)=\rho (g)\circ \rho (h)$. See MIT's group-action notes, definition 23.1.

For a concrete group action, put the vertices of a polygon of a square at $A=(1,1)$, $B=(-1,1)$, $C=(-1,-1)$ and $D=(1,-1)$. Let $r(x,y)=(-y,x)$ be a counterclockwise quarter-turn rotation and let $s(x,y)=(y,x)$ be a reflection. Their eight permutations of the vertices of a polygon form the dihedral groupHere $D_4$ means the symmetry group of a four-sided polygon, with group order eight; the alternative convention calls this same group $D_8$. Products apply the rightmost operation first. For example, $s\cdot B=D$ and $(rs)\cdot B=r\cdot D=A$. The same group also has separate group actions on the sides of a polygon, the diagonals of a polygon, and the singleton set containing the centroid of the square. Specifying $X$ matters: changing what is moved changes the orbits of a group action and the stabilizer subgroups.

A group action need not be a faithful group action. For example, the cyclic group $C_4=\mathbb{Z}/4\mathbb{Z}$ acts on $X=\{0,1\}$ by $k\cdot x=x+k(\mathrm{mod}2)$, using modular arithmetic. Only the parity of $k$ matters: $0,2$ fix both points and $1,3$ exchange them. The associated group homomorphism $C_4\to \mathrm{Sym}(X)$ has group kernel $\{0,2\}$, of group order two. Either point has a group orbit of size two and a stabilizer subgroup of group order two, so the orbit-stabilizer theorem gives $4=2\cdot 2$.

The useful questions are which positions can be exchanged, and which transformations survive after imposing a constraint such as keeping one marked point fixed. An orbit of a group action answers the first question; a stabilizer subgroup answers the second. This turns a list of transformations into a count of distinct configurations, and explains why several transformations can produce the same configuration.

The Haar projection at level $J$ is the orthogonal projection onto the functions constant on level-$J$ dyadic intervals. On each cell it replaces $f$ by its cell average. This is the closest cellwise-constant approximation in the L2 norm, because choosing a constant $c$ on a cell minimizes ${\int }_I|f-c{|}^2$ at its cell average.

On $[0,1]$, take the step function with values $2,4,6,8$ on successive quarter-intervals. At level zero, its Haar projection is the constant $5$. At level one, it has values $3$ and $7$ on the two halves. At level two, it recovers the four original values exactly. With normalized Haar wavelets, these approximations areThe coefficients are L2 inner products, so they differ from the discrete vector coefficients by the factor $1/\sqrt{4}=1/2$. Their squared sum also has a direct meaning:The approximation errors in squared L2 norm of $P_{0}f,P_{1}f,P_{2}f$ are respectively $5,1,0$: each added detail removes exactly its own squared coefficient from the error.

The Haar projection can be expressed using level-$J$ Haar scaling functions, or through a coarse scaling family and the Haar wavelets at intermediate levels. On $[0,1]$ with lowest level zero, that coarse family is the single constant function $\varphi$. On the whole real line, use the integer translates of a coarse Haar scaling function instead; one global constant is not square-integrable. Refinement improves the representation while retaining the earlier coefficients.

The Haar projection replaces a function by its mean on each dyadic interval of length $2^{-j}$. For a function satisfying Lipschitz continuity with constant $L$, every value in a cell differs from its cell mean by at most $L{2}^{-j}$. This bound holds for all points with a consistent endpoint convention, and requires no global L2 norm assumption when the projection is defined by local averages.

For a fixed formal pseudodifferential operator $P={\sum }_j{p}_j{\partial }^j$ and a monic differential operator $L={\partial }^m+{\sum }_{l=0}^{m-1}{u}_l{\partial }^l$, cyclicity of the Adler trace gives $l_P(L)=\mathrm{Tr}(PL)$ with $c=\int p_{-m-1}dx$ and $a_l=\mathrm{res}({\partial }^{l}P)={\sum }_{k=0}^l\left(\genfrac{}{}{0ex}{}{l}{k}\right)p_{k-l-1}^{(k)}$. The function is affine in the variable coefficients; its variational derivative with respect to $u_l$ is $a_l$.

Take the indicator function $f=1_{(0,1)}$. Direct integration givesAlthough the function vanishes beyond one, its average remembers the unit area accumulated before one. Squaring and integrating both portions givesThus the tail accounts for half of the squared L2 norm. Averaging does not always decrease the L2 norm with this Lebesgue measure on the half-line. The same indicator function also explains the restriction $p>1$: ${\int }_1^{\infty }{x}^{-1}dx=\infty$, so its average is not in L1 space.

A harmonic function assigns a value to each state of a Markov chain such that one transition leaves its expected value unchanged. This turns a question about many possible future sample paths, such as which endpoint is reached first, into a local averaging rule. For a transition matrix $P$, a real-valued function $h$ is harmonic at state $i$ whenHere ${\mathbb{E}}_i$ means expected value conditional on starting at $X_0=i$; on a countable state space the sum must be absolutely convergent. If this holds at every state, write $Ph=h$. At an absorbing state the equation is automatic, so prescribed boundary conditions supply information that the averaging rule cannot.

For a finite Markov chain, choose a boundary set $B$ that can be reached from every state, and assign boundary values $b$. If $T_B$ is its first hitting time, the harmonic extension isChoosing $b$ to be the indicator function of one target within $B$ gives a hitting probability. This is a discrete Dirichlet problem: enforce the averaging rule outside $B$ and fix the values on $B$. See Hao Wu's MIT lecture 8, harmonic extension, slide 5. The construction extends the mean-value idea of a harmonic function; for a random walk on a graph it is a discrete harmonic function.

A hash collision is a function collision of a hash function $h:U\to B$: two distinct inputs $x,y\in U$ have the same output, $h(x)=h(y)$. Repeating the same input is not a hash collision. Unequal hash values prove the keys differ; equal hash values only identify candidates that might be equal. This makes a hash function useful as a compact filter before comparing the original data.

Here is a deliberately simple example using modular arithmetic. Let $h(k)=k\mathrm{mod}16$ for nonnegative integer keys, and let a four-bucket hash table use the further bucket index $b(k)=h(k)\mathrm{mod}4$. For keys $2,6,18$, the hash values are $2,6,2$, while all three bucket indices are $2$. Thus $2$ and $18$ form a hash collision for $h$; $2$ and $6$ share a table bucket even though their full hash values differ. Always specify which function is being compared: a table collision concerns the bucket-index function, which may discard more information than the original hash function.

With separate chaining, bucket $2$ holds all three records in a linked list. A search for $18$ visits that bucket and compares the stored keys until it finds $18$; a search for $34$ visits the same bucket but rejects every stored key. A hash collision changes the search work, while key comparison preserves correctness. Storing only one record per hash value would incorrectly merge distinct keys. This is the purpose of collision handling in a hash table.^[ref]

The pigeonhole principle explains inevitability: if a hash function has only $M$ possible outputs, any $M+1$ distinct inputs contain a hash collision. In particular, a function whose domain of a function is larger than its finite codomain cannot be an injective function. This is an existence statement; it gives neither an efficient way to find the pair nor a probability for a smaller collection of keys. A particular small collection might have no hash collision at all.

For a cryptographic hash function, collision resistance asks that finding any two distinct messages with equal full digests be computationally infeasible under the specified model and resources. It does not mean that hash collisions do not exist. Preimage resistance asks a different question: given a target digest $t$, how hard is it to find a message $x$ with $h(x)=t$? The collision finder may choose both messages and their common digest; the preimage finder is given the digest in advance. These definitions distinguish two search tasks, independently of how a hash table stores records.^[ref]

A hash function is a function assigning each key in an input set $U$ a value in an output set $B$. Usually $B$ is much smaller: a long name or large integer becomes a small bucket index. Equal keys must receive equal values from the same hash function; different keys may also receive equal values. Such a hash collision means "look in the same place", and does not establish key equality. If $|U|>|B|$, the pigeonhole principle makes some collisions unavoidable.

For example, modular arithmetic gives the hash function $h(k)=k\mathrm{mod}7$, with seven bucket indices $0,\dots ,6$. Store the seven keys $0,2,3,10,11,17,24$: their values are respectively $0,2,3,3,4,3,3$. In particular, $h(3)=h(10)=3$ although $3\ne 10$. A hash table is a data structure that uses these indices to locate records. With separate chaining, each bucket holds a linked list of records, so bucket $3$ retains all four keys $3,10,17,24$. Inserting $10$ must not overwrite $3$ merely because their hash function values agree.

Searching for $10$ computes bucket $3$, then compares the actual keys until it reaches $10$. Searching for absent key $31$ reaches that same bucket and must reject every stored key. This data structure trades a search through all records for a search through one short chain, provided the hash function distributes keys adequately. A fixed hash function can perform poorly on patterned keys: $3,10,17,24$ already demonstrate the problem. A universal hash family introduces controlled randomness to limit the expected value of this extra work. Neither indexing nor a small collision probability inherently supplies encryption or message authentication; a cryptographic hash function has additional requirements such as collision resistance.

The Hessian matrix describes how the slope of a function changes in different directions. For a real-valued function $f$ with continuous second partial derivatives on an open subset of ${\mathbb{R}}^n$, it isThe symmetry of second derivatives makes $H_f$ a symmetric matrix under these hypotheses. It is also the Jacobian matrix of the gradient: near $x$, a small displacement $h$ changes $\nabla f$ by $H_f(x)h+o(\Vert h\Vert )$. Thus the gradient measures the current slope, while the Hessian measures its local variation. ^[ref]

For example, take the quadratic formIts gradient and Hessian matrix areThe only critical point is the origin. Completing the square gives $q=(x+y{)}^2+2y^2$, so the origin is a strict global minimum. The eigenvalues $4-2\sqrt{2}$ and $4+2\sqrt{2}$ are both positive, recovering the same conclusion from the positive definiteness of the Hessian. Its eigenvectors identify the rotated directions in which the quadratic form has its smallest and largest bending.

For a fixed vector $v$, restriction to a straight line gives the directional interpretationThis is the quadratic form associated with the Hessian matrix. For a unit eigenvector $v$, it equals the corresponding eigenvalue. Opposite signs therefore mean that some directions bend upwards and others downwards. The second-derivative test turns this information into a classification when the gradient vanishes.

The same object is useful for computation. Newton's method in optimization chooses a displacement $h$ by solving $H_f(x)h=-\nabla f(x)$ when the Hessian matrix is an invertible matrix; this makes the gradient of the local quadratic model vanish. For the displayed $q$, the equation gives $h=-(x,y{)}^T$, so one exact step reaches the minimum from any starting point. For a general function, a Hessian with opposite-sign eigenvalues or a large condition number need not give a useful minimizing step, and the local minimum need not be a global minimum.

The name honors Otto Hesse. ^[ref] An older geometric use is the Hessian criterion for flexes of a plane cubic, connecting a determinant of second partial derivatives with inflection points of an algebraic curve. Hesse's 1844 paper Über die Wendepuncte der Curven dritter Ordnung is an early source on that geometric problem. ^[ref]

A Hilbert space is a real or complex inner product space that is complete in the norm $\Vert v\Vert =\sqrt{⟨v,v⟩}$. Completeness means that every Cauchy sequence has a limit in the space: if its terms become arbitrarily close in this norm, they converge to an allowed vector. The inner product supplies lengths and orthogonality; completeness ensures that limiting approximation procedures do not leave the space.

Finite-dimensional Euclidean spaces are examples, but the same geometry also works for sequences and functions. In the l2 sequence space,In the L2 space on $[-1,1]$ with Lebesgue measure,These formulas use the convention linear in the first argument. Elements of the L2 space are equivalence classes of square-integrable functions agreeing almost everywhere, so zero distance really identifies the same element. A vector can therefore be a whole function, and its squared length can measure an integrated squared error.

For example, approximating $f(x)=x^2$ by $a+bx$ is a nearest-point problem in this Hilbert space. The allowed approximations form the linear span of $1,x$, and the orthogonal projection is the constant $1/3$. Its residual $x^2-1/3$ is orthogonal to both allowed directions because its integral and its inner product with $x$ vanish. The geometry therefore identifies the best approximation without searching through every pair of coefficients.

This is useful whenever a complicated vector must be represented by a tractable collection of directions. Fourier series approximate functions with orthogonal oscillations; the Parseval identity relates the sum of squared coefficients to the squared norm. Least-squares solutions approximate attainable data using a linear operator. The Hilbert projection theorem explains why a nearest element exists and is unique for a nonempty closed convex set. Distinct application settings share the same geometry of useful components and orthogonal residuals. Casey Rodriguez's MIT lectures develop these connections between Hilbert spaces, Fourier series, and nearest-point problems.^[ref]

A historical mathematical setting is David Hilbert's Grundzüge einer allgemeinen Theorie der linearen Integralgleichungen (1912). Its preface states that it reprints six communications published during 1904–1910 on linear integral equations. This provides a concrete source for the integral-equation setting associated with the name, while the abstract definition above incorporates later developments.^[ref]

Write $\alpha =r+\beta$ with an integer $r\ge 0$ and $0<\beta \le 1$, using $r=\alpha -1$ at integer $\alpha$. For $f\in C^{r,\beta }$, subtract its degree-$r$ Taylor polynomial at $x_0$. For $r\ge 1$, the integral Taylor remainder with $f^{(r)}(t)-f^{(r)}(x_0)$ is bounded using the Hölder seminorm; for $r=0$ this is exactly Hölder continuity. The resulting bound is the displayed estimate. At integer order, the convention is $C^{r,1}$; a $C^{r+1}$ function on a compact closed interval also obeys this estimate.

A complex-valued function $f:U\to \mathbb{C}$ is holomorphic on an open set $U$ when it has a complex derivative at every point of $U$. Requiring a derivative throughout a neighbourhood is much stronger than complex differentiability at a point. It forces locally convergent Taylor series and derivatives of every order, as follows from the Cauchy integral formula and Cauchy derivative formula.

To see the restriction in real coordinates, write $z=x+iy$ and $f(z)=u(x,y)+iv(x,y)$. The real and imaginary increment quotients must agree, giving the Cauchy-Riemann equationsConversely, if $u,v$ have continuous partial derivatives on $U$ and satisfy the Cauchy-Riemann equations there, then $f$ is a holomorphic function. The equations at a lone point, without a differentiability hypothesis for the real coordinate map, are insufficient. Their role is to force the Jacobian matrix to have the special formSuch a matrix represents multiplication by a complex number; it has only two free real entries. ^[ref]

For $f(z)=z^2$, $u=x^2-y^2$ and $v=2xy$, so $u_x=v_y=2x$ and $u_y=-v_x=-2y$. Directly,At $z_0=1+i$, multiplication by $2+2i$ scales lengths by its modulus $2\sqrt{2}$ and rotates by its argument $\pi /4$. A horizontal increment $h=0.01$ gives the exact displacement $0.0201+0.02i$; a vertical increment $h=0.01i$ gives $-0.0201+0.02i$. The first-order predictions $0.02+0.02i$ and $-0.02+0.02i$ are perpendicular, and the errors have modulus $10^{-4}$.

At every nonzero $z_0$, this local rotation and scaling makes $z^2$ a local conformal map. At zero, the first-order map vanishes: $r{e}^{i\theta }$ becomes $r^2{e}^{2i\theta }$, so the argument doubles and the origin is a critical point. Globally $z$ and $-z$ have the same square. Local preservation of angles therefore coexists with global folding, a useful warning when using holomorphic functions as coordinate changes.

A function is homogeneous of degree $k$ when rescaling its arguments by a common scalar $\lambda$ rescales its value by ${\lambda }^k$, whenever the arguments and that power are defined. For integer $k$ over a vector space, one can require every nonzero scalar; a homogeneous polynomial gives an example. On a domain stable under positive real rescaling, the positive-scaling version allows real $k$. Degree-one positive homogeneity is the convention used for norms and many convex functions. The Euler theorem for homogeneous functions turns this scaling law into a differential identity for a differentiable function.