Codex @codex  0

A computation-cost convention assigning constant cost to specified primitive operations. For exact unbounded integer arithmetic this can differ substantially from bit complexity: a multiplication of increasingly large values is one primitive operation but requires more bit operations. State which convention is used when estimating an algorithm's running time.

For a number field $K$ and an algebraic integer $\alpha \in {\mathcal{O}}_K$, the criterion isHere the absolute field norm means the field norm down to $\mathbb{Q}$; its absolute value is one. Necessity follows from $N(\alpha )N({\alpha }^{-1})=1$ with both factors integers. Conversely, multiplication by $\alpha$ on an integral basis is a matrix with integer entries and determinant $\pm 1$. Its inverse also has integer entries, and applying that inverse to $1$ gives ${\alpha }^{-1}\in {\mathcal{O}}_K$. The integrality hypothesis matters: $\alpha =(3+\sqrt{2})/(3-\sqrt{2})=(11+6\sqrt{2})/7$ has field norm one, but is not in $\mathbb{Z}[\sqrt{2}]$.

In $\mathbb{Z}[\sqrt{2}]$, the criterion becomes $a^2-2b^2=\pm 1$. Thus $(1+\sqrt{2}{)}^{-1}=\sqrt{2}-1$ and $(3+2\sqrt{2}{)}^{-1}=3-2\sqrt{2}$ are again algebraic integers. These units produce infinite families of solutions to the Pell equation.

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]

The unit $\epsilon =1+\sqrt{2}$ has field norm minus one and is the least unit greater than one in the field embedding sending $\sqrt{2}$ to its positive value. It is a fundamental unit. The Dirichlet unit theorem therefore gives

Writing ${\epsilon }^n=a_n+b_n\sqrt{2}$, direct multiplication givesFor $n=0,1,2,3,4$, the pairs $(a_n,b_n)$ are $(1,0),(1,1),(3,2),(7,5),(17,12)$, andIn particular, $\eta ={\epsilon }^2=3+2\sqrt{2}$ has field norm one. Its powers start $1$, $3+2\sqrt{2}$, $17+12\sqrt{2}$, $99+70\sqrt{2}$, and give solutions $(a,b)$ of the Pell equation $a^2-2b^2=1$. This turns finding one unit into generating infinitely many exact integer solutions.

The two field embeddings show a striking balance:For positive $n$, one value grows while the other approaches zero, and their product stays $(-1{)}^n$. Taking logarithms of their absolute values converts this multiplication into equally spaced points, the simplest example of the logarithmic embedding of number field units.^[ref]

Consider an original abstract data type whose values are rational numbers. Store an ordered pair $(n,d)$ of integers, interpreted as a numerator and a denominator. Use exact, unbounded integer arithmetic in this model. The storage space, representation invariant and abstraction function areThe representation invariant does not require a positive denominator or a reduced fraction. Consequently $(1,2)$, $(2,4)$ and $(-1,-2)$ are three different concrete states with the same abstract rational number $1/2$. Similarly, $(0,1)$ and $(0,-3)$ both represent zero. The abstraction function is a surjection: every rational number has an integer numerator and a nonzero integer denominator, so every abstract value has a representation.

Both $(1,0)$ and $(0,0)$ violate the representation invariant; neither has a value under this abstraction function. By contrast, $(2,4)$ is completely valid. Simplifying it to the reduced fraction $1/2$ may be a useful implementation choice, but is not a requirement of this representation. Strengthening the representation invariant to require a positive denominator and a greatest common divisor of one would choose a unique stored representative for each rational number; every constructor and operation would then need to establish that stronger condition.

Equality of abstract values is therefore different from equality of stored ordered pairs. For valid $(a,b)$ and $(c,d)$,This defines an equivalence relation on $R_{\mathrm{valid}}$: each equivalence class contains all representations of one rational number. An API equality operation can compare these cross-products using exact integer arithmetic. Comparing the two fields individually would incorrectly declare $(1,2)$ and $(2,4)$ unequal as rational numbers. The general reason is that an abstraction function may map several concrete values to one abstract value.^[ref]

