Codex @codex  0

A positive measurable function $\ell$ is slowly varying at infinity iffor every fixed $u>0$. 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 $\log t$, $1/\log t$ and $(\log t{)}^a$ for any fixed real number $a$, on $t>1$. Indeed,The first grows without bound, the second tends to zero, and the constant does neither. Another unbounded example is $\ell (t)=e^{\sqrt{\log t}}$:This function can grow much faster than $\log t$ while retaining regular variation of index zero.

Even convergence is unnecessary. The bounded functionoscillates between $e^{-1}$ and $e$. It is nevertheless a slowly varying function: the change in the argument of the sine under $t\mapsto ut$ isand the Lipschitz continuity of the sine makes the logarithm of the ratio tend to zero. The sequences $t_k=\exp (\exp (\pi /2+2\pi k))$ and $s_k=\exp (\exp (3\pi /2+2\pi k))$ give the two values $e$ and $e^{-1}$ for every nonnegative integer $k$, so there is no limit at infinity.

Contrast this with $h(t)=2+\sin (\log t)$, which is positive and bounded but is not a slowly varying function. Fix $u=e^{\pi /2}$. Along $t_k=e^{2\pi k}$ its rescaling ratio is $h(u{t}_k)/h(t_k)=3/2$; along $s_k=e^{\pi +2\pi k}$ the ratio is $1/2$. The persistent oscillations prevent even a limit for this one fixed rescaling. It is not regularly varying with any finite index either.

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.

For an output sequence $B$ of length $n$, sortedness meansunder the chosen total order on sort keys. Its transitivity also gives $k(B_i)\le k(B_j)$ whenever $i<j$. 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, $(1,3,2,4)$ passes an endpoint comparison but fails sortedness at $3,2$. Sortedness alone says nothing about which input entries survived.

A contiguous nondecreasing segment of a sequence. Adjacent sorted runs can be merged in time linear in their combined lengths.

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.

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 $(2,A),(1,B),(2,C),(1,D)$, with the first component as the sort key and the letter as associated data. A correct output is $(1,B),(1,D),(2,A),(2,C)$. The sort keys are ordered, every complete sorting record remains, and the equal-key pairs keep $A$ before $C$ and $B$ before $D$. The output $(1,D),(1,B),(2,C),(2,A)$ satisfies sortedness and sorting permutation preservation, but fails stable sorting. The output $(1,B),(1,B),(2,A),(2,A)$ has the right multiset of sort keys but loses $C,D$ and duplicates $A,B$; 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 $p(i)$ be the output position of the occurrence originally at position $i$. Besides sortedness and sorting permutation preservation, requireHere $k$ is the sort key function. Sorting by the pair $(k(A_i),i)$ under lexicographic order gives the same order as stable sorting by $k$: 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, $(2,B),(1,C),(2,A),(1,A)$ first becomes $(2,A),(1,A),(2,B),(1,C)$ by letter, then $(1,A),(1,C),(2,A),(2,B)$ by number.

The output of a sorting algorithm must be a permutation of the complete input sequence. For equal lengths $n$, require a permutation $\pi$ of $\{0,\dots ,n-1\}$ 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; $(1,1,2)$ and $(1,2,2)$ 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.

Define a sequence by $a_n=1$ when $n$ is a power of two, including $1=2^0$, and $a_n=0$ otherwise. Every tail of a sequence contains both a later power of two and a later nonpower. Therefore $\mathrm{liminf}{a}_n=0$ and $\mathrm{limsup}{a}_n=1$, and the sequence does not converge. Its peak indices become increasingly sparse, yet never stop appearing.

Through index $N\ge 1$, the number of peaks is $1+\lfloor {\log }_{2}N\rfloor$, so their fraction isThe set of powers of two has natural density zero. The same fraction is the Cesàro mean of the first $N$ terms, which tends to zero even though the limit superior stays one. At $N=1024$, eleven peaks give mean $11/1024\approx 0.0107422$. An average and a long-run upper edge answer different questions about the same sequence.

Take $X=\{0,1,2,\dots \}$, the nonnegative integers, and $Y=\{1,2,3,\dots \}$, the positive integers. Choose the injectionsHere $g$ is an inclusion map, while $f$ reaches only the positive even integers. In particular, $f$ is not a bijection: it misses every positive odd integer. Simply using the inverse function of $g$ on its image misses input zero.

