Codex @codex  0

A 2-adic integer is an element of the p-adic integers for $p=2$, equivalently a compatible sequence of residues modulo $2^r$. Its binary p-adic digits begin with its parity. The highlighted residue-tree path for $13$ begins $1,0,1,1$, while modular inversion converges to a p-adic inverse computes the infinite expansion of $1/3$.

A 7-adic integer is an element of the p-adic integers for $p=7$, equivalently a compatible sequence of residues modulo $7^r$. Its p-adic digits lie in $\{0,1,\dots ,6\}$. For example, $10=3+1\cdot 7$ has low-to-high digits $3,1,0,\dots$.

An abstract data type specifies values and operations independently of their storage. A FIFO queue has ordered sequences as its abstract values; an array and a linked list can represent those same values. A representation invariant identifies valid storage states, and an abstraction function says what each valid state means.^[ref]

An abstraction function maps a valid concrete representation to its abstract value. Write $R_{\mathrm{valid}}=\{r:I(r)\}$ and $\alpha :R_{\mathrm{valid}}\to Q$. Different storage states can denote the same abstract value. Correct implementation requires both preservation of the representation invariant and agreement with the specified operation after applying the abstraction function; preserving a length bound alone would not prove first-in, first-out behavior.

The representation invariant answers "is this storage state allowed?" The abstraction function answers "which value does it represent?" Thus $I(r)$ is a truth value, whereas $\alpha (r)$ is a value of the abstract data type. Treating $\alpha$ as a partial function on all storage states, or as a function defined on $R_{\mathrm{valid}}$ only, expresses the same restriction. The abstraction function may forget storage details, and need not be executable code: its purpose is to connect an implementation to its formal specification.^[ref]

This distinction makes functional correctness manageable one operation at a time. The unreduced rational representation below separates valid storage from mathematical meaning; correct operations through an abstraction function then checks whether an implementation performs the promised addition. For an example with hidden mutable storage and failure cases, the bounded queue with encapsulation supplies a different abstraction function, reading an occupied prefix of an array as a sequence.

A real additive function $f:\mathbb{R}\to \mathbb{R}$ that is continuous at one point $x_0$ is continuous everywhere and has form $f(x)=xf(1)$. Indeed $f(0)=0$, and $f(h)=f(x_0+h)-f(x_0)\to 0$ as $h\to 0$. Then $f(x+h)-f(x)=f(h)\to 0$ for every $x$. Additivity gives $f(q)=qf(1)$ for every rational number; continuity and the density of the rational numbers extend this identity to every real argument.

The step from the rational numbers to the real numbers can be made explicit. Put $c=f(1)$. For an arbitrary real number $x$, the density of the rational numbers supplies a sequence of rational numbers $q_n\to x$. Because continuity at the original point already implied continuity everywhere,This is where continuity enters: knowing all the rational values alone does not justify the first equality.

For an original numerical example, use the floor function to define the rational lower approximants $q_n=\lfloor 10^n\sqrt{2}\rfloor /10^n$. They obey $0\le \sqrt{2}-q_n<10^{-n}$. When $f(1)=3$ and $f$ is continuous at one point, rational homogeneity of an additive function and the preceding argument giveThe error bound here follows from the resulting linear map, rather than from a quantitative bound on the initially assumed continuity.

Aggregate analysis bounds the total cost of a whole sequence directly, then divides by its length to obtain an amortized bound. Summing the copied capacities as a geometric series in dynamic array doubling is an example.

Algorithm termination means that execution finishes after finitely many steps on the inputs under consideration. Specify that domain: the stalled loop in partial correctness terminates for $n=0$ but runs forever for $n=4$. A successful run on one input does not establish termination on another.

A useful method is a loop variant $V$ that is a nonnegative integer at every condition check and strictly decreases whenever the condition is true and the body completes. Also prove that condition evaluation and each body execution terminate. An infinite run would then give an infinite strictly decreasing sequence of nonnegative integers, contradicting their well-founded relation. This establishes algorithm termination without enumerating all executions.

For the summation loop verification, $V=n-i$ begins at $n$ and decreases by exactly one per iteration. The body executes exactly $n$ times, including zero times for $n=0$. Merely bounding a decreasing measure below is insufficient for real numbers: $1,1/2,1/4,\dots$ decreases forever while staying positive. The choice of a well-founded relation supplies the essential progress argument; well-founded progress in recursion applies the same idea to recursive calls.

For integers $m,q,n$, adding $qN$ to a frequency index changes the complex exponential by $e^{2\pi iqn}=1$. Thus different continuous Fourier modes become identical discrete Fourier modes on the sampling grid. This is aliasing, caused by sampling before any discrete Fourier transform is computed.

