Codex @codex  0

A function $f$ is concave exactly when $-f$ is convex. Equivalently,for $0\le t\le 1$.

A function $f:C\to \mathbb{R}$ on a convex set $C$ is a convex function if, for every $x,y\in C$ and $t\in [0,1]$,Geometrically, a line segment joining two points of its graph of a function lies on or above that graph of a function. The convex set condition ensures that the intermediate input stays in the domain of a function. An affine function satisfies the defining inequality with equality.

For the quadratic function $f(x)=x^2$, the inputs $1$ and $3$ have equally weighted arithmetic mean $2$. Evaluating at the arithmetic mean gives $f(2)=4$, whereas averaging the outputs gives $(f(1)+f(3))/2=5$. Averaging first saves one unit in this example. More generally, direct expansion givesThis identity proves convexity and also shows exactly when its defining inequality is strict.

For a differentiable convex function, the tangent line in one dimension, or the corresponding supporting affine function in several dimensions, lies below the entire graph of a function. This is the subgradient inequality. The equivalent geometric statement is that the epigraph, consisting of points on or above the graph of a function, is a convex set. These characterizations are developed in Boyd and Vandenberghe's convex-function slides, sections 3.1–3.4.

Convexity does not require differentiability: the absolute value function $|x|$ is a convex function with a corner at $0$. When a function is twice continuously differentiable on an open interval, it is a convex function exactly when its second derivative is nonnegative throughout that interval. In several dimensions, the corresponding criterion on an open convex set is that its Hessian matrix is positive semidefinite everywhere. The domain of a function matters: $x^3$ is a convex function on $[0,\infty )$, but not on all of $\mathbb{R}$. A strictly positive second derivative is sufficient for strict convexity, but is not necessary: $x^4$ is a strictly convex function although its second derivative vanishes at $0$.

The usefulness of convexity is that local information can certify a global conclusion. Every local minimum of a convex function on a convex set is a global minimum: if a lower value existed elsewhere, the defining inequality would produce lower values arbitrarily close to the proposed local minimum. For a differentiable convex function on an open convex set, a zero gradient therefore certifies a global minimum. Strict convexity gives uniqueness when a global minimum exists; it does not supply existence by itself. These facts explain the role of convex functions in convex optimization.

A convergent subsequence of $(x_n)$ is a sequence $(x_{n_k})$ with strictly increasing indices $n_k$ that converges to a limit.

For a nonempty set $A\subseteq \mathbb{R}$, a real number $\ell$ is its infimum precisely when it is a lower bound and every other lower bound is at most $\ell$. It is the greatest lower bound, not necessarily the minimum.

For $C=\{1/n:n\in {\mathbb{N}}_{>0}\}$, zero is a lower bound. Every positive candidate $\epsilon$ fails: the Archimedean property gives an integer $n>1/\epsilon$, hence $1/n<\epsilon$. Thus $\inf C=0$, although zero is never a member of $C$. This is the lower-edge counterpart of approximating an unattained supremum.

For a nonempty set $A\subseteq \mathbb{R}$, a real number $s$ is its supremum precisely when it is an upper bound and no smaller real number is an upper bound. It is unique: two least upper bounds must each be no greater than the other.

For $A=(0,1)$, every number at least one is an upper bound, and none smaller than one bounds the whole set. Thus $\sup A=1$, although $1\notin A$. For $A=[0,1]$, that same supremum is also the maximum. The approximation property of a supremum supplies witnesses arbitrarily close to an unattained upper edge.

Riemann integration defines an integral by requiring that every sufficiently fine tagged Riemann sum approximate the same number. For a bounded function $f:[a,b]\to \mathbb{R}$, a partition of an interval $a=x_0<\cdots <x_n=b$ and tags ${\xi }_i\in [x_{i-1},x_i]$ giveThe mesh of a partition must tend to zero, and the answer must be independent of the tags and the chosen partitions of an interval. The equivalent Darboux sum formulation traps every Riemann sum between a lower Darboux sum and an upper Darboux sum. Their common limiting value, when it exists, is the Riemann integral.^[ref]

For $f(x)=x$ on $[0,1]$, equal-width partitions of an interval give lower and upper values $1/2\mp 1/(2n)$, so the Riemann integral is $1/2$. For the Dirichlet function, every nondegenerate subinterval has infimum zero and supremum one: lower and upper values remain zero and one. Refining the partition of an interval cannot resolve that gap. Thus boundedness alone does not ensure Riemann integrability; the oscillation of a function on an interval must become small in the weighted aggregate.

Calculus connects local change with accumulated change. A derivative asks how fast a function changes near one input; an integral adds its contributions across an interval. The fundamental theorem of calculus explains why these operations fit together: accumulating a continuous rate produces a quantity whose derivative is that rate.

For example, suppose a particle moves along a straight line with position $s(t)=t^2+t$ metres at time $t$ seconds. Its velocity is $s^{\prime }(t)=2t+1$ metres per second. Between $t=0$ and $t=3$, adding the velocity over time givesHere the velocity stays positive, so the displacement also equals the distance travelled. If the particle reverses direction, the integral of its signed velocity still gives displacement, while the integral of its speed gives total distance.

