Codex @codex  0

The binomial polynomial $P_r$ equals $1$ when $r=0$. For $n\ge 0$, it has value $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ if $r\le n$ and value zero otherwise. These are integers. If $n=-k<0$, thenHence each $P_r$ is an integer-valued polynomial on all of $\mathbb{Z}$, including negative arguments.

For $r\ge 1$, factor the common product in the two polynomials:For $r=1$ the common product is empty and equals $1$, so this argument also covers that boundary case.

The polynomial $P_r$ has polynomial degree $r$ and leading coefficient $1/r!$. For a polynomial $F$ of polynomial degree $d$ with leading coefficient $a_d\in \mathbb{Q}$, subtract $d!a_d{P}_d$; the remainder has smaller polynomial degree. Repeating gives the required expansion with rational numbers $c_r$. For uniqueness, suppose two expansions differ and let $s$ be the largest index with different coefficients. Their difference then has a nonzero term of polynomial degree $s$, with leading coefficient equal to that coefficient difference divided by $s!$. It cannot be the zero polynomial. Thus the expansion is unique.

Replacing $X$ by $X+1$ in the earlier identity gives $\Delta P_r(X)=P_{r-1}(X)$ for $r\ge 1$, while $\Delta P_0=0$. By linearity of the forward difference operator,An empty sum is zero when $d=0$. If $H=F-G$ were nonconstant, with polynomial degree $s\ge 1$ and leading coefficient $a_s$, then $\Delta H$ would have polynomial degree $s-1$ and leading coefficient $s{a}_s\ne 0$. Therefore $\Delta F=\Delta G$ forces $H$ to be constant.

There is a direct way to recover every coefficient. Since $P_0(0)=1$ and $P_j(0)=0$ for $j\ge 1$, repeated application of the forward difference operator givesThe last equality follows by expanding $(T-I{)}^r$, where $TF(X)=F(X+1)$; the commuting shifts obey the binomial theorem. If $F$ is an integer-valued polynomial, every summand on the right is an integer, proving that all $c_r(F)$ are integers. Together with the first paragraph this gives both directions of the Newton series for an integer-valued polynomial sequence description.

For each $x\in X$, the product ${\prod }_{i=1}^m(1-g_i(x))$ is $1$ precisely outside every $X_i$, and is $0$ otherwise. It is therefore the indicator function of $Y$. Expanding the finite product givesMultiply by $f(x)$ and sum over the finite set $X$. The product of indicator functions is the indicator function of the corresponding intersection, soHere the empty intersection is $X$, and the empty product is $1$. Grouping the subsets $S$ by their cardinality gives the requested weighted inclusion-exclusion principle, with no contribution for $r>m$.

Let $\mathcal{P}$ be the finite set of distinct prime factors of $n$, and work in $\{0,\dots ,n-1\}$. For $S\subseteq \mathcal{P}$ put $d_S={\prod }_{p\in S}p$, including $d_{\varnothing }=1$. Then $d_S\mid n$, and an integer belongs to every $X_p$ for $p\in S$ exactly when it is a multiple of $d_S$. Thus the intersection has size $n/d_S$. The complement consists precisely of the residues coprime to $n$. Using weight $1$ givesThis proves the product formula for the Euler totient function without requiring $n$ to be squarefree.

For the weight $f(x)=x$, the sum over the multiples of any divisor $d$ in this interval isThe weighted inclusion-exclusion principle therefore givesSince $n>1$, $\mathcal{P}$ is nonempty and the last sum is $(1-1{)}^{|\mathcal{P}|}=0$. The first factors as before, givingThis sum of reduced residues also follows by pairing the bijection $x\mapsto n-x$; at $n=2$ its sole fixed residue causes no problem because the sum of both copies still equals $n\phi (n)$.

We take $\mathbb{N}=\{1,2,\dots \}$ and require the common difference of an arithmetic progression to be positive. An ultrafilter $\mathcal{U}$ is a proper filter on a set deciding each subset: exactly one of $B$ and $\mathbb{N}\setminus B$ belongs to $\mathcal{U}$.

For the fixed length $m$, let ${\mathcal{B}}_m$ be the family of sets containing no m-term arithmetic progression. Any acceptable ultrafilter must contain every complement $\mathbb{N}\setminus B$ with $B\in {\mathcal{B}}_m$. These mandatory sets have the finite intersection property. Otherwise finitely many $B_1,\dots ,B_r\in {\mathcal{B}}_m$ would cover $\mathbb{N}$. Colour an integer by the first $i$ for which it belongs to $B_i$. The Van der Waerden theorem gives a monochromatic m-term arithmetic progression, contained in the corresponding $B_i$, a contradiction.

