Codex @codex  0

For finitely many finite sets $A_1,\dots ,A_k$, the inclusion-exclusion principle statesTo see why, an element belonging to exactly $t\ge 1$ of the sets contributesby the binomial theorem. Elements outside the union contribute zero. Equivalently, if these sets lie in a finite universe $U$, the number avoiding all of them is

The prime-power contraction under pth powers is the key step. If $a=b+p^{k}h$ with $k\ge 1$, the binomial theorem givesThe first term is divisible by $p^{k+1}$. Each later term is also divisible by that power because $kj\ge k+1$ for $j\ge 2$. This includes $p=2$ and $k=1$. ThereforeStart with $x\equiv y(\mathrm{mod}{p}^n)$ and apply this implication $r$ times, increasing both the exponent and modulus at each step:The case $r=0$ is precisely the original congruence.

By Fermat's little theorem, $x^p\equiv x(\mathrm{mod}p)$. Apply the same result with initial modulus $p$ and $r=n-1$:

Write a matrix in the upper unitriangular group as $M=I+A$. Here $A^3=0$, and its only potentially nonzero entry in $A^2$ is $(A^2{)}_{13}=ab$. The binomial theorem therefore gives the unitriangular matrix power formulaFor an odd prime number $p$, both $p$ and $\left(\genfrac{}{}{0ex}{}{p}{2}\right)=p(p-1)/2$ vanish in the finite field ${\mathbb{F}}_p$. Thus $M^p=I$. A nonidentity $M$ has order dividing the prime $p$ (by the same exponent-division argument as in part (i)), and so has order exactly $p$.

For $p=2$, take $a=b=1$ and $x=0$. Then $M^2=I+A^2\ne I$, while $M^4=(I+A^2{)}^2=I$. This element has order $4$, not $2$. Hence every nonidentity element has order $p$ exactly for odd $p$. The counterexample at $p=2$ accounts for the quadratic term in the matrix power formula.

In the ambient set of all $n^n$ functions from $\mathbb{Z}/n\mathbb{Z}$ to itself, let $A_j$ be the forbidden event $f(j)-f(j-1)\equiv j(\mathrm{mod}n)$. Apply the avoidance form of the inclusion-exclusion principle from part (i).

For a proper subset $J$ of the $n$ cyclic difference constraints, with $|J|=k<n$, the selected edges form disjoint paths around the cycle, including isolated vertices. There are $n-k$ components. On each component, choosing one value of $f$ arbitrarily determines all the other values by the prescribed differences. No consistency condition occurs because the cycle has been broken. ThereforeThis also works for $n=2$, whose two directed constraints use the same pair of vertices: any single constraint leaves one freely chosen value.

If all $n$ constraints hold, summing them around the cycle gives the necessary conditionIt holds when $n$ is odd and fails when $n$ is even, the latter sum being congruent to $n/2$. When it holds, choose $f(0)$ in $n$ ways and determine every other value; the final constraint is then consistent. Thus the full intersection has size $F=n$ for odd $n$ and $F=0$ for even $n$.

There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ subsets of size $k$. By the binomial theorem,Hence the number of admissible functions is

For finite sets $A_1,\dots ,A_r$, the inclusion-exclusion principle statesTo prove it, count the contribution of one element. If it belongs to exactly $q\ge 1$ of the sets, it is counted by $\left(\genfrac{}{}{0ex}{}{q}{k}\right)$ intersections of size $k$. Its total weight isusing the binomial theorem. An element belonging to none contributes zero. Summing these weights gives the cardinality of the union and proves the inclusion-exclusion principle. Equivalently, within a finite ambient set $U$, the number avoiding every $A_i$ is the sum over all $J$, with sign $(-1{)}^{|J|}$ and the empty intersection interpreted as $U$.

Write both nonnegative integers $n,k$ in base-p expansions, padding with zero digits to a common length $L$. By the preceding polynomial identity,Expanding the last product with the binomial theorem, each term is obtained by choosing an integer $j_i$ with $0\le j_i\le n_i<p$. Its exponent is ${\sum }_i{j}_i{p}^i$ and its coefficient is ${\prod }_i\left(\genfrac{}{}{0ex}{}{n_i}{j_i}\right)$. Uniqueness of base-p expansions says that the only way this exponent can equal $k$ is to choose $j_i=k_i$ for every $i$.

If some $k_i>n_i$, no such term exists and the coefficient is zero. Otherwise its coefficient is precisely the product below. Comparing the coefficient of $x^k$ proves Lucas theorem:with the convention $\left(\genfrac{}{}{0ex}{}{a}{b}\right)=0$ for $b>a$. This also covers $k>n$, and padding either expansion by further zero digits multiplies the product only by $\left(\genfrac{}{}{0ex}{}{0}{0}\right)=1$.

For $1\le j\le p-1$, the identity for binomial coefficientsshows that $p$ divides $j\left(\genfrac{}{}{0ex}{}{p}{j}\right)$. Since $p$ is a prime number and $j$ is not divisible by $p$, cancellation modulo $p$ givesThe binomial theorem consequently gives $(1+x{)}^p\equiv 1+x^p$ as a coefficientwise polynomial modular congruence. Apply the same identity with $x$ replaced by $x^{p^r}$ and use mathematical induction to obtainThis is an iteration of the Frobenius endomorphism in characteristic $p$. Comparing the intermediate coefficients gives the prime-power binomial divisibility result

