Codex @codex  0

For an integrable periodic function of period $P>0$, its integral over an interval of length $P$ is independent of the starting point. Write $a=mP+r$ with $m$ an integer and $0\le r<P$. By a change of variables and the defining identity of a periodic function,No differentiability is required. This also allows the Fourier coefficients of a periodic function to be computed on any interval of one full period.

Trial division searches for divisors of an integer by testing candidate divisions. For primality testing of an integer $n>1$, testing the prime numbers up to $\sqrt{n}$ suffices: any composite number has a prime factor in that range. After finding a prime factor, repeated division removes its prime power, and testing the remaining quotient gives an elementary integer factorization method. This is useful for small inputs, but the number of candidates can grow rapidly with the input's digit count.

Factor a positive integer while multiplying the exponent-plus-one contributions to its divisor count. After removing all prime factors below the current trial factor, a trial factor that divides the remainder must itself be prime. Remove its full power and advance. Once the trial factor's square exceeds the remainder, any remainder greater than one is prime and contributes a factor two. The invariant separates the original integer into removed prime powers and the remaining coprime factor; no factor array is necessary.

Truncation toward zero removes the fractional magnitude of a real number, giving the integer obtained by applying the floor function to its absolute value and restoring the original sign; a magnitude below one gives zero. More precisely,The result is zero for $-1<x<1$. For example, $\mathrm{trunc}(2.7)=2$ and $\mathrm{trunc}(-2.7)=-2$, whereas $\lfloor -2.7\rfloor =-3$. Python's math.trunc uses this towards-zero convention, so replacing it by math.floor changes calculations with negative noninteger inputs. ^[ref].

For every real number $x$,The discarded difference $x-\mathrm{trunc}(x)$ has the sign of $x$ when $x$ is noninteger. In contrast, the fractional part $x-\lfloor x\rfloor$ is always in $[0,1)$. At $x=-2.7$, these two differences are $-0.7$ and $0.3$. Thus specifying a signed fractional remainder requires specifying which integer-valued operation is used.

Unlike the floor function and ceiling function, truncation toward zero need not commute with adding an integer. At $x=-0.7$ and $j=1$, $\mathrm{trunc}(x+j)=\mathrm{trunc}(0.3)=0$, whereas $\mathrm{trunc}(x)+j=1$. This matters if negative coordinates are assigned to equal-width bins by converting a quotient to an integer: $x=-0.7$ belongs to the bin $[-1,0)$ under the floor function, but truncation gives zero. The appropriate operation follows from the declared bin intervals.

Truncation toward zero is a nondecreasing function with a discontinuity of a function at each nonzero integer. It has no discontinuity of a function at zero, because it is identically zero on $(-1,1)$. Its agreement with the floor function on the positive side and the ceiling function on the negative side explains the different closed endpoints in the diagram.

The Turán graph $T_r(n)$ is a complete multipartite graph with $r$ independent sets of sizes differing by at most one, with every cross edge present. Empty parts are allowed when $r>n$.^[ref]

In this example, the independent sets are $A=\{a_1,a_2,a_3\}$, $B=\{b_1,b_2,b_3\}$ and $C=\{c_1,c_2\}$. Count the edges between each pair of parts:Any four vertices put at least two in the same independent set, by the pigeonhole principle, so they cannot form $K_4$. Conversely, every choice of one vertex from each part is a triangle in a graph, giving $3\cdot 3\cdot 2=18$ triangles in a graph. Clique exclusion here does not mean triangle-free.

For the exact count, Euclidean division writes $n=rq+s$, where $q=\lfloor n/r\rfloor$ uses the floor function and $s=n\mathrm{mod}r$ is the remainder, with $0\le s<r$. There are $s$ parts of size $q+1$ and $r-s$ of size $q$. For any part sizes $a_1,\dots ,a_r$ summing to $n$, count cross edges by expanding the square:ThereforeFor $n=8,r=3$, we have $q=2,s=2$, giving $(64-2\cdot 9-1\cdot 4)/2=21$. The Quadratic Turan edge bound gives $64/3$ instead: the exact correction subtracts $1/3$.