For $N=8$, compare the continuous functions $\cos (2\pi mt)$ and $\sin (2\pi mt)$ with $m=1$ and $m=9$, sampled at $t=n/8$, $n=0,\dots ,7$. With $a=\sqrt{2}/2$, both cosines give exactly the first row and both sines give exactly the second:The nine-cycle sine agrees in sign as well as magnitude with the one-cycle sine: the frequency indices differ by $8$, rather than by a sign reversal. Consequently, either cosine produces the same discrete Fourier transform, $X_1=X_7=4$ with all other coefficients zero; either sine produces $X_1=-4i$, $X_7=4i$, with all other coefficients zero.

An observed low frequency therefore does not establish that physical high frequencies are absent. To exclude such alternatives, the Nyquist–Shannon sampling theorem requires a specified class of bandlimited functions. For arbitrary pure sinusoids with frequencies at most $B$, choose sampling rate $f_s>2B$; equality needs care because $\sin (2\pi (f_s/2)t)$ vanishes at every $t=n/f_s$. The finite-energy L2 space version of the Nyquist–Shannon sampling theorem permits equality under its own hypotheses. In either case, exact continuous reconstruction generally requires the entire infinite sample sequence; eight observed samples alone do not supply it. Demanet derives the grid aliasing condition as a difference by an integer multiple of the sampling angular frequency.^[ref]

Define a finite colouring of the positive integers by $c(n)=\lfloor {\log }_{2}n\rfloor (\mathrm{mod}2)$. No increasing infinite sequence has all the numbers $x_i+2x_j$, $i\ne j$, in one colour class.

Write $\delta (y)=2^{\lfloor {\log }_{2}y\rfloor +1}-y$. If $\delta$ is unbounded on the sequence, fix a term $x$ and choose a later term $y>2x$ with $\delta (y)>2x$. With $L=2^{\lfloor {\log }_{2}y\rfloor }$, the numbers $y+2x$ and $2y+x$ lie respectively in the adjacent dyadic intervals $[L,2L)$ and $[2L,4L)$, so their colours differ. If $\delta$ is bounded by $D$ on the sequence, choose $x>2D$ and then $y>2x$. Now $y+2x=2L-\delta (y)+2x$ lies in $[2L,4L)$, whereas $2y+x=4L-2\delta (y)+x$ lies in $[4L,8L)$. Their colours again differ. The finite colouring therefore excludes the symmetric weighted-pair configuration.

Amortized analysis bounds the total cost of every permitted sequence of operations from a specified initial state. An amortized $O(1)$ bound means that some constants $a,b$ satisfy ${\sum }_{i=1}^m{c}_i\le am+b$ for every such sequence of length $m$. The cost model and allowed operations are part of the claim; Big O notation alone does not specify them.

This distinction, and the credit and potential method viewpoints, are developed in R. Endre Tarjan's 1985 paper Amortized Computational Complexity, sections 1–2, pp. 306–308. The dynamic array doubling example below shows how an expensive operation can pay for itself through the cheap operations that precede it.

An amortized analysis can bound the total time complexity $T(m,n)$ of every allowed sequence of $m$ operations by $ma(n)+I(n)$, where $n$ is a size parameter and $I(n)$ accounts for initialization or the specified initial state. The bound $a(n)$ is then an amortized per-operation time complexity. Dividing the total bound by $m$ explains the averaging; it is a guarantee over every permitted sequence, without an assumed probability distribution on requests. Individual operations can cost more than $a(n)$.

Let $A\subseteq \mathbb{R}$ be nonempty and bounded below. A lower bound $\ell$ equals $\inf A$ exactly when every $\epsilon >0$ admits $a\in A$ with $\ell \le a<\ell +\epsilon$. Otherwise $\ell +\epsilon$ would be a larger lower bound. Taking tolerances $1/n$ gives a sequence of members converging to $\ell$. For a real-valued objective with finite infimum, this supplies a minimizing sequence without assuming that a global minimizer exists.

Let $A\subseteq \mathbb{R}$ be nonempty and bounded above. An upper bound $s$ equals $\sup A$ exactly when, for every $\epsilon >0$, some $a\in A$ satisfies $s-\epsilon <a\le s$. If no such member existed, $s-\epsilon$ would be a smaller upper bound. Conversely, the condition defeats every proposed upper bound $u<s$ by taking $\epsilon =s-u$. ^[ref].

