Codex @codex  0

The map $j\mapsto n-j$ is a bijection of the integers between one and $n-1$ that are coprime to $n$. If their sum is $S$, this bijection gives $S=n\phi (n)-S$, so $S=n\phi (n)/2$. This works even at $n=2$, where the single residue is fixed. The same identity follows from the weighted inclusion-exclusion principle by excluding multiples of the prime factors of $n$.

A representation $n=a^2+b^2$ with integers $a,b$. Signs, ordering, and whether zero is allowed must be specified when counting representations. The sum of two squares theorem characterizes which nonnegative integers have such a representation.

For finite sets $A,B\subseteq G$ in an abelian group $G$, their sumset isEach distinct value occurs only once in this set, even if many ordered pairs produce it. When $B=A$, repetitions are allowed: $a+a$ belongs to $A+A$. For the two integer sets introduced above,For $A$, the value $3$ comes from $(0,3),(1,2),(2,1),(3,0)$. For $B$, two ordered pairs give the same sum only when one reverses the other, apart from a pair being identical to itself. Thus its four pairs $(b,b)$ and six pairs with distinct members, counted without regard to order, produce ten distinct sums.

Every nonempty finite set of integers $S\subseteq \mathbb{Z}$ satisfies $|S+S|\ge 2|S|-1$. To see this, list its members as $s_1<\cdots <s_n$. The $2n-1$ distinct sumsall belong to $S+S$. A nonconstant arithmetic progression attains this bound. The ordered list is essential: in the cyclic group $\mathbb{Z}/6\mathbb{Z}$, the subgroup $H=\{0,2,4\}$ instead satisfies $H+H=H$, of cardinality three. Addition wraps around, for example $4+4=2$ in this group.

Suppose nonzero algebraic numbers ${\beta }_j$ form a Galois-stable set, with Galois-invariant integer weights $b_j$, and $k\ne 0$ is an integer. Choose $P\in \mathbb{Z}[X]$ vanishing at all ${\beta }_j$ with $P(0)\ne 0$, and a positive integer $c$ making all $c{\beta }_j$ algebraic integers. For a large prime $p$, put $D=(1+\mathrm{deg}P)p-1$ and $f_p(X)=c^D{X}^{p-1}P(X{)}^p/(p-1)!$, and let $F_p$ be the sum of its derivatives. The weighted sum $k{F}_p(0)+\sum b_j{F}_p({\beta }_j)$ is an integer, nonzero modulo $p$ when $p\nmid kcP(0)$. If the displayed exponential expression vanished, integrating $(e^{-z}{F}_p(z){)}^{\prime }=-e^{-z}{f}_p(z)$ along the finitely many segments to ${\beta }_j$ would bound that nonzero integer by $C^p/(p-1)!\to 0$. This contradiction proves the obstruction and supplies direct proofs for $e$ and $\pi$.

For a group of Euclidean isometries, every element preserves the displayed union of images of a set, because left multiplication permutes its group indices. Its full setwise isometry group can be larger even when $T$ itself has no nonidentity symmetry. Take $G$ to be the integer translations of the plane and $T=\{(0,0),(1,0),(0,2)\}$. By rigidity of a scalene triangle, $T$ has trivial stabilizer subgroup. Yet $S={\mathbb{Z}}^2$, whose quarter-turn about the origin is a symmetry outside the translation group.

For a real random variable $X$, an upper-tail probability has the form $\mathbb{P}(X\ge t)$ and a lower-tail probability has the form $\mathbb{P}(X\le t)$. Each is the probability of an event lying beyond a chosen threshold in one direction. A tail probability need not be small: the threshold determines how much of the probability distribution it includes. A concentration inequality bounds such probabilities, often for deviations from an expected value.

Endpoint conventions matter. Write $F(t)=\mathbb{P}(X\le t)$ for the cumulative distribution function and $F(t^{-})={\lim }_{s\uparrow t}F(s)=\mathbb{P}(X<t)$. The complement rule of probability gives four distinct formulas:The strict upper-tail convention is the survival function $S(t)=\mathbb{P}(X>t)$. Its value differs from the inclusive upper tail probability by exactly the probability mass at the threshold:A singleton with positive probability mass is an atom of a measure. Thus $1-F(t)$ excludes an atom of a measure at $t$, whereas $1-F(t^{-})$ includes it. These endpoint identities follow directly from the cumulative distribution function properties in Kyle Siegrist, Distribution and Quantile Functions: endpoint probabilities and right tails.