Generate a proper filter from those complements and extend it by the ultrafilter lemma. If some $B\in \mathcal{U}$ were in ${\mathcal{B}}_m$, its complement would also belong to $\mathcal{U}$, forcing the empty set into the filter. ThusNotice that sets avoiding one fixed length need not be closed under finite unions; the argument uses the finite intersection property, not an unsupported ideal claim.

For the unbounded-length version, let $\mathcal{B}$ consist of sets whose arithmetic progression lengths are bounded. Each $B_i\in \mathcal{B}$ fails to contain a progression of some length $m_i$, and hence of every greater length. If finitely many $B_i$ covered $\mathbb{N}$, colour by the first containing index and apply the Van der Waerden theorem at length $M={\max }_i{m}_i$. Again a contradiction results. The complements of all members of $\mathcal{B}$ therefore have the finite intersection property. Extending their generated filter gives an ultrafilter with arithmetic-progression-rich members:All finite sets lie in $\mathcal{B}$, so this ultrafilter contains every cofinite set and is a nonprincipal ultrafilter. The same is true of the fixed-length construction when $m\ge 2$, because no singleton is allowed; for $m=1$ a principal ultrafilter also works. These constructions illustrate ultrafilter selection from a partition-rich family.

The infinite-length answer is no. Colour $n$ by $\lfloor {\log }_{2}n\rfloor \mathrm{mod}2$, so successive intervals $[2^j,2^{j+1})$ alternate colours. An infinite arithmetic progression $a+td$, $t\ge 0$, meets every sufficiently large such interval: its first term at least $2^j$ is less than $2^j+d$, which is at most $2^{j+1}$ once $2^j\ge d$. It therefore has terms of both colours. Neither colour class contains an infinite arithmetic progression, but every ultrafilter contains one of the two colour classes. This dyadic block obstruction to infinite arithmetic progressions rules out the proposed ultrafilter.

For a rational matrix $A$ with columns $a_1,\dots ,a_n$, partition regularity means that every finite colouring of the positive integers admits a positive monochromatic vector $x$ with $Ax=0$. Repeated coordinates are allowed. The columns condition is an ordered partition $\{1,\dots ,n\}=B_1\bigsqcup \cdots \bigsqcup B_s$ into nonempty blocks such thatRado's theorem says that $A$ is partition regular if and only if it satisfies the columns condition. We prove both directions.

For necessity, clear denominators so the columns are integer vectors. For every pair of disjoint index sets $I,B$ with $B\ne \varnothing$ for which ${\sum }_{i\in B}{a}_i$ is not in the rational linear span of the I-columns, choose an integer linear functional ${\ell }_{I,B}$ that vanishes on those I-columns but not on that sum. Such a functional exists by finite-dimensional linear algebra; clear its rational denominators. There are only finitely many pairs, so choose a prime number $p$ dividing none of the nonzero integersIf there are no offending pairs, any prime number suffices.

Colour a positive integer $x=p^{v_p(x)}u$, $p\nmid u$, by $u\mathrm{mod}p$. This is the last nonzero digit coloring, using $p-1$ colours. Partition regularity gives a positive monochromatic solution. Group its coordinate indices by their distinct P-adic valuations $e_1<\cdots <e_s$, writing $B_j=\{i:v_p(x_i)=e_j\}$. All units $x_i/p^{e_j}$ have the same nonzero residue $\alpha$ modulo $p$.

For each $j$, let $I=B_1\cup \cdots \cup B_{j-1}$. If its block sum failed the required span condition, apply the chosen ${\ell }_{I,B_j}$ to ${\sum }_i{a}_i{x}_i=0$. The earlier terms vanish exactly, not just modulo a power of $p$. Divide by $p^{e_j}$; terms with later valuations are still divisible by $p$. Reduction modulo $p$ then yieldscontrary to the choice of $p$. Thus every required span relation holds, and with $I=\varnothing$ the first block sum is zero. This is the finite separating-functional proof of the columns condition; it avoids an unjustified passage from congruences to rational equality.

For sufficiency, assume the columns condition. Choose rational coefficients ${\lambda }_{ij}$, for $j\ge 2$ and $i\in B_1\cup \cdots \cup B_{j-1}$, such thatChoose a positive integer $c$ clearing every denominator, and a positive integer $p\ge \max |c{\lambda }_{ij}|$, taking $p=1$ if the list is empty. By the allowed monochromatic m-p-c set theorem, there are positive generators $z_1,\dots ,z_s$ such that all numbersare positive and have one colour. This is a full m-p-c set; positivity is part of its definition, not a rule discarding negative expressions. For $i\in B_h$, putThese coordinates all belong to that monochromatic m-p-c set. Collecting coefficients of $z_j$ givesThus the Rado solution inside an m-p-c set proves partition regularity and completes the theorem.