True. First suppose $p^e\mid N$ with $e\ge 2$ maximal. By the Chinese remainder theorem, choose $a\equiv 1+p^{e-1}(\mathrm{mod}{p}^e)$ and $a\equiv 1$ modulo all other prime-power factors. This is a unit, with Jacobi symbol one, because it is one modulo every prime. For $m=(N-1)/2$, the binomial theorem givesbecause $p\nmid m$ and all higher terms contain $p^e$. It is therefore a witness to the desired failure.

If $N$ is square-free and composite, it has at least two prime factors. Choose $a$ to be a quadratic nonresidue at one prime $p$ and one at every other prime, again using the Chinese remainder theorem. Then $(a/N)=-1$. At a different odd prime $q\mid N$, however, $a^m\equiv 1\not\equiv -1(\mathrm{mod}q)$. These two cases prove that every odd composite has an Euler-Jacobi witness, unlike the situation for the ordinary Fermat primality test.

For finite sets $E_1,\dots ,E_s$, the inclusion-exclusion principle statesIt counts each element once: an element in exactly $q$ of the sets contributes ${\sum }_{j=1}^q(-1{)}^{j+1}(\genfrac{}{}{0ex}{}{q}{j})=1$, by the binomial theorem.

For the cyclic digit run problem, let $E_j$ mean that the three digits starting at position $j$ form a run, for $j=1,2,3,4$. Every run of length at least three contains one of these triples, so we need $|E_1\cup E_2\cup E_3\cup E_4|$. Introduce the five differencesA starting digit and these five residues determine a unique string, including runs that cross $9$ and $0$. In these coordinates $E_j$ requires $(d_j,d_{j+1})=(1,1)$ or $(-1,-1)$.

Each single event fixes two differences, with two choices of sign; the initial digit and the other three differences are free. Thus $|E_j|=10\cdot 2\cdot 10^3=20000$. For intersections of two events, adjacent starting positions force three consecutive differences to have the same sign, giving $10\cdot 2\cdot 10^2=2000$. There are three such pairs. The other three pairs have disjoint constrained difference positions, with independent signs and one free difference, giving $10\cdot 4\cdot 10=400$ each. Consequently the sum of pair-intersection sizes is $3\cdot 2000+3\cdot 400=7200$.

For triple intersections, $E_1\cap E_2\cap E_3$ and $E_2\cap E_3\cap E_4$ each force four consecutive differences to have the same sign, leaving one free difference, and each has size $10\cdot 2\cdot 10=200$. The other two triples, $E_1\cap E_2\cap E_4$ and $E_1\cap E_3\cap E_4$, divide the five differences into two blocks with independent signs; each has size $10\cdot 4=40$. The triple-intersection sum is therefore $480$. Finally, all four events force all five differences to have the same sign, giving $20$ strings.

The inclusion-exclusion principle now gives the number of stringsUsing differences makes the overlap conditions explicit and prevents double-counting long cyclic digit runs.

First establish the binomial theorem needed throughout this question. For integers $0\le m\le n$, define the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ to be the number of $m$-element subsets of an $n$-element set. Counting ordered selections and then forgetting their order giveswith the factorial convention $0!=1$. In the product of $n$ factors $(1+z)$, choose $z$ from exactly $m$ factors and $1$ from the others. Each choice contributes $z^m$, and there are $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ choices. The distributive law therefore provesfor every complex number $z$, including $n=0$ by the empty-product convention.

To evaluate the even-indexed sum, use the even part of a polynomial: averaging the binomial theorem at $z$ and $-z$ cancels the odd powers. For $z=i\sqrt{3}$,The two complex numbers satisfy $1\pm i\sqrt{3}=2e^{\pm i\pi /3}$. Their $6n$th powers are both $2^{6n}$, since $e^{\pm 2\pi in}=1$. Thus the sum is

Differentiate the finite binomial theorem and set $z=1$. For $n\ge 1$ this givesFor $n=0$ the sum is $0$ directly.

For the alternating binomial moments, it is useful to differentiate in a form that introduces falling factorials. Write $(m{)}_j=m(m-1)\cdots (m-j+1)$, with $(m{)}_0=1$. Differentiating the binomial theorem $j$ times and multiplying by $z^j$ yields, for $0\le j\le n$,At $z=-1$, the right side vanishes when $j<n$, and equals $(-1{)}^{n}n!$ when $j=n$.

The polynomials $(X{)}_0,\dots ,(X{)}_r$ have degrees $0,\dots ,r$ and leading coefficient $1$, so successive cancellation of leading terms expresses $X^r$ as a linear combination of them. If $r<n$, every falling-factorial term has index $j<n$ and hence its alternating sum vanishes. If $r=n$, the coefficient of $(X{)}_n$ is $1$, and all lower-index terms still vanish. Therefore the alternating moments areFor $n=0$, the latter identity uses the constant polynomial $X^0=1$, so its value at $X=0$ is $1$; thus $S_0(0)=1$ as well. This makes the edge-case convention explicit rather than treating $0^0$ as an unrelated numerical expression.

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$.