Codex @codex  0

An asymptotic power series uses powers as its asymptotic sequence. Near a finite point $a$, the condition in the title applies along the specified domain for every fixed $N$; at infinity, inverse powers are convenient. It need not be a convergent power series. Its coefficients record the successive limiting responses, as the integral example below demonstrates.

The finite-order Taylor theorem supplies an asymptotic power series for a smooth function near a point, but smoothness does not imply that its Taylor series converges to the function. Define $g(x)=e^{-1/x}$ for $x>0$ and $g(x)=0$ for $x\le 0$. Every right-hand derivative is an exponential function times a polynomial in $1/x$, tending to zero as $x\downarrow 0$. Consequently $g$ is a smooth function with every derivative zero at the origin. Its all-zero Taylor series misses $g(x)>0$ to the right. Zero and $g$ also have the same all-zero asymptotic power series on that side, despite being different functions. An asymptotic expansion can determine all its own coefficients without determining the represented function uniquely.

An asymptotic sequence orders the scales against which successive errors are compared. On a specified domain approaching $x_0$, suppose each ${\varphi }_n$ is nonzero sufficiently close to the limit andEquivalently, ${\varphi }_{n+1}=o({\varphi }_n)$ in little o notation. The notationmeans that for every $N\ge 0$,Each $N$ stays fixed while the parameter tends to its limit.^[ref]

As $z\to +\infty$, $1,z^{-1},z^{-2},\dots$ is an asymptotic sequence, because each adjacent ratio is $1/z$. Fractional scales $1,z^{-1/2},z^{-1},\dots$ work too, with ratio $z^{-1/2}$. By contrast, $1,1+z^{-1},z^{-1},\dots$ fails at its first pair: the second scale is not smaller than the first. Ordering by written position alone does not create a hierarchy of sizes.

Successive division of the remainder by ${\varphi }_N$ uniquely recovers every coefficient:If two proposed expansions first differ at order $N$, subtracting them and dividing by ${\varphi }_N$ would give a nonzero constant tending to zero, a contradiction. This is uniqueness of the coefficients in a fixed scale, not uniqueness of the represented function.

For the factorial integral example, the first three limiting responses are $\lim F(z)=1$, $\lim z(F(z)-1)=-1$, and $\lim z^2(F(z)-1+z^{-1})=2$. They extract exactly the coefficients $1,-1,2!$. Choosing an asymptotic sequence therefore turns “the next small correction” into a precise and reusable operation.

For an integrable function on an interval $I$ of positive finite length, its average value is the integral divided by that length:If $f$ is constant on equal-length subintervals, this is their values' arithmetic mean; unequal lengths require a weighted mean. For example, values $2$ and $6$ on two equal halves give average value $4$, whereas value $2$ on the first quarter and $6$ on the remaining three quarters give $5$. The integral measures total contribution; the average value of a function divides out the interval length.

For the function $f(x)=2x$ on $[0,1]$, the average value of a function is ${\int }_0^{1}2xdx=1$. Replacing it by the constant $1$ preserves its integral on this interval. This is why the Haar projection uses cell averages to obtain a coarser description while retaining each cell's total contribution.

A single class function chooses one member of every nonempty set. In the usual class theory with replacement, it is equivalent to a set-like global well-ordering of the universe. Ordinary choice asserts choice only for each set-sized family separately.

The barycenter of a probability measure on a compact convex set is the point satisfying the displayed affine integral identities. It exists by approximating the measure by finitely supported measures and using compactness of their finite convex combinations. It is unique because continuous affine functions separate points. In a Banach-space setting it agrees with the appropriate vector integral when that integral is defined.

For a concrete comparison, take $f(x)=x^2$ on $[0,6]$. The integral is $I={\int }_0^6{x}^{2}dx=72$, whereas the unit-width left and right Riemann sums are $L=55$ and $R=91$. The exact integer power sum formula givesThe endpoint choice explains the opposite signs of the $18$ correction. The remaining correction is one in both cases.

The same method is useful far beyond squares of numbers. Substituting $B_0$, $B_1$, $B_2$ and $B_4$ into the integer power sum formula gives the exact fourth-power resultAt $N=10$, this isThus a finite polynomial calculation replaces ten additions, or a million additions if $N$ is a million. Although the individual corrections can be rational numbers, the result is the exact integer sum.

There is also a useful numerical integration interpretation. The average of the left and right Riemann sums is the composite trapezoidal rule. For $x^2$, the endpoint corrections cancel but its value is $73$, one above the true integral. Subtracting the $B_2$ correction makes this particular polynomial example exact. For $f(x)=x^4$, the two interior corrections above can be written $B_2(f^{\prime }(N)-f^{\prime }(0))/2!$ and $B_4(f^{\prime \prime \prime }(N)-f^{\prime \prime \prime }(0))/4!$. These are exact identities for these polynomials; extending such corrections to general functions requires a separate error analysis.