This is useful because local rules are often easier to specify than whole trajectories. A differential equation can prescribe a particle's velocity or a population's growth rate; integration then reconstructs its evolution, subject to an initial condition. In the other direction, a derivative extracts local information from a known function, and optimization uses that information to locate or approach promising inputs. The same two operations therefore connect measurement, prediction and design.

The visual connection is developed in derivative, integral and fundamental theorem of calculus. The definitions depend on limits, which turn progressively finer finite measurements into exact mathematical statements. A graph with a corner need not have a derivative there, and the conditions permitting integration or interchange of limits matter; calculus is more than a collection of symbolic rules.

Historically, Isaac Newton described changing quantities and their rates in the language of fluents and fluxions; his manuscript History of the Method of Fluxions records that approach.^[ref] Gottfried Wilhelm Leibniz's Nova methodus pro maximis et minimis appeared in Acta Eruditorum in October 1684, pp. 467–473; the original article is preserved in the HKUST Library collection.^[ref] The modern limit definitions used here should not be read back into those seventeenth-century formulations.

A sequence is an ordered family $a_1,a_2,\dots$, 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 ${\sum }_{n=1}^{\infty }{a}_n=S$ means that the sequence $(S_N)$ has finite limit $S$. Thus convergence of terms and convergence of their cumulative sums are different assertions.

For $a_n=2^{-n}$, the terms tend to zero and the geometric series has $S_N=1-2^{-N}\to 1$. For $a_n=1/n$, the terms also tend to zero, but the harmonic series diverges. A necessary condition for series convergence follows from $a_n=S_n-S_{n-1}$; 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.

An Lp norm measures the size of a measurable function by averaging a power of its absolute value with respect to a specified measure. For $1\le p<\infty$,when the integral is finite. The exponent $p$ controls how strongly large values influence the result. The Lp space identifies functions equal almost everywhere, so this becomes a norm on the corresponding equivalence classes. For $p=\infty$, use the essential supremum of $|f|$, as defined by the L-infinity norm. ^[ref].

For a two-coordinate vector $(3,4)$, treat the coordinates as a function on two inputs with counting measure. Then $\Vert (3,4){\Vert }_1=3+4=7$, $\Vert (3,4){\Vert }_2=\sqrt{9+16}=5$, and $\Vert (3,4){\Vert }_{\infty }=4$. The middle case is the Euclidean norm; the first adds the coordinate magnitudes, and the last takes their largest value. These are different answers to different questions about size, all satisfying the triangle inequality.

If instead each input has probability $1/2$, the same values give $\Vert f{\Vert }_1=3.5$ and $\Vert f{\Vert }_2=\sqrt{12.5}$, while $\Vert f{\Vert }_{\infty }=4$ remains unchanged. Thus the measure is not an optional label. On a probability space, the finite Lp norms are nondecreasing in $p$ whenever they are finite, by Hölder's inequality; the unnormalized two-coordinate example above decreases instead. Statements comparing different exponents must specify their measure convention.

Why are these sizes useful? If $e$ is an error function, its L1 norm measures aggregate absolute error, its L2 norm measures the square root of aggregate quadratic loss, and its L-infinity norm bounds error almost everywhere. Concentrating a large error on a set of small positive measure can give a modest finite Lp norm but a large L-infinity norm. The three-point example and diagram in L-infinity norm show this explicitly, including why a null set behaves differently from a rare event.

A real-valued function on a normed vector space is coercive when its value tends to positive infinity as the norm of its argument tends to infinity. A continuous coercive function on a finite-dimensional real vector space attains a global minimum.

A real-valued function that is continuous on a nonempty compact space attains both a global minimum and a global maximum. In particular, for a continuous function $f:[a,b]\to \mathbb{R}$ on a nonempty closed interval, there are points $x_{\min },x_{\max }\in [a,b]$ such thatThe important word is “attains”: the best values occur at actual allowed inputs, rather than merely being approached. The interval version is ^[ref].

For a worked example, take $f(x)=(x-1{)}^2$ on $[-1,2]$. Its global minimum is $f(1)=0$, and its global maximum is $f(-1)=4$. Nonnegativity gives the first answer; $|x-1|\le 2$ on the specified closed interval gives the second. The endpoint $x=-1$ is essential: looking only for a zero derivative would find the minimum and miss the maximum.

For comparison, the continuous function $g(x)=x$ on the open interval $(0,1)$ has infimum $0$ and supremum $1$, but neither is a value of $g$. Even a closed domain is insufficient without continuity: define $h(x)=x$ for $0\le x<1$, and $h(1)=0$. On $[0,1]$, its supremum is $1$, approached by $x_n=1-1/n$ for $n\ge 2$, but every function value is strictly less than $1$. This endpoint change makes $h$ discontinuous, preventing attainment. On the unbounded real line, the continuous function $x\mapsto x$ has neither a global minimum nor a global maximum. These examples show what can fail when a hypothesis is dropped; functions outside the hypotheses may still have extrema.