For a $w$-bit unsigned integer type without padding, C programming language arithmetic on that type reduces results modulo $2^w$. In particular, subtracting two uint32_t timestamps gives their modular difference when that subtraction is evaluated in the 32-bit unsigned type. Integer promotions must be checked for narrower types or unusual implementations. Signed integer overflow has different rules and must not be treated as the same operation.^[ref]

If an element $w$ of the module ${\prod }_{j\in J}\mathbb{Z}$ is divisible by every power of two within that module, then every coordinate $w(j)$ is an integer divisible by every power of two. A nonzero integer $a$ cannot be divisible by $2^i>|a|$, so each coordinate is zero and $w=0$. This argument applies to any index set $J$ and to powers of any fixed integer $b$ with $|b|>1$.

For coefficients $b_n$ supported on an interval of $H$ consecutive integers, set $B=\sum b_n$ and $B_p(a)={\sum }_{n\equiv a(\mathrm{mod}p)}{b}_n$. ThenThe orthogonality of roots of unity gives $p{\sum }_a|B_p(a)-B/p{|}^2={\sum }_{r=1}^{p-1}|{\sum }_n{b}_{n}e(rn/p){|}^2$. The distinct fractions $r/p$ have circular spacing at least $Q^{-2}$; now apply the exponential-sum large sieve.

The Von Mangoldt function assigns a natural logarithm weight to each positive power of a prime number. For a positive integer $n$,Here and throughout the Chebyshev functions, $\log$ means the natural logarithm. In particular, $\Lambda (1)=0$: the exponent must be positive, even though the convention in prime power allows exponent zero. The support of a function of $\Lambda$ therefore consists precisely of the prime powers greater than one. ^[ref]

For example, $\Lambda (2)=\Lambda (4)=\Lambda (8)=\log 2$ and $\Lambda (3)=\Lambda (9)=\log 3$, whereas $\Lambda (6)=\Lambda (12)=0$. A composite number can have a nonzero weight: $8$ has just one distinct prime factor. But $12=2^2\cdot 3$ has two distinct prime factors, so its weight is zero. At $p^k$ the weight is $\log p$, not $\log (p^k)=k\log p$. This choice lets successive powers record successive copies of the same prime factor in the Von Mangoldt divisor identity.

The Von Mangoldt function is useful because it connects two views of the prime numbers: the prime factorization of an individual integer, through a divisor sum, and the accumulated weights below a cutoff, through the Second Chebyshev function. The latter turns questions about the distribution of prime numbers into questions about a partial sum of an arithmetic function.

The waveguide cutoff frequency separates oscillatory axial propagation from exponential decay for a particular normal mode. For the vacuum-filled rectangular electromagnetic waveguide, the dispersion relation isFor a transverse electric mode of a rectangular waveguide, $m,n$ are nonnegative integers but not both zero. For a mode with $B_z=0$ and nonzero $E_z$, both indices must be positive. The lowest cutoff for $a>b$ is consequently ${\omega }_{10}=\pi c/a$, or ordinary frequency $f_c=c/(2a)$.

A square cross-section instead gives equal ${\mathrm{TE}}_{10}$ and ${\mathrm{TE}}_{01}$ cutoffs. The absence of a transverse electromagnetic mode is specific to this hollow pipe, rather than all electromagnetic waveguides.^[ref]

For $\omega >{\omega }_{mn}$, choose real $\beta >0$ for propagation toward $+z$. For $0<\omega <{\omega }_{mn}$, a field decaying into a semi-infinite guide hasA finite section can contain both growing and decaying axial solutions set by its two ends; the single decaying solution is not a complete finite-section transmission calculation. At exact cutoff $\beta =0$, the two axial solutions become a constant and a linear function of $z$: there is no finite axial wavelength for a traveling sinusoid.

In the chosen $a=30\mathrm{mm}$ guide at $f=0.8f_c=3.99723277\mathrm{GHz}$, the ${\mathrm{TE}}_{10}$ branch has $\alpha =20\pi {\mathrm{m}}^{-1}$. Its amplitude decay length is $1/\alpha \simeq 15.9155\mathrm{mm}$; after $50\mathrm{mm}$, its normalized wave amplitude is $e^{-\pi }\simeq 0.0432139$. This is geometric evanescence even with ideal walls, not Joule heating. A single decaying branch has zero cycle-averaged axial Poynting vector: substituting $\beta =i\alpha$ makes $B_x$ a quarter-cycle out of phase with $E_y$. Coupling across a finite section requires the complete boundary-value solution.

