Uniformly continuous function Created 2026-09-24 Updated 2026-10-18
A uniformly continuous function has one input tolerance valid throughout its domain of a function. For , with , uniform continuity meansChoose the output tolerance first, then a positive valid for every pair of function inputs. It may depend on , the function and its domain of a function, but not on the pair’s location. The absolute values measure input and output distance.[ref]
Basic Analysis: Introduction to Real Analysis, Volume I by Jiří Lebl. §3.4, Definition 3.4.1: a single positive input tolerance for all pairs in the specified real domain
Compare the quantifier order with the epsilon-delta definition of continuity:Both lines end with . In the first, can depend on the point ; in the second, it is chosen before . Thus uniform continuity implies continuity at every point. Each requested gets its own shared tolerance.
For an exact example, take the polynomial function on the closed interval . For every pair of function inputs in that interval, polynomial factorization givesConsequently works everywhere on this domain of a function. With , the common tolerance is . Near the right endpoint, for example, and have input distance and output distance . The bound is sufficient; it does not claim the largest admissible input window at each point.
On the whole real line, the same polynomial function is a continuous function but fails uniform continuity. Take the sequences and , for positive integers . ThenFor any proposed , choose an integer . The inputs are closer than , yet their outputs violate the fixed tolerance . The sequences need not themselves have a finite limit: their mutual distance is what tends to zero. This is the obstruction captured by the sequential criterion for uniform continuity. Restricting the domain of a function to removes these escaping pairs.
A uniformly continuous function need not be a bounded function. The identity function on the real line has , so always works, although its image of a function is the unbounded real line. Uniform continuity controls changes between nearby inputs, not the overall size of outputs. Likewise, an unbounded domain of a function does not by itself prevent uniform continuity.
The square root supplies a different common tolerance on the interval . Assuming , put and . Since ,Interchanging the inputs when necessary provesThus guarantees uniform continuity on the entire domain of a function, including zero. For , any input distance below suffices. The pairs and both have input distance ; their output distances are respectively and . The common guarantee accommodates quite different local sensitivities.
This Hölder continuity bound allows a curved tolerance rule. It is weaker than a Lipschitz bound: at zero the output change divided by the input change isNo finite Lipschitz constant works near zero, even though uniform continuity does. A Lipschitz function does have uniform continuity, choosing when its Lipschitz bound is positive; when it is a constant function.[ref]
Basic Analysis: Introduction to Real Analysis, Volume I by Jiří Lebl. §3.4, Proposition 3.4.8 and Example 3.4.10: Lipschitz continuity implies uniform continuity; the square root on the nonnegative half-line separates the properties
Square-root input changes share an output tolerance even though amplification near zero is unbounded
. At left, the exact output changes for base points stay inside whenever and . The right panel computes the amplification for inputs : it grows without bound as decreases. These are calculated function graphs, with no experimental measurements. Details.For general metric spaces, replace the absolute values by the respective distance functions. The Heine-Cantor theorem gives an existence guarantee: every continuous function on a compact metric space is uniformly continuous. In particular, continuity on a finite closed interval provides a common tolerance, even when no simple formula for it is known.[ref]
Basic Analysis: Introduction to Real Analysis, Volume I by Jiří Lebl. §7.5, Definition 7.5.10 and Theorem 7.5.11: uniform continuity between metric spaces and the compact-domain theorem
For a short proof outline, fix . Continuity gives each point an open ball of radius within which outputs differ from by less than . The open balls of half these radii still cover the domain of a function. Compactness supplies a finite subcover. Take to be the smallest half-radius in this finite set. Two inputs closer than lie together in one of the original open balls, so the triangle inequality bounds their output distance by . The beautiful step is that the compact set turns local choices into finitely many choices, whose minimum stays positive.
A shared tolerance also makes uniformly continuous functions preserve Cauchy sequences: after choosing for , all sufficiently late input pairs are closer than , so all corresponding output pairs are closer than . Unlike a convergent sequence argument, this does not require an input limit inside the domain of a function. It is why uniform continuity is useful for extending a function toward missing endpoints and for the decay argument below.
For each positive integer , put on . Its supremum norm is exactly , so this sequence of functions converges to zero by uniform convergence. Nevertheless,Each of its complete sine oscillations contributes : rise from zero to , fall through zero to , then return to zero. Taking a partition of an interval through all extrema attains . Every further partition refinement merely subdivides monotone function segments, so the same reasoning as in partition example of total variation proves the upper bound too.
The functions sin(2πnt)/n converge uniformly to zero while their total variation remains 4; all three function plots use the same vertical scale
. Details. For a continuously differentiable function on a closed bounded interval, total variation also satisfiesApplied here, the derivative is , and integrating its absolute value over periods gives . The differentiability hypothesis matters: the partition definition applies much more widely than this derivative formula.[ref]
1 Algebraic and Analytic Methods. NIST Digital Library of Mathematical Functions; §1.4(v), equations 1.4.33–1.4.34, Functions of Bounded Variation
Small pointwise size and small accumulated movement are different approximation goals. Unimodality of binomial coefficients 2026-10-31
For fixed nonnegative integer , the row increases to its middle and then decreases. Indeed, for , the ratio of consecutive binomial coefficients is , which is greater than, equal to, or less than according as is less than, equal to, or greater than . Thus even has one maximum at , while odd has two equal maxima at .
Unimodular basis test for an integer direct summand Created 2026-10-14 Updated 2026-11-05
Integer row vectors forming a square unimodular matrix are a basis of the corresponding free abelian group: the adjugate formula makes the inverse integral. The subgroup spanned by any subset of that basis is therefore a direct summand, complemented by the remaining basis vectors. In contrast, a proper finite-index subgroup of a free abelian group cannot be a direct summand: its nonzero finite quotient would have to embed as a subgroup of a torsion-free group.
Unimodular matrix Created 2026-09-24 Updated 2026-10-14
A unimodular matrix is a square integer matrix whose determinant is or . The decisive property is that its inverse matrix also has integer entries: multiplication by gives a bijection of the integer lattice onto itself. Thus an invertible linear map can preserve not only real coordinates but the requirement that every coordinate is an integer. These matrices form the integral general linear group.[ref]
Lecture 1: Introduction. §7, Definition 11 and Lemma 12, printed p. 9: determinant and integer-inverse characterization
For an original two-dimensional example, takeIts determinant is one, and it maps to . Conversely, the integer point comes from . For instance, has new coordinates relative to the columns and . No integer point disappears, although the basis vectors and their fundamental cell change shape.
Two lattice bases generate exactly the same integer points
. Original drawings of the standard basis and the columns of . Both displayed cells have area one. The point has coordinates in the standard basis and in the sheared basis. Details.This is useful whenever coordinates must remain integral. A unimodular change of lattice basis can give a shorter or more convenient description without changing the objects represented. Smith normal form and Hermite normal form use controlled integer operations to simplify integer matrices; ordinary Gaussian elimination may divide by numbers that destroy integrality. The geometric freedom is substantial: a sheared basis may look completely different while describing exactly the same infinite set of integer points.
A determinant of is allowed too. Swapping two basis columns reverses orientation while preserving the integer lattice. The condition is therefore preservation of the complete integer structure, rather than a requirement to preserve orientation.
Unimodular reduction of a discriminant-minus-four form to two squares Created 2026-09-24 Updated 2026-11-05
Union by rank 2026-10-18
Union by rank keeps a nonnegative integer rank, initially zero, for each member. For each input, obtain its root of a tree using the disjoint-set find operation, then compare the resulting ranks. Attach the lower-rank root of a tree below the higher-rank root of a tree, leaving both ranks unchanged. When the two disjoint-set representatives differ but their ranks are equal, choose either survivor and increase its rank by exactly one. A redundant disjoint-set union operation changes no ranks. Path compression also changes no ranks. The surviving root's rank bounds the height of its rooted tree, measured in edges; after path compression it need not equal that height.[ref]
COS 226 Bob’s Notes 1: Union-Find and Percolation (Version 2) by Robert Tarjan. Robert Tarjan, COS 226 Bob’s Notes 1: Union-Find and Percolation, Version 2, Fall 2010, p. 4: rank linking, equal-rank increment and upper-bound interpretation after compression
In our example, let the first argument's root of a tree survive equal-rank ties. The first two merges create roots , each of rank . The third gives and increases the rank of to . The fourth creates root of rank . The fifth attaches below without increasing any rank. Before any subsequent compression queries, the indexed arrays areThe redundant call on leaves these arrays unchanged. In particular, the disjoint-set representative of is , although is the minimum member of its block of a set partition.
Two short arguments explain the rank invariant. First, a root of rank has at least members in its block of a set partition: rank zero starts with one, and increasing rank combines two disjoint blocks of a set partition with at least members each. Unequal-rank linking only adds members. Thus every rank is at most for stored members, using the floor function and logarithm. Second, height is initially zero; unequal-rank linking adds at most one to the lower height, while equal-rank linking raises the available bound by one. Path compression only shortens routes. These arguments prove a height bound, not the stronger amortized analysis below.
Unique factorization domain Created 2026-09-24 Updated 2026-11-05
A unique factorization domain is an integral domain in which every nonzero nonunit factors into finitely many irreducible elements, uniquely up to reordering and multiplying individual factors by units. Existence and uniqueness are both required. The integers and the polynomial ring over a field are examples.
In a unique factorization domain, every irreducible element is a prime element. Comparing prime factorizations therefore justifies cancellation of common factors and the usual exponent rules for a greatest common divisor. The integral domain fails uniqueness, as gives inequivalent factorizations into irreducible elements.
Unit-cost model 2026-10-31
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.
Unit from norm one or minus one Created 2026-09-24 Updated 2026-10-14
For a number field and an algebraic integer , the criterion isHere the absolute field norm means the field norm down to ; its absolute value is one. Necessity follows from with both factors integers. Conversely, multiplication by on an integral basis is a matrix with integer entries and determinant . Its inverse also has integer entries, and applying that inverse to gives . The integrality hypothesis matters: has field norm one, but is not in .
In , the criterion becomes . Thus and are again algebraic integers. These units produce infinite families of solutions to the Pell equation.
Unit in a ring Created 2026-09-24 Updated 2026-11-05
A unit in a unital ring is an element with a two-sided multiplicative inverse :The ring is part of the condition. In the only units are and , whereas every nonzero rational number is a unit in . Modulo six, is a unit because , while is a nonunit.
In a nonzero ring, zero is never a unit, since . Every unit has multiplicative cancellation, but a cancellable element need not be a unit: can be cancelled in the integers, yet its reciprocal is not an integer. The units form the unit group of the ring.
Unit modulo n Created 2026-09-29 Updated 2026-10-14
For a positive integer modulus , a residue class is a unit when it has a modular multiplicative inverse: some integer satisfies . Modulo twelve, the units are exactlyIn particular, five is its own modular inverse, since . 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.
Multiplication by five permutes all twelve residue classes, whereas multiplication by six merges distinct inputs
. Details. In general, the exact criterion isFor the forward direction, implies every common divisor of divides one. Conversely, if their greatest common divisor is one, Bézout's identity supplies , so is a modular inverse. The extended Euclidean algorithm computes these coefficients. The units form the unit group under multiplication. [ref]
https://ocw.mit.edu/courses/18-200-principles-of-discrete-applied-mathematics-spring-2024/mit18_200_s24_lec15.pdf. Ankur Moitra, MIT 18.200, Lecture 15 (2024), pp. 3–4: inverses, coprimality and the unit group
Multiplicative cancellation while keeping the same integer modulus is valid for a unit modulo n: from , multiply by a modular inverse of to get . A nonunit cannot be cancelled as a general rule. For example, , yet . 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 , every nonzero residue class is a unit, so is a finite field. Modulo twelve it is a commutative ring with zero divisors, and is not a field. For , the sole class satisfies and is a unit; this one-element zero ring is not a field. [ref]
https://ocw.mit.edu/courses/18-200-principles-of-discrete-applied-mathematics-spring-2024/mit18_200_s24_lec15.pdf. Moitra, MIT 18.200, Lecture 15, pp. 8–9: the prime-modulus field criterion
Unit reduction for quadratic norm equations Created 2026-10-14 Updated 2026-11-05
In a real quadratic integer ring, multiplying by a positive norm-one fundamental unit preserves a prescribed norm. Choose an exponent so that a positive representative lies in a half-open interval . Its conjugate is the prescribed norm divided by the representative, so both integer coefficients are bounded on that interval. Enumerating these reduced representatives gives a complete finite list of unit orbits of solutions.
Units of Q of square root minus three Created 2026-09-24 Updated 2026-11-05
Let and . Its ring of integers is , and its unit group isTo prove the unit claim, the field norm of isA unit must have norm , because the field norm is multiplicative and is a nonnegative integer here. Conversely, an element of norm has its complex conjugate as an inverse in .
The equation is equivalent to . Thus , and checking these values gives precisely the six displayed elements. The element has order six, so they form a cyclic group.
Units of Q of square root two Created 2026-09-29 Updated 2026-10-14
The unit has field norm minus one and is the least unit greater than one in the field embedding sending to its positive value. It is a fundamental unit. The Dirichlet unit theorem therefore gives
Writing , direct multiplication givesFor , the pairs are , andIn particular, has field norm one. Its powers start , , , , and give solutions of the Pell equation . This turns finding one unit into generating infinitely many exact integer solutions.
The two field embeddings show a striking balance:For positive , one value grows while the other approaches zero, and their product stays . 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]
https://www.jmilne.org/math/CourseNotes/ANT.pdf. Milne, Algebraic Number Theory, Chapter 5, the unit theorem
Unreduced rational representation 2026-10-14
Consider an original abstract data type whose values are rational numbers. Store an ordered pair 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 , and are three different concrete states with the same abstract rational number . Similarly, and 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 and violate the representation invariant; neither has a value under this abstraction function. By contrast, is completely valid. Simplifying it to the reduced fraction 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 and ,This defines an equivalence relation on : 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 and unequal as rational numbers. The general reason is that an abstraction function may map several concrete values to one abstract value.[ref]
8.3 Module Documentation. Section 8.3.1, Abstraction Functions: several concrete values mapping to one abstract value; Section 8.3.4, Representation Invariants: valid domain of AF
Unsigned integer arithmetic in C 2026-10-24
For a -bit unsigned integer type without padding, C programming language arithmetic on that type reduces results modulo . 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] Upward skip-free random walk Created 2026-10-14 Updated 2026-11-05
An upward skip-free random walk has integer-valued increments bounded above by one. Arbitrarily large downward jumps are permitted, but a first crossing of a nonnegative integer level from below must land exactly at . This removes the overshoot from the stopped likelihood ratio under exponential tilting and permits the exact geometric maximum of an upward skip-free random walk. For a real threshold , the first crossing is the crossing of , so the overshoot-free formula must use that integer level.
Valuation of a primitive p-power root of unity Created 2026-10-14 Updated 2026-11-05
In a mixed-characteristic discretely valued field, a primitive th root of unity reduces to one. For every prime to , the ratio is a unit, so all factors of have the same valuation. Taking valuations gives the formula. Because the left side is a positive integer for a normalized valuation, the existence of such a root forces , bounding the possible -power torsion.
Van der Corput sum-integral lemma Created 2026-10-06 Updated 2026-11-05
For a real phase with continuous monotone derivative and , the sum-integral discrepancy has the displayed uniform bound. Periodization and the Dirichlet-Jordan convergence theorem express it as symmetric nonzero Fourier modes. Integration by parts gives endpoint terms and reciprocal-derivative variations. Monotonicity bounds their total variation by . Pairing the leading endpoint terms reduces them to the uniformly bounded sine series. The exclusion of integer nonzero frequencies is essential.