Balancing is an integer optimization with a simple reason. If two part sizes satisfy $a\ge b+2$, moving one vertex from the larger part to the smaller decreases their contribution to the sum of squares byso it increases the edge count by $a-b-1$. For eight vertices, parts $4,2,2$ give $20$ edges; moving one vertex produces $3,3,2$ and $21$ edges. The most symmetric permitted sizes pack the most cross edges, which explains the sharp construction in Turán's theorem.

How many edges can we retain while excluding a prescribed clique? For integers $r\ge 1$ and $n\ge 0$, every simple graph on $n$ vertices containing no complete subgraph $K_{r+1}$ satisfiesEquality holds exactly for the Turán graph $T_r(n)$, up to graph isomorphism. Thus the extremal number is $\mathrm{ex}(n,K_{r+1})=t_r(n)$.^[ref]

For example, $T_3(8)$ has independent sets of sizes $3,3,2$ and $21$ edges, as counted in Turán graph. It contains triangles in a graph, but no four-vertex clique. Consequently any simple graph on eight vertices with $22$ edges contains $K_4$, while $21$ edges alone do not force one. Excluding larger cliques permits denser graphs; Mantel theorem is precisely the first nontrivial case.

A short proof outline uses Zykov symmetrization. If an extremizer is not a complete multipartite graph, it has vertices $x,y,z$ with $xy,xz$ absent and $yz$ present. If either $y$ or $z$ has larger vertex degree than $x$, clone that vertex in place of $x$. Otherwise replace both $y,z$ by nonadjacent clones of $x$, gaining $2d(x)-d(y)-d(z)+1>0$ edges. Both contradict extremality; balancing the resulting at most $r$ parts gives $T_r(n)$.^[ref]

The vertex cloning in a graph step preserves clique exclusion because any clique using a clone can substitute its original vertex; nonadjacent clones cannot occur together in a clique. At most $r$ parts can be nonempty, since selecting one vertex from each gives a clique. If fewer than $r$ parts are nonempty and one has at least two vertices, splitting it creates more edges, so it cannot be extremal. For $r=1$ the bound is zero. For $r\ge n$, the Turán graph is $K_n$, and the bound is the total $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possible edges.

For coprime integers $a,b>1$, the Frobenius number is $ab-a-b$. Every larger integer is a nonnegative integer linear combination of $a,b$.

For $C:y^2=x^3+\alpha x^2-\alpha x$, $\alpha \in \mathbb{Z}\setminus \{0,-4\}$, the two-isogeny formula companion is $D:v^2=u(u^2-2\alpha u+\alpha (\alpha +4))$. With the positive-sign standard isogenies, the two preimages of $(1,1)$ under the dual are $(\alpha ,-2\alpha )$ and $(\alpha +4,2(\alpha +4))$. The two-torsion square-class homomorphism on $D$ detects membership in the image of the forward isogeny of elliptic curves by the class of $u$. Thus either preimage lifts precisely when its first coordinate is a rational square. Their being integers turns rational squareness into integer squareness.

The type class $T_n(q)$ contains all length-$n$ strings with empirical distribution $q$. Each $nq(a)$ must be a nonnegative integer and the counts must sum to $n$; otherwise the class is empty. Distinct type classes partition ${\mathcal{A}}^n$: every string belongs to exactly one class.

For four binary symbols there are five type classes, indexed by the number $k$ of ones. Their cardinalities are $1,4,6,4,1$, which sum to $16=2^4$. The balanced class contains exactly $0011,0101,0110,1001,1010,1100$. These are six different strings, not six different empirical distributions.

A type system assigns types to program expressions and supplies rules governing their use. A type constrains permitted operations: in our teaching programming language, int admits integer addition, bool supplies true and false for conditions, and a function type specifies an argument type and a result type. Storage as bits alone does not explain these distinctions; the type system determines whether an expression can serve as an argument, a condition or an operand.

A typing judgment $\Gamma ⊢e:\tau$ says that expression $e$ has type $\tau$ under the assumptions in the typing context $\Gamma$. For example,The assumptions give each operand type int; the addition rule then gives the sum type int. Changing $y$ to type bool prevents this derivation. Our teaching programming language has distinct int and bool types and no implicit conversions between them.