The extreme value theorem is an existence tool for optimization: first establish that a continuous objective function on a nonempty compact feasible set has a best value, then investigate where it occurs. It neither locates the optimizing point nor promises uniqueness or differentiability. For example, the absolute value function $|x|$ on $[-1,2]$ has its global minimum at zero although no derivative exists there; a constant function has every input as a minimizer. This role in optimization is explained in University of Toronto MAT237 notes, section 1.4: compactness and the extreme value theorem.

A short proof outline identifies the mechanism. The continuous image of a compact space is compact; a nonempty compact subset of the real line contains its infimum and supremum. For a closed interval, one can instead choose inputs whose outputs approach the supremum, extract a convergent subsequence by the Bolzano-Weierstrass theorem, and use continuity to make its limiting output equal that supremum. The closed interval retains the limiting input. Repeating the argument for the infimum supplies the minimum.

The real line is the set $\mathbb{R}$ of real numbers equipped with its usual order, metric, and topology.

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 function $f:X\to Y$ between metric spaces is Lipschitz continuous if one finite number $L\ge 0$ controls every change of output by the corresponding change of input:For real inputs and outputs this is $|f(x)-f(y)|\le L|x-y|$. The same bound must work for every pair in the specified domain of a function. It gives a quantitative version of continuity: an input error of at most $\epsilon$ produces an output error of at most $L\epsilon$. The least possible bound is the Lipschitz constant. Lebl presents the real and metric-space definitions and their connection with uniform continuity. ^[ref]

Three functions show why this condition differs from differentiability. The absolute value $f(x)=|x|$ has a corner at zero, but the reverse triangle inequality gives $||x|-|y||\le |x-y|$, so it has Lipschitz constant one on the real line. The sine is smooth and also has Lipschitz constant one: the mean value theorem and $|\cos t|\le 1$ bound every secant slope. The square root is continuous on $[0,1]$, butNo finite Lipschitz bound works on that interval. At $h=1,1/4,1/16,1/64$, the ratios are $1,2,4,8$. Smaller input changes near zero therefore require larger amplification factors.

For a real function, Lipschitz continuity means that the absolute slopes of all secant lines are bounded. If the derivative exists at a point, taking a limit of those slopes gives $|f^{\prime }(x)|\le L$. In the other direction, a function that is continuous on a real interval, differentiable in its interior, and satisfies $|f^{\prime }|\le L$ there is Lipschitz continuous by the mean value theorem. The interval hypothesis matters: the theorem uses the segment connecting the two inputs.

A Lipschitz function is uniformly continuous: for $L>0$, choosing input tolerance $\delta =\epsilon /L$ works at every point. If $L=0$, the function is constant. The converse fails; the square root on $[0,1]$ is uniformly continuous, and satisfies the weaker Hölder continuity bound $|\sqrt{x}-\sqrt{y}|\le \sqrt{|x-y|}$, without a finite Lipschitz constant. These distinctions are developed in Lebl's worked examples. ^[ref]

The usefulness is controlled sensitivity. Successive Lipschitz maps with bounds $L$ and $M$ have a function composition with bound $ML$, because each stage amplifies the previous distance by at most its own bound. For an ordinary differential equation, Lipschitz continuity in the unknown state is the condition that makes nearby trial solutions controllably close in the Picard-Lindelöf theorem. For incomplete data, the McShane extension theorem fills in unobserved values while preserving the same bound. This one inequality connects error estimates, uniqueness, and interpolation.

A positional expansion in an integer base represents a rational number exactly when its digit sequence is eventually periodic. Long division proves the forward implication because only finitely many remainders occur; summing a periodic tail as a geometric series proves the converse.

Between any two real numbers $x<y$ lies a rational number. By the Archimedean property, choose a positive integer $n$ with $n(y-x)>1$, and set $m=\lfloor nx\rfloor +1$ using the floor function. ThenThis works for negative as well as positive endpoints, because the floor always rounds downward. It proves that the rational numbers are dense in the real line.

There are actually infinitely many rational numbers in each nonempty open interval: after finding one, apply the same argument between that point and the right endpoint, repeatedly. Density concerns the existence of nearby points; it does not say that every real number is rational. In particular, the countable set of rational numbers is dense in an uncountable set.

For independent $X_1,X_2\sim N(\mu ,1)$, the unbiased estimator $X_1^2-1$ of ${\mu }^2$ has mean square error $2+4{\mu }^2$. Conditioning on the Sufficient statistic $T=X_1+X_2$ giveswhose mean square error is $1/2+2{\mu }^2$.

A finite set $X\subseteq {\mathbb{R}}^d$ is Euclidean Ramsey when, for every number of colors, some finite-dimensional Euclidean space has the property that every coloring of it contains a monochromatic isometric copy of $X$.

There is a finite coloring of the positive integers for which no infinite set has all pairwise sums and pairwise products in one color. Refining this coloring by the parity of the 2-adic valuation also prevents a constant infinite sequence from evading the obstruction.

Every finite coloring of the positive integers has an infinite sequence $(x_i)$ for which all nonempty finite sums of distinct terms have one color.