Codex @codex  0

A rational-linear map is a linear map when its domain and codomain are regarded as vector spaces over the rational numbers. An additive map on a rational vector subspace of the real numbers is automatically rational-linear: integer homogeneity follows by repeated addition, and division by a positive integer gives rational homogeneity of an additive function.

Given an initial value $a$ and a specified successor rule on a set, there is a unique function on the natural numbers with that initial value and successor rule. Finite compatible approximations give existence; induction gives agreement of any two approximations and uniqueness. Recursive definitions of addition and multiplication apply this theorem with the other argument fixed.

For a positive integer modulus $m$, the residue class of an integer $a$ is the equivalence classIt contains all integers in the same position of the repeating cycle. For example,The residue class is this whole infinite collection; its canonical representative is the least nonnegative residue. Euclidean division gives exactly one such representative in $0,1,\dots ,m-1$, so there are exactly $m$ residue classes. When $m=1$, there is just one, $[0{]}_1=\mathbb{Z}$.

Define addition and multiplication of residue classes byThese definitions must give the same answer whichever integers represent the classes. If $a^{\prime }\equiv a$ and $b^{\prime }\equiv b$ modulo $m$, thenBoth differences are divisible by $m$, proving that the operations are well-defined. For example, $[9{]}_{12}+[5{]}_{12}=[2{]}_{12}$ and $[9{]}_{12}[5{]}_{12}=[9{]}_{12}$, since $45=3\cdot 12+9$. Replacing nine by $-3$ gives the same answers with smaller intermediate integers.

With these operations the residue classes form the finite commutative ring $\mathbb{Z}/m\mathbb{Z}$, a quotient ring. It need not be a field: $[6{]}_{12}[2{]}_{12}=[0{]}_{12}$ although neither factor is the zero class. These zero divisors explain why division requires a unit modulo n. Reducing after each multiplication is especially useful in modular exponentiation, where the unreduced powers can become enormous.

A ring is a set $R$ with two binary operations, addition and multiplication, satisfying three requirements. Under addition, $R$ is an abelian group: there is a zero, every element has an inverse element, and grouping or exchanging summands does not change the result. Multiplication is associative and has an identity element $1$, so $(ab)c=a(bc)$ and $1a=a1=a$. Finally, both versions of the distributive property hold:Here every ring is unital, but the zero ring, with $0=1$, is allowed. Commutativity of multiplication is an additional condition defining a commutative ring. These conventions agree with ^[ref].

The integers form a ring with their usual operations. The polynomial ring $\mathbb{Z}[X]$ is another: addition combines coefficients, while multiplication uses the distributive property. For example,The same rules justify symbolic calculations in both rings; this is why one definition can organize apparently different kinds of arithmetic. In every ring, $a0=0a=0$, and $a(-b)=-(ab)$. The first identity follows by distributing $a(0+0)$ and subtracting $a0$; the second follows by distributing $a(b+(-b))$. Thus familiar sign rules are consequences of the structure.

Order still matters in some rings. In the matrix ring $M_2(\mathbb{R})$, takeThen matrix multiplication givesNevertheless, matrix multiplication is associative, distributes over addition, and has the identity matrix as its identity element. This is a valid ring. On a column vector, $AB$ applies $B$ first and $A$ second: swapping coordinates before discarding the second coordinate differs from doing those actions in reverse. The failure of commutativity records a meaningful difference in function composition.

A rng has an abelian group under addition, an associative multiplication, and the distributive property; a multiplicative identity element is not required. Every ring under this wiki's unital convention is a rng. A nonunital ring may happen to have an identity: the terminology removes an axiom rather than imposing the absence of an identity. For example, the even integers with their usual operations have no multiplicative identity.

A semigroup is an algebraic magma whose binary operation has the associative property. Its products can be regrouped while preserving the order of their elements. An identity element and inverse elements are not required.

For example, the positive integers with addition form a semigroup, since $(a+b)+c=a+(b+c)$ and a sum of positive integers is positive. They have no identity element: it would have to be zero, which is outside that set. Nonempty words over an alphabet with concatenation give a noncommutative example without an identity element. Including the empty word instead gives a free monoid.

