Uniform convergence Created 2026-09-24 Updated 2026-10-14
A sequence of functions converges uniformly to , where is a metric space with metric , precisely whenFor real numbers, use the absolute value . Compare the universal quantification and existential quantification:The decisive change is whether can depend on . Uniform convergence implies pointwise convergence.[ref]
6.1 Pointwise and uniform convergence. Basic Analysis: Introduction to Real Analysis, Volume I by Jiří Lebl, §6.1.2, Definition 6.1.6 and Proposition 6.1.7
For functions taking values in real numbers on a nonempty domain of a function, the supremum error is , allowing . Then uniform convergence is equivalent to . The supremum need not be a maximum: pointwise strict bounds below only give , so use tolerance when proving this equivalence. This single error bound controls every possible input, including one chosen after seeing the index.
For and its pointwise limit on , the error is zero at one but approaches one as from below. Consequentlyfor every positive integer . This supremum is never attained: below one the error is , and at one it is zero. Deleting the endpoint leaves the same supremum error on . To disprove uniform convergence directly, choose : for any proposed , take and . The error equals , violating the strict tolerance. Thus a moving input defeats every proposed common threshold.
On the smaller interval , for a fixed , the pointwise limit is zero andFor and , the exact first successful common threshold isThe logarithm and floor function turn an infinite approximation statement into a finite stopping rule. At , fails tolerance , while succeeds. At and , the ratio is exactly three: is necessary because equality is insufficient. For , every error is zero. The domain of a function determines whether one threshold can certify every input.
For another explicit stopping rule, let on . Its uniform limit is zero and its supremum error is . For every , works, using the ceiling function. Unlike on , it controls even the endpoint.
The practical beauty of uniform convergence is that one quantitative bound can survive further operations: the uniform limit theorem preserves continuity, and uniform convergence preserves integrals on a compact interval controls accumulated error. Differentiation needs additional hypotheses, such as uniform derivative convergence with an anchored value. These results distinguish an approximation that looks accurate at selected inputs from one that justifies replacing a whole function in a calculation.
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.
