Right tree rotation 2026-10-25
Roberto Grossi 2026-11-05
Roberto Grossi coauthored the 2003 entropy-compressed text-index paper with Ankur Gupta and Jeffrey Scott Vitter. The paper combines compressed suffix-array techniques with a wavelet tree, routing sequence positions through bitvectors that partition the alphabet. Its indexing bounds relate stored space to empirical entropy while retaining pattern-search functionality. The mathematical aim is both compression and access, rather than simply making a file small.[ref]
Root-of-unity Euler system Created 2026-10-14 Updated 2026-11-05
Fix a finite excluded set containing two, and let contain the roots of unity of orders coprime to every prime in . A root-of-unity Euler system is a nonzero algebraic-valued function on that is even and Galois equivariant, satisfies for , and satisfies when the order of is prime to , for every prime over . Values are required to be locally integral units where the congruence is used. These distribution and congruence properties provide auxiliary cyclotomic extensions, beyond a single norm-compatible p-power sequence.
Second moment method Created 2026-09-24 Updated 2026-10-14
The second moment method uses a random variable's expected value and second moment to establish that a counted or measured quantity is positive with substantial probability. It is useful when a positive average alone could be caused by extremely large values on very rare outcomes. Controlling the variance rules out too much of that concentration in rare outcomes.
For a nonnegative random variable with and finite second moment, the second-moment bound for positivity givesEquivalently, . The method also includes the simpler Chebyshev's inequality bound . Thus a sequence of such random variables with has with probability tending to one. These statements require no independence assumption. The variance argument and its use for random counts are developed in Zhao's lecture notes. [ref].
For an original toy count, let count successes in ten independent Bernoulli trials with success probability . The binomial distribution givesConsequently . The exact probability is . The first moment method and union bound only give the upper bound here. First and second moments therefore answer complementary existence questions.
The second moment method certifies a positive count, while statistical dependence can change the conclusion despite an unchanged mean
. Left: exact binomial distribution probabilities of at least one success and second-moment lower bounds for ten independent trials as the success probability varies. Right: the same ten trials with either occur independently or share one common Bernoulli outcome. Both counts have mean one, but the perfectly linked count has much larger variance and only probability of being positive. All data are original specified probability models. Details.For a sum of indicator random variables, the variance of a sum isIndependence makes the covariances vanish, but the formula itself also covers dependent counts. For the same ten success probabilities, let every trial share a single Bernoulli random variable : then , with mean one, variance nine, and . The second-moment lower bound is exactly . Ignoring the positive covariances would produce the false independent-count conclusion. Zhao's discussion of sums of indicators explains why overlapping counted structures require these pairwise terms. [ref]
https://ocw.mit.edu/courses/18-226-probabilistic-methods-in-combinatorics-fall-2022/mit18_226_f22_lec06-07.pdf. Zhao, MIT 18.226, §4.1: indicator covariances and Bernoulli counts
. Seminorm topology 2026-10-14
Given a nonempty family of finite-valued seminorms on a real or complex vector space , its seminorm topology has basic open zero neighbourhoodsTheir translates form a basis of a topology. Only finite intersections are required: an infinite intersection might impose a stronger topology. Equivalently, put ; then is a seminorm and . See Günther Hörmann, Advanced Functional Analysis, section 4, neighbourhood systems from seminorms for the general construction.
Each defining seminorm is continuous, since . A sequence satisfies precisely when for every ; the same criterion holds for nets. Finitely many measurements can each meet a prescribed tolerance after a common index.
The seminorm axioms also establish the required joint continuity of vector addition and scalar multiplication:For a basic neighbourhood, apply these estimates to its finitely many seminorms; near the absolute value is bounded. This gives a locally convex space even when some directions are invisible to every measurement.
Sensorless planning 2026-10-25
Sensorless planning chooses one action sequence that succeeds from every possible initial physical state without receiving distinguishing observations during execution. A belief state is a set of possibilities. For a deterministic search transition model , an applicable action maps to ; for nondeterministic outcomes, take the union of all possible successors. Applicability must hold for every member of , and success requires the resulting belief state to be a subset of the physical goal set.
Every fixed action sequence preserves inclusion of the initial belief states. Consequently, a successful plan for also succeeds for every subset of . Success on a superset is an additional requirement, so cannot be inferred from success on alone. This property supports incremental belief-state search.
Sentinel value 2026-10-31
Separate chaining Created 2026-10-13 Updated 2026-10-20
With separate chaining, each hash bucket in a hash table contains a collection of records, often a linked list. Lookup computes the bucket index, then follows that chain until a key equality comparison succeeds or the chain ends. A hash collision therefore affects the search work without merging unequal keys. Deletion searches the same chain and unlinks the matching record; in a singly linked list, remembering the preceding record during the search permits the unlink.[ref]
For the four-key integer example in hash table, insert a new record at the head of its chain after checking that its key is absent. Inserting in that order makes hash bucket hold , hash bucket hold , and the other two hash buckets empty. All five subsequent operations below select hash bucket because :
Separate chaining traces lookup, replacement, deletion and insertion through key equality
. Original deterministic model with . The table counts actual keys inspected, not elapsed machine time. Operations occur from top to bottom; only an absent key adds a new record, and the untouched record remains in hash bucket . Details.get(5) rejects key , accepts key , and returns after two key equality comparisons. get(13) rejects and reports absence after three comparisons. put(5,B*) examines and replaces the value without changing . delete(9) examines just the head record, removes it, and gives . Finally, put(13,E) rejects before inserting the new head record; returns to and the chain is . The successive hash table load factors are . These counts follow from the stipulated chain order; a different insertion policy changes the successful-search counts.For a chain of length , lookup and deletion by key take time complexity in Big O notation. The same applies to
put before any resizing, since replacement semantics require checking for an existing equal key. Head insertion alone is if absence is already known; that is a different precondition. These bounds assume bucket-index hashing, array access, key equality comparisons, allocation and link updates. A long string or large integer can make hashing or comparison depend on its encoded length, so counting record visits alone does not establish constant running time.Under simple uniform hashing, each distinct key's bucket index is an independent random variable with a uniform distribution on a finite set of indices. The keys and query are fixed independently of this random assignment. Then lookup has expected time complexity, where is the hash table load factor; it is expected when stays bounded. These are model assumptions, not an automatic consequence of using a deterministic hash function.[ref]
Lecture 8: Hashing I. 6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff; pp. 4–5, chaining worst case and simple uniform hashing assumption
Here is the short calculation. For an absent query and stored keys , let be the indicator random variable of . The number of records inspected has expected valueby linearity of expectation. For a present fixed query, scanning its entire chain inspects at most itself plus all other colliding records, with expected value ; stopping at the match only decreases this upper bound. Adding constant hashing and bucket access yields expected for either query. The argument needs pairwise collision bounds; it does not require all the indicator random variables to be independent. A universal hash family can provide a related bound by random choice of a hash function for a fixed key set, as explained in that article.
The worst case remains , and an absent query takes comparisons if all records occupy its hash bucket. For instance, all collide under . Separate chaining remains correct, but a sequence of insertions that each checks the existing chain can take quadratic total work. Amortized analysis of resizing does not remove this search cost, and an adaptive choice of keys based on a known hash function is outside the stated simple uniform hashing model.
Separating subspace of an algebraic dual Created 2026-10-05 Updated 2026-11-05
A linear subspace is separating if every nonzero has for some . For finite-dimensional , an evaluation map is injective, so the rank-nullity theorem forces and . For the infinite-dimensional polynomial space, the span of its coefficient functionals is a proper separating linear subspace of the dual space, which contains all sequences of coefficients, not just finitely supported ones.
Sequence Created 2026-09-24 Updated 2026-10-14
A sequence assigns a value to each position in an ordered index list. For an infinite sequence in a set , one standard convention is a function , written with . Some applications start the index at zero, and a finite sequence has only finitely many positions. Values may repeat; both order and repetition matter. [ref].
For example, begins , whereas begins . Their sets of values are both , but these are different sequences. A subsequence keeps selected positions in increasing order; the subsequence of at its even integers is the constant sequence . A tail of a sequence retains all positions from one index onward.
Sequences express successive approximations, repeated observations, and the iterates of a recurrence relation. A limit of a sequence describes where its terms eventually concentrate. Finite observations alone cannot establish that behaviour: for any positive integer , the all-zero sequence and the sequence with for and for agree through index , yet have different limits of sequences. A formula or bound controlling the entire future, such as the tail diameter of a sequence in the Cauchy sequence condition, supplies information that a finite list cannot.
Sequence and series Created 2026-09-24 Updated 2026-11-05
A sequence is an ordered family , formally a function from the positive integers into a chosen set. The indices record position and allow repeated values. A series formed from that sequence studies the partial sumsWriting means that the sequence has finite limit . Thus convergence of terms and convergence of their cumulative sums are different assertions.
For , the terms tend to zero and the geometric series has . For , the terms also tend to zero, but the harmonic series diverges. A necessary condition for series convergence follows from ; it is not sufficient. The Cauchy criterion for series instead controls every sufficiently late finite tail.
For a sequence of functions, there are two further choices: pointwise convergence checks a separate limit at each input, while uniform convergence requires a common error bound over the domain. These distinctions determine when infinite sums may be integrated or differentiated.
Sequence convergence in the cofinite topology Created 2026-10-14 Updated 2026-10-31
By convergence of a sequence in a topological space, means that every open neighbourhood of contains all sufficiently late terms. In the cofinite topology, this is equivalent to the condition that, for every , the value occurs only finitely often. Necessity uses the open neighbourhood ; sufficiency chooses an index beyond every last occurrence of the finitely many points excluded by a given open neighbourhood.
Consequently a sequence with distinct terms converges to every point of . For the original choice on , take the two open neighbourhoodsAll terms with lie in and all terms with lie in . More generally, each finite excluded set has a last visit, so and , and in fact for every . No numerical distance is tending to zero here; the open sets specify the meaning of convergence.
The same sequence eventually stays in neighbourhoods of two different limits
. Original sequence in the cofinite topology. Two sample neighbourhoods have different finite exclusions and different last-visit indices. Their memberships illustrate the general finite-exclusion argument; testing just these two neighbourhoods would not by itself prove convergence. Details.Distinct terms are sufficient, not necessary. The sequence also converges to every point, since each value occurs only twice. By contrast, the constant sequence converges only to : an open neighbourhood of any can exclude . The alternating sequence converges to no point, since some value different from any proposed limit occurs infinitely often.
Sequence index 2026-10-18
A sequence index labels a position in a sequence; the sequence term at that position is its value. For a finite sequence of length , one possible index set is ; a zero-based convention instead uses . Equal sequence terms can have different sequence indices.
Sequence of functions Created 2026-10-18 Updated 2026-10-25
A sequence whose terms are functions on a common domain. Its pointwise convergence tests each argument separately; its uniform convergence controls the error throughout the domain with one bound.
Sequence space Created 2026-10-14 Updated 2026-11-05
A sequence space is a vector space of scalar sequences, closed under coordinatewise addition and scalar multiplication. Examples include the l-p sequence space, the l-infinity sequence space and spaces of convergent sequences.
Sequence term 2026-10-18
A sequence term is an entry of a sequence at a specified sequence index. The sequence index distinguishes the position even when different entries have the same value.
Sequential criterion for a function limit 2026-11-05
For a function between metric spaces, and an accumulation point of , the limit of a function satisfies exactly when every sequence converging to has .
The forward implication substitutes eventual closeness of into the epsilon-delta condition. For the converse, if that condition fails, some permits a choice of withThis sequence approaches while its images fail to approach , a contradiction.
For near zero, take and . Both sequences tend to zero, but their images are and . Hence the limit of a function does not exist there. The metric-space hypothesis matters: sequences do not detect all limits in arbitrary topological spaces.
Series (mathematics) 2026-10-14
A series adds the terms of a sequence in their specified order. Its infinite-sum notation is defined through finite partial sums:when the displayed limit of a sequence exists as a finite number. Otherwise the series is not a convergent series in the ordinary sense. Writing an infinite list of additions does not by itself assign it a finite sum. Cesàro summation is a different prescription, with its own definition.
Two positive series make the distinction concrete. For , the individual terms tend to zero but the harmonic series has unbounded partial sums. For , partial fraction decomposition reveals a telescoping series whose partial sums tend to one. The useful question is how much all the remaining terms can contribute together, rather than only how small the next term looks.
Set-theoretic limit Created 2026-10-25 Updated 2026-10-31
For a sequence of sets, the limit superior of sets consists of points belonging to infinitely many members, while the lower limit consists of points belonging to every sufficiently late member. If the two sets coincide, their common value is the set-theoretic limit.
Shared iterator consumption 2026-10-24


