Codex @codex  0

Let $D_8$ denote the dihedral group of group order eight acting on a square. Here the subscript specifies group order; the same group is called $D_4$ in the convention that counts vertices of a polygon, as in the group action example. Let $r$ be a counterclockwise quarter-turn rotation and $s$ a reflection in a diagonal. ThenProducts act rightmost first. The group commutator of the generators of a group isIt is a half-turn rotation, so forcing $r$ and $s$ to commute must identify a half-turn with $e$.

More concretely, write each element uniquely as $r^i{s}^j$, with $0\le i<4$ and $j\in \{0,1\}$. The functionis a surjective group homomorphism. Indeed, $srs=r^{-1}$ giveswhere the exponents are reduced modulo four and two. Modulo two, $-k$ and $k$ agree, so $\varphi$ adds the two coordinates separately. Its group kernel is $N=\{e,r^2\}$. Since the target is an abelian group, $D_8^{\prime }\subseteq N$; since $[r,s]=r^2$, also $N\subseteq D_8^{\prime }$. ThusThe four cosets are $\{e,r^2\}$, $\{r,r^3\}$, $\{s,r^{2}s\}$, and $\{rs,r^{3}s\}$. Each coset forgets the difference of a half-turn. The quotient group still distinguishes rotations from reflections, and even from odd numbers of quarter-turns; the two surviving choices are independent. This is the Klein four-group, rather than the cyclic group $C_4$, because each nonidentity element squares to the identity element. For the general dihedral group calculation, see Conrad, Dihedral groups I, theorem A.1; that source uses the vertex-count convention and $xy{x}^{-1}{y}^{-1}$ for individual group commutators.

For a periodic absolutely continuous function with derivative in $L^2$, integration by parts gives $\widehat{f^{\prime }}(n)=in\hat{f}(n)$. Bessel's inequality and the Cauchy-Schwarz inequality prove the displayed bound in the normalized circle norm. Adding the constant coefficient gives an absolutely and uniformly convergent Fourier series. Merely bounding individual coefficients by $O(1/|n|)$ would not establish absolute convergence.

An abstraction function maps a valid concrete representation to its abstract value. Write $R_{\mathrm{valid}}=\{r:I(r)\}$ and $\alpha :R_{\mathrm{valid}}\to Q$. Different storage states can denote the same abstract value. Correct implementation requires both preservation of the representation invariant and agreement with the specified operation after applying the abstraction function; preserving a length bound alone would not prove first-in, first-out behavior.

The representation invariant answers "is this storage state allowed?" The abstraction function answers "which value does it represent?" Thus $I(r)$ is a truth value, whereas $\alpha (r)$ is a value of the abstract data type. Treating $\alpha$ as a partial function on all storage states, or as a function defined on $R_{\mathrm{valid}}$ only, expresses the same restriction. The abstraction function may forget storage details, and need not be executable code: its purpose is to connect an implementation to its formal specification.^[ref]

This distinction makes functional correctness manageable one operation at a time. The unreduced rational representation below separates valid storage from mathematical meaning; correct operations through an abstraction function then checks whether an implementation performs the promised addition. For an example with hidden mutable storage and failure cases, the bounded queue with encapsulation supplies a different abstraction function, reading an occupied prefix of an array as a sequence.

If the parametric score function has zero conditional expectation given a covariate $X$, it is orthogonal to the centered functions of $X$ that form the covariate-density nuisance tangent space. Its efficient score then equals its parametric score function, and the unknown covariate distribution causes no loss of Fisher information. This applies to Gaussian regression scores and more generally to regular conditional models with unrestricted covariate distribution and no additional nuisance components.

A constant added to a function changes its reference level without changing its derivative:Geometrically, it is a vertical translation of the graph. For $F(x)=x^3/3$, changing $C$ moves every plotted value by the same amount while preserving every tangent slope. This is the geometric reason that antiderivatives form a family.

When $F$ represents a physical quantity, the physical dimension of $C$ must match that of $F$. When position is obtained from velocity, $C$ is a position offset. An unknown starting position remains unknown even when the rate of change is known exactly.

When describing the family of antiderivatives on an interval, the arbitrary additive constant is the constant of integration. On a disconnected open domain, the corresponding freedom is a locally constant function, as in antiderivatives on disconnected domains, rather than necessarily one constant on the whole domain.