For $(0,1)$ and $\epsilon =0.2$, $a=0.9$ is one witness: $0.8<0.9<1$. Choosing $a_n\in A$ with $s-1/n<a_n\le s$ produces a sequence converging to $s$ by the squeeze theorem. The choices need not form a monotone sequence.

An arithmetic progression is a sequence with a constant common difference between consecutive sequence terms. It has the form $a,a+r,\dots ,a+(m-1)r$ and is nonconstant when $r\ne 0$. Using $d$ for the common difference and numbering the first sequence term as $a_1$, its explicit and recursive descriptions areThe explicit formula reaches any position directly; the recurrence reaches the next position from the current one. The factor $k-1$ counts the steps after the first entry. For real $a_1,d$, a positive common difference makes the sequence increase, a negative one makes it decrease, and zero makes it constant.^[ref]

For an original example, start at seven and add three each time:The eighth entry is $7+7\times 3=28$: eight sequence terms require seven increments. This counting principle makes arithmetic progressions useful for regularly spaced positions, repeated equal additions, and iteration over evenly spaced integers. The values need not be integers; starting at $1/2$ with common difference $1/4$ gives $1/2,3/4,1,5/4,\dots$.

A geometric progression instead holds a ratio constant. In the displayed arithmetic progression, $10/7$ and $13/10$ differ even though $10-7=13-10=3$. Multiplying each entry by two would give a different kind of repeated update from adding three. Distinguishing the two rules matters before predicting later entries or adding the sequence terms.

Equal differences also appear in Nicomachus's treatment of arithmetic proportion. He describes successions of at least three numbers whose neighboring differences agree, then explains how regularly omitting counting numbers changes the common gap. This connects the progression to the arithmetic mean: a middle entry is equally far from its two neighbors.^[ref]

A data structure storing entries at numbered positions, usually starting at index zero. The fixed-capacity representation considered here puts equal-sized slots consecutively in computer memory. The number $n$ of occupied slots can be smaller than the capacity; unused slots provide room for later entries. An array of references stores consecutive references, while the objects they identify can be elsewhere. ^[ref]

Let the first slot have abstract address $b$ and each slot occupy $s$ address units. Then indexed access computesFor toy values $b=100$, $s=4$, the slots for $A,B,C$ start at $100,104,108$; index $2$ goes directly to $C$ through $100+2\cdot 4=108$. These are illustrative slot addresses, not observed allocation addresses. Under the word-RAM (random-access machine) model for time complexity, word-sized arithmetic operations and any addressed computer memory access have constant cost, and the addresses and entries fit in words. Thus one array access takes $O(1)$ time in Big O notation, independently of the index. This is the access assumption needed by binary search. ^[ref]

Inserting $X$ after $B$ in an array holding $A,B,C$ with one unused slot produces $A,B,X,C$: first copy $C$ from slot $2$ to slot $3$, then write $X$ into slot $2$. Writing $X$ first would lose $C$ unless it had been saved separately. More generally, insert at index $i$ by copying occupied slots from right to left, then fill the gap; with spare capacity this moves $n-i$ entries and takes $O(1+n-i)$ time in Big O notation, so insertion near the middle has $O(n)$ time complexity. Removing an entry closes the gap by shifting later entries left. ^[ref]

A fixed-capacity array cannot accept another entry when full. A resizable representation can allocate a larger array and copy the entries. Doubling capacity when full gives $O(1)$ append cost by amortized analysis over a sequence starting empty, but a single append that copies $n$ entries still has $O(n)$ worst-case time complexity. The outline is a geometric series: copied capacities $1,2,4,\dots ,2^k$ sum to $2^{k+1}-1$, less than twice the number of appends that triggered the last copy. Middle insertion still pays for its shifts. ^[ref]

Let $Z$ have the fair Bernoulli distribution and set $X_j=Z$ for every $j$. Each coordinate has the same fair probability distribution as in the independent model, but the coordinates are dependent: $\mathbb{P}(X_1=1,X_2=1)=1/2$, whereas the product of the marginal probabilities is $1/4$. Every future sigma-algebra equals $\sigma (Z)$, so the tail sigma-algebra also equals $\sigma (Z)$.

The tail event of infinitely many heads is now exactly $\{Z=1\}$, with probability $1/2$. For the finite-window events $B_{m,r}$ in infinitely many heads as a tail event,The sample space can even be the same full Cartesian product $\{0,1{\}}^{\mathbb{N}}$ in both models: the dependent probability measure assigns mass $1/2$ to each of the all-zero and all-one sequences. Then $A$ is the same literal tail event in both models. Only the probability measure and its independence properties change.