For a bounded function on an interval with finitely many jumps and piecewise $C^{\alpha }$ bounds, localized orthonormal wavelets with sufficient vanishing moments give squared best N-term approximation error $O(N^{-2\alpha })$. There are $O(2^j)$ smooth-region coefficients of size $O(2^{-j(\alpha +1/2)})$, and only $O(K)$ jump-crossing coefficients of size $O(2^{-j/2})$ per level. Retain all coefficients through level $J$ and the jump-crossing coefficients through $L=\lceil 2\alpha J\rceil$ when $\alpha >1/2$. This costs $O(2^J+KJ)$ and leaves squared tails $O(2^{-2\alpha J}+2^{-L})$. Choosing $2^J$ comparable to $N$ proves the rate by the Parseval identity.

Given a family $A$ of approximating functions, a best uniform approximation to $f$ is an element $p\in A$ satisfying

For a proper extended-real function with an affine minorant, biconjugate gives its greatest lower-semicontinuous convex minorant. Geometric separation of its epigraph turns containing closed half-spaces into affine lower bounds. Vertical half-spaces are recovered by adding multiples of a domain-separating inequality to one fixed affine minorant.

The statement $f(n)=O(g(n))$ as $n\to \infty$ means there are constants $C>0$ and $N$ such thatThe same constant must work for all sufficiently large inputs. Near a finite limit point $a$, replace $n\ge N$ by $0<|x-a|<\delta$ within the domain. Absolute values allow signed or complex-valued functions; when discussing nonnegative operation counts they can be omitted.

The notation records an upper bound, not an exact leading coefficient or necessarily a tight growth order. For example, $3n^2+7n+4=O(n^2)$ because for $n\ge 1$ it is at most $14n^2$. It is also $O(n^3)$, a weaker statement. A tight comparison uses big theta notation; a ratio tending to one uses asymptotic equivalence. Formally $O(g)$ denotes a class of functions, and writing $f=O(g)$ is conventional shorthand for membership in that class. ^[ref]

The first panel compares stipulated operation counts $A(n)=1000n$ and $B(n)=n^2$. Although $A$ is linear and $B$ quadratic, $B(n)<A(n)$ for $1\le n<1000$; the ordering reverses beyond their crossing. These are mathematical cost models, not measured runtimes. The time complexity notation describes the growth of whichever cost function has been specified, whether that function represents a worst-case bound, an average, or another explicit quantity.

The middle panel gives a concrete eventual bound: $n^2+10^{5}n\le 2n^2$ for every $n\ge 10^5$. Its normalized ratio approaches one, but the threshold matters. The final panel shows the asymptotic comparison of exponential functions, with its geometrically shrinking relative difference.

Constants may depend on fixed parameters. For each fixed $\alpha >0$, $f_{\alpha }(n)=\alpha n$ is $O(n)$ with $C=\alpha$; one constant cannot cover every positive $\alpha$. A uniform big O bound makes this extra quantifier explicit.

The notation was already used in nineteenth-century number theory. In his 1976 paper, Donald E. Knuth reports Landau identifying Bachmann's 1894 book as the first appearance of $O$ known to him. Knuth's account gives the earlier mathematical setting of a notation now also common in time complexity analysis. ^[ref]

A bijection $f:X\to Y$ is a function that is both injective and surjective: each element of its codomain is the output of exactly one element of its domain of a function. The two requirements exclude unused targets and merged inputs respectively. The finite example $f(A)=1$, $f(B)=2$, $f(C)=3$ is a bijection from $\{A,B,C\}$ to $\{1,2,3\}$, whereas adding an unused target $4$ makes that same rule fail surjectivity.

A bijection gives an inverse function by reversing every pairing. Conversely, a two-sided inverse function implies a bijection, as the proof under inverse function shows. This is useful for transporting structures without losing or identifying elements. It also defines equality of cardinality: two sets have equal cardinality exactly when a bijection pairs them. An infinite example is $n\mapsto 2n$ from the integers to the even integers, with inverse $m\mapsto m/2$ on that specified codomain. A proper subset can therefore have the same cardinality as an infinite set. ^[ref].

With uniform expectations and real or complex functions,Apply the Cauchy-Schwarz inequality first in $y$. Expand the remaining square, and apply the Cauchy-Schwarz inequality in $(x,x^{\prime })$ to $u(x)u(x^{\prime })$ and ${\mathbb{E}}_{y}f(x,y)f(x^{\prime },y)$. Their squared averages are $\Vert u{\Vert }_2^4$ and $\Vert f{\Vert }_{\square }^4$, respectively.

A total binary-valued function is diagonally noncomputable if it differs from each defined diagonal value in an effective enumeration of partial computable functions. Nonbinary diagonal outputs are automatically different. No such function is computable: its own program index would contradict the defining condition. Choosing the opposite bit at every defined binary diagonal value proves existence without supplying a computable procedure.

