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.
Uniform payoff bound against Tit for tat 2026-10-25
In a symmetric two-action stage game write for mutual cooperation, mutual defection, sole defection and sole cooperation payoffs. Suppose , and . Against an initially cooperative Tit for tat, every action sequence has limiting upper average payoff at most .
For a deviator's actions , put , and . The opponent at time plays . Check the four transitions: to and to satisfywith equality; to uses , and to uses . A telescoping sum gives the displayed finite-horizon bound. Divide by the horizon and let it increase. Mutual Tit for tat yields every round, so it is a Nash equilibrium under the long-run average payoff criterion. The argument is pathwise and therefore covers arbitrary deviations representable by finite-state machines, as well as action sequences outside that class.
Uniform recurrence Created 2026-10-05 Updated 2026-10-14
A two-sided sequence over a finite alphabet is uniformly recurrent if every finite word over an alphabet occurring in it occurs with bounded gaps. More precisely, for each such word some ensures that every length- interval contains a complete occurrence. This is equivalent to being a minimal point of the full shift: a finite cover of the orbit closure by preimages of a word's cylinder set bounds its return gaps; conversely, bounded gaps pass to all points of the orbit closure and make every forward orbit dense there. The property concerns finite words, not infinite integer intervals.
Union-find operation bounds 2026-10-18
Assume identifiers, pointers and ranks fit into constant-size machine words, with constant-cost indexed array access, comparison and assignment. Initializing members costs time and machine words. With union by rank and full path compression, any sequence of disjoint-set find operations and disjoint-set union operations then has total time complexity, in Big O notation,Here is a conventionally normalized inverse Ackermann function. The documented path-halving implementation has the same amortized analysis bound.[ref]
UF.java. Algorithms, 4th edition by Robert Sedgewick and others; UF.java, class documentation: linear constructor, logarithmic worst-case operations and inverse-Ackermann sequence bound for rank with halving
A disjoint-set union operation includes two disjoint-set find operations and a constant amount of additional linking work. Including in the bound accounts for initialization even if no queries follow.
This is a bound on an entire sequence. It is not a worst-case constant bound for each call: a disjoint-set find operation can still encounter a previously uncompressed route of logarithmic length. The inverse Ackermann function grows extraordinarily slowly but is unbounded, so it cannot be replaced by a mathematical constant in this asymptotic statement. The general distinction between a per-operation maximum and a whole-sequence guarantee is explained in amortized analysis.
Robert Tarjan's 1975 paper established an inverse Ackermann function bound for set union. Its abstract states the sharper two-parameter form for representative queries and intermixed merges: the worst total cost is bounded above and below by positive constant multiples of . Those variables count different operations from the convenient formulation above; the abstract's matching lower bound is about its analyzed method, rather than a claim that every conceivable representation obeys the same lower bound.[ref]
The intuition is that union by rank limits how parent routes grow, while path compression makes an expensive traversal improve later queries. The rank argument alone proves only a logarithmic bound. Establishing the inverse Ackermann function bound requires a finer accounting of traversals across rank ranges; it does not follow merely from drawing a flatter rooted tree. The useful result is that repeated merging and membership queries can share the work of maintaining a changing partition of a set.
Walk in a graph Created 2026-10-06 Updated 2026-10-14
A walk records a journey through a graph as a finite alternating sequencewhere each edge joins the consecutive vertices and . Both vertices and edges may repeat. Its length is , counting edge traversals with repetitions, rather than counting different edges or measuring the drawing. Here a graph path means a walk with no repeated vertices; a trail instead forbids repeated edges. These conventions distinguish a journey's record from the subgraph consisting of the connections it used.[ref]
https://ptwiddle.github.io/MAS341-Graph-Theory-2017/lecturenotes/lecture3.html. Paul Johnson, MAS341, Lecture 3: walks and trails
Unless stated otherwise, the examples below use a finite simple graph that is an undirected graph, so an edge may be traversed in either direction. In a multigraph, retain each edge's individual identity as well as its endpoint vertices: two parallel edges are different choices for the same step. If self-loops are allowed, traversing one leaves the current vertex unchanged but adds one to the length. In a directed graph, each step must follow its directed edge from its initial to its terminal vertex, giving a directed walk; reversing a journey need not be possible.[ref]
https://people.math.binghamton.edu/zaslav/Oldcourses/581.S99/notes.html. Thomas Zaslavsky, Supplementary Notes for Graduate Graph Theory: edge identities and walks
We allow the zero-length walk at every vertex . It uses no edges, so it is also a trail and a graph path, and its coinciding endpoints make it a closed walk. This means staying put is a legitimate journey; a graph with no vertices has no such walk. Positive-length restrictions will be stated explicitly.[ref]
Mathematics for Computer Science by Eric Lehman and others. Lehman, Leighton and Meyer, Mathematics for Computer Science, §11.8.1: length-zero convention
Use the same constructed graph throughout these three sections:Here denotes the unordered pair , and . Two triangles in a graph, and , share , with one extra edge . These are schematic connections, not measured roads; the highlighted connections in the diagram show which edges are used, while the numbered sequence records their order.
The length-six walk uses and twice, so it is not a trail. The length-six trail returns to but uses six different edges, so it is not a graph path. The length-three graph path repeats neither vertices nor edges. Thusfor this particular graph. The restrictions answer different routing questions: revisiting a junction is harmless for many journeys, whereas reusing a serviced road segment can matter for an inspection route. Travel costs require a weighted graph; a walk's cost adds the weight of each traversal, even when an edge is used again.
Every finite walk from to contains a graph path from to after deleting detours. For a proof outline, if with , delete the intervening closed walk. The retained steps still meet at the same vertex, and the length strictly decreases. Repeating terminates with no repeated vertices, or with the zero-length graph path when . This explains why reachability can be formulated using either walks or graph paths. With nonnegative edge weights, deletion also cannot increase cost, connecting the argument to the shortest path problem; with negative weights that cost conclusion fails.[ref]
https://ptwiddle.github.io/MAS341-Graph-Theory-2017/lecturenotes/lecture3.html. Paul Johnson, MAS341, Lecture 3: deleting repeated-vertex detours
Wavelet tree Created 2026-10-20 Updated 2026-11-05
A wavelet tree stores a sequence over an ordered alphabet by repeatedly splitting the alphabet into two parts. At an internal node, a bit vector records zero or one according to each element's part; the children receive the corresponding stable subsequences. The original wavelet-tree construction uses such relative position encodings to support compact indexed access.[ref]
To answer a rank query for character in the first positions, follow the branch containing . Replace by the number of that branch's bits among the current bit vector's first positions. At the leaf, the resulting is the answer. Stable filtering proves the invariant: it is the number of original-prefix elements reaching the current node.
For example, split as and . The string
cadaba gives root bit vector 101000 and left subsequence aaba. In its first five characters there are three left-part elements. The left bit vector 0010 contains two zeros among those first three positions, so the number of a occurrences is two. With constant-time bit rank queries and a balanced alphabet split, character rank queries take time. Weak lower semicontinuity Created 2026-09-24 Updated 2026-11-05
A functional on a normed vector space has weak lower semicontinuity when each sublevel set is closed in the weak topology. Equivalently, for every weakly convergent net ,The analogous condition for sequences defines sequential weak lower semicontinuity. In a general topological space, sequence tests alone need not characterize a closed set.
For a convex functional on a normed vector space, lower semicontinuity in norm topology is equivalent to weak lower semicontinuity: convex sublevel sets are norm closed exactly when they are weakly closed, by the Hahn-Banach separation theorem. In this convex setting the sequential condition also suffices, because norm-convergent sequences converge weakly and the norm topology is metrizable. In particular, the norm has weak lower semicontinuity. Its negative is not: in , , while . The correct semicontinuity is what preserves an objective bound when a minimizing sequence has only a weak limit.
Well-quasi-ordering Created 2026-10-06 Updated 2026-10-14
Working set 2026-10-13
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 identify the memory page accessed by the th memory reference, and let the positive integer be the window length. Immediately after reference ,Repeated memory references to the same memory page contribute only one set element. The working set size is the cardinality . 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 , the successive working sets begin , , and . At , the window is references 2–5, namely , so again. Every later four-reference window contains all four memory pages. Under three-page frame LRU replacement, however, the resident set at is : 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.
A four-reference working set remains four pages while a three-frame resident set contains only three
. Details. Window choice matters: on this same sequence, 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 , 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]
https://denninginstitute.com/pjd/PUBS/WSModel_1968.pdf. The Working Set Model for Program Behavior, Communications of the ACM, May 1968, sections 3–4
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. Zero padding 2026-10-14
Zero padding extends a finite sequence by zero entries to a specified length. For input lengths , their full discrete convolution has length at most . Padding both inputs to allows circular convolution to represent this full result without folded entries.
Zorn's lemma 2026-10-14
Let be a nonempty partially ordered set. If every chain in a partial order has an upper bound in , then has a maximal element. The hypothesis meansThe upper bound may depend on and need not belong to . A least upper bound is not required. The conclusion asserts that some satisfies ; it does not assert a greatest element, which would satisfy for every .[ref]
How to use Zorn’s lemma by Timothy Gowers. How to use Zorn’s lemma, “General discussion”: statement and distinction between maximal and bigger than everything else
Here a chain in a partial order may be the empty set. Every member of is an upper bound of the empty chain in a partial order, so including it in the hypothesis already forces to be nonempty. If “chain” means only nonempty chains in a partial order, the separate nonempty- assumption is essential: the empty poset otherwise satisfies the hypothesis vacuously and has no maximal element. These are two equivalent conventions for the theorem.
The strength of Zorn's lemma is that compatible partial constructions can have a completed, unextendible member without an explicit procedure for finding it. The next examples separate the upper bound calculation from the reason a maximal element has the desired property. All chains in a partial order must be covered, including uncountable ones, rather than just increasing sequences. The condition is sufficient, not necessary: a poset can have a maximal element and still have an unbounded chain in a partial order elsewhere.