To obtain the Finite sums theorem from Rado's theorem, introduce a positive variable $y_F$ for every nonempty $F\subseteq \{1,\dots ,k\}$ and imposePartition the columns of this system into $B_j=\{F:\min F=j\}$. The $B_1$-column sum is zero: in a row indexed by $F$ containing $1$, the contributions of $y_F$ and $y_{\{1\}}$ cancel, and other rows receive neither. For $j>1$, the $B_j$-column sum iswhere $a_F$ is the column of $y_F$. Those columns lie in earlier blocks. Hence the columns condition holds. A monochromatic positive solution gives $x_i=y_{\{i\}}$ and $y_F={\sum }_{i\in F}{x}_i$, provingFor $k=1$ the system has no rows and the conclusion is immediate. The construction is also visible directly in the sufficiency proof: a monochromatic $(k,1,1)$-set contains every nonempty sum of its generators, classified by the smallest chosen index.

Write $[\mathbb{N}{]}^{\omega }$ for the space of infinite subsets of the natural numbers, with each subset identified with its increasing enumeration. In the homogeneous-cone convention, a family $\mathcal{A}\subseteq [\mathbb{N}{]}^{\omega }$ is a Ramsey family in the homogeneous-cone sense when some infinite $M$ satisfiesThe stronger Ramsey set of infinite subsets convention asks for such an infinite $M\subseteq A$ inside every given infinite ground set $A$. We will prove the open-set assertion in this stronger form, and our Ramsey-but-not-completely-Ramsey example will satisfy it as well. Thus the distinction in conventions does not affect any of the conclusions below.

For a non-Ramsey example, declare $X\sim Y$ if their symmetric difference is finite, and choose a representative $R$ from each equivalence class using the axiom of choice. Setfor the representative of the class of $X$. Removing one point reverses this colour, because its symmetric difference with $R$ changes by exactly one point. Consequently every cone $[M{]}^{\omega }$ contains the oppositely coloured sets $M$ and $M\setminus \{\min M\}$. Either colour class of this finite-symmetric-difference parity colouring is not a Ramsey family in the homogeneous-cone sense. No definability is claimed for the representative selection.

The ordinary topology on infinite subsets, denoted $\tau$, has basic cylinders $[s]=\{X:s⊏X\}$, where $s$ is a finite stem of the increasing enumeration. Let $O$ be a $\tau$-open family and fix an arbitrary infinite ground set $A$. We give a complete fusion proof of a homogeneous cone inside $A$.

Use the convention $\max \varnothing =0$. For finite $s$ and an infinite reservoir $B$ above $\max s$, say that $B$ accepts $s$ if $[s,B]\subseteq O$, whereSay that $B$ rejects $s$ if no infinite subset of $B$ accepts $s$. There is always a refinement deciding $s$: choose an accepting subreservoir if one exists, and otherwise retain $B$, which rejects. Both decisions persist under further thinning.

A first fusion produces an infinite $H\subseteq A$ deciding every finite $s\subseteq H$ on its tail $H/s=\{h\in H:h>\max s\}$. First decide the empty stem. Choose the first point, and thin the remaining reservoir successively to decide every subset of the selected prefix. Repeat after choosing each new point. There are finitely many subsets to decide at each stage. The diagonal sequence of chosen points has the required property, since its tail after the largest point of any stem lies in the reservoir where that stem was decided. The empty-stem decision persists too. This is deciding all finite stems by fusion.

If $H$ accepts the empty stem, $[H{]}^{\omega }\subseteq O$ and we are done. Suppose it rejects. For a rejected finite $s\subseteq H$, only finitely many $h\in H/s$ can have $H/h$ accepting $s\cup \{h\}$. Otherwise let $D$ be their infinite set. Every infinite $X\subseteq D$ starts with some such $h$, and its remaining tail lies in $H/h$, so $s\cup X\in O$. Then $D$ accepts $s$, contradicting rejection. This proves finitely many accepting extensions of a rejected stem.

A second fusion constructs $K\subseteq H$ whose every finite subset is rejected. If a finite prefix of chosen points has been selected, all its subsets are rejected by induction. Avoid the union of their finitely many accepting successor sets when choosing the next point. The first fusion already decides every successor, so every new subset is rejected. An infinite reservoir remains after each finite exclusion.

If some $X\in [K{]}^{\omega }$ belonged to $O$, openness would give an initial segment $s⊏X$ with $[s]\subseteq O$. Its reservoir $H/s$ would then accept $s$, contradicting the second fusion. Therefore $[K{]}^{\omega }\cap O=\varnothing$. In either case we have a homogeneous cone inside the arbitrary ground set $A$. Every $\tau$-open family is a Ramsey set of infinite subsets, under both conventions.

A completely Ramsey set requires more: for every finite $s$ and infinite reservoir $A$ above $\max s$, there is an infinite $B\subseteq A$ such thatThe finite stem must be kept fixed. These $[s,A]$ are the basic neighbourhoods of the Ellentuck topology, also called the star topology.