A binary operation on a set $S$ is a function $\ast :S\times S\to S$. It takes two ordered inputs from the same set and returns exactly one output in that set. The codomain is part of the definition: ordinary subtraction is a binary operation on the integers, but not on the positive integers, since $2-3=-1$ leaves that set. Ordinary division is not a total binary operation on the real numbers, because division by zero is undefined; it is one on the nonzero real numbers.

The same set can carry several different binary operations. On $S=\{0,1,2\}$, both $a\ast b=(a+b)\mathrm{mod}3$ and $a\diamond b=(a-b)\mathrm{mod}3$ return an element of $S$, using modular arithmetic. Yet the addition operation is commutative and associative, while the subtraction operation is neither. Specifying the allowed inputs and outputs tells us what can be evaluated; additional laws tell us how expressions may be transformed. ^[ref].

For a finite set, a Cayley table records every ordered pair and its result. This turns abstract laws into checkable examples. It also makes the order of the inputs explicit: the row gives the first input, and the column gives the second.

In exact arithmetic, after $k$ completed halvings the retained root bracket has width $W_k=b_k-a_k$ and midpoint $m_k$, whereThe absolute value bound holds for every zero of a function $x_{\ast }$ in the current root bracket, including the one approached by continued bisection method updates. A zero of a function discarded with an earlier half need not satisfy later bounds. Before update $k\ge 1$, the evaluated candidate is $m_{k-1}$, whose corresponding guarantee is $(b-a)/2^k$. After update $k$, the new midpoint $m_k$ has the smaller guarantee $(b-a)/2^{k+1}$, even without evaluating $f(m_k)$.

The guaranteed error halves at every step; the actual absolute value error need not decrease at every step or have successive ratio $1/2$. In the square root example it increases from $|m_6-\sqrt{2}|\approx 0.000151062$ to $|m_7-\sqrt{2}|\approx 0.003755188$, while both errors remain below their guarantees. An exact midpoint zero of a function instead gives zero error and immediate termination. For this example $\sqrt{2}$ is an irrational number, so no finite exact halving can produce it as a midpoint.

For a brief proof outline, each retained half has half the previous width and contains a zero of a function by the intermediate value theorem. Every point in the retained root bracket is at most half its width from its midpoint. If the process does not stop at a zero of a function, the nested interval theorem gives one common point as the widths tend to zero; continuity and the opposite endpoint signs force its function value to be zero. Uniqueness in the initial root bracket is unnecessary.

For a requested absolute tolerance $\epsilon >0$, stop when the retained root bracket has width at most $2\epsilon$, and report its midpoint. The bisection error bound then guarantees $|m_k-x_{\ast }|\le \epsilon$ in exact arithmetic. Using the ceiling function and the base-two logarithm, the required number of halvings isThe zero allows stopping before any update when the initial root bracket is already sufficiently narrow. For the polynomial $f(x)=x^2-2$ on $[1,2]$ with $\epsilon =10^{-3}$, $k_{\min }=\lceil {\log }_{2}500\rceil =9$. After nine halvings,Thus the reported midpoint meets the tolerance; its actual error from the square root $\sqrt{2}$ is approximately $0.000825500126905$. After eight halvings the bound is $1/512>10^{-3}$, so eight do not give this worst-case guarantee.

Cache the endpoint values. Each update of the bisection method needs just one new function evaluation, at the old midpoint. With no early zero of a function, $k$ updates therefore cost $k+2$ function evaluations, including the two initial endpoints. Returning the new midpoint requires no additional function evaluation; requesting its value would add one. The nine-update example needs eleven evaluations for the guarantee.

A small function value $|f(m_k)|$ alone does not guarantee a small position error: rescaling $f$ changes those values without changing its zeros of a function. In a practical implementation, use an explicit width test and an iteration limit. With floating-point arithmetic, also stop if the computed midpoint equals either endpoint: the root bracket can no longer shrink, so repeating the update would loop forever. Report this precision limit separately if the requested tolerance remains unmet. Reliable sign evaluations are needed to preserve the root bracket; compare signs directly rather than multiplying endpoint values, which can suffer overflow or underflow in floating-point arithmetic.

For a rounded midpoint $m$ still inside a valid root bracket, the geometric error bound is $\max \{m-a_k,b_k-m\}$; it need not equal $W_k/2$ because of roundoff error. A rigorous computed enclosure also needs conservative arithmetic for that bound and reliable endpoint signs. The exact-arithmetic bisection error bound should not be claimed unchanged after precision prevents further halving.

For practical tolerance conventions, SciPy's bisect combines absolute and relative tolerances through $|x-x_0|\le \mathrm{xtol}+\mathrm{rtol}|x_0|$, and provides a maximum iteration count and convergence status. These differ from the purely absolute width test above.^[ref]