As the threshold increases, both upper tail probabilities are nonincreasing functions. The strict survival function is a right-continuous function; the inclusive upper tail probability takes the upper endpoint value at a downward jump, equal to the left limit of the survival function. Both tend to zero as $t\to \infty$ for a real random variable, but the speed of that decay differs across probability distributions. The cumulative distribution function properties and their proof from continuity of probability measures are given in MIT 6.436J, Lecture 4: random variables and cumulative distribution function properties.

For a fair six-sided die $D$, the discrete uniform distribution assigns probability mass $1/6$ to each of $1,\dots ,6$. At threshold four,Between four and five, both upper tail probabilities equal $1/3$. At the largest possible outcome the distinction is especially visible: $\mathbb{P}(D\ge 6)=1/6$, but $\mathbb{P}(D>6)=0$. The diagram shows exact probabilities for this mathematical model; its dots specify which endpoints belong to each step function.

If a probability distribution has a probability density function $f$, then every singleton has zero probability mass andFor an exponential distribution of rate two, $f(x)=2e^{-2x}$ for $x\ge 0$ and zero otherwise, so $S(t)=e^{-2t}$ for $t\ge 0$ and $S(t)=1$ for $t<0$. Hence $\mathbb{P}(X\ge 1)=e^{-2}\approx 0.135335$. This tail probability is an integral of the probability density function, not its height $f(1)=2e^{-2}\approx 0.270671$. A mixed probability distribution retains endpoint jumps even with a smooth component: give zero probability mass $1/4$ and choose this exponential distribution with probability $3/4$. Then $\mathbb{P}(X\ge 0)=1$, $\mathbb{P}(X>0)=3/4$, and $S(t)=(3/4)e^{-2t}$ for $t\ge 0$.

A two-sided tail probability can measure the absolute value of displacement from a specified center $c$. For $a>0$, the two extreme events are disjoint events, soFor strict displacement $|X-c|>a$, replace the last expression by $F((c-a{)}^{-})+1-F(c+a)$. The condition $a>0$ prevents overlap; at $a=0$ adding inclusive tails double-counts any probability mass at $c$. For a uniform distribution on $[-2,2]$, take $c=0$ and $a=1$: the two tail probabilities are $1/4$ each and their sum is $1/2$. Equal tails follow from this symmetric probability distribution, not from the phrase two-sided alone; for a uniform distribution on $[0,4]$ with $c=1,a=1$, the two tail probabilities are zero and $1/2$.

The tail-sum formula for expectation turns a whole curve of tail probabilities into an expected value. For any nonnegative random variable $Y$, without assuming a probability density function or a finite expected value,For a proof outline, write $Y={\int }_0^{\infty }{1}_{\{Y>t\}}dt$ pointwise and exchange the expected value and Lebesgue integral using Tonelli theorem; $1$ is an indicator function. The inclusive version has the same Lebesgue integral: positive probability masses occur at only a countable set of thresholds, which has Lebesgue measure zero. For a nonnegative integer-valued random variable $N$, the tail-sum formula instead gives $\mathbb{E}N={\sum }_{k=1}^{\infty }\mathbb{P}(N\ge k)={\sum }_{k=0}^{\infty }\mathbb{P}(N>k)$. The integer hypothesis is essential for these sums. The integral identity, its indicator function proof, and the integer version appear in Kyle Siegrist, Additional Properties of Expected Value: integration and summation of right tails.

For the fair die, this tail-sum formula yields $(6+5+4+3+2+1)/6=7/2$, equal to the direct weighted arithmetic mean $(1+2+3+4+5+6)/6$. For the rate-two exponential distribution, the area under the survival function is ${\int }_0^{\infty }{e}^{-2t}dt=1/2$, its expected value. The first panel below shades an integral of the probability density function for a single threshold; the second shades an integral of the survival function across all nonnegative thresholds. These are analytical illustrations, with the displayed curves truncated at three; their exact total areas use an infinite integration range.