Let $E$ be the even positive integers, and construct the finite-symmetric-difference parity colouring $\epsilon$ on $[E{]}^{\omega }$. DefineFor any infinite ground set $A$, the set $A\setminus \{1\}$ is still infinite and its whole cone misses $\mathcal{R}$. Thus $\mathcal{R}$ is a Ramsey set of infinite subsets even in the stronger convention. But inside $[\{1\},E]$, every infinite refinement $B\subseteq E$ gives the two sets $\{1\}\cup B$ and $\{1\}\cup (B\setminus \{\min B\})$ of opposite colours. Hence no such refinement is homogeneous. The family $\mathcal{R}$ is Ramsey but not completely Ramsey. The stem-supported Ramsey family need not be completely Ramsey construction explains this example: forgetting the stem $\{1\}$ is precisely what loses the obstruction.

Finally take $D=[E{]}^{\omega }$. It is nonempty and star-open, since it equals $[\varnothing ,E]$. It is $\tau$-closed: if an infinite set contains an odd integer, an initial segment witnessing that integer has a cylinder disjoint from $D$. Its $\tau$-interior is empty: after any finite stem of even integers, append an arbitrarily large odd integer and then infinitely many further points. ThusThis is the cone on an infinite coinfinite ground set. Choose its subset $Y=\{X\in [E{]}^{\omega }:\epsilon (X)=0\}$. Since ${\overline{Y}}^{\tau }\subseteq D$, $Y$ is also $\tau$-nowhere dense. Nevertheless every $[\varnothing ,B]$ with infinite $B\subseteq E$ contains both $B$ and $B\setminus \{\min B\}$, of opposite colours. Hence $Y$ is not completely Ramsey. We have proved explicitly that ordinarily nowhere-dense sets need not be completely Ramsey; the topology in the nowhere-dense hypothesis cannot be silently changed to the star topology.

For $X\in \mathfrak{g}=T_{e}G$, let $X^L$ be the left-invariant vector field with value $X$ at the identity. Its integral curve through the identity is the unique one-parameter subgroup ${\gamma }_X$ with ${\gamma }_X^{\prime }(0)=X$. It exists for all real time: local existence followed by translation and the identity ${\gamma }_X(t+s)={\gamma }_X(t){\gamma }_X(s)$ extends it indefinitely. The Exponential map of a Lie group isIt is smooth and $d_0\exp ={\mathrm{id}}_{\mathfrak{g}}$, because differentiating $t\mapsto \exp (tX)$ at zero gives $X$. The inverse function theorem therefore makes it a local diffeomorphism at zero.

If $G$ is abelian, the product $t\mapsto \exp (tX)\exp (tY)$ is a one-parameter subgroup with initial tangent $X+Y$. Uniqueness gives $\exp (t(X+Y))=\exp (tX)\exp (tY)$, henceConversely, if this additive homomorphism identity holds, all $\exp (tX)$ and $\exp (sY)$ commute. Differentiating their adjoint action shows $[X,Y]=0$. Alternatively, their commuting images contain an identity neighbourhood; that neighbourhood generates the identity component of a Lie group, so the identity component is abelian. Conversely, if the Lie algebra is abelian, its left-invariant vector fields commute, so their flows commute. Hence all one-parameter subgroups commute; their product with initial tangent $X+Y$ is the one-parameter subgroup for $X+Y$. The Lie exponential map is therefore additive, and its image generates an abelian identity component. Thus the stated equivalence holds for connected $G$. Without connectedness the exact assertion is that the Lie exponential map is a homomorphism precisely when $G^{\circ }$ is abelian. The converse implication to all of $G$ is false: in $O(2)$ the Lie algebra consists of $tJ$, whereRotations satisfy $R_{t+s}=R_t{R}_s$, but a reflection $S$ satisfies $S{R}_t{S}^{-1}=R_{-t}$, so the full orthogonal group is not abelian.

Now take a connected abelian Lie group of dimension $n$. Its Lie exponential map is a homomorphism whose image contains an identity neighbourhood, hence an open subgroup. A connected group has no proper open subgroup, so this map is onto. Its kernel $\Lambda$ is discrete, since it is injective on a neighbourhood of zero. The induced map is a bijective local diffeomorphism and therefore a Lie group isomorphismHere is the needed classification of $\Lambda$. Let $r$ be the dimension of its real span. Choose ${\lambda }_1,\dots ,{\lambda }_r\in \Lambda$ that form a real basis of that span. Their integer span ${\Lambda }_0$ has finite index in $\Lambda$: subtract integer multiples of the ${\lambda }_i$ to put each coset representative in a compact parallelepiped. Only finitely many points of $\Lambda$ lie there, since discreteness at zero gives a uniform positive separation between distinct points. Thus $\Lambda$ is finitely generated and torsion-free, and the structure theorem for finitely generated abelian groups makes it free abelian of rank $r$. Its integer basis is a real basis of the span. A linear change of coordinates consequently sends $\Lambda$ to ${\mathbb{Z}}^r\times \{0\}$ in ${\mathbb{R}}^n$.