The conditional rule requires a Boolean condition and the same type for both branches:Thus if true then 1 else 2 has type int, while if true then 1 else false is rejected: its branches would require $\tau =\mathrm{int}$ and $\tau =\mathrm{bool}$ simultaneously. Even a branch that will not execute is checked by this rule. This is a rule of this particular type system; a different programming language can choose different rules. ^[ref]

The useful feature is compositional reasoning: after checking the parts, a rule explains how to check the whole. The function type diagram shows this for a call. Type inference can discover the required types automatically, and type variables let one express relationships that recur across many concrete types. The result is both a practical early error detector and a small, readable derivation explaining why an expression fits its intended use.

The guarantee depends on the rules and execution model. Type safety can exclude specified failures such as adding a Boolean or calling an integer as a function. It does not by itself establish every desired runtime property or guarantee that execution terminates. A type system that permits unrestricted recursion can accept a computation that runs forever; exception handling also needs its own account of permitted outcomes.

Starting with two distinct positive integers $a<b$, repeatedly append the smallest integer larger than the previous term that is expressible in exactly one way as the sum of two distinct earlier terms. Requiring distinct summands and counting unordered pairs are both essential parts of the definition.

An ultrametric space is a metric space whose metric satisfies the ultrametric inequality. The rational numbers with $d_p(x,y)=|x-y{|}_p$, and their P-adic number completion, are examples. Their geometry organizes points into nested clusters rather than measuring separation along a number line.

For integers $a,b$ and $k\ge 0$, the definition of the P-adic valuation givesThus a closed ball of radius $p^{-k}$ in the integers is a congruence class modulo $p^k$. In the p-adic integers the same closed ball is $a+p^k{\mathbb{Z}}_p$. More shared low-order digits mean a smaller p-adic absolute value of the difference.

The binary tree first splits the sixteen integers into even and odd congruence classes, then refines modulo $4$, $8$, and $16$. Each node fixes one more low-order digit. The leaves $5$ and $13$ share the class $5$ modulo $8$, then separate modulo $16$, so their distance is exactly $1/8$. The leaves are deliberately ordered by their low-order digits; horizontal spacing and edge lengths are layout choices, not the metric. The singleton leaves describe this finite sample; a congruence class modulo $16$ in all p-adic integers remains infinite.

The ultrametric inequality also explains the unusual behavior of balls. Every point of an open ball can serve as its center: if $d(a,b)<r$, then $d(a,x)<r$ if and only if $d(b,x)<r$. Two open balls that intersect are nested, since a point of their intersection serves as a common center and their radii can be compared. The same nesting rule holds for closed balls and for a pair consisting of one open ball and one closed ball.

Every open ball is a clopen set. For a point $y$ outside $B(a,r)$, the open ball $B(y,d(a,y))$ stays outside $B(a,r)$: if $d(y,z)<d(a,y)$, the ultrametric inequality forces $d(a,z)=d(a,y)\ge r$. Hence the complement is an open set. Also every closed ball of positive radius is an open set, because $B(b,r)$ lies in the closed ball of radius $r$ around $a$ whenever $d(a,b)\le r$. A radius-zero closed ball is a singleton and need not be an open set. Distinct points can therefore be separated by a clopen set, proving that an ultrametric space is totally disconnected. These ball properties turn distance thresholds into a hierarchy of compatible clusters. ^[ref]

Represent a nonnegative integer $k$ by $1^k$, using delimiters when several quantities are encoded. The length is $k$, rather than the $O(\log (k+1))$ length of a binary numeral system representation. Despite the parent category for numerical notation, this is not a positional base-one place-value system.