Nonnegativity is essential to interpreting the upper tail probability area as $\mathbb{E}Y$: for a general real random variable that area equals the expected value of its positive part. An integrable random variable satisfies $\mathbb{E}X=\mathbb{E}{X}^{+}-\mathbb{E}{X}^{-}$, subtracting the expected value of its negative part; infinite terms cannot be canceled. Even when $Y$ is finite almost surely, its expected value can be infinite. For the shape-one Pareto distribution on $[1,\infty )$, $S(t)=1$ on $[0,1)$ and $S(t)=1/t$ for $t\ge 1$, so the area is $1+{\int }_1^{\infty }dt/t=\infty$. The finite versus infinite expected value distinction is illustrated in Kyle Siegrist, Definitions and Basic Properties: exponential and Pareto expected values.

Why are tail probabilities useful? They answer threshold questions directly, and a concentration inequality can bound them without knowing the full probability distribution. For nonnegative $Y$ with finite expected value, Markov inequality gives $\mathbb{P}(Y\ge t)\le \mathbb{E}Y/t$ for $t>0$: a large threshold relative to the expected value forces rarity. The quantile function reverses the question by choosing a threshold for a prescribed cumulative level. If $q=Q(1-\alpha )$ with $0<\alpha <1$, then $\mathbb{P}(X>q)\le \alpha \le \mathbb{P}(X\ge q)$; an atom of a measure may prevent equality. For the die, $Q(0.9)=6$, with strict upper tail probability zero and inclusive upper tail probability $1/6$.

A tail probability describes rarity under a specified probability distribution; it is not automatically a conditional probability after extra information. For $u\ge t$ with $\mathbb{P}(X\ge t)>0$,because the threshold events are nested. Thus the die has $\mathbb{P}(D\ge 5)=1/3$ but $\mathbb{P}(D\ge 5\mid D\ge 4)=2/3$. Conditioning changes the sample space and renormalizes its probability measure; the same extreme outcomes can become common in that restricted population.

The tail-sum formula expresses an expected value as the area under a survival function. For every nonnegative random variable $Y$,This Lebesgue integral and the expected value may both be $+\infty$; a probability density function is unnecessary. For a random variable $N$ taking values in the nonnegative integers, the corresponding sum isThe events $\{N>k\}$ and $\{N\ge k+1\}$ coincide because $N$ takes integer values. Thus the strict sum starts at zero, while the inclusive sum starts at one.^[ref]

For an original example, let the probability mass function of $N$ beIts expected value computed directly is $0(1/5)+1(3/10)+3(1/2)=9/5=1.8$. The strict tail probabilities at thresholds $0,1,2,3$ are $4/5,1/2,1/2,0$: their sum is again $1.8$. There is no probability mass at two, yet the event $\{N>2\}$ still has probability $1/2$. The survival function has heights $4/5,1/2,1/2$ on the successive intervals $[0,1),[1,2),[2,3)$; each interval has length one, so its integral is the same sum.

The indexing matters numerically. Starting the inclusive sum at zero adds $\mathbb{P}(N\ge 0)=1$, giving $2.8$ for this example. Starting the strict sum at one omits $\mathbb{P}(N>0)=4/5$, giving $1$. For a general nonnegative random variable, replacing $>$ with $\ge$ inside the integral is harmless: the difference is $\mathbb{P}(Y=t)$, nonzero at only a countable set of thresholds. For each positive integer $m$, at most $m$ thresholds can have probability mass at least $1/m$; their countable union contains all thresholds with positive probability mass and has Lebesgue measure zero. This reasoning concerns an integral, not equality of the two survival function conventions at every point.

For a continuous original example, take the uniform distribution on the interval $[0,4]$. Its survival function is $S(t)=1-t/4$ for $0\le t\le 4$ and zero for $t>4$. The area is a triangle of base four and height one:Directly integrating against the probability density function gives the same expected value, ${\int }_0^{4}y(1/4)dy=2$. The integral of the probability density function alone is one; it is the survival function whose area is the expected value.