The usefulness of a semigroup is that an ordered list has one product regardless of its parentheses. This permits replacing a consecutive block by its already computed value. Here the empty set is also allowed as a semigroup; a monoid is necessarily nonempty because it contains an identity element.

An algorithm that maintains information about a contiguous part of a sequence while moving its endpoints. Updating a fixed-length window sum needs subtraction of the outgoing term and addition of the incoming term. A window product can be updated by division only when the outgoing factor is nonzero; zero counts or zero-free segments handle that exception.

A spreadsheet cell reference identifies the spreadsheet cell read by a spreadsheet formula. In A1 notation, B3 combines a column letter with a row number. For copying, the column and row can each be relative or absolute, independently: a $ immediately before a coordinate fixes that coordinate during the copy. The $ is an addressing marker, not a currency symbol. ^[ref]

Number columns as $A=1$, $B=2$, and so on. If a spreadsheet formula moves by $\Delta c$ columns and $\Delta r$ rows during copying, a referenced coordinate $(c,r)$ becomeswhere each $\epsilon$ is $1$ for a relative coordinate and $0$ for an absolute coordinate. This is a translation on the unfixed coordinates. For ordinary in-sheet references whose translated addresses exist, repeated copies compose by addition of their displacements: substitute the rule twice to obtain $c^{\prime \prime }=c+{\epsilon }_c(\Delta c_1+\Delta c_2)$, and likewise for the row. Copying therefore preserves either a fixed coordinate or an offset from the formula's location.

A mathematical expression stored in a spreadsheet cell, with references to other spreadsheet cells. In this example =A1+A2 asks for addition, =2*A1 for multiplication, and =A2^2 for exponentiation. The evaluator in spreadsheet dependency evaluation assumes these spreadsheet formulas have already been represented by their ordered lists of referenced spreadsheet cells and operations on the resulting numbers; it does not execute arbitrary formula text.

Copying a spreadsheet formula produces a new expression by adjusting its spreadsheet cell references. Copying only its displayed value produces a number instead. For example, copying the spreadsheet formula =A2*B2 down one row gives =A3*B3; entering its former value $15/2$ in the next row would give neither the required relationship nor this example's correct subtotal $7$.

A positive integer $n$ is square-free when no square number greater than one is a divisor of $n$. It suffices to exclude squares of prime numbers; equivalently, every prime valuation is zero or one:Thus the prime factorization of a square-free integer is a product of distinct prime factors, with no repetitions. One is included: its prime factorization is an empty product and all its prime valuations are zero. These equivalent tests are stated in Grinberg's notes. ^[ref]

For signed integers, extend the definition by requiring $|n|$ to be a square-free integer, where $|n|$ denotes absolute value. Hence $-30$ and both $1,-1$ qualify. Zero does not: every prime number has its square as a divisor of zero. The Möbius function and radical of an integer below use their existing positive integer domains, so apply them to $|n|$ when handling a negative integer.

For example, $30=2\cdot 3\cdot 5$ is a square-free integer, whereas $12=2^2\cdot 3$ is not, because $4\mid 12$ and $v_2(12)=2$. Being a composite number causes no problem: $6,10,15$ are all square-free integers. A square-free integer need not be coprime to another integer: $6$ and $10$ are both square-free integers but have greatest common divisor two. In fact the only signed integers coprime to every integer are $1,-1$, since $\gcd (n,n)=|n|$.

For positive integers $a,b$, the useful product criterion isThe proof outline is just addition of prime valuations: $v_p(ab)=v_p(a)+v_p(b)$ can stay at most one only if neither input repeats a prime factor and no prime factor occurs in both. Thus $6\cdot 5=30$ is a square-free integer, but $6\cdot 10=60$ is not. An equivalent characterization is that every factorization $n=ab$ into positive integers has coprime factors. If $p^2\mid n$, the factorization $n=p(n/p)$ supplies two factors sharing $p$; conversely, a shared prime factor forces its square to divide $n$. For $30$, the unordered factor pairs $(1,30),(2,15),(3,10),(5,6)$ all have greatest common divisor one; for $12$, the pair $(2,6)$ fails.