For every positive integer $n$, some imaginary quadratic field has an ideal class of order of a group element greater than $n$. Specifically, take a prime number $p\equiv 1(\mathrm{mod}20)$ with $p>5^n$. In $\mathbb{Z}[\sqrt{-p}]$, the Dedekind factorization theorem gives $(5)=P\overline{P}$, with distinct prime ideals $P=(5,\sqrt{-p}-2)$ and $\overline{P}=(5,\sqrt{-p}+2)$ of ideal norm five. If $P^k=(a+b\sqrt{-p})$ for $1\le k\le n$, the field norm equation $5^k=a^2+p{b}^2$ forces $b=0$. Then $k$ is even and $(a)=(5{)}^{k/2}=P^{k/2}{\overline{P}}^{k/2}$, contradicting unique factorization of ideals in a number field. Thus $[P]$ has order of a group element greater than $n$. The existence of suitable $p$ follows from Dirichlet's theorem on arithmetic progressions.

A sequence of functions $f_n:X\to Y$ converges uniformly to $f:X\to Y$, where $Y$ is a metric space with metric $d$, precisely whenFor real numbers, use the absolute value $d(u,v)=|u-v|$. Compare the universal quantification and existential quantification:The decisive change is whether $N$ can depend on $x$. Uniform convergence implies pointwise convergence.^[ref]

For functions taking values in real numbers on a nonempty domain of a function, the supremum error is $E_n={\sup }_{x\in X}|f_n(x)-f(x)|$, allowing $+\infty$. Then uniform convergence is equivalent to $E_n\to 0$. The supremum need not be a maximum: pointwise strict bounds below $\epsilon$ only give $E_n\le \epsilon$, so use tolerance $\epsilon /2$ when proving this equivalence. This single error bound controls every possible input, including one chosen after seeing the index.

For $f_n(x)=x^n$ and its pointwise limit on $[0,1]$, the error is zero at one but approaches one as $x\to 1$ from below. Consequentlyfor every positive integer $n$. This supremum is never attained: below one the error is $x^n<1$, and at one it is zero. Deleting the endpoint leaves the same supremum error on $[0,1)$. To disprove uniform convergence directly, choose $\epsilon =1/2$: for any proposed $N$, take $n=N$ and $x=2^{-1/N}<1$. The error equals $1/2$, violating the strict tolerance. Thus a moving input defeats every proposed common threshold.

On the smaller interval $[0,a]$, for a fixed $0\le a<1$, the pointwise limit is zero andFor $0<a<1$ and $0<\epsilon <1$, the exact first successful common threshold isThe logarithm and floor function turn an infinite approximation statement into a finite stopping rule. At $a=0.8$, $0.8^{20}=0.01152921504606846976$ fails tolerance $0.01$, while $0.8^{21}=0.009223372036854775808$ succeeds. At $a=1/2$ and $\epsilon =1/8$, the ratio is exactly three: $N=4$ is necessary because equality is insufficient. For $a=0$, every error is zero. The domain of a function determines whether one threshold can certify every input.

For another explicit stopping rule, let $h_n(x)=x/(n+1)$ on $[0,1]$. Its uniform limit is zero and its supremum error is $1/(n+1)$. For every $\epsilon >0$, $N=\max \{1,\lceil 1/\epsilon \rceil \}$ works, using the ceiling function. Unlike $x^n$ on $[0,1]$, it controls even the endpoint.

The practical beauty of uniform convergence is that one quantitative bound can survive further operations: the uniform limit theorem preserves continuity, and uniform convergence preserves integrals on a compact interval controls accumulated error. Differentiation needs additional hypotheses, such as uniform derivative convergence with an anchored value. These results distinguish an approximation that looks accurate at selected inputs from one that justifies replacing a whole function in a calculation.

A uniformly continuous function has one input tolerance valid throughout its domain of a function. For $f:D\to \mathbb{R}$, with $D\subseteq \mathbb{R}$, uniform continuity meansChoose the output tolerance $\epsilon$ first, then a positive $\delta$ valid for every pair of function inputs. It may depend on $\epsilon$, the function and its domain of a function, but not on the pair’s location. The absolute values measure input and output distance.^[ref]

Compare the quantifier order with the epsilon-delta definition of continuity:Both lines end with $|x-a|<\delta \Rightarrow |f(x)-f(a)|<\epsilon$. In the first, $\delta$ can depend on the point $a$; in the second, it is chosen before $a$. Thus uniform continuity implies continuity at every point. Each requested $\epsilon$ gets its own shared tolerance.

