Shift operator Created 2026-10-14 Updated 2026-11-05
A shift operator translates the components of a function or sequence by a fixed displacement. Bilateral shifts act on doubly infinite sequences; the unilateral shift operator acts on a one-sided sequence space and has distinct forward and backward versions.
Shortest common supersequence Created 2026-10-20 Updated 2026-11-05
A shortest common supersequence of two finite sequences is a shortest sequence containing each as a subsequence. Order is retained, but occurrences need not be contiguous. For and , is such a sequence; is another.
For lengths , its length is , where is the longest common subsequence length. Align a common subsequence of maximal length and merge the unmatched portions to prove the upper bound. Conversely, an alignment inside any common supersequence identifies at least shared positions when its length is , proving the lower bound. This formula is for two inputs; several inputs require a different analysis.
Shortest-processing-time order Created 2026-10-25 Updated 2026-10-31
On one server with all jobs initially available, nonnegative fixed durations and no sequence-dependent setup, a nondecreasing-duration order minimizes the sum of completion times. Swapping adjacent durations reduces their combined contribution by and changes no later completion time, because their total duration is unchanged. Repeated adjacent exchanges remove every inversion. The sum of pre-service waiting times has the same optimum, differing by the fixed total duration.
Sieve distribution Created 2026-09-28 Updated 2026-11-05
Put . A nonnegative sequence has distribution when is multiplicative on the squarefree divisors of , , andfor every .
Sifting function Created 2026-09-24 Updated 2026-11-05
For a finite set of positive integers and a set of prime numbers , the sifting function counts elements divisible by no prime number in strictly below :The strict inequality is the endpoint convention used in the Buchstab identity here. With an empty product, and every element survives.
For a finitely supported nonnegative weighted sequence , use the same notation for . Choosing to be the indicator function of recovers the set version. For , all prime numbers allowed, and , only and are removed as divisors, leaving and giving .
Sigma-algebra Created 2026-09-24 Updated 2026-10-14
A sigma-algebra on a set is a collection of subsets such that , implies , and for all implies . Thus it contains the empty set and is closed under countable intersections as well. This is precisely the closure needed to apply countable additivity without leaving the domain of a measure.
For ,is a sigma-algebra. It describes observations that distinguish from the pair , but cannot distinguish from . The power set provides a finer sigma-algebra with all eight subsets. Both are valid; choosing a sigma-algebra records which questions the model can answer.
On the real numbers, the Borel sigma-algebra contains all open sets and everything generated from them by these operations. The Lebesgue measurable sets form a larger sigma-algebra, including all subsets of Borel null sets. Closure under countable unions accommodates constructions involving an entire sequence of observations or approximations.
Signal Created 2026-10-13 Updated 2026-10-14
A signal is a function or sequence representing a quantity that carries information. An electric potential difference measured over time can be written ; regularly recorded values give a discrete-time signal . The meaning includes the measured quantity, units, time reference and sampling interval. The same list of numbers sampled once per second or once per millisecond describes different physical frequencies.
Sign of an abacus hook-removal sequence Created 2026-09-28 Updated 2026-11-05
Simple-root Hensel lifting by successive residues Created 2026-10-14 Updated 2026-11-05
Simply normal number 2026-10-14
A real number is simply normal in base if each individual digit in its positional notation has limiting digit block frequency . This is the length-one part of the definition of a normal number. It places no equal-frequency requirement on longer words.
For example, is a simply normal number in base two: each binary digit has frequency . But and never occur, and and each have frequency . Thus is not a normal number in base two. Even a sequence that looks more complicated, such as the deterministic Thue–Morse sequence, must be tested against the actual digit block frequency definition; visual complexity is no substitute for it.
The decimal representation makes the same point in base ten. Every digit has frequency , yet the only adjacent pairs areEach has limiting digit block frequency ; the other ninety pairs have frequency zero. A normal number in base ten requires for every one of the hundred pairs. This rational number is a simply normal number in base ten, but it is not a normal number in that base.
Single-box up-move Created 2026-10-05 Updated 2026-11-05
A single-box up-move changes a partition of an integer by adding one to row and subtracting one from row , provided the result remains a partition. It increases exactly the partial sums ending between rows and . A partition dominates precisely when it is obtainable from by a sequence of these moves: fill the first deficient row from the row at the first return of the cumulative deficit to zero. This preserves the partition inequalities and decreases the distance to .
Skip list 2026-10-31
A skip list stores an ordered sequence in a bottom linked list, with successively sparser linked lists above it. Searching moves right while the next key is too small, then down a level. Randomly chosen node heights give logarithmic expected search and update time complexity with a suitable height policy. Repeated keys require distinguishing equal-valued nodes by identity when removing their links.
Sliding-window algorithm 2026-10-20
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.
Slowly varying function Created 2026-10-05 Updated 2026-10-14
A positive measurable function is slowly varying at infinity iffor every fixed . It has regular variation of index zero. “Slowly” concerns relative change under multiplication of the argument; it does not mean that the function must be bounded, have a small derivative, or converge to a finite value.
Every positive constant is a slowly varying function. So are , and for any fixed real number , on . Indeed,The first grows without bound, the second tends to zero, and the constant does neither. Another unbounded example is :This function can grow much faster than while retaining regular variation of index zero.
Even convergence is unnecessary. The bounded functionoscillates between and . It is nevertheless a slowly varying function: the change in the argument of the sine under isand the Lipschitz continuity of the sine makes the logarithm of the ratio tend to zero. The sequences and give the two values and for every nonnegative integer , so there is no limit at infinity.
Contrast this with , which is positive and bounded but is not a slowly varying function. Fix . Along its rescaling ratio is ; along the ratio is . The persistent oscillations prevent even a limit for this one fixed rescaling. It is not regularly varying with any finite index either.
Two bounded oscillating functions: logarithmic rescaling makes one ratio approach one, while the other keeps oscillating
. The horizontal coordinate is , and the fixed rescaling is . The displayed range illustrates the formulas; the limiting claims follow from the arguments in the text. Details.The useful distinction is whether a fixed proportional change of input eventually produces a negligible proportional change of output. A slowly varying function can therefore preserve the scaling exponent of a power law while changing its magnitude substantially. The decomposition in regular variation explains why a logarithmic factor can matter in numerical estimates without changing the limiting exponent.
Sortedness 2026-10-13
For an output sequence of length , sortedness meansunder the chosen total order on sort keys. Its transitivity also gives whenever . An empty sequence and a one-entry sequence satisfy sortedness without any adjacent comparison. For longer sequences, checking adjacent pairs suffices; checking only the first and last sort keys does not. For example, passes an endpoint comparison but fails sortedness at . Sortedness alone says nothing about which input entries survived.
Sorted run 2026-10-31
Sorting 2026-10-20
Rearranging a finite sequence according to a specified order while preserving its entries and their multiplicities. A sorting algorithm performs this operation; lexicographic order supplies a common order for tuples or strings.
Sorting algorithm 2026-10-13
A sorting algorithm rearranges a finite sequence into nondecreasing order under a chosen total order on its keys. Its output must contain every input entry exactly once, including repetitions: producing ordered values is insufficient if entries are lost. Merge sort is one such algorithm; stable sorting adds a requirement about equal keys.
Sorting creates reusable structure: equal sort keys become adjacent, and a sorted array supports binary search. However, an algorithm correctness check must establish both sortedness and sorting permutation preservation. Replacing every entry by the smallest key can produce ordered keys while destroying the original data. Stable sorting imposes a third condition when equal sort keys occur: retain their arrival order.
For example, take complete sorting records , with the first component as the sort key and the letter as associated data. A correct output is . The sort keys are ordered, every complete sorting record remains, and the equal-key pairs keep before and before . The output satisfies sortedness and sorting permutation preservation, but fails stable sorting. The output has the right multiset of sort keys but loses and duplicates ; it fails sorting permutation preservation of complete sorting records.
To express stable sorting precisely, label every input occurrence by its original position, even when two complete sorting records have identical contents. Let be the output position of the occurrence originally at position . Besides sortedness and sorting permutation preservation, requireHere is the sort key function. Sorting by the pair under lexicographic order gives the same order as stable sorting by : the original position breaks ties without discarding associated data. For a two-field ordering, first apply stable sorting by the secondary sort key, then apply stable sorting by the primary sort key. The second pass retains the secondary order within each group of equal primary sort keys. For instance, first becomes by letter, then by number.
Sorting permutation preservation 2026-10-13
The output of a sorting algorithm must be a permutation of the complete input sequence. For equal lengths , require a permutation of such thatEquivalently, the input and output have the same multiset of complete entries: each entry has the same multiplicity. Equality of the underlying sets is insufficient; and have the same set of values and the same length but different multisets. When tracking occurrences rather than contents, retain original identity labels to check that each one is moved exactly once. A swap preserves this multiset automatically; an overwrite need not.
Sparse peaks can determine a limit superior 2026-10-14
Define a sequence by when is a power of two, including , and otherwise. Every tail of a sequence contains both a later power of two and a later nonpower. Therefore and , and the sequence does not converge. Its peak indices become increasingly sparse, yet never stop appearing.
Through index , the number of peaks is , so their fraction isThe set of powers of two has natural density zero. The same fraction is the Cesàro mean of the first terms, which tends to zero even though the limit superior stays one. At , eleven peaks give mean . An average and a long-run upper edge answer different questions about the same sequence.

