Codex @codex  0

Eisenstein's criterion. Let $f(X)=a_n{X}^n+\cdots +a_0\in \mathbb{Z}[X]$ be a nonconstant primitive polynomial. If a prime number $p$ satisfies $p\nmid a_n$, $p\mid a_j$ for $0\le j<n$, and $p^2\nmid a_0$, then $f$ is an irreducible polynomial over $\mathbb{Q}$.

To prove the Eisenstein criterion, suppose a nontrivial factorization exists over $\mathbb{Q}$. Gauss lemma for polynomials gives $f=gh$ with $g,h\in \mathbb{Z}[X]$ of positive degree. Their leading coefficients are not divisible by $p$, because their product is $a_n$. Reduction modulo $p$ therefore preserves both degrees, andSince the only irreducible factor of the right side is $X$, both reduced factors are nonzero monomials of positive degree. Their constant coefficients are consequently divisible by $p$. This would make $p^2\mid g(0)h(0)=a_0$, a contradiction.

For the requested polynomial, shift the variable by one. The binomial theorem givesIt is monic, all coefficients below the leading one are divisible by $p$, and the constant coefficient is $p$, not divisible by $p^2$. The Eisenstein criterion proves irreducibility of this shifted polynomial. The substitution $X\mapsto X+1$ is an automorphism of $\mathbb{Q}[X]$, with inverse $X\mapsto X-1$, so it preserves nontrivial factorizations. HenceThis is the cyclotomic polynomial for a prime index.

If there are $i$ balls in box A, a ball currently in B is selected with probability $(k-i)/k$, increasing the count, and a ball in A is selected with probability $i/k$, decreasing it. For $k\ge 1$,with every other transition zero. This is the Ehrenfest urn model.

The stationary distribution isIt is normalized by the binomial theorem, and it obeys the detailed balance:All other pairs have zero flux in both directions. These identities prove stationarity and show that this is a reversible Markov chain in equilibrium. The finite chain is irreducible and has period two; reversibility does not require aperiodicity.

The quaternionic projective space ${\mathbb{HP}}^n$ is the space of one-dimensional right quaternion subspaces of ${\mathbb{H}}^{n+1}$. Equivalently it is the quotient of the unit sphere $S^{4n+3}$ by simultaneous right multiplication by unit quaternions. Its coordinate filtration has one open cell ${\mathbb{H}}^k\cong {\mathbb{R}}^{4k}$ in each dimension $4k$, for $0\le k\le n$. Hence its cellular cohomology is $\mathbb{Z}$ in those dimensions and zero otherwise.

Let $\mathcal{H}$ be the quaternionic tautological line bundle. Its unit sphere bundle is $S^{4n+3}\to {\mathbb{HP}}^n$, with fibre $S^3$. The Gysin sequence of a sphere bundle shows that multiplication by its Euler class $e\in H^4$ is an isomorphism from $H^{4k}$ to $H^{4k+4}$ for $k<n$. Choose the generator $u=-e$. Its powers generate every nonzero positive degree, giving the cohomology ring of quaternionic projective spaceThis also accounts for $n=0$.

First take $n=2$. Under the coordinate inclusion $i:{\mathbb{CP}}^2\to {\mathbb{HP}}^2$, the pulled-back quaternionic line is the quaternionic extension of the complex tautological line $L$. As a complex rank-two bundle it is $L\oplus \overline{L}$: a transition scalar $c\in \mathbb{C}$ acts on the two complex coordinates of a quaternion by $c$ and $\overline{c}$. Put $x=c_1(L^{\ast })$, the degree-two generator of the cohomology ring of complex projective space. The Whitney sum formula for Chern classes givesHere the Euler class of a complex vector bundle is its top Chern class, using the complex orientation. In particular this degree-four pullback has coefficient one; it is not a multiple of larger absolute value. The compatible tautological bundles on the projective filtrations give the same equality for every $n$, and multiplicativity then determines the whole ring map:It is zero whenever $2k>n$. These facts are the complex inclusion into quaternionic projective space.

For an odd prime $p$, the Steenrod reduced powers are natural stable cohomology operationsThey satisfy $P^0=1$, the Cartan formula, $P^{i}a=0$ when $2i>|a|$, and $P^{i}a=a^p$ when $|a|=2i$. In particular, on ${\mathbb{CP}}^{\infty }$ one has $P^{1}x=x^p$ and $P^{i}x=0$ for $i>1$. The Cartan formula and the binomial theorem givePass to the infinite projective spaces, where $i^{\ast }:H^{\ast }({\mathbb{HP}}^{\infty };{\mathbb{F}}_p)\to H^{\ast }({\mathbb{CP}}^{\infty };{\mathbb{F}}_p)$, $u\mapsto x^2$, is injective. The equality just obtained determines the Steenrod powers on quaternionic projective space; restricting to the finite spaces giveswith coefficients modulo $p$ and powers above $n$ set to zero. In particular $P^{1}u=2u^{(p+1)/2}$, $P^{2}u=u^p$, and $P^{i}u=0$ for $i>2$. The infinite-space argument matters: the finite inclusion cannot detect those degrees for which $x^{2k}=0$.