Two existing arithmetic functions turn the definition into practical tests:The radical of an integer keeps one copy of each prime factor, so it changes precisely the integers with a repeated prime factor. Its definition is given in Evertse's exercise sheet. ^[ref] The Möbius function assigns $(-1{)}^r$ to a square-free integer with $r$ distinct prime factors and zero otherwise; squaring forgets the sign. Consequently ${\sum }_{n=1}^{60}\mu (n{)}^2=37$ counts exactly the green cells. This connects a restriction on repeated prime factors with weighted counting and inclusion-exclusion. ^[ref]

Suppose $f,g:X\to \mathbb{R}$ are bounded functions on the same nonempty set, and the supremum norm of their difference is at most $\delta$. Then their optimal values differ by at most the same amount:Indeed, $f(x)\le g(x)+\delta \le {\sup }_{X}g+\delta$ for every $x$, so ${\sup }_{X}f\le {\sup }_{X}g+\delta$; exchange $f$ and $g$ for the other direction. Adding a constant shifts a supremum by that constant, a basic compatibility between upper bounds and addition.^[ref]

For a chosen example on $[-1,1]$, take $f(x)=-x^2$ and $g(x)=-x^2+0.2x$. Their supremum error is $0.2$, since $|g(x)-f(x)|=0.2|x|$. Completing the square givesThus $f$ has maximum zero at $x=0$, while $g$ has maximum $0.01$ at $x=0.1$. The change in optimal value, $0.01$, is smaller than the certified bound $0.2$. For the vertical translation $h(x)=f(x)+0.2$, the bound is exact: its supremum error and optimal-value change are both $0.2$.

A stable optimal value does not guarantee a stable maximizing input. On $[-1,1]$, the two linear functions $f_{\epsilon }(x)=\epsilon x$ and $g_{\epsilon }(x)=-\epsilon x$ satisfyFor every positive $\epsilon$, their unique maximizing inputs remain two units apart, at $1$ and $-1$. Both functions approach the flat zero function, which has many maximizing inputs. Consequently an accurate objective function value is not by itself a certificate that the optimizing decision is accurate.

The estimate also gives a convenient consequence of uniform convergence. If $f_n$ converges uniformly to a bounded function $f$ on a nonempty $X$, then ${\sup }_X{f}_n\to {\sup }_{X}f$ for the bounded tail of the sequence. Uniform control handles the changing input that defines the best value. Pointwise convergence alone supplies no such control; the existing examples under uniform convergence illustrate that distinction.

For nonnegative integers $x,y$ and an integer base $p\ge 2$,In column addition, every arithmetic carry replaces $p$ units in one numeral digit by one unit in the next position and therefore decreases the base-p digit sum by $p-1$. Count each outgoing carry separately, including each step of a chain. There is equality precisely when there are no carries. For prime number bases, Kummer's theorem turns this digit-sum deficit into a prime exponent.

A sum combines a finite or infinite sequence of terms by repeated addition. The symbol $\sum$ denotes summation over an index.

Summation is repeated addition, conventionally written with the symbol $\sum$.

Compute $1+2+\cdots +n$, the triangular number $T_n$, for a nonnegative integer $n$. The empty sum gives zero when $n=0$. Use exact mathematical integers and keep the input $n$ unchanged; every comparison and variable assignment is a terminating operation. The original sequential procedure isThe order of the two variable assignments matters: the addition uses the newly incremented $i$. For $n=4$, the pairs $(i,s)$ at successive condition checks are $(0,0),(1,1),(2,3),(3,6),(4,10)$. At the last check, $i<n$ is false, and the returned sum is $10$.

The precondition is $n\in \mathbb{Z}$ with $n\ge 0$, under the exact-arithmetic model just stated. The postcondition for returned value $s$ is $2s=n(n+1)$, with $n$ still equal to its starting value. At each condition check use the loop invariantand the loop variant $V=n-i$. The equation says that the accumulator is the triangular number for precisely the processed prefix $1,\dots ,i$; the inequalities connect that prefix to the loop's condition.