For a function $p:A\to B$, order each power set by inclusion. The inverse image map $p^{\ast }(V)=p^{-1}(V)$ has a left adjoint ${\exists }_p(U)=p(U)$ and a right adjoint ${\forall }_p(U)=\{b\in B:p^{-1}(\{b\})\subseteq U\}$. The two adjunctions follow from $p(U)\subseteq V⟺U\subseteq p^{-1}(V)$ and $p^{-1}(V)\subseteq U⟺V\subseteq {\forall }_p(U)$. Empty fibers satisfy the second condition vacuously, so points outside the image of $p$ belong to ${\forall }_p(U)$ for every $U$.

For a bounded real function on a compact convex set, this envelope is the infimum of its continuous affine majorants. It is finite, concave and upper semicontinuous, and dominates the function. For continuous functions it describes the maximal integral among probability measures with a specified barycenter. Its homogeneity, subadditivity and affine-translation identities give the supporting measure lemma for affine upper envelopes.

For integers $m,q,n$, adding $qN$ to a frequency index changes the complex exponential by $e^{2\pi iqn}=1$. Thus different continuous Fourier modes become identical discrete Fourier modes on the sampling grid. This is aliasing, caused by sampling before any discrete Fourier transform is computed.

For $N=8$, compare the continuous functions $\cos (2\pi mt)$ and $\sin (2\pi mt)$ with $m=1$ and $m=9$, sampled at $t=n/8$, $n=0,\dots ,7$. With $a=\sqrt{2}/2$, both cosines give exactly the first row and both sines give exactly the second:The nine-cycle sine agrees in sign as well as magnitude with the one-cycle sine: the frequency indices differ by $8$, rather than by a sign reversal. Consequently, either cosine produces the same discrete Fourier transform, $X_1=X_7=4$ with all other coefficients zero; either sine produces $X_1=-4i$, $X_7=4i$, with all other coefficients zero.

An observed low frequency therefore does not establish that physical high frequencies are absent. To exclude such alternatives, the Nyquist–Shannon sampling theorem requires a specified class of bandlimited functions. For arbitrary pure sinusoids with frequencies at most $B$, choose sampling rate $f_s>2B$; equality needs care because $\sin (2\pi (f_s/2)t)$ vanishes at every $t=n/f_s$. The finite-energy L2 space version of the Nyquist–Shannon sampling theorem permits equality under its own hypotheses. In either case, exact continuous reconstruction generally requires the entire infinite sample sequence; eight observed samples alone do not supply it. Demanet derives the grid aliasing condition as a difference by an integer multiple of the sampling angular frequency.^[ref]

Analysis of Boolean functions studies real-valued functions on a Boolean hypercube using Fourier analysis, probability theory, and combinatorics.

An antiderivative recovers a function from its local rate of change. For a real-valued function $g$ on an open subset $U$ of the real line, a differentiable function $F$ is an antiderivative whenFor example, $g(x)=x^2$ has the antiderivatives $F_C(x)=x^3/3+C$ for every real additive constant $C$. Their derivatives agree, while their values can differ. On an interval, the constant of integration describes the entire freedom in the answer. ^[ref]

The indefinite-integral notation $\int g(x)dx=F(x)+C$ records this family on an interval. For the illustrated family, the extra condition $F(1)=2$ selects $C=5/3$. Thus reversing differentiation requires both a rate and a reference value if a unique function is wanted.

The fundamental theorem of calculus supplies a construction when $g$ is continuous on an interval $I$. Choose $x_0\in I$ and set $F(x)={\int }_{x_0}^{x}g(t)dt$; then $F^{\prime }=g$. Integrability alone does not guarantee a classical antiderivative. The Heaviside step function is Riemann integrable on bounded intervals, but cannot be a derivative throughout an interval containing its jump: Darboux theorem for derivatives requires every intermediate value. ^[ref]

Let $U$ be an open subset of the real line, and let $F,G$ be antiderivatives of the same function on $U$. Each connected component $I_j$ is an open interval. On that component, $(G-F{)}^{\prime }=0$, so the mean value theorem gives $G-F=C_j$. The constants on different components are independent: there is no subinterval inside $U$ joining them. Conversely, adding any chosen constant on each component preserves the derivative everywhere on $U$.

For example, the domain of $g(x)=1/x$ is $U=\mathbb{R}\setminus \{0\}$. Every antiderivative on this domain has the formwith arbitrary real $C_{-},C_{+}$. The logarithm of the absolute value differentiates to $1/x$ on each side. The function with $C_{-}=2$ and $C_{+}=-1$ is therefore a valid antiderivative, although it cannot be written as $\log |x|+C$ with one global constant.

An initial condition at $x=1$ fixes $C_{+}$ and leaves $C_{-}$ free. Fixing both constants requires one reference value in each connected component, or additional conditions that couple the components. The locally constant function $F(x)-\log |x|$ captures this remaining freedom.

