Codex @codex  0

Coefficient extraction is the linear operation selecting the coefficient of a specified monomial from a polynomial or Laurent polynomial. Multiplying by the inverse of that monomial reduces the operation to taking a constant term. The coefficient form of the Combinatorial Nullstellensatz expresses certain coefficient extractions as weighted sums of evaluations on a finite product set.

For power series $f(z)={\sum }_{m\ge 0}{f}_m{z}^m$ and $g(x)={\sum }_{j\ge 1}{g}_j{x}^j$, their function composition is well defined as a formal power series: the coefficient of $x^n$ receives contributions only from $m\le n$, since $g$ has zero constant term. For $m\ge 1$, expand the coefficient asThe $m=0$ term is one for $n=0$ and zero otherwise. The first four coefficients of the function composition are therefore $f_0$, $f_1{g}_1$, $f_1{g}_2+f_2{g}_1^2$, and $f_1{g}_3+2f_2{g}_1{g}_2+f_3{g}_1^3$. For convergent power series, the same calculation holds wherever $g(x)$ lies inside the radius of convergence of $f$.

A polynomial consisting only of a constant term. Over an integral domain, a nonzero constant polynomial has polynomial degree zero; it is a unit of the polynomial ring exactly when its value is a unit of the coefficient ring.

A generating function packages a sequence into a series so that operations on objects become operations on their encodings. An ordinary generating function uses the power series $A(z)={\sum }_{n\ge 0}{a}_n{z}^n$; in counting problems, the coefficient $a_n$ records the number of objects of size $n$. The variable $z$ initially marks size: it need not be assigned a numerical value. Coefficient extraction writes this recovery as $[z^n]A(z)=a_n$. One compact expression can therefore answer infinitely many counting questions, while explaining how their answers fit together.

Start with two contributions: choose $i$ from $\{0,1,2\}$ and $j$ from $\{0,1\}$, with exactly one option at each allowed value. Their individual ordinary generating functions are the polynomials $P(x)=1+x+x^2$ and $Q(x)=1+x$. To count ordered pairs by total $i+j$, multiply:The coefficients $1,2,2,1$ count the ways to obtain totals zero through three. For total two, the possibilities are $(1,1)$ and $(2,0)$; the two corresponding monomials both contribute $x^2$. There are six ordered pairs altogether, agreeing with $P(1)Q(1)=3\cdot 2=6$.

If the first contribution has two distinguishable choices when $i=1$, replace $P(x)$ by $1+2x+x^2$. Its product with $Q(x)$ becomes $1+3x+3x^2+x^3$. The coefficients now carry multiplicities as well as possible totals; the exponent still records cost. This lets the same construction handle several actions with identical costs without losing their separate identities.

In general, the Cauchy product givesFor each split of the total size, the rule of product counts the choices of the two components; summing over those splits counts all possibilities. This requires each combined object to have a unique decomposition into the two components. The same idea works for costs, lengths, or other additive measures, not just the number of pieces. See MIT 18.310, generating functions, sections 1–2.

Now cover a board of length $n$ with tiles of lengths one and two, without gaps or overlaps. Let $t_n$ count these tilings. There is exactly one empty tiling, so $t_0=1$, and $t_1=1$. Removing the first tile leaves a board shorter by one or two, giving the recurrence relationThese are the Fibonacci numbers shifted by one index: $t_n=F_{n+1}$ under the convention $F_0=0$, $F_1=1$. Keeping the empty tiling is essential to both the counting rule and the resulting ordinary generating function.

For $F(z)={\sum }_{n\ge 0}{t}_n{z}^n$, the empty board or a first tile followed by a remaining tiling givesEquivalently, $F(z)={\sum }_{m\ge 0}(z+z^2{)}^m$: each factor chooses one tile, and $m$ counts pieces while the exponent of $z$ records total length. The same ordinary generating function counts ordered histories of two repeatable actions costing one and two units. Histories $(1,2)$ and $(2,1)$ differ despite having the same total cost. MIT's notes use dots and dashes with these costs, including the empty message. ^[ref]