A weakly linear partial function on the real numbers has a domain closed under rational scalar multiplication and addition, and it preserves addition on that domain. A nonempty domain is a vector space over the rational numbers, and additivity implies rational homogeneity of an additive function by integer multiplication and division. The empty function also satisfies the defining conditions vacuously. This terminology does not assert homogeneity under arbitrary real scalars.

A base case and a decreasing natural number measure work together. Check that every invocation satisfies its precondition, each base case finishes with the correct output, and every other invocation makes finitely many recursive calls with strictly smaller measure. All local work must also terminate. By well-founded induction, the children finish, so their caller finishes; if their answers are correct and the combination rule preserves the postcondition, the caller is correct too. This proves total correctness, not just correctness conditional on return.

Strict decrease without a lower bound is insufficient: subtracting one forever from a negative integer never reaches zero. Even a positive real-valued measure can decrease indefinitely, as $1,1/2,1/4,\dots$ shows. A well-founded relation rules out that descent. In structural recursion, a proper child subtree of a finite binary tree supplies progress without numeric arguments. The proof obligation is the relation between parent and child instances, together with terminating local work and complete base cases.

For an integer $n>1$, Wilson's theorem characterizes prime numbers by a factorial:The right side is an integer congruence, so the least nonnegative remainder is $n-1$. For example, $4!=24\equiv 4(\mathrm{mod}5)$ certifies that five is a prime number, whereas $5!=120\equiv 0(\mathrm{mod}6)$ rules out six. ^[ref]

For an odd prime number $p$, each nonzero congruence class has a unique modular multiplicative inverse. Pair each class with its inverse: each distinct pair contributes one. A class is its own inverse exactly when $a^2\equiv 1(\mathrm{mod}p)$; since $p\mid (a-1)(a+1)$, Euclid's lemma leaves only $a\equiv \pm 1$. Their product is $-1$. The prime number two needs a separate check: $1!\equiv -1(\mathrm{mod}2)$. Conversely, a proper divisor $1<d<n$ divides both $n$ and $(n-1)!$, so the displayed integer congruence would force $d\mid 1$, a contradiction. ^[ref]

The composite numbers have an even sharper pattern: $(n-1)!\equiv 0(\mathrm{mod}n)$ for every composite number $n>4$, but $3!=6\equiv 2(\mathrm{mod}4)$. To check the zero claim, write $n=ab$ with $1<a\le b<n$. If $a<b$, both occur as different factors in the factorial. If $a=b\ge 3$, the different factors $a$ and $2a$ both occur since $2a<a^2=n$, and their product is divisible by $n$. The only excluded case is $a=b=2$. Thus four is an exception to the zero pattern, but still fails Wilson's theorem: its required remainder would be three.

This is an exact primality testing criterion, but direct evaluation is expensive: even reducing modulo $n$ after every multiplication still takes a number of multiplications proportional to $n$, which grows exponentially with the number of binary digits of $n$. The problem is not merely storing a huge factorial. The more useful role of Wilson's theorem is simplifying factorial expressions in modular arithmetic. For instance, if $p>2$ is a prime number, then $(p-1)(p-2)!\equiv -1(\mathrm{mod}p)$ gives $(p-2)!\equiv 1(\mathrm{mod}p)$ by a modular multiplicative inverse.

The winding number records how many net turns a closed piecewise smooth curve makes around a chosen point $w$. Counterclockwise turns contribute positively, clockwise turns negatively. It measures a traversal, including repeated visits; a drawing of the curve's outline alone can lose that information. For a closed curve $\gamma$ avoiding $w$,Equivalently, continuously follow an argument of $\gamma (t)-w$ along one journey and divide its total change by $2\pi$. The start and endpoint agree as complex numbers, so the change is an integer number of full turns. The principal argument at the endpoints cannot retain those turns; a continuous choice along the parametrized path can.^[ref]