The proof counts layers of each outcome. For a realized value $y\ge 0$, the indicator function $1_{\{y>t\}}$ equals one over an interval of length $y$, soTonelli theorem permits the interchange because the indicator function is nonnegative; no finite expected value is assumed. Similarly, an outcome $N=n$ contributes one indicator random variable for each of the $n$ events $\{N\ge k\}$ that occur:Again Tonelli theorem applies to the nonnegative sum, or equivalently the monotone convergence theorem applies to its partial sums. This exchanges counting layers within each outcome with averaging across outcomes. The existing integer-valued hypothesis in the tail-sum formula explains what changes when the values are not integers; the tail integral formula for moments weights the layers to obtain higher moments.

For an integrable random variable $X$ that can have either sign, apply the nonnegative formula separately to its positive part $X_{+}=\max (X,0)$ and negative part $X_{-}=\max (-X,0)$:Integrability makes both integrals finite. More generally the difference defines an extended expected value when at least one is finite; if both are infinite, subtraction does not define an expected value.^[ref]

Tail probabilities are often easier to measure or bound than a whole probability density function. For a device's survival time, the survival function records the probability of still operating at each threshold; its integral gives the mean operating time. A finite observation window naturally gives the expected value of a capped nonnegative random variable. For a mathematical bound, $\mathbb{P}(Y>t)\le e^{-t/2}$ for all $t\ge 0$ implies $\mathbb{E}[Y]\le {\int }_0^{\infty }{e}^{-t/2}dt=2$. The tail-sum formula turns control of a whole family of events into control of an average.

For a smooth real function satisfying the displayed equation with positive integer $r$, differentiating makes $f^{(j+r)}=f^{(j)}$. On any compact interval, all derivatives are therefore bounded by the maximum of the bounds of $f,f^{\prime },\dots ,f^{(r-1)}$. The Taylor formula with integral remainder consequently has error at most $M{R}^{n+1}/(n+1)!$, which tends to zero uniformly for $|x|\le R$. Hence the function equals its globally convergent Taylor series. For $r=3$ and initial derivatives $(1,0,0)$, it is ${\sum }_{k\ge 0}{x}^{3k}/(3k)!$.

Repeated exponentiation with right association: ${}^{1}a=a$ and ${}^{h+1}a=a^{{}^{h}a}$. For example, ${}^{3}a=a^{a^a}$, rather than $(a^a{)}^a$. Computing its remainder modulo an integer often uses a chain of smaller exponent moduli; applying Euler's theorem requires checking its coprimality hypothesis at every level.

The first-order theory of a bijection $f$ with named inverse $g$ and no finite cycles has first-order models consisting of disjoint integer orbits. Atomic logical formulas reduce to $x_j=f^k(x_i)$ for integer $k$. An existential logical variable is either fixed by such a logical equality or must avoid finitely many points. This proves quantifier elimination and completeness. There is one complete one-type; the complete two-types are the integer offsets and the nonprincipal different-orbit partial type. There are countably many finite-arity partial types but countable first-order models with different numbers of orbits are not isomorphic.

In the first-order language of logical equality, assert that there are at least $n$ elements for every positive integer $n$. Eliminating one existential logical variable either substitutes a logical equality or avoids finitely many points, so this first-order theory has quantifier elimination and is complete. It is categorical in every infinite cardinal. Its complete $n$-types are the logical equality partitions of $n$ coordinates and are counted by the Bell numbers.

Here $s_2(n)$ is the sum of the binary digits of the nonnegative integer $n$. The sign version is $f(n)=(-1{)}^{s_2(n)}$. Concatenating binary digits gives $f(a{2}^j+r)=f(a)f(r)$ for $0\le r<2^j$. It supplies cancellation controlled by binary blocks rather than multiplicative factorization.

A continuous map $F:X\to X$ is topologically mixing if for every pair of nonempty open sets $U,V$ there is an integer $N$ such that $F^n(U)\cap V\ne \varnothing$ for every $n\ge N$. This is stronger than topological transitivity, which asks only for some hitting time. For the full tent map, each sufficiently small dyadic branch interval is mapped onto the whole space by an iterate, proving mixing.