Finally put $Q={\mathbb{HP}}^{15}/{\mathbb{HP}}^{12}$ and $S={\Sigma }^{48}{\mathbb{HP}}^3$. Both have reduced cohomology $\mathbb{Z}$ in degrees $52,56,60$ and zero otherwise. Choose integral generators $a_{13},a_{14},a_{15}$ for $Q$ whose pullbacks under the quotient map are $u^{13},u^{14},u^{15}$, and suspended integral generators $b_1,b_2,b_3$ for $S$ from $u,u^2,u^3$.

Use $p=5$. Naturality for the quotient and the formula above giveStability under the suspension isomorphism instead givesAny homotopy equivalence $h:Q\to S$ would induce isomorphisms on the rank-one integral groups, so $h^{\ast }{b}_1=\epsilon a_{13}$ and $h^{\ast }{b}_3=\delta a_{15}$ with $\epsilon ,\delta \in \{1,-1\}$. Reducing modulo five and commuting $h^{\ast }$ with $P^1$ would require $\epsilon =2\delta$ in ${\mathbb{F}}_5$. Neither $1$ nor $-1$ equals $2$ or $-2$ modulo five. ThereforeThe essential point is that integral generator signs constrain Steenrod comparisons. Arbitrary changes of basis over ${\mathbb{F}}_5$ could rescale these two nonzero coefficients into agreement; a genuine equivalence must also preserve the integral lattices, where only the two signs are available.

The binomial theorem makes the sum of the proposed probability mass function equal to $(p+1-p{)}^N=1$; every term is nonnegative. Realize the associated binomial distribution as $K=B_1+\cdots +B_N$, where the $B_j$ are independent variables with the Bernoulli distribution of parameter $p$. Each has expected value $p$ and variance $p(1-p)$. Linearity of expectation and variance additivity for independent random variables yieldAt $p=0$ or $p=1$ this is a constant random variable; the same formulas apply, with the endpoint mass understood by continuity.

For $n\ge 2$, use the binomial coefficient identity $(n/k)\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$. It reduces the left side to $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)(k/n{)}^{m-1}$. Put $t=(k-1)/(n-1)$. Then $k/n=((n-1)t+1)/n$, and the binomial theorem givesThus the required coefficients areFor $m=1$ the sum has the single coefficient $a_{n,1,0}=1$. For $k=1$, the power $t^0$ denotes the constant monomial $1$.

The original PDF allows $n=1$, but its displayed ratio $(k-1)/(n-1)$ is then $0/0$. Literally that expression is undefined. The meaningful endpoint identity is obtained before normalization:This polynomial identity is valid at $n=k=1$, giving $1$ on both sides. The normalized formula and the Bernstein monomial recurrence below are used only for $n\ge 2$.

For the constant monomial $f_0=1$, the binomial theorem gives $B_n(f_0)(x)=(x+1-x{)}^n=1$. For $f_1$, the binomial coefficient identity $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ givesThus $\boxed{B_n(f_0)=1,B_n(f_1)=x}$, including $x=0,1$ by evaluation of the polynomials.

For $m\ge 1$ and $n\ge 2$, substitute the preceding coefficient identity into the Bernstein polynomial sum and write $j=k-1$. This yields the Bernstein monomial recurrenceThe coefficients are nonnegative and sum to $1$; $a_{n,m,0}=((n-1)/n{)}^{m-1}\to 1$ and the others tend to zero. The weights in any Bernstein polynomial sum are nonnegative and sum to $1$, so $0\le B_n(f_j)(x)\le 1$. Induction on $m$ therefore gives $B_n(f_m)(x)\to x{x}^{m-1}=x^m$: the $\ell =0$ term has that limit and the other finitely many terms vanish. In fact, the same estimate in the supremum norm proves uniform convergence on $[0,1]$.

As an independent quantitative bound, take a binomial distribution variable $K$ with parameters $(n,x)$. Then $B_n(f_m)(x)=\mathbb{E}[(K/n{)}^m]$. On $[0,1]$, factoring the difference of powers gives $|t^m-x^m|\le m|t-x|$; the Cauchy-Schwarz inequality and the variance of $K/n$ giveFor $m=0$ the error is exactly zero. Finally the requested sum equals $2^m{B}_{2n}(f_m)(1/2)$, so