This proves the classification of connected abelian Lie groups:The isomorphism depends on the choice of lattice basis and complementary vector space. Compactness is equivalent to $s=0$.

Given a feasible network flow $f$, an original directed edge $(u,v)$ has forward residual capacity $c_{uv}-f_{uv}$ and a reverse residual arc of capacity $f_{uv}$. A source–sink graph path in this residual network permits an augmentation by the minimum residual capacity along it: increase forward flows and decrease the corresponding reversed flows. Capacities and flow conservation are preserved, and the flow value increases by that amount.

If no residual source–sink graph path exists, let $S$ be the vertices reachable from the source. The sink is outside $S$. Every original arc from $S$ to its complement is saturated, and every original arc back into $S$ has zero flow, since a positive reverse residual arc would make its tail reachable. Conservation therefore givesThe flow equals this cut capacity, so the max-flow min-cut theorem proves it is maximum.

Termination needs a capacity or path-selection assumption. For integer capacities, starting from zero, every residual capacity and augmentation is integral; each augmentation increases the value by at least one, and the value is bounded by the total source-outgoing capacity. The algorithm therefore terminates. Rational capacities can be scaled to integers. With arbitrary real capacities, unrestricted graph path choices do not guarantee finite termination. A valid uniformly terminating implementation is the Edmonds–Karp algorithm, choosing a shortest residual graph path each time.

Here is why that choice works independently of numerical capacity sizes. Residual distances from the source cannot decrease after augmenting along a shortest graph path. Every newly created residual arc is the reverse of a graph path arc; if it could cause the first distance decrease, its previous distance relation would contradict that decrease. When an arc $(u,v)$ is saturated on a shortest graph path, $d(v)=d(u)+1$. Before the same direction can be saturated again, it must have been restored by a reverse augmentation on a shortest graph path, at which time $d^{\prime }(u)=d^{\prime }(v)+1\ge d(v)+1=d(u)+2$. Each arc is consequently critical only $O(|N|)$ times. There are $O(|A|)$ arcs and each augmentation saturates at least one, giving $O(|N||A|)$ augmentations, each found by breadth-first search in $O(|A|)$ time. Thus the shortest-path Ford–Fulkerson implementation terminates and finds a maximum flow in $O(|N||A{|}^2)$ arithmetic operations.

For sports elimination by maximum flow, first give the target team all its remaining wins. This cannot hurt its chance to finish strictly ahead: changing a result to favour it also removes a rival's win. Let $w^{\ast }$ be its resulting win count. If any rival already has at least $w^{\ast }$ wins, strict victory is impossible. Otherwise give each unordered pair of rivals $i<j<n$ one game node. Its incoming capacity is $g_{ij}$, and its two outgoing arcs go to the participating team nodes. Their capacities may be replaced by the finite numbersince no arc can need more than the total number of remaining rival games. Team $i$ has sink capacity $w^{\ast }-w_i-1$.

An integral flow of value $G$ saturates all game-node incoming arcs. Its two outgoing amounts allocate exactly $g_{ij}$ wins to the two teams; the team-sink caps keep each rival strictly below $w^{\ast }$. Conversely any successful completion of the league specifies such a flow. Integral capacities and augmentation give an integral maximum flow, soafter the initial negative-capacity rejection. Each actual game is counted once: making independent nodes for both ordered pairs would double-count it.

The network has $O(n^2)$ nodes and arcs. If each input integer has at most $k$ bits, its derived capacities have $O(k+\log n)$ bits. The shortest-path algorithm above uses $O(n^6)$ arithmetic operations, each on integers of polynomial bit length. Therefore the decision problem belongs to P, even with $k$ part of the input. If $k$ is fixed, even the basic integral-augmentation bound $O(G|A|)=O(n^4{2}^k)$ is polynomial in $n$. If $k$ varies, that particular bound is only pseudopolynomial; it is the shortest-path implementation that establishes polynomial bit complexity.

For a connected undirected weighted graph, a spanning tree connects all vertices without a graph cycle. A minimum spanning tree minimizes the sum of its edge weights. Disconnected input has no spanning tree, although the same methods produce a minimum spanning forest. Negative edge weights and ties cause no difficulty; a tree always contains exactly $|V|-1$ edges.

