What is the theory of polynomials? - MathOverflow

What is the theory of polynomials?

2011-08-25T14:19:03Z

We all know what polynomials are, along with their elementary properties and many effective algorithms for different representations of polynomials.

The question here is more of a universal algebra question: what is the signature of the theory which best corresponds to polynomials? To illustrate what this question means, it is probably easiest to do this by example:

In the category of Unital Rings, the integers are the initial algebra.
In the category of semirings, the natural numbers are the initial algebra.

So what is a small presentation of a category (in the sense of giving signatures and axioms) for which the polynomials are initial? Naturally, for $R[x]$, one expects that this presentation will either include the presentation of the ring $R$, or be parametric in that presentation. But what else is needed to characterize univariate polynomial rings from general rings?

The motivation is that I am looking for a semantic type for univariate polynomials. In most cases, the type for polynomials one encounters in the litterate is the type of its representations. This is like saying that a matrix has semantic type 'square array', rather than to say that a matrix (in linear algebra) is a representation of a linear operator (with linear operator being the correct semantic type).

EDIT: one note of clarification. After I figure out the 'theory of polynomials', I then wish to be able to write it down as well, so I want a 'presentation', universal-algebra-style, of the 'theory of polynomials' (whether that is plethories or free V-algebras on one generator or ...). With the integers, it is easy to write down a set of axioms that define unital rings.

Answer by Todd Trimble for What is the theory of polynomials?

2011-08-25T15:08:38Z

My first reaction to this is that you might be interested in the general theory of Tall-Wraith monoids. The special case which might be of more immediate interest to you is the notion of plethory. A good reference is this paper by Borger and Wieland (you will see your polynomial algebra on page 2).

It works like this: suppose you have a (commutative and cocommutative) biring $H$ over a commutative ring $R$. Just having a commutative algebra $A$ over $R$ gives you a representable functor

$$\hom(A, -): CAlg_R \to Set$$

but having a biring $H$ over $R$ means you have enough structure to lift the representable to a functor

$$\hom(H, -): CAlg_R \to CAlg_R$$

Such endofunctors on $CAlg_R$ can be composed, and it turns out that there is a monoidal product $\odot$ on birings which represents this composition, in the sense of there being a canonical isomorphism

$$\hom(H \odot H', -) = \hom(H, -) \circ \hom(H', -)$$

A plethory is by definition a monoid object in this monoidal category of birings.

Getting to your question, the biring which represents the identity functor on $CAlg_R$ is the polynomial algebra $R[x]$. This is therefore the monoidal unit in the monoidal category of birings, or the initial object in the category of plethories over $R$.

Therefore it seems you want to study the universal algebra of plethories. This is probably best carried out in context of props whose semantics is valued in a symmetric monoidal category, particularly the symmetric monoidal category $Mod_R$.

A local MO expert in these matters is Andrew Stacey.

Answer by Emil Jeřábek for What is the theory of polynomials?

2011-08-26T15:18:59Z

Following suggestion of Jacques, I’m reposting my comments above as an answer.

The ring $R[x]$ is formed by adding to $R$ a generic element $x$ commuting with $R$. If $R$ itself is commutative, this essentially amounts to taking the free algebra over one generator in the variety of commutative rings, except that we also have to ensure that the ring contains $R$, and this can be achieved by including in the axiomatization of the variety the positive (aka atomic) diagram of $R$ (as model theorists call it).

That is, we consider the signature $\sigma_0=\{+,\cdot\}\cup R$ , where elements of $R$ serve as constants (nullary functions), and we take the variety $V_0$ axiomatized by the axioms of commutative rings (with $(-1)\cdot u$ playing the rôle of $-u$) and all axioms of the form $a+b=c$ or $a\cdot b=c$ that hold in $R$, where $a,b,c$ are constants from $R$. Then $R[x]$ is the free $V_0$-algebra over one generator.