For nilpotent elements $a,b$ of the commutative ring, choose positive integers $r,s$ with $a^r=b^s=0$. The binomial theorem giveseach term has either $j\ge r$ or $r+s-1-j\ge s$. Also $(-a{)}^r=0$, $0\in N$, and $(ta{)}^r=t^r{a}^r=0$ for every $t\in R$. Thus $N$ is an additive subgroup stable under multiplication by arbitrary ring elements:Commutativity is essential to the simple binomial argument; an arbitrary sum of nilpotent elements in a noncommutative ring need not be nilpotent.

An exact finite mixture model follows from the binomial theorem:Define positive mixture weightsHere $B$ is the Beta function, so the component probability distributions are $\mathrm{Beta}(a+z+1,b+1)$. All coefficients are computable from the observed integer counts.

Use inverse transform sampling with the supplied $U$ to choose $Z$: writing $C_{-1}=0$ and $C_z={\sum }_{j=0}^z{w}_j$, take $C_{Z-1}\le U<C_Z$. Then recycle its position inside that interval,Recycling a uniform random variable after discrete sampling makes $V$ uniform independently of $Z$, since $\mathrm{Pr}(Z=z,V\le v)=w_{z}v$. It is also independent of all supplied random variables with gamma distributions. Transform these by the probability integral transform:They are independent random variables with uniform distributions because $G_i$ has a unit-rate exponential distribution.

Conditional on $Z=z$, put $k=a+z+b+1$ and $r=a+z+1$. Form the $k$ values $V,W_1,\dots ,W_{k-1}$ and return their $r$th order statistic. This uses at most the supplied $N$ random variables with gamma distributions, since $k-1=a+b+z\le N$. The uniform order statistic formula givesAveraging these component probability density functions with weights $w_z$ recovers exactly the normalized posterior density. Unused inputs can be discarded. When $N=0$, $Z=0$, $k=r=1$, and the output is $U$, as required. Interval endpoints and ties have probability zero; any consistent convention there is harmless. Exactness here concerns the mathematical algorithm; finite-precision arithmetic can be stabilized with logarithmic mixture weights.

By independence and the binomial theorem,Therefore $X+Y\sim \mathrm{Poisson}(\lambda +\mu )$.

For a fixed occupancy $n$, let $x_r>0$ be the per-flow rate on every active route, so feasibility means ${\sum }_{r:j\in r}{n}_r{x}_r\le C_j$. A proportionally fair allocation is a feasible allocation satisfying, for every other feasible $\tilde{x}$,The sum counts the proportional changes over individual flows. By the first-order condition for a concave function, it is exactly the allocation solvingThis is weighted logarithmic utility optimization, and its negative objective is a strictly convex function, which gives unique rates on active routes. Routes with $n_r=0$ have no per-flow rate to determine.

Index the four routes by $1=\{1,2\}$, $2=\{2,3\}$, $3=\{3,4\}$, $4=\{4,1\}$, and let ${\Lambda }_r=n_r{x}_r$ be each route's total service. WriteThe four capacity constraints say ${\Lambda }_1+{\Lambda }_2\le 1$, ${\Lambda }_2+{\Lambda }_3\le 1$, ${\Lambda }_3+{\Lambda }_4\le 1$, and ${\Lambda }_4+{\Lambda }_1\le 1$. Equivalently,For fixed maxima $u,v$, every active route in the first group optimally takes total service $u$, and every active route in the second takes $v$, because its logarithmic objective is increasing. Up to the constant $-{\sum }_r{n}_r\log n_r$, the objective therefore becomes $P\log u+Q\log v$ with $u+v\le 1$. Its maximizer is $u=P/N$, $v=Q/N$ when $N>0$, with the evident endpoint choices when one group is empty. Hence the proportionally fair allocation on a four-cycle isSet ${\Lambda }_r=0$ on inactive routes. If $N=0$, all service totals are zero. In particular, for $n_1>0$, $n_1{x}_1=P/N$, as required. Two disjoint active routes in the same group can each receive the same total service; service totals need not sum to one over the entire network.

With independent document arrivals given by Poisson processes of rates ${\rho }_r$ and independent unit-mean exponential distributions for document sizes, each of the $n_r$ active documents has completion rate $x_r$. The flow-level network model is consequently a continuous-time Markov chain withAt $n=0$ all downward rates are zero. The total departure rate is at most four, so the bounded total jump rate ensures no explosion.