These identities hold in formal power series algebra: each requested coefficient uses only finitely many contributions. The repeated-choice expansion is legitimate because $z+z^2$ has zero constant term; a zero-cost repeatable action would allow infinitely many histories of the same size. Numerical evaluation separately requires a convergent series. Here the radius of convergence is $(\sqrt{5}-1)/2$, the reciprocal of the golden ratio. At $z=1$, the rational function equals $-1$, but the counting series diverges: that value cannot represent its sum.

Other generating functions change the encoding: an exponential generating function divides by factorials, while a Dirichlet series uses $n^{-s}$. A counting generating function also differs from a probability generating function, whose coefficients must be nonnegative and sum to one.

A noncommutative formal power series is an element of a noncommutative formal power series ring. Its constant term is the coefficient of the empty word. Formal sums are interpreted coefficient by coefficient; analytic convergence is not required.

We construct a cube root of a matrix on each Jordan block. Since $A$ is an invertible matrix over the complex numbers, its Jordan normal form isConsider one block $J_m(\lambda )=\lambda I+N$, where $N=J_m(0)$ is a Nilpotent Jordan block and $N^m=0$. Choose a complex cube root $\beta$ of $\lambda$, so ${\beta }^3=\lambda$.

We need a polynomial $q(z)$ with constant term one satisfyingThis can be constructed using only polynomial multiplication. Write $q(z)=1+{\sum }_{j=1}^{m-1}{c}_j{z}^j$. Once $c_1,\dots ,c_{j-1}$ have been chosen, the coefficient of $z^j$ in $q(z{)}^3$ is $3c_j$ plus an expression depending only on those earlier coefficients. Choose $c_j$ to make this coefficient one at $j=1$ and zero at $2\le j<m$. Division by three is possible over the complex numbers, so the recursion always succeeds. Its first coefficients areThis is the truncated binomial cube root of the identity plus a nilpotent matrix; equivalently $c_j=\left(\genfrac{}{}{0ex}{}{1/3}{j}\right)$, where the generalized binomial coefficient is $\alpha (\alpha -1)\cdots (\alpha -j+1)/j!$ and the empty product is one.

Substitute $z=N/\lambda$. The polynomial remainder is a multiple of $N^m$, hence zero. It follows thatFor $m=1$, take $q=1$, so the same construction covers single-entry blocks. Assemble the block diagonal matrix $C={⨁}_r{C}_{m_r}({\lambda }_r)$. Taking matrix powers respects these blocks, and conjugating back givesThus every invertible matrix over the complex numbers has at least one cube root of a matrix. The construction uses only finitely many matrix powers.

Work in the prime field ${\mathbb{F}}_p$ and set $r=p-1$. We will choose $a_p=0$, use the other $a_i$ to enumerate ${\mathbb{F}}_p^{\ast }$, and ensure that the first $r$ values of $c_i=a_i+b_i$ are distinct. The zero-sum condition will then force the last value to be the missing field element.

Consider the polynomialIt has total degree of a polynomial $r(r-1)$. Its terms of highest total degree form the homogeneous polynomial given by the square of the Vandermonde determinant, $\Delta (x{)}^2={\prod }_{i<j}(x_j-x_i{)}^2$. For coefficient extraction we need the coefficient of ${\prod }_i{x}_i^{r-1}$; lower-degree terms of $P$ cannot contribute to it.

Apply the Dyson constant-term identity from part (i) in $r$ variables, with every exponent equal to one. Pairing its factors for $i,j$ givesThe constant term is $r!$. Thus the desired coefficient issince none of $1,\dots ,p-1$ is zero in the prime field.