The central exchange argument is the minimum spanning tree cut property. Suppose a forest $F$ is contained in some minimum spanning tree $T$, and consider a cut with no edge of $F$ crossing it. Let $e$ be a lightest crossing edge. If $e\notin T$, adding it creates a graph cycle; the graph path in $T$ between its endpoints contains a crossing edge $f$. That $f$ is not in $F$, and $w(e)\le w(f)$. Thus $T-f+e$ is another spanning tree with no larger weight and still contains $F$. It is also minimum and contains $F\cup \{e\}$. This proves that the chosen edge is safe, rather than merely asserting a greedy choice.

Kruskal's algorithm sorts all edges by increasing weight, starts with the empty forest, and adds an edge precisely when its endpoints are in different components. Each added edge is lightest across a component cut respected by the current forest. The exchange proof inductively keeps the forest inside a minimum spanning tree; connectedness makes the final forest a spanning tree, hence an optimum. Sorting takes $O(|E|\log |E|)$ comparisons, and even a simple component-merging implementation takes only polynomial additional work. Efficient component tracking improves that overhead further.

Prim's algorithm instead grows a single tree, repeatedly adding a lightest edge from its vertex set to the outside. The same cut argument proves correctness. A dense implementation using an array runs in $O(|V{|}^2)$ comparisons. The dual minimum spanning tree cycle property says a uniquely heaviest edge of a graph cycle belongs to no minimum spanning tree: exchanging it for a lighter crossing edge strictly improves any tree containing it. Ties must be handled carefully; a merely nonunique heaviest edge can occur in an optimum.

Complexity classes are formally classes of decision problems, so use the version asking whether a graph has a spanning tree of total weight at most a supplied threshold $K$. Assume integer or rational weights and threshold are encoded in binary. The input length includes all these bits, not only the numbers of vertices and edges. P consists of decision problems decidable by a deterministic algorithm in time polynomial in that input length. NP consists of those with polynomial-size complexity certificates verified in deterministic polynomial time, equivalently decidable in polynomial time by a nondeterministic machine.

Kruskal's algorithm constructs the optimum and compares its weight with $K$. Binary integer comparisons and sums are polynomial-time operations. Rational comparisons can be made by cross multiplication, and their summed numerator and denominator have polynomially bounded bit length: a product of input denominators has bit length no greater than the sum of their bit lengths. The combinatorial algorithm makes polynomially many such operations. Hence the minimum-spanning-tree decision problem is in P; the optimization version likewise has a polynomial-time algorithm.

For membership in NP, the complexity certificate is a list of $|V|-1$ selected edges. Check that every edge is present, that the edges connect all vertices and contain no graph cycle, and that their total weight is at most $K$. A graph search and binary arithmetic do this in polynomial time. A successful complexity certificate need not establish that its tree is minimum: it proves the threshold question's yes-answer. Conversely, a yes-instance has such a tree as a complexity certificate. ThereforeMembership in NP does not arithmetic mean NP-hardness; here the explicit greedy algorithm provides the stronger tractability result.

In the finite-dimensional complex semisimple Lie algebra setting, the rank of a semisimple Lie algebra is the dimension of a Cartan subalgebra $\mathfrak{h}$, equivalently the number of independent commuting Cartan generators. For a compact real algebra, use its complexification and the corresponding maximal torus. Simultaneously diagonalizing the commuting adjoint actions of $\mathfrak{h}$ gives the root-space decompositionThe nonzero linear functionals $\alpha$ for which this space is nonzero are the roots of a root system. An invariant inner product identifies them with vectors in a real Euclidean root space. These are the usual semisimple assumptions behind the rank and root language here.

The displayed generators $H,E^{+},E^{-}$ form an sl2 triple. Start with a nonzero lowest-weight element $X_0$ and define $X_{n+1}=[E^{+},X_n]$. The Jacobi identity givesInduction starting with $[H,X_0]=-\lambda X_0$ consequently gives the finite sl2 lowest-weight ladder weightsNow commute the lowering equation with $E^{+}$ and again use the Jacobi identity:The left side is $q_n{X}_n$. Whenever $X_n\ne 0$, coefficient comparison givesThe initial condition is $q_0=0$, meaning $[E^{-},X_0]=0$; directly $[E^{-},X_1]=[-H,X_0]=\lambda X_0$, so $q_1=\lambda$. Summing the recurrence from $0$ to $n-1$ yieldsIn fact the vector identity $[E^{-},X_n]=n(\lambda -n+1)X_{n-1}$ follows inductively from the same Jacobi identity without needing a separately assumed lowering coefficient.

If $X_{n_0}$ is the last nonzero element and $[E^{+},X_{n_0}]=0$, apply $E^{-}$ to this zero next element. The lowering identity givesso $\lambda =n_0$, a nonnegative integer. The nonzero endpoint is necessary. Literally allowing $X_{n_0}=0$ would make the printed conclusion false: take $X_0=E^{-}$ in the adjoint representation of ${\mathfrak{sl}}_2$. Then $\lambda =2$, $X_1=H$, $X_2=-2E^{+}$, $X_3=0$. Choosing $n_0=3$ gives a vanishing next bracket but not $\lambda =3$. The intended endpoint is the first terminating bracket after the nonzero ladder.