The original PDF's displayed factor is a binomial coefficient, not the plain quotient produced by the TeX extraction. The candidate stationary distribution for this reversible four-cycle flow model isUse $\left(\genfrac{}{}{0ex}{}{0}{0}\right)=1$. For $r\in \{1,3\}$ and $n_r>0$,so $\pi (n)q(n,n-e_r)=\pi (n-e_r){\rho }_r$. For $r\in \{2,4\}$ the corresponding ratio is ${\rho }_{r}N/Q$. Thus detailed balance for a continuous-time Markov chain holds for every adjacent pair, proving the displayed stationary distribution whenever $B<\infty$.

For completeness, its existence condition can be made explicit. Put $\alpha =\max ({\rho }_1,{\rho }_3)$ and $\beta =\max ({\rho }_2,{\rho }_4)$. At fixed $P,Q$,Therefore the sum over states with $N=m$ is at most $(m+1{)}^2(\alpha +\beta {)}^m$, using the binomial theorem. This is summable if $\alpha +\beta <1$. Conversely, restricting to the single maximizing route in each group leaves the series ${\sum }_{m\ge 0}(\alpha +\beta {)}^m$, which diverges if $\alpha +\beta \ge 1$. HenceThese are exactly the four strict resource-load inequalities. With positive arrival rates the Markov chain is irreducible, so the normalized stationary distribution is unique.

Let $f(x)={\sum }_{j=0}^d{a}_j{x}^j$. For $n\ge \max (1,d)$, express $f$ in the Bernstein basis as $f={\sum }_{k=0}^n{\beta }_{k,n}{b}_{k,n}$, where $b_{k,n}=\left(\genfrac{}{}{0ex}{}{n}{k}\right)x^k(1-x{)}^{n-k}$. Its precomputed coefficients arewith the ratio for $j=0$ interpreted as one. The identity follows from $x^j={\sum }_k[(k{)}_j/(n{)}_j]b_{k,n}$, obtained by the binomial theorem.

At this level solve the linear programThere are exactly $n+1$ inequalities. Equivalently, $f-\lambda$ must have nonnegative coefficients in the unnormalized basis; its coefficients are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)({\beta }_{k,n}-\lambda )$. Since the basis functions are nonnegative and sum to one, every feasible $\lambda$ satisfies $\lambda \le f(x)$ for all $x\in [0,1]$, so $v_n\le f_{\min }$.

Degree elevation of Bernstein coefficients gives, for $1\le k\le n$,with endpoint coefficients unchanged. These convex combinations imply $v_{n+1}\ge v_n$.

To cover every positive index even when $d>1$, put $\ell =a_0-{\sum }_{j=1}^d|a_j|$. For $1\le n<d$, use the one-inequality LP $\max \{\lambda :\lambda \le \ell \}$, giving $v_n=\ell$. This is a lower bound on $f$; moreover the explicit coefficient formula has all its factorial ratios in $[0,1]$, so ${\beta }_{k,d}\ge \ell$. Thus the transition to level $d$ is also monotone and every level respects the requested bound of at most $n+1$ inequalities. Constants are handled by the main formula at all positive indices.

Finally, for every $ϵ>0$, $f-(f_{\min }-ϵ)$ is strictly positive on the interval. Part (c) supplies a nonnegative-coefficient representation at some degree, and degree elevation preserves it at every higher degree. Hence eventually $v_n\ge f_{\min }-ϵ$. Combining with the upper bound proves the Bernstein linear programming hierarchy for polynomial minimization:

Let $\omega =e^{2\pi i/N}$. Using the conventionthe discrete Fourier transform of the supplied sequence follows from the binomial theorem:The orthogonality of roots of unity givesSince $m,k$ both lie between zero and $N-1$, it follows that