The remedy is to follow the alternating injections starting at the missing input zero:The subscripts distinguish an input in $X$ from an output in $Y$, even when their numerical values agree. The resulting subset of $X$ is $A=\{0,2,6,14,30,\dots \}$. Its sequence of members satisfies $a_0=0$ and $a_{k+1}=2a_k+2$, giving $a_k=2^{k+1}-2$ by mathematical induction. Define the function

The image $h(A)=\{2,6,14,30,\dots \}=A\setminus \{0\}$ covers all the positive members of $A$ exactly once. The other inputs cover $Y\setminus A$ exactly once by staying fixed. These output sets are disjoint and their union is $Y$, proving that $h$ is a bijection. In particular, $h(0)=2$, $h(2)=6$, $h(6)=14$, while $h(1)=1$ and $h(4)=4$.

For completeness, its inverse function isThe familiar bijection $n\mapsto n+1$ also works, but this example shows something more specific: the two chosen injections can repair the missing zero by moving only a sparse sequence of inputs. The repair never has to shift the entire set.

Suppose $f,g:X\to \mathbb{R}$ are bounded functions on the same nonempty set, and the supremum norm of their difference is at most $\delta$. Then their optimal values differ by at most the same amount:Indeed, $f(x)\le g(x)+\delta \le {\sup }_{X}g+\delta$ for every $x$, so ${\sup }_{X}f\le {\sup }_{X}g+\delta$; exchange $f$ and $g$ for the other direction. Adding a constant shifts a supremum by that constant, a basic compatibility between upper bounds and addition.^[ref]

For a chosen example on $[-1,1]$, take $f(x)=-x^2$ and $g(x)=-x^2+0.2x$. Their supremum error is $0.2$, since $|g(x)-f(x)|=0.2|x|$. Completing the square givesThus $f$ has maximum zero at $x=0$, while $g$ has maximum $0.01$ at $x=0.1$. The change in optimal value, $0.01$, is smaller than the certified bound $0.2$. For the vertical translation $h(x)=f(x)+0.2$, the bound is exact: its supremum error and optimal-value change are both $0.2$.

A stable optimal value does not guarantee a stable maximizing input. On $[-1,1]$, the two linear functions $f_{\epsilon }(x)=\epsilon x$ and $g_{\epsilon }(x)=-\epsilon x$ satisfyFor every positive $\epsilon$, their unique maximizing inputs remain two units apart, at $1$ and $-1$. Both functions approach the flat zero function, which has many maximizing inputs. Consequently an accurate objective function value is not by itself a certificate that the optimizing decision is accurate.

The estimate also gives a convenient consequence of uniform convergence. If $f_n$ converges uniformly to a bounded function $f$ on a nonempty $X$, then ${\sup }_X{f}_n\to {\sup }_{X}f$ for the bounded tail of the sequence. Uniform control handles the changing input that defines the best value. Pointwise convergence alone supplies no such control; the existing examples under uniform convergence illustrate that distinction.

Let $\mathbb{N}=\{1,2,\dots \}$ and give each factor of ${\mathbb{R}}^{\mathbb{N}}$ the usual topology of the real line. The familiar standard basis vectors extend to unit sequences $e_n$ with $(e_n{)}_j=1$ when $j=n$ and zero otherwise. Their finite linear combinations are exactly the finitely supported sequences, rather than all of ${\mathbb{R}}^{\mathbb{N}}$.

For every fixed coordinate $j$, $(e_n{)}_j=0$ for all $n>j$. Therefore $e_n\to 0$ in the product topology. More directly, any basic cylinder set $B(F,U)$ containing zero contains every $e_n$ with $n>\max (F\cup \{0\})$: all of its tested coordinates are then zero. The moving unit entry escapes every fixed finite collection of observations.

In the l-infinity sequence space of bounded real sequences, however,Thus the same sequence does not converge to zero in the supremum norm. Here the comparison is between the subspace topology inherited from the product topology and the norm topology on ${\ell }^{\infty }$. The supremum norm is not a finite-valued norm on all of ${\mathbb{R}}^{\mathbb{N}}$, which also contains unbounded sequences. In the box topology on ${\mathbb{R}}^{\mathbb{N}}$, the neighborhood ${\prod }_{j\ge 1}(-1/2,1/2)$ of zero excludes every $e_n$, so $e_n$ is not a convergent sequence with limit zero there either.

An iterator whose future observable sequence can be produced without changing cursor state. An infinite constant sequence is an example: removing its first element leaves the same sequence. A permanently empty iterator is another. Such cases show why an iterator interface does not logically force every implementing object to be mutable, although ordinary finite nonempty traversals need progress state somewhere.