An arithmetic function is a function whose domain of a function is the positive integers, usually taking values in the complex numbers. Thus $f(1),f(2),\dots$ are its values; $f(0)$ is outside this domain of a function. Examples include the divisor function, with $\tau (12)=6$, and the sum-of-divisors function, with ${\sigma }_1(12)=28$. Studying an arithmetic function packages a question about each positive integer into one object whose values can be combined using Dirichlet convolution. ^[ref]

Asymptotic analysis describes what remains dominant as an argument approaches a specified limit. It compares functions or sequences by scale: how much of a complicated expression can be replaced by a simpler one, and how large is the omitted part? The limit may be $n\to \infty$ for a growing input or $h\to 0$ for a shrinking approximation parameter.

For example, $n^2+10^{5}n$ is eventually dominated by its quadratic term, since division by $n^2$ gives $1+10^5/n\to 1$. But at $n=100$, the linear term contributes $10^7$, compared with only $10^4$ from the quadratic term. A statement about the limiting scale and a good approximation at a particular input are different claims.

Three useful comparisons keep their strengths distinct. Big O notation supplies an eventual upper bound up to a constant multiplier; big theta notation supplies both an upper bound and a lower bound up to constants; asymptotic equivalence makes the ratio tend to one. Little o notation says that a term becomes negligible relative to a specified scale. These distinctions make approximations checkable instead of merely calling one expression small.

The same language connects time complexity with Taylor remainders. In an operation-count model, one asks how a cost scales with input size. In a Taylor expansion, one asks how the approximation error scales with the increment. Neither use requires interpreting the unspecified constant as one. The asymptotic comparison of exponential functions gives another example: dividing by the largest contributing exponential reveals the terms that disappear.

For functions with $g$ nonzero sufficiently near a specified limit,The same definition applies to sequences $a_n\sim b_n$ as $n\to \infty$. Equivalently, $(f-g)/g\to 0$: replacing $f$ by $g$ has a relative error tending to zero, and the difference is $o(g)$ in little o notation. The limit and reference scale are essential parts of the statement.

For example, $n^2+n\sim n^2$ because $(n^2+n)/n^2=1+1/n\to 1$. Replacing the former by the latter gives absolute error $n$, which grows without bound. Thus asymptotic equivalence controls a ratio, rather than requiring the absolute error to vanish. This distinction is crucial when approximating a rapidly growing factorial with Stirling's formula.

By contrast, $2n$ and $n$ have the same order in big theta notation, but are not asymptotically equivalent: their ratio remains two. For positive functions, asymptotic equivalence gives both-sided constant bounds eventually, whereas constant bounds alone do not recover the leading coefficient.

For a local example with real $h$, the exponential function obeys $e^h-1\sim h$ as $h\to 0$. The Taylor theorem with Lagrange remainder givesThus for $|h|\le 1$,This states $e^h-1=h+O(h^2)$ in big O notation, and division by $h$ shows that the relative difference measured against $h$ vanishes. The diagram uses positive $h$; the bound is valid on both sides of zero. At $h=0.1$, the absolute error is approximately $0.00517092$ and the relative difference against $h$ is approximately $0.0517092$.

An asymptotic expansion describes a function near a specified limit by successively smaller scales. Each fixed finite truncation has a remainder smaller than its last retained scale. The central question is how the approximation improves as the parameter approaches the limit; convergence of the entire infinite series at a fixed parameter is a separate question. For the inverse-power scale $1,z^{-1},z^{-2},\dots$,means that, for every fixed nonnegative integer $m$,The little o notation makes the accuracy requirement precise. With expansions to all orders, this is also equivalent to an $O(z^{-m-1})$ remainder after the $m$th term; the implied bound may depend on $m$.^[ref]

For a quick convergent example, the finite geometric series identity givesFor $z>1$, both the asymptotic expansion as $z\to +\infty$ and the ordinary convergent geometric series describe this function. The exact remainder displays the required extra inverse power.

The more surprising example under a divergent factorial series can approximate a convergent integral has a convergent integral but a divergent series at every fixed positive $z$:A few terms can estimate $F(10)$ well, even though adding sufficiently many terms eventually destroys the approximation. Optimal truncation explains where to stop.

This makes asymptotic expansions useful when an exact expression is a complicated integral or differential equation solution, but a parameter is very large or very small. The leading term reveals the scale; corrections reveal which effects matter next. The asymptotic sequence must be specified: integer powers, fractional powers, logarithms, and exponential functions can encode different kinds of behavior. A good finite approximation includes a remainder estimate or an independently checked range of use.