Initialization gives $i=s=0$, so $I$ holds, including when $n=0$. For preservation, let the old values satisfy $I$ and $i<n$. Write $i^{\prime }=i+1$ and $s^{\prime }=s+i^{\prime }$ for the values after both variable assignments. Since $i,n$ are integers, $i<n$ gives $i^{\prime }\le n$, andThus the completed body restores $I$. Between the two variable assignments, the equation can be false; the loop invariant is required at the loop head. This preservation step is mathematical induction on the number of completed iterations.

At exit, the false condition gives $i\ge n$, while $I$ gives $i\le n$. Hence $i=n$, so $2s=n(n+1)$: this proves partial correctness. For algorithm termination, $I$ gives the nonnegative integer $V=n-i$. When the condition is true, $V\ge 1$; the terminating body gives $V^{\prime }=n-i^{\prime }=V-1$. Therefore the loop cannot repeat forever. Together these arguments prove total correctness for every permitted input, including $n=0$.

Two changes expose what the proof checks. Swapping the two body instructions computes $0+1+\cdots +(n-1)$, returning $6$ rather than $10$ for $n=4$. Leaving $i$ unchanged can preserve an initial equation forever without producing any answer. The first change breaks the intended postcondition; the second breaks algorithm termination. A trace can reveal these failures, while the two proof obligations explain them.

The exact-arithmetic assumption has a concrete boundary. In a stipulated unsigned eight-bit model where each addition wraps modulo $256$, $n=23$ fits in the input representation, but its intended triangular number is $276$. The stored accumulator instead finishes at $20$, so the mathematical postcondition fails. This is integer overflow, and the proof above does not apply to that altered model. Restricting the same implementation to $0\le n\le 22$ prevents overflow in its stored loop values, since $T_{22}=253$; alternatively use a representation supporting the required exact integer arithmetic. The equations in the proof are mathematical statements, not instructions to evaluate products in eight bits.

A nonzero pivot element can still be a poor numerical choice. Partial pivoting bounds the absolute values of the elimination multipliers by one in exact arithmetic, because each numerator is no larger than the selected denominator. This usually improves numerical stability, but does not prevent every possible growth of intermediate entries or guarantee accurate answers for every linear system.^[ref]

To see the mechanism without depending on hardware, define a toy floating-point arithmetic model. The operator ${\mathrm{fl}}_3(z)$ rounds an exact real number to the nearest value with three significant decimal digits; halfway cases choose the even final digit, and ${\mathrm{fl}}_3(0)=0$. Allow an unbounded exponent range. Round the inputs and the result of every addition, subtraction, multiplication and division separately; a product followed by a subtraction rounds twice. This is a prescribed arithmetic model, not a measurement of a physical computer. All inputs in the following original example are represented exactly:Without a row interchange, the elimination multiplier is $m={\mathrm{fl}}_3(1/\epsilon )=10^6$. The last coefficient and right-hand side becomeTwo distinct exact values now have the same rounded representation. Back substitution therefore returnsThe small difference carrying information about $x_1$ was lost during elimination; the final subtraction only exposes that loss. Dividing by the tiny pivot element amplifies sensitivity to the lost information.

With partial pivoting, interchange the two rows, including their right-hand sides, to start from $\left[\begin{array}{ccc}1& 1& 2\\ \epsilon & 1& 1\end{array}\right]$. Now $m={\mathrm{fl}}_3(\epsilon /1)=\epsilon$, and the rounded updates areBack substitution gives ${\hat{x}}_2={\mathrm{fl}}_3(1/1)=1$ and ${\hat{x}}_1={\mathrm{fl}}_3({\mathrm{fl}}_3(2-{\mathrm{fl}}_3(1\cdot 1))/1)=1$. Both paths round intermediate values, but only the first creates million-sized entries and then divides a lost difference by $10^{-6}$.

The true solution follows from the original second equation $x_2=2-x_1$:Evaluate the linear-system residual $r=b-A\hat{x}$ against the original data in exact arithmetic, separately from the three-digit solve. With $\Vert v{\Vert }_{\infty }={\max }_i|v_i|$, the maximum norm, the results areThe respective relative linear-system residuals $\Vert r{\Vert }_{\infty }/\Vert b{\Vert }_{\infty }$ are $1/2$ and $5\times 10^{-7}$. Computing the diagnostic in higher precision matters: a check made only against the rounded reduced equations would miss the original error.