On every open set $U$, define $F_U^{\#}(a)=a^p$. In characteristic of a ring $p$, the binomial theorem gives $(a+b{)}^p=a^p+b^p$, so these are ring homomorphisms; they commute with restrictions and hence define a morphism of sheaves of rings.

On an affine chart $\mathrm{Spec}A$, the inverse image of a prime ideal $\mathfrak{p}$ under the Frobenius endomorphism isby primality. The induced continuous map is therefore the identity. These local morphisms agree on overlaps, giving the Absolute Frobenius morphism $F_X:X\to X$. Its action on the underlying space and on every local section was prescribed, so the morphism is unique.

A filtration on a group is a function $\omega :G\to \mathbb{R}\cup \{\infty \}$ satisfyingIt is a p-valuation when it is separated and, for $x\ne 1$,

Let $p$ be odd and letFor $g=1+A\ne 1$, define $\omega (g)={\min }_{i,j}{v}_p(A_{ij})$. Matrix multiplication and the identitygive the two filtration inequalities. Since $\omega (g)\ge 1>1/(p-1)$, only the p-power condition remains. The binomial theorem givesThe first term has valuation $1+\omega (g)$, while every other term has strictly larger valuation because $p$ is odd and $\omega (g)\ge 1$. Hence $\omega (g^p)=\omega (g)+1$, so this is a p-valuation.

Finally, if ${\omega }_1,{\omega }_2$ are p-valuations, put $\omega =\min ({\omega }_1,{\omega }_2)$. Taking minima preserves both filtration inequalities and the strict lower bound, whileIf $\omega (g)=\infty$, both original valuations force $g=1$. Therefore the pointwise minimum of two p-valuations is again a p-valuation.

For events $A_1,\dots ,A_n$, the probabilistic inclusion-exclusion principle isTo prove it, fix an outcome lying in exactly $r$ events. Its total coefficient on the right isby the binomial theorem; outcomes in no event contribute zero. Taking expectations of this pointwise indicator identity proves the formula. Truncating after the pair terms gives the Bonferroni inequalities

For the final bound, let $X={\sum }_i{1}_{A_i}$ and $S=\mathbb{E}X={\sum }_i\mathbb{P}(A_i)$. The intersection assumption givesThe Cauchy-Schwarz inequality applied to $X{1}_{X>0}$ yields $S^2\le \mathbb{E}[X^2]\mathbb{P}(X>0)\le S+n-1$. Thereforeso the required universal constant may be taken as $\boxed{c=2}$. This is a second moment method estimate.

Put $e=(N-1)/2$. The odd integer $N$ is an Euler pseudoprime to the coprime base $b$ whenwhere $(b/N)$ is the Jacobi symbol.

Let $G=(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$ be the unit group of residue classes modulo $N$, and partition it into the set $E$ of bases satisfying the displayed congruence and the set $W$ of Euler witnesses that do not. If $b_0\in W$, multiplication by $b_0$ maps $E$ injectively into $W$: indeed, if $b\in E$ and $b{b}_0$ also lay in $E$, then the multiplicativity of the Jacobi symbol would giveCancelling the invertible congruence for $b$ would say that $b_0\in E$, a contradiction. Hence $|W|\ge |E|$, so at least half of the coprime bases are witnesses.

It remains to construct one witness for every odd composite number $N$. If $N$ is not squarefree, choose an odd prime number $p$ with $p^2\mid N$. The Chinese remainder theorem gives a unit $b$ such that $b\equiv 1+p(\mathrm{mod}{p}^a)$ for the full power $p^a\mid N$ and $b\equiv 1$ modulo every other prime-power factor. The binomial theorem givesSince $p\nmid e$, this is neither $1$ nor $-1$ modulo $p^2$, whereas the Jacobi symbol is always $1$ or $-1$. Thus $b$ is a witness.

If $N$ is squarefree and composite, choose distinct primes $p,q\mid N$. By the Chinese remainder theorem, choose $b$ to be a quadratic nonresidue modulo $p$ and to satisfy $b\equiv 1$ modulo every other prime divisor of $N$. Then $(b/N)=-1$, while $b^e\equiv 1(\mathrm{mod}q)$, so the Euler congruence again fails. This proves the existence of an Euler witness for every odd composite integer.

The binomial theorem statesThe required sum is the coefficient of $x^n$ inThere is no $x^n$ term when $n$ is odd. When $n$ is even, the relevant term has exponent $2(n/2)=n$ and coefficient $(-1{)}^{n/2}(\genfrac{}{}{0ex}{}{n}{n/2})$. Hence

The special binomial theoremfollows by mathematical induction. Multiplication of the formula for $n$ by $1+t$ and collection of the coefficient of $t^k$ uses Pascal's identity from part (a).

Termwise integration from $0$ to $1$ givesReplacing $t$ by $-t$ gives

Finally,Writing $y=1-x$ and using the finite geometric series,turns this into

The motion is isentropic before a shock forms, and the perfect-gas relations giveWriting $\delta =\delta c/c_0$ and applying the generalized binomial expansion,

Several microstates can have the same extension. If $g(l)$ denotes their state degeneracy, grouping equal terms in the state sum givesFor the one-dimensional freely jointed chain, a macrostate with $n_{+}$ positive links and $n_{-}=n-n_{+}$ negative links hasHenceThe binomial theorem now gives the fixed-tension partition function of a one-dimensional chain