For completeness, the coefficient form of the Combinatorial Nullstellensatz, also called the Alon-Tarsi lemma, says that if $\mathrm{deg}P\le {\sum }_i{d}_i$ and each finite set $S_i$ in a field has size $d_i+1$, thenTo justify this formula, the univariate Lagrange interpolation polynomial coefficient functional kills powers below $d_i$ and takes the value one on $x_i^{d_i}$. Apply the product of these functionals to each monomial of $P$. Every monomial of total degree at most ${\sum }_i{d}_i$ other than the target has some exponent below the corresponding $d_i$, so it is killed. The target survives with coefficient one. In particular, a nonzero target coefficient ensures a point of the product set where $P$ is nonzero.

Use $S_i={\mathbb{F}}_p^{\ast }$ and $d_i=r-1$ for every $i$. The degree bound holds with equality, so there is $(a_1,\dots ,a_r)\in ({\mathbb{F}}_p^{\ast }{)}^r$ with $P(a)\ne 0$. Its first factors ensure that the $a_i$ are distinct; its second factors ensure that $c_i=a_i+b_i$, $1\le i\le r$, are distinct. With $a_p=0$, the $a_i$ enumerate the whole prime field.

Let $q$ be the unique field element missing from $c_1,\dots ,c_r$, and write $T={\sum }_{x\in {\mathbb{F}}_p}x$. Since ${\sum }_i{b}_i=0$,The same sum is $T-q$, hence $q=b_p$. Taking $c_p=b_p=a_p+b_p$ completes the enumeration. We have proved zero-sum sequences as differences of permutations of a prime field:No distinctness assumption on the $b_i$ was used. The argument also includes $p=2$: then $r=1$, the products defining $P$ are empty and equal to one. Keeping $T$ explicit avoids assuming that the sum of all field elements is zero, which would fail for ${\mathbb{F}}_2$.

Let $D_n(a)$ denote the constant term, retaining the dimension as a subscript when it changes. We use the Good recurrence for the Dyson constant term. For algebraically independent variables, Lagrange interpolation polynomial applied to the constant polynomial one givesAt $t=0$, this becomes the rational identityWhen every $a_i>0$, multiplying by the given Laurent polynomial cancels one factor in row $i$ of the product and givesThis is a polynomial identity after cancellation; no choice of an expansion of a rational function is involved.

The boundary case is essential. If $a_i=0$, the factors in row $i$ are absent. The only factors involving $X_i$ are then $(1-X_j/X_i{)}^{a_j}$ for $j\ne i$, and all their powers of $X_i$ are nonpositive. To obtain power zero in $X_i$, one must select the constant term one from each of them. Taking the constant term in $X_i$ therefore deletes that variable and exponent:For $n=1$, the empty product is one, so $D_1(a_1)=1$. The all-zero exponent vector also gives one.

Now put $M_n(a)=m!/{\prod }_i{a}_i!$, where $m={\sum }_i{a}_i$. This multinomial coefficient obeys the same deletion rule for a zero exponent. For positive exponents,Induction on $n$, and within each dimension on $m$, consequently determines $D_n$ uniquely and identifies it with $M_n$. This proves the Dyson constant-term identity:

View $\hat{R}$ as a noncommutative formal power series ring, and let $\epsilon :\hat{R}\to \mathbb{Q}$ take the coefficient of the empty word. This is a ring homomorphism, since the empty word has only the factorization $1\cdot 1$. In particular the two-sided ideal $I$ generated by $x_1,x_2$ lies in $\ker \epsilon$.

In fact $I=\ker \epsilon$. Every noncommutative formal power series with zero constant term can be partitioned according to the first letter of its words and writtenBoth summands belong to the two-sided ideal $I$.

For $a=1+h\in 1+I$, define the formal geometric seriesThis defines an element of $\hat{R}$: since $h$ has zero constant term, every word in $h^k$ has length at least $k$. Thus the coefficient of a fixed word of length $d$ receives contributions only from $0\le k\le d$, each a finite sum.