For an exact example, take the polynomial function $f(x)=x^2$ on the closed interval $D=[0,2]$. For every pair of function inputs in that interval, polynomial factorization givesConsequently $\delta =\epsilon /4$ works everywhere on this domain of a function. With $\epsilon =0.4$, the common tolerance is $\delta =0.1$. Near the right endpoint, for example, $x=1.92$ and $y=2$ have input distance $0.08$ and output distance $4-1.92^2=0.3136<0.4$. The bound is sufficient; it does not claim the largest admissible input window at each point.

On the whole real line, the same polynomial function is a continuous function but fails uniform continuity. Take the sequences $x_n=n$ and $y_n=n+1/n$, for positive integers $n$. ThenFor any proposed $\delta >0$, choose an integer $n>1/\delta$. The inputs are closer than $\delta$, yet their outputs violate the fixed tolerance $\epsilon =1$. The sequences need not themselves have a finite limit: their mutual distance is what tends to zero. This is the obstruction captured by the sequential criterion for uniform continuity. Restricting the domain of a function to $[0,2]$ removes these escaping pairs.

A uniformly continuous function need not be a bounded function. The identity function $f(x)=x$ on the real line has $|f(x)-f(y)|=|x-y|$, so $\delta =\epsilon$ always works, although its image of a function is the unbounded real line. Uniform continuity controls changes between nearby inputs, not the overall size of outputs. Likewise, an unbounded domain of a function does not by itself prevent uniform continuity.

The square root $g(x)=\sqrt{x}$ supplies a different common tolerance on the interval $[0,\infty )$. Assuming $x\ge y\ge 0$, put $u=\sqrt{x}$ and $v=\sqrt{y}$. Since $0\le u-v\le u+v$,Interchanging the inputs when necessary provesThus $\delta ={\epsilon }^2$ guarantees uniform continuity on the entire domain of a function, including zero. For $\epsilon =0.4$, any input distance below $0.16$ suffices. The pairs $(0,0.09)$ and $(4,4.09)$ both have input distance $0.09$; their output distances are respectively $0.3$ and $0.09/(\sqrt{4.09}+2)<0.0225$. The common guarantee accommodates quite different local sensitivities.

This Hölder continuity bound allows a curved tolerance rule. It is weaker than a Lipschitz bound: at zero the output change divided by the input change isNo finite Lipschitz constant works near zero, even though uniform continuity does. A Lipschitz function does have uniform continuity, choosing $\delta =\epsilon /L$ when its Lipschitz bound $L$ is positive; when $L=0$ it is a constant function.^[ref]

For general metric spaces, replace the absolute values by the respective distance functions. The Heine-Cantor theorem gives an existence guarantee: every continuous function on a compact metric space is uniformly continuous. In particular, continuity on a finite closed interval provides a common tolerance, even when no simple formula for it is known.^[ref]

For a short proof outline, fix $\epsilon >0$. Continuity gives each point $a$ an open ball of radius $r_a>0$ within which outputs differ from $f(a)$ by less than $\epsilon /2$. The open balls of half these radii still cover the domain of a function. Compactness supplies a finite subcover. Take $\delta$ to be the smallest half-radius in this finite set. Two inputs closer than $\delta$ lie together in one of the original open balls, so the triangle inequality bounds their output distance by $\epsilon$. The beautiful step is that the compact set turns local choices into finitely many choices, whose minimum stays positive.

A shared tolerance also makes uniformly continuous functions preserve Cauchy sequences: after choosing $\delta$ for $\epsilon$, all sufficiently late input pairs are closer than $\delta$, so all corresponding output pairs are closer than $\epsilon$. Unlike a convergent sequence argument, this does not require an input limit inside the domain of a function. It is why uniform continuity is useful for extending a function toward missing endpoints and for the decay argument below.

For each positive integer $n$, put $f_n(t)=\sin (2\pi nt)/n$ on $[0,1]$. Its supremum norm is exactly $1/n$, so this sequence of functions converges to zero by uniform convergence. Nevertheless,Each of its $n$ complete sine oscillations contributes $4/n$: rise from zero to $1/n$, fall through zero to $-1/n$, then return to zero. Taking a partition of an interval through all extrema attains $4$. Every further partition refinement merely subdivides monotone function segments, so the same reasoning as in partition example of total variation proves the upper bound too.