For $\gamma (t)=e^{it}$, $0\le t\le 2\pi$, the winding number about zero is one. Traversing the same unit circle twice makes it two; reversing its orientation of a contour makes it negative. The winding number about $w=2$ is zero: the same journey now stays to one side of the point being measured. Joining one counterclockwise loop and one clockwise loop around zero gives net winding number zero even though both loops encircle zero.

The winding number does not change during a homotopy of closed curves avoiding $w$. This is why it is useful: complicated curves can often be deformed to simple ones whose count is obvious. The argument principle transfers that robust geometric integer to a count of zeros of a function and poles. The example in boundary sampling can miss winding shows why finite samples of a curve need control between samples before they can certify the same winding number.

The word length is the cost of building a group element from the allowed generators of a group. For a symmetric generating set of a group $S$ of a group $G$, defineThe empty word over an alphabet represents the identity element and has length zero. A representative with this least number of letters labels a shortest graph path from $1$ to $g$ in the Cayley graph. Thus word length minimizes over all representatives, rather than counting the letters in whichever expression we happened to write down.^[ref]

For the additive integers with $S=\{-1,1\}$, the expression $1+1-1$ has three letters but represents $1$, whose word length is one. With $T=\{-2,-1,1,2\}$, the integer $5$ has word length three, realized by $2+2+1$. The Cayley graphs of the integers visualize why these are minimal. A freely reduced word is always shortest in a free group with its free generators and their inverses; free reduction alone need not give a shortest representative in a general group.

Concatenating representatives and reversing their letters with inverse elements giveThese make word length a length function. A finite $S$ gives finite word metric balls, since only finitely many words over an alphabet have length at most a fixed radius. The definition itself also works for infinite symmetric generating sets of a group; the bounded-metric example in equivalence of finite word metrics shows what finiteness adds.

The additive group ${\mathbb{Z}}^2$ gives a useful way to see what a word metric measures. Let $e_1=(1,0)$ and $e_2=(0,1)$, and choose the four-move generating set of a group $S=\{\pm e_1,\pm e_2\}$. Its Cayley graph is the square lattice. Each move changes exactly one coordinate by one, so the word length is the L1 norm, and the word metric is Manhattan distance:At least this many moves are necessary, and moving horizontally then vertically attains the bound. Bridson gives this square lattice as a basic Cayley graph example.^[ref]

Now allow all eight neighbouring lattice points as moves:Each coordinate changes by at most one per move. Use diagonal moves until the smaller displacement is exhausted, then use axis moves: the resulting word length is the maximum norm, and the word metric is Chebyshev distance. From $(0,0)$ to $(2,3)$, an $S$-route has five steps, while the $T$-route $(0,0),(1,1),(2,2),(2,3)$ has three.

The closed word metric balls $B_S(0,r)=\{v\in {\mathbb{Z}}^2:d_S(0,v)\le r\}$ consist of lattice points inside a diamond for $S$, and inside an axis-aligned square for $T$. For every nonnegative integer radius $r$,The diamond has $4k$ lattice points at word length $k>0$; the square has $2r+1$ choices for each coordinate. At radius three the counts are $25$ and $49$. These are discrete closed balls for Manhattan distance and Chebyshev distance; an Euclidean distance bound would instead select lattice points inside a Euclidean disk.

An operating-system process's working set is the set of distinct memory pages used in a declared recent window. Here the window counts memory references, not clock time: let $r_i$ identify the memory page accessed by the $i$th memory reference, and let the positive integer $\Delta$ be the window length. Immediately after reference $t$,Repeated memory references to the same memory page contribute only one set element. The working set size is the cardinality $|W(t,\Delta )|$. This recent footprint estimates current demand; it cannot guarantee which memory pages future memory references will need. The resident set instead records which memory pages are actually present in computer memory.

For the 20-reference sequence in memory thrashing and $\Delta =4$, the successive working sets begin $\{1\}$, $\{1,2\}$, $\{1,2,3\}$ and $\{1,2,3,4\}$. At $t=5$, the window is references 2–5, namely $2,3,4,1$, so $W(5,4)=\{1,2,3,4\}$ again. Every later four-reference window contains all four memory pages. Under three-page frame LRU replacement, however, the resident set at $t=5$ is $\{1,3,4\}$: page 2 was evicted. Consequently the working set size is four even though only three memory pages are resident. Under four-page frame LRU replacement, the resident set contains the complete working set after reference 4.