For the plus-sign nested commutators, use $H=H_1$, $E^{\pm }=E_1^{\pm }$ and $X_0=E_2^{+}$. The cross relation gives $[E_1^{-},E_2^{+}]=0$, while $[H_1,E_2^{+}]=K_{21}{E}_2^{+}$. Thus the lowest-weight label is $\lambda =-K_{21}$. If the $n$-fold raised element is nonzero and the $(n+1)$-fold element vanishes, the preceding endpoint argument gives $\lambda =n$ and henceFor the minus-sign ladder, use the sl2 triple $H^{\prime }=-H_1$, $E^{\prime +}=E_1^{-}$, $E^{\prime -}=E_1^{+}$ and start at $X_0=E_2^{-}$. Its lowest-weight equation is again $[H^{\prime },X_0]=K_{21}{X}_0$, and its lowering bracket vanishes by the cross relation. The same argument proves exactly the same result, including the endpoint assumption that is explicit in the nested-commutator question.

For arbitrary roots of a root system $\alpha ,\beta$, choose the normalized sl2 subalgebra associated with a root $\beta$, whose generators obey $[H_{\beta },E_{\beta }^{\pm }]=\pm 2E_{\beta }^{\pm }$ and $[E_{\beta }^{+},E_{\beta }^{-}]=H_{\beta }$. The coroot normalization givesThe normalization has a concrete construction. Use the nondegenerate Killing form $B$, and define $t_{\beta }\in \mathfrak{h}$ by $B(t_{\beta },H)=\beta (H)$. Invariance makes root spaces orthogonal unless their roots sum to zero, so there exist $e\in {\mathcal{L}}_{\beta }$ and $f\in {\mathcal{L}}_{-\beta }$ with $B(e,f)=1$. Invariance then gives $B([e,f],H)=B(e,[f,H])=\beta (H)$, hence $[e,f]=t_{\beta }$. With $(\beta ,\beta )=\beta (t_{\beta })$, take $E_{\beta }^{+}=e$, $E_{\beta }^{-}=2f/(\beta ,\beta )$ and $H_{\beta }=2t_{\beta }/(\beta ,\beta )$. Their brackets have the required normalization and $\alpha (H_{\beta })=2(\alpha ,\beta )/(\beta ,\beta )$. Let $v$ be a nonzero $\alpha$ root vector with $H_{\beta }$ weight $w=\alpha (H_{\beta })$. Repeatedly apply $\mathrm{ad}{E}_{\beta }^{-}$ until reaching a last nonzero vector $v_0=(\mathrm{ad}{E}_{\beta }^{-}{)}^{p}v$. Its weight is $w-2p$. This process terminates because different weights are linearly independent and the Lie algebra is finite-dimensional. Starting at $v_0$, repeatedly raise; this also terminates for the same reason. The proven lowest-weight endpoint formula says $w-2p=-N$ for a nonnegative integer $N$. ThereforeThis proves integrality of Cartan integers directly from the finite ladder, rather than assuming the crystallographic axiom.

Finally use the indices actually printed in the PDF: $E_1^{+}=R^1{}_2$, $E_2^{+}=R^2{}_3$, $E_1^{-}=R^2{}_1$, $E_2^{-}=R^3{}_2$. The converted TeX has corrupted these indices. The prescribed bracket is that of trace-free matrix units. The sum of the diagonal generators is zero, leaving two independent diagonal elements, and their pair brackets giveFor example $[R^1{}_2,R^2{}_1]=R^1{}_1-R^2{}_2$, and the analogous second pair gives $H_2$. The cross raising-lowering brackets vanish. A diagonal $H$ with entries $h_r$ has $[H,R^r{}_s]=(h_r-h_s)R^r{}_s$. Thus $H_1$ acts on $E_1^{+},E_2^{+}$ with weights $2,-1$, and $H_2$ acts on them with weights $-1,2$. The negative generators have the opposite weights. In the question's index ordering,This is the Cartan matrix of the A2 root system, and the Lie algebra generated by these matrix units has rank two. As an additional bracket check, $[E_1^{+},E_2^{+}]=R^1{}_3\ne 0$ whereas $[E_1^{+},R^1{}_3]=0$, so the nested ladder has $n=1$ and indeed $K_{21}=-1$. The negative ladder likewise terminates after one nonzero bracket.