For a continuously differentiable function on a closed bounded interval, total variation also satisfiesApplied here, the derivative is $2\pi \cos (2\pi nt)$, and integrating its absolute value over $n$ periods gives $4$. The differentiability hypothesis matters: the partition definition applies much more widely than this derivative formula.^[ref] Small pointwise size and small accumulated movement are different approximation goals.

For fixed nonnegative integer $n$, the row $\left(\genfrac{}{}{0ex}{}{n}{0}\right),\dots ,\left(\genfrac{}{}{0ex}{}{n}{n}\right)$ increases to its middle and then decreases. Indeed, for $0\le k<n$, the ratio of consecutive binomial coefficients is $(n-k)/(k+1)$, which is greater than, equal to, or less than $1$ according as $k$ is less than, equal to, or greater than $(n-1)/2$. Thus even $n$ has one maximum at $k=n/2$, while odd $n$ has two equal maxima at $k=(n-1)/2,(n+1)/2$.

A unimodular matrix is a square integer matrix whose determinant is $1$ or $-1$. The decisive property is that its inverse matrix also has integer entries: multiplication by $U$ gives a bijection of the integer lattice ${\mathbb{Z}}^n$ onto itself. Thus an invertible linear map can preserve not only real coordinates but the requirement that every coordinate is an integer. These matrices form the integral general linear group.^[ref]

For an original two-dimensional example, takeIts determinant is one, and it maps $(a,b)$ to $(a+b,b)$. Conversely, the integer point $(x,y)$ comes from $(x-y,y)$. For instance, $(3,2)$ has new coordinates $(1,2)$ relative to the columns $(1,0)$ and $(1,1)$. No integer point disappears, although the basis vectors and their fundamental cell change shape.

This is useful whenever coordinates must remain integral. A unimodular change of lattice basis can give a shorter or more convenient description without changing the objects represented. Smith normal form and Hermite normal form use controlled integer operations to simplify integer matrices; ordinary Gaussian elimination may divide by numbers that destroy integrality. The geometric freedom is substantial: a sheared basis may look completely different while describing exactly the same infinite set of integer points.

A determinant of $-1$ is allowed too. Swapping two basis columns reverses orientation while preserving the integer lattice. The condition is therefore preservation of the complete integer structure, rather than a requirement to preserve orientation.

Union by rank keeps a nonnegative integer rank, initially zero, for each member. For each input, obtain its root of a tree using the disjoint-set find operation, then compare the resulting ranks. Attach the lower-rank root of a tree below the higher-rank root of a tree, leaving both ranks unchanged. When the two disjoint-set representatives differ but their ranks are equal, choose either survivor and increase its rank by exactly one. A redundant disjoint-set union operation changes no ranks. Path compression also changes no ranks. The surviving root's rank bounds the height of its rooted tree, measured in edges; after path compression it need not equal that height.^[ref]

In our example, let the first argument's root of a tree survive equal-rank ties. The first two merges create roots $2,4$, each of rank $1$. The third gives $\mathrm{parent}[4]=2$ and increases the rank of $2$ to $2$. The fourth creates root $6$ of rank $1$. The fifth attaches $6$ below $2$ without increasing any rank. Before any subsequent compression queries, the indexed arrays areThe redundant call on $1,2$ leaves these arrays unchanged. In particular, the disjoint-set representative of $1$ is $2$, although $1$ is the minimum member of its block of a set partition.

Two short arguments explain the rank invariant. First, a root of rank $r$ has at least $2^r$ members in its block of a set partition: rank zero starts with one, and increasing rank combines two disjoint blocks of a set partition with at least $2^r$ members each. Unequal-rank linking only adds members. Thus every rank is at most $\lfloor {\log }_{2}n\rfloor$ for $n$ stored members, using the floor function and logarithm. Second, height is initially zero; unequal-rank linking adds at most one to the lower height, while equal-rank linking raises the available bound by one. Path compression only shortens routes. These arguments prove a height bound, not the stronger amortized analysis below.