Alternatively, $V_0$ is term-equivalent to the variety of unital associative commutative $R$-algebras: here we have unary functions $a(u)$ for $a\in R$, denoting scalar multiplication. The constant $a$ of $V_0$ is then definable as $a(1)$, and conversely, in $V_0$ we can define scalar multiplication by $a$ using the binary ring multiplication and the constant for $a$. As noted by Andrew Stacey above, commutativity of the algebras is not needed here: $R[x]$ is also the free unital associative $R$-algebra over one generator.

If we want $R[x]$ to be an initial algebra (= free algebra over the empty set of generators), and/or if $R$ is not commutative, we can include $x$ in the signature as a new constant: we take $\sigma_1=\sigma_0\cup\{x\}$ , and $V_1$ is the variety axiomatized by the axioms of rings, the positive diagram of $R$ as in $V_0$ (i.e., the axioms of the form $a+b=c$ and $a\cdot b=c$), and the axiom $x\cdot u=u\cdot x$ (where $x$ is the nullary function from $\sigma_1$, whereas $u$ is a universally quantified variable). Then $R[x]$ is the initial algebra in $V_1$. (This is still true if we replace the last axiom with its instances $a\cdot x=x\cdot a$ for $a\in R$; this makes a larger but messier variety.)

If we want to endow $R[x]$ with composition, we can take the signature $\sigma_1\cup\{\circ\}$ , and the variety axiomatized by the axioms of $V_1$ together with $(u\circ v)\circ w=u\circ(v\circ w)$, $(u+v)\circ w=(u\circ w)+(v\circ w)$, $(u\cdot v)\circ w=(u\circ w)\cdot(v\circ w)$, $a\circ u=a$ for $a\in R$, $x\circ u=u\circ x=u$. Then $R[x]$ is the initial algebra in this variety (and again, not all of these axioms are needed to obtain this property).

EDIT: Even if we fix the signature, there are may be many varieties whose initial algebra is $R[x]$. However, a canonical choice among them is the smallest such variety, i.e., the variety generated by $R[x]$, which is axiomatized by the set of all equations valid in $R[x]$. Now, I claim that if $R$ is commutative, then this minimal variety in signature $\sigma_1$ is axiomatized by the axioms of commutative rings and the positive diagram of $R$ as above. In other words, in the language using unary functions instead of constants, $R[x]$ generates the variety of commutative associative unital $R$-algebras.

This can be seen as follows. Using the axioms of commutative rings and the positive diagram of $R$, any equation $t=s$ in signature $\sigma_1$ in variables $u_1,\dots,u_n$ is equivalent to an equation of the form $f(u_1,\dots,u_n)=0$, where $f\in(R[x])[u_1,\dots,u_n]=R[x,u_1,\dots,u_n]$. It suffices to prove that if $f$ is not the zero polynomial, then this equation is not valid in $R[x]$, i.e., there exist $a_1,\dots,a_n\in R[x]$ such that $f(a_1,\dots,a_n)\ne0$. This can be shown by straightforward induction on $n$. The only interesting case is $n=1$, where we can take $a_1=x^d$ for any $d>\deg_x(f)$.

Answer by beroal for What is the theory of polynomials?

2011-08-27T16:14:51Z

IMHO the answer to “where polynomials are initial” (not to the title question, which is too broad for me) is already given in “Awodey. Category theory. 9. Adjoints. 9.3. Examples of adjoints. Example 9.10.”

In that example, the adjunction of functors is constructed, where its free (left adjoint) functor $F$ goes from the category of rings (=RingCat) to the category of rings with distinguished element (= pointed rings). If we define this adjunction via unit ($\eta$), then the definition says that

for every object $R$ in RingCat (= for every ring $R$) there is an initial object in the category $select(R)\downarrow U$ (comma category),

where $U$ is the forgetful functor.

Furthermore, a chosen initial object for $R$ consists of $F(R)$ (= $R[x]$) and $\eta(R):R\to U(F(R))$ (= a ring homomorphism constructing constant polynomials). The distinguished element in $F(R)$ is “$x$” (the projection polynomial).