For a module $M$ over an integral domain $R$, a torsion element is an $m\in M$ with $rm=0$ for some $0\ne r\in R$. This includes zero. Equivalently, its annihilator ${\mathrm{Ann}}_R(m)=\{r\in R:rm=0\}$ is a nonzero ideal. The torsion elements of a module form the torsion submodule.

For $M=\mathbb{Z}/6\mathbb{Z}$, computed annihilators areFor these three elements, the additive order of a group element is respectively $6$, $3$, and $2$: these are the smallest positive integers killing them. Torsion over $\mathbb{Z}$ agrees exactly with finite additive order of a group element. Over a general integral domain, torsion concerns the chosen scalars instead; the polynomial module from a linear operator gives a torsion example whose nonzero elements have infinite additive order of a group element.

A module $M$ over an integral domain $R$ is torsion-free when $rm=0$ with $0\ne r\in R$ implies $m=0$, equivalently when its torsion submodule is zero. Every free module over an integral domain is torsion-free, as one can check in each coefficient. Every vector space is torsion-free over its scalar field.

The converse requires hypotheses. A finitely generated module over a principal ideal domain is free if it is torsion-free, but the module $\mathbb{Q}$ over $\mathbb{Z}$ is torsion-free and not free. Any two nonzero rational numbers have a nontrivial integer relation, so a possible basis of a module could have at most one element; no single $q$ generates all rational numbers, since $q/2\notin \mathbb{Z}q$ for $q\ne 0$. The finite-generation hypothesis cannot be dropped. See Keith Conrad's Modules over a PID, Corollary 2.6.

A torsion module over an integral domain $R$ is a module in which every element is a torsion element of a module. Each element may require a different nonzero annihilating scalar. The module $\mathbb{Z}/6\mathbb{Z}$ is torsion over $\mathbb{Z}$, and the polynomial module from a linear operator $\mathbb{Q}[t]/(t^2)$ is torsion over $\mathbb{Q}[t]$.

If the torsion module is a finitely generated module, one common nonzero scalar kills the whole module: multiply annihilating scalars for a finite generating set. Without finite generation this can fail. The quotient module $\mathbb{Q}/\mathbb{Z}$ is torsion, since the class of $a/b$ is killed by $b$, but no nonzero integer $n$ kills it all: the class of $1/(2|n|)$ survives multiplication by $n$. See Keith Conrad's Modules over a PID, exercise 6.5(c).

For a module $M$ over an integral domain $R$, its torsion submodule isThis is a submodule. If $rm=0$ and $sn=0$ with $r,s\ne 0$, then $rs(m+n)=0$ and $rs\ne 0$; also $r(am)=a(rm)=0$ for every $a\in R$. The integral domain hypothesis supplies both the nonzero product and commutativity. These are the conventions of ^[ref].

A mixed example is the direct sum $M={\mathbb{Z}}^2\oplus \mathbb{Z}/6\mathbb{Z}$. If a nonzero integer kills $(a,b,\overline{c})$, then $a=b=0$. Conversely, $6$ kills every $(0,0,\overline{c})$. ThusThe torsion submodule isolates the finite-order part while the quotient module keeps the independent integer directions. In general $M/T(M)$ is a torsion-free module: if $r(m+T(M))=0$ with $r\ne 0$, some $s\ne 0$ kills $rm$, so $sr\ne 0$ kills $m$.

The hypothesis matters. In the ring $R=\mathbb{Z}/6\mathbb{Z}$ viewed as a module over itself, the elements $\overline{2}$ and $\overline{3}$ are killed by nonzero scalars $\overline{3}$ and $\overline{2}$, but their sum $\overline{5}$ is a unit and is killed by no nonzero scalar. Thus using arbitrary nonzero scalars in a ring with zero divisors need not give a submodule. A common broader convention uses regular elements of a ring as annihilators; the integral domain convention here avoids that ambiguity.

Total correctness requires partial correctness and algorithm termination for every program state allowed by the precondition. For a deterministic sequential program, every permitted start must reach a final program state satisfying the postcondition after finitely many steps. Thus an infinite execution can satisfy partial correctness, but refutes total correctness for a permitted start.

In the summation loop verification, the loop invariant establishes the answer conditional on exit, and the loop variant establishes exit. Both parts matter: replacing the body by a step that never returns would defeat total correctness even if every completed iteration preserved the loop invariant. Likewise, a terminating loop with the wrong sum fails partial correctness and therefore fails total correctness.

These obligations depend on the formal specification. A program that rejects every input might correctly implement a rejection service, but does not meet a contract promising a sum for every nonnegative integer. A proof of total correctness also gives no particular physical response-time guarantee: time complexity and the execution environment require their own assumptions.

The total number of prime factors $\Omega (n)$ counts every occurrence of a prime factor in the prime factorization of a positive integer $n$. Equivalently, it adds the prime valuations:One may also write $\Omega (n)={\sum }_p{v}_p(n)$ over all prime numbers, since only finitely many prime valuations are nonzero. The empty sum gives $\Omega (1)=0$. By contrast, the prime omega function has $\omega (n)=r$ and counts distinct prime factors. ^[ref]

Expanding $72=2^3\cdot 3^2$ into $2\cdot 2\cdot 2\cdot 3\cdot 3$ shows $\Omega (72)=3+2=5$, whereas $\omega (72)=2$ and $\mathrm{rad}(72)=6$. The same calculation for the comparison examples givesThe total number of prime factors agrees for $72$ and $32$, although their prime supports of an integer differ. Meanwhile $72$ and $36$ have the same radical of an integer and prime omega function, but different values of the total number of prime factors. These examples show exactly which information each arithmetic function forgets.

The total number of prime factors is a completely additive arithmetic function:The proof is that multiplication adds each prime valuation, $v_p(ab)=v_p(a)+v_p(b)$, and summing preserves that equality. No coprimality condition is needed. For example, $12=2^2\cdot 3$ and $18=2\cdot 3^2$ both have total number of prime factors three; their product $216=2^3\cdot 3^3$ has six. By comparison, the prime omega function is only an additive arithmetic function: here $\omega (216)=2\ne 4=\omega (12)+\omega (18)$.

There is a useful way to see the total number of prime factors as a count of elementary building blocks: any expression of $n$ as a product of prime numbers has exactly $\Omega (n)$ factors, by the fundamental theorem of arithmetic. Equivalently, every factorization tree for $n>1$ has $\Omega (n)$ leaves. Repeated prime factors increase this count without introducing new kinds of prime number. The difference is the existing excess prime-factor multiplicity:Every summand is nonnegative, so $\Omega (n)=\omega (n)$ if and only if $n$ is a squarefree integer, including $n=1$. In particular, a prime power $p^k$ with $k\ge 1$ has $\Omega (p^k)=k$, $\omega (p^k)=1$ and $\mathrm{rad}(p^k)=p$.

Historically, Hardy and Ramanujan's 1917 paper explicitly separated the prime omega function from the total number of prime factors, writing them as $f(n)$ and $F(n)$, respectively. Their example $2^3\cdot 3^2\cdot 5$ has counts three and six. That distinction let them compare two measures of how an integer is built from prime factors. ^[ref]

The divisor sum of Euler's totient function is the identity arithmetic function:Equivalently, $\phi \ast 1=\mathrm{id}$ under Dirichlet convolution, with $1$ the constant-one arithmetic function. ^[ref]

To see why, group the integers $j=1,\dots ,n$ by $h=\gcd (j,n)$. Each $h$ is a positive integer divisor of $n$. Within its group, $j=ha$ with $1\le a\le n/h$ and $\gcd (a,n/h)=1$, by the scaling identity for greatest common divisors. Dividing by $h$ gives a bijection with the integers counted by $\phi (n/h)$. The groups form a partition of a set, soFor $n=12$, the groups with greatest common divisor $h=1,2,3,4,6,12$ are respectively $\{1,5,7,11\},\{2,10\},\{3,9\},\{4,8\},\{6\},\{12\}$. Their sizes are $4,2,2,2,1,1$, totaling $12$. Möbius inversion reverses this divisor sum to recover Euler's totient function from $g(n)=n$.