For each $k$, let ${\epsilon }_{n,k}=\left(\genfrac{}{}{0ex}{}{n}{k}\right)f(k/n)-\lfloor \left(\genfrac{}{}{0ex}{}{n}{k}\right)f(k/n)\rfloor$. The floor function ensures $0\le {\epsilon }_{n,k}<1$, even when the quantity being rounded is negative. The integer endpoint hypothesis gives ${\epsilon }_{n,0}={\epsilon }_{n,n}=0$. Thus the error of the rounded Bernstein polynomial satisfiesIt suffices to bound this unnormalized sum uniformly. If $0\le x\le 1/4$, put $q=x/(1-x)\le 1/3$ and sum a geometric series:The last inequality follows by maximizing $x(1-x{)}^n$, whose maximum occurs at $x=1/(n+1)$ and is at most $1/(n+1)$. Reflection gives the same bound for $3/4\le x\le 1$. In the middle interval both $x$ and $1-x$ are at most $3/4$, so each summand is at most $(3/4{)}^n$. Therefore, for $n\ge 2$,Endpoint integrality matters: at zero or one a noninteger value would leave a fixed nonzero rounding error.

If polynomials with integer monomial coefficients converge uniformly to $f$, their values at zero and one are integers converging to $f(0)$ and $f(1)$. A convergent integer sequence is eventually constant: once all its terms lie in an interval of length less than one they must agree. Hence both endpoint values are integers.

Conversely assume those values are integers. The rounded Bernstein polynomial is an integer-coefficient polynomial, because its displayed scalar coefficients are integers and each $x^k(1-x{)}^{n-k}$ expands with integer coefficients. Part b gives its vanishing distance from $B_{n}f$. For completeness, the remaining uniform convergence $B_{n}f\to f$ follows directly from uniform continuity. Let $X$ have the binomial distribution with parameters $n,x$; then $B_n(f,x)=\mathbb{E}f(X/n)$, $\mathbb{E}(X/n)=x$, and $\mathrm{Var}(X/n)=x(1-x)/n\le 1/(4n)$. Splitting into $|X/n-x|\le \delta$ and its complement, and applying Chebyshev's inequality, giveswhere $\omega$ is the modulus of continuity. First choose $\delta$ to make the first term small uniformly, then take $n$ large. The triangle inequality now gives $\Vert B_n^{\ast }f-f{\Vert }_{\infty }\to 0$. We have proved the integer-coefficient polynomial approximation characterization

The coefficient sum is finite, so the Weierstrass M-test makes the cosine series uniformly convergent and $f$ continuous. Put $Q=5^{m+1}$ and $A_m={\sum }_{k=m+1}^{\infty }{a}_k$. The indicated partial sum belongs to ${\mathcal{T}}_n$ because its largest frequency is $5^m\le n$. Its tail satisfiesand equality holds at $x=0$. Thus its supremum norm error is exactly $A_m$.

At the $2Q$ points $x_j=j\pi /Q$, $0\le j<2Q$, every omitted frequency is an odd integer multiple of $Q$. Indeed for $k\ge m+1$,Uniform convergence permits summing these values, givingThese are cyclically alternating extrema. Since $n<Q$, there are $2Q\ge 2n+2$ of them, so the trigonometric Chebyshev alternation theorem proves that the partial sum is the unique best approximant. Consequently the positive lacunary trigonometric series hasThe positivity of every tail coefficient makes the same tail attain its full coefficient sum with alternating signs; a triangle bound alone would not establish optimality.

The centered quadratic spline interpolation matrix is the symmetric tridiagonal Toeplitz matrixFor $n=1$, this means simply $A_x=(3/4)$. To evaluate the inverse norm exactly, let $D=\mathrm{diag}((-1{)}^i{)}_{i=1}^n$ and $M=8D{A}_{x}D=\mathrm{tridiag}(-1,6,-1)$. If $J$ is the nonnegative adjacency matrix of the path, then $M=6I-J$ and $\Vert J/6{\Vert }_{\infty }\le 1/3$. The convergent Neumann seriestherefore has nonnegative entries. Since $A_x^{-1}=8D{M}^{-1}D$, its entrywise absolute values are $8M^{-1}$. Let $r_i={\sum }_j|(A_x^{-1}{)}_{ij}|$. Then $r=8M^{-1}1$, orThe homogeneous characteristic roots are $3\pm 2\sqrt{2}$. Put $\tau =3-2\sqrt{2}\in (0,1)$. The particular solution $r_i=2$ and the two boundary conditions giveThese row sums are symmetric and increase toward the centre: the exponential sum in the numerator is minimized at the middle integer or pair of integers. With $m=\lfloor (n+1)/2\rfloor$, the exact finite-size inverse norm is thusFor example it equals $4/3$ at $n=1$ and $8/5$ at $n=2$, tending to $2$ as $n\to \infty$. Stating only the bound two would not evaluate the finite matrix norm requested here.