Window choice matters: on this same sequence, $\Delta =2$ reports only two distinct memory pages after reference 2, despite the recurring four-page cycle. A short window forgets useful memory pages sooner; a long window retains evidence from older phases. Enlarging the window can only enlarge or preserve the working set at fixed $t$, because the shorter window is contained in the longer one. No single window is best for every workload.

For a concrete multiprogramming budget, suppose three operating-system processes each have a four-page working set, no shared page frames, and only eight page frames are available for their data. Their combined demand is 12 page frames; all three working sets cannot be resident together. Letting two operating-system processes run while the third waits makes their eight-page demand fit in this simplified model. Real budgets also reserve computer memory for the operating system and other uses; shared memory pages must not be counted repeatedly as different physical copies.

Peter J. Denning's ^[ref] formalized the working set using recent process execution time, rather than this article's reference count. Its central insight connected memory demand to process scheduling: deciding which operating-system processes run also decides which working sets need room. Temporal locality makes recent use informative, without making it a promise about the future. The beautiful distinction is between a large possible address space and the smaller footprint of the current activity.

A Young tableau is a filling of a Young diagram with entries, typically positive integers. The shape is the partition of an integer giving its row lengths. We draw Young tableaux in the English convention of Young diagram, with left-aligned rows arranged from top to bottom. A filling need not obey increasing conditions unless these are specified: standard Young tableaux use each of $1,\dots ,n$ exactly once and strictly increase along rows and down columns; Semistandard Young tableaux permit repetitions and require weakly increasing rows and strictly increasing columns.

In the constructions for a symmetric group involving Young symmetrizers, tabloids, and polytabloids, an unqualified numbered Young tableau means a bijective filling by $1,\dots ,n$, with no increasing condition imposed. This narrower convention is compatible with the broader use needed for Semistandard Young tableaux. Historically, Young's work connected these fillings to representation theory of the symmetric group; in particular, the equality between standard Young tableau counts and irreducible representation degrees over the complex numbers predates the modern hook-length formula. See Stanley's Algebraic Combinatorics, historical notes to Chapter 8.

Let $X$ have survival function $\mathbb{P}(X\ge x)=x^{-s}$ for $x\ge 1$, with $s>1$. Its expected value is $s/(s-1)$. The tail-sum formula for expectation givesThe absolutely continuous probability distribution gives zero mass to the integers, so $\lceil X\rceil =\lfloor X\rfloor +1$ almost surely and $\mathbb{E}[\lceil X\rceil ]=\zeta (s)+1$. Taking expectations of $\lfloor X\rfloor \le X\le \lceil X\rceil$ gives $\zeta (s)\le s/(s-1)\le \zeta (s)+1$, which rearranges to the displayed bounds on the Riemann zeta function. Finiteness is justified by $\lfloor X\rfloor \le X$ and $\lceil X\rceil \le X+1$.

For a real exponent $s>1$ and a positive integer $N$, the series truncation error in the defining Riemann zeta function series isThe integral comparison for the positive decreasing function $x^{-s}$ gives the explicit boundsOn each unit interval, the area under $x^{-s}$ lies between its endpoint heights. Summing from the first omitted term gives the lower integral from $N+1$ to infinity and the upper integral from $N$ to infinity. This uses positivity and monotonicity, not an assumption that the last computed term equals the remaining error.

At $N=10$, the bounds are $1/11\le R_{10}(2)\le 1/10$, whereas $1/(3\cdot 11^3)\le R_{10}(4)\le 1/(3\cdot 10^3)$. The errors above fit both intervals. Merely looking at the eleventh term would give $1/121\approx 0.008264$ for squares, far smaller than the actual remaining $0.095166$.

For a chosen absolute error target $\epsilon >0$, the sufficient condition is $N\ge ((s-1)\epsilon {)}^{-1/(s-1)}$, rounded upward to an integer. Thus $\epsilon =10^{-4}$ requires $N=10000$ by this bound for squares but only $N=15$ for fourth powers. This is a guarantee from an upper bound, not a claim that those are the smallest successful term counts.