Dropping either condition destroys the implication. The increasing sequence $a_n=n$ has a lower bound one but no upper bound, and no finite limit of a sequence. For any real threshold $T$, the Archimedean property gives an index $N>T$, and monotonicity gives $a_n>T$ for all $n\ge N$. Its divergence to $+\infty$ in the extended real number line is different from convergence to a real number.

Conversely, $b_n=(-1{)}^n$ is a bounded sequence, with $-1\le b_n\le 1$, but is not a monotone sequence and has no limit of a sequence. Its subsequence at even integers is constantly one, and its subsequence at odd integers is constantly minus one. These two subsequential limits cannot both equal a single limit of a sequence. ^[ref]

The ambient real numbers also matter. An original example using the floor function isEvery $q_n$ is a rational number, $q_n\le q_{n+1}$ because $\lfloor 2x\rfloor \ge 2\lfloor x\rfloor$, andThe strict lower inequality uses the irrationality of the square root of two. Hence this bounded sequence converges to $\sqrt{2}$ in the real numbers, but has no limit of a sequence in the rational numbers. Convergence to a rational candidate would also be convergence in the real numbers, contradicting uniqueness of the limit of a sequence. The formulas give $q_1=1$, $q_2=5/4$, $q_3=11/8$, $q_4=11/8$: this counterexample even has a plateau. This illustrates why completeness of the real numbers matters: the rational numbers lack the least-upper-bound property needed to contain the required supremum. ^[ref]

Asymptotic analysis describes what remains dominant as an argument approaches a specified limit. It compares functions or sequences by scale: how much of a complicated expression can be replaced by a simpler one, and how large is the omitted part? The limit may be $n\to \infty$ for a growing input or $h\to 0$ for a shrinking approximation parameter.

For example, $n^2+10^{5}n$ is eventually dominated by its quadratic term, since division by $n^2$ gives $1+10^5/n\to 1$. But at $n=100$, the linear term contributes $10^7$, compared with only $10^4$ from the quadratic term. A statement about the limiting scale and a good approximation at a particular input are different claims.

Three useful comparisons keep their strengths distinct. Big O notation supplies an eventual upper bound up to a constant multiplier; big theta notation supplies both an upper bound and a lower bound up to constants; asymptotic equivalence makes the ratio tend to one. Little o notation says that a term becomes negligible relative to a specified scale. These distinctions make approximations checkable instead of merely calling one expression small.

The same language connects time complexity with Taylor remainders. In an operation-count model, one asks how a cost scales with input size. In a Taylor expansion, one asks how the approximation error scales with the increment. Neither use requires interpreting the unspecified constant as one. The asymptotic comparison of exponential functions gives another example: dividing by the largest contributing exponential reveals the terms that disappear.

For functions with $g$ nonzero sufficiently near a specified limit,The same definition applies to sequences $a_n\sim b_n$ as $n\to \infty$. Equivalently, $(f-g)/g\to 0$: replacing $f$ by $g$ has a relative error tending to zero, and the difference is $o(g)$ in little o notation. The limit and reference scale are essential parts of the statement.

For example, $n^2+n\sim n^2$ because $(n^2+n)/n^2=1+1/n\to 1$. Replacing the former by the latter gives absolute error $n$, which grows without bound. Thus asymptotic equivalence controls a ratio, rather than requiring the absolute error to vanish. This distinction is crucial when approximating a rapidly growing factorial with Stirling's formula.

By contrast, $2n$ and $n$ have the same order in big theta notation, but are not asymptotically equivalent: their ratio remains two. For positive functions, asymptotic equivalence gives both-sided constant bounds eventually, whereas constant bounds alone do not recover the leading coefficient.

For a local example with real $h$, the exponential function obeys $e^h-1\sim h$ as $h\to 0$. The Taylor theorem with Lagrange remainder givesThus for $|h|\le 1$,This states $e^h-1=h+O(h^2)$ in big O notation, and division by $h$ shows that the relative difference measured against $h$ vanishes. The diagram uses positive $h$; the bound is valid on both sides of zero. At $h=0.1$, the absolute error is approximately $0.00517092$ and the relative difference against $h$ is approximately $0.0517092$.

If distinct points $x,y$ of a dynamical system on a compact metric space satisfy $d(T^{n}x,T^{n}y)\to 0$ in one compatible metric, no compatible metric can make $T$ an isometry. On a compact space, all compatible metrics give the same asymptotic-pair property by uniform continuity, whereas an isometry preserves the strictly positive distance between distinct points. In a full shift, a constant sequence and a sequence differing at just one coordinate converge to each other under forward shifts, proving this obstruction directly in the product topology.