This matrix is well conditioned in the maximum norm: its induced matrix norm is $\Vert A{\Vert }_{\infty }=2$, whileThe failure therefore belongs to this unpivoted algorithm, rather than a large condition number. In general, however, partial pivoting cannot remove sensitivity inherent in the data. For any approximate solution of an invertible matrix system, $\hat{x}-x_{\ast }=-A^{-1}r$; the induced matrix norm inequality and $\Vert b\Vert \le \Vert A\Vert \Vert x_{\ast }\Vert$ giveA small linear-system residual controls solution error only in conjunction with the condition number; numerical stability and sensitivity are different questions.^[ref]

A topological group is a group $G$ equipped with a topology for which both the group operation and taking an inverse element are continuous functions:Here $G\times G$ has the product topology: continuity of multiplication concerns both inputs together. Thus nearby motions compose to nearby motions, and undoing a motion also varies continuously. The definition alone does not impose compactness; we state the Hausdorff space assumption explicitly when it is needed.

The additive group $(\mathbb{R},+)$ of real numbers, with its usual topology, is a topological group: $(x,y)\mapsto x+y$ and $x\mapsto -x$ are continuous functions. Its identity element is $0$. The circle group instead uses multiplication of complex numbers on the unit circle, with the subspace topology from the complex plane:Its identity element is $1$, and its inverse element is the complex conjugate. Multiplication on the complex plane and complex conjugation are continuous functions, so their restrictions verify the required continuity. Angles add, but points multiply: a quarter-turn followed by another quarter-turn gives $i\cdot i=-1$, and the next two quarter-turns return to $1$. Ordinary addition would fail to stay on the unit circle, since $1+1=2$.

For any fixed $a\in G$, the translations $x\mapsto ax$ and $x\mapsto xa$ are homeomorphisms, with inverses given by translation by $a^{-1}$. Consequently the neighbourhoods of the identity element determine the entire topology. This is why local information near one motion can control a whole family of symmetries. See Tornier, Haar Measures, section 1.1 for these basic properties of topological groups.

For the displayed unpivoted Thomas algorithm with one right-hand side, count each scalar addition, subtraction, multiplication or division as one arithmetic operation. Forming $m_i,p_i,g_i$ takes five arithmetic operations per forward step. The last unknown takes one division; each remaining back substitution step takes three arithmetic operations. ThusThis is an operation-count model, excluding assignments, indexing, pivot checks and any special simplifications of the coefficients. It is not a timing benchmark. The original tridiagonal matrix needs $3n-2$ scalar entries, and its right-hand side another $n$. Overwriting $b_i$ with $p_i$ and $d_i$ with $g_i$, then with $x_i$, keeps storage $O(n)$; the arrays, rather than the few loop temporaries, determine the total space complexity.

For repeated right-hand sides, retain the LU decomposition: computing $m_i,p_i$ once costs $3(n-1)$ arithmetic operations, and each subsequent pair of forward substitution and back substitution sweeps costs $5n-4$. Hence $r$ right-hand sides cost $3(n-1)+r(5n-4)$ arithmetic operations. This is the banded counterpart of Reusing LU factors for multiple right-hand sides.

For floating-point arithmetic with precision $p$ in radix $\beta$ and rounding to nearest, unit roundoff is the half-gap scale $u={\beta }^{1-p}/2$. If a nonzero exact real number $z$ lies in the normal finite range, its nearest rounded value satisfiesIndeed, the absolute distance to the nearest value is at most ${\Delta }_e/2$, and $|z|\ge {\beta }^e$ gives the bound. For a correctly rounded addition, subtraction, multiplication or division, apply this estimate to the exact result of that one operation on the stored operands. The bound does not include earlier roundoff error or automatically bound a whole algorithm. Results outside the finite range and tiny subnormal numbers require separate treatment. Rounding in a directed mode also changes the bound.^[ref]

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.