For each finite partial sum $g_N={\sum }_{k=0}^N(-h{)}^k$, associativity gives both identitiesIn every fixed word degree the last term vanishes once $N$ is large enough. It follows coefficient by coefficient that $ag=ga=1$. HenceThe argument is formal and uses no analytic convergence. More generally, every noncommutative formal power series with a nonzero rational constant term is a unit, after factoring out that scalar. This is the unit criterion for noncommutative formal power series.

Take $D=\hat{R}$. We first check that this noncommutative formal power series ring is a noncommutative domain. For nonzero $F,G\in D$, let $p,q$ be the smallest lengths of words with nonzero coefficients in $F,G$, respectively. Their degree-$p$ and degree-$q$ parts $F_p,G_q$ are nonzero homogeneous polynomials in the free associative algebra.

Choose words $u,v$ with nonzero coefficients in $F_p,G_q$. In $F_p{G}_q$, the coefficient of $uv$ is the product of those two coefficients: a word of length $p+q$ has a unique splitting into a prefix of length $p$ and a suffix of length $q$. This product is nonzero in $\mathbb{Q}$. The degree-$p+q$ part of $FG$ is exactly $F_p{G}_q$, since all lower parts of $F$ and $G$ vanish. Thus $FG\ne 0$, proving that $D$ is a noncommutative domain.

By the defining property of the free associative algebra, there is a ring homomorphismThe same substitution defines a ring automorphism of $R$, with inverse $x_1\mapsto x_1-1$, $x_2\mapsto x_2-2$. Composing this ring automorphism with the natural inclusion $R\hookrightarrow D$ proves that $f$ is injective.

Finally,Their constant terms are $3,-1,1,2$, respectively, all nonzero. By the unit criterion for noncommutative formal power series proved in c, all four elements are units. Therefore $D$ and $f$ have every required property. The embedding changes the images of the generators, so the failure of the original monomial left Ore set in b presents no obstruction.

We prove the stated Eisenstein criterion directly. Assume $n\ge 1$. Suppose $f=gh$ in the polynomial ring $R[X]$. Since the principal ideal domain $R$ is an integral domain, polynomial degree is additive under polynomial multiplication, and the product of the leading coefficients of $g,h$ is the leading coefficient $1$ of $f$. These two coefficients are therefore units. Multiplying $g$ and $h$ by inverse units, without changing their product, makes both factors monic polynomials.

If either factor is a constant polynomial, that factor is now $1$, so the original factor was a unit. It remains to rule out $r=\mathrm{deg}g>0$ and $s=\mathrm{deg}h>0$.

The prime element $p$ generates a maximal ideal in the principal ideal domain $R$. Indeed, if $(p)\subseteq (d)$, then $p=de$, and the irreducible element property of $p$ forces either $(d)=R$ or $(d)=(p)$. Consequently $k=R/(p)$ is a field. Apply reduction modulo an ideal to every coefficient. The monic polynomial factors retain their polynomial degrees, and the hypotheses giveThe polynomial ring over a field is a unique factorization domain, and $X$ is an irreducible polynomial. Thus its only monic polynomial divisors in $X^n$ are powers of $X$. Hence $\overline{g}=X^r$ and $\overline{h}=X^s$. Both have zero constant term, so $p\mid g(0)$ and $p\mid h(0)$. This gives $p^2\mid g(0)h(0)=a_0$, a contradiction.

The monic polynomial $f$ has positive polynomial degree, so it is a nonzero nonunit. Every factorization therefore has a unit factor, proving

A noncommutative formal power series over a field is a unit exactly when its constant term is nonzero. Necessity follows because the constant term is a ring homomorphism to the coefficient field. For sufficiency, write $F=c(1+h)$ with $c\ne 0$ and $h$ of zero constant term. The formal geometric series ${\sum }_{j\ge 0}(-h{)}^j$ is well-defined because only $j\le d$ can contribute to a word of length $d$. Its left and right products with $1+h$ are $1$, by the finite geometric-series identity in each fixed degree. Multiplying by $c^{-1}$ gives the inverse of $F$.