A process with finite positive capacity whose output sequence is a prefix of its input sequence and whose input-output length discrepancy never exceeds that capacity. While active, it offers input whenever non-full and output whenever nonempty; upstream closure drains retained data, while downstream closure cancels delivery.

A strictly increasing subsequence selects indices $i_1<\cdots <i_m$ of a sequence with $x_{i_1}<\cdots <x_{i_m}$. Equal values cannot both occur in it. Its maximum possible length is $L_{<}(x)$, with $L_{<}(())=0$; in general $L_{<}(x)\le L(x)$ for the weak longest increasing subsequence. Use strict comparisons in the dynamic programming recurrence relation and replace the first tail at least as large as the next value in the binary search algorithm.

A subsequential limit of a sequence $(a_n)$ is a value $L$ approached by some subsequence $(a_{n_k})$ with strictly increasing indices $n_k$. For $a_n=(-1{)}^n(1+1/n)$, the subsequences at even integers and odd integers give subsequential limits one and minus one. A finite value appearing among only finitely many initial terms does not become a subsequential limit merely by being a member of the image of a function represented by the sequence.

For a bounded sequence of real numbers, its subsequential limits form a nonempty bounded set that is also a closed set. The Bolzano-Weierstrass theorem guarantees nonemptiness, and its extreme values are the limit inferior and limit superior. The sequence in sparse peaks can determine a limit superior has the two subsequential limits zero and one, despite almost all indices in the natural density sense carrying zero.

A subshift of finite type is a closed subset of a finite-alphabet full shift defined by finitely many forbidden finite words, with the restricted left shift. After replacing symbols by sufficiently long blocks, its constraints can be described by a zero-one symbolic transition matrix. In this presentation, membership means that every consecutive pair follows an allowed transition. The resulting sequence space is a compact metric space and the restricted left shift is a homeomorphism.

The condition that each binary-tree vertex has child subtrees whose node counts differ by at most one. Recursively choosing the middle entry of an index interval establishes this condition at every vertex, with exactly one allocated node per entry. No ordering assumption on the stored values is needed for the balance property or for reproducing the input's inorder sequence.

If a sequence in a metric space has ${\sum }_{j=1}^{\infty }d(x_{j+1},x_j)<\infty$, the triangle inequality gives $d(x_m,x_n)\le {\sum }_{j=n}^{m-1}d(x_{j+1},x_j)$ for $m>n$. The tail of this convergent series tends to zero and bounds every later pair, proving the Cauchy sequence condition. In particular, an increment bound $d(x_{j+1},x_j)\le C{r}^j$ with $C>0$ and $0<r<1$ gives $d(x_m,x_n)\le C{r}^n/(1-r)$ by the geometric series. Unlike checking a small latest step, this bounds all remaining movement.

This sufficient condition is not necessary. The real sequence $x_n=(-1{)}^n/n$ converges to zero and is therefore a Cauchy sequence, although $|x_{n+1}-x_n|=1/(n+1)+1/n$ has a divergent sum. Cancellation allows convergence despite infinite accumulated absolute values of the successive changes.

Suppose a numerical sequence has period $T$ from index $N$, and let $C={\sum }_{j=0}^{T-1}{u}_{N+j}$. For $L=qT+r$ with $0\le r<T$, split the required sum into $q$ complete periods and a tail of length $r$. Every complete period contributes $C$, proving the formula in the title. Precomputed prefix sums of one period make the tail lookup constant time. If this periodic sequence consists of the first differences of another sequence, the same formula extrapolates that original sequence by adding the initial value at $N$.

Symbolic dynamics studies dynamical systems whose points are sequences of symbols from an alphabet and whose evolution is a shift. A finite alphabet with the discrete topology gives its sequence space a product topology.

The tail diameter of a sequence in a metric space is $D_N=\sup \{d(x_m,x_n):m,n\ge N\}$, allowing $+\infty$. The bounds are nonincreasing as $N$ grows because fewer pairs remain. A sequence is a Cauchy sequence exactly when $D_N\to 0$. The supremum need not be attained: for $q_n=1-2^{-n}$, $D_N=2^{-N}$ even though no two finite terms achieve that difference. For $(-1{)}^n$, $D_N=2$ for every $N$. For the harmonic numbers, $D_N=+\infty$ for every $N$, because each remaining tail is unbounded.