## What is the theory of polynomials?

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.

-
Assuming $R$ is commutative: let $V$ be the variety in the signature $\{+,-,0,\cdot,1\}\cup R$ whose axioms consist of the axioms of commutative rings plus the atomic diagram of $R$. Then $R[x]$ is the free $V$-algebra over one generator. This is a universal algebra characterization. However, you apparently mean category theory rather than universal algebra; I suppose you can characterize free algebras as initial in a suitable category (I’m not sure what to do about the generator). – Emil Jeřábek Aug 25 2011 at 14:29
Actually, you can include $x$ in the signature as yet another constant, with no further axioms. Then $R[x]$ becomes the free $V$-algebra over the empty set of generators, aka the initial algebra in $V$ as a category. – Emil Jeřábek Aug 25 2011 at 14:51
@Gerhard: I am aware that the literature is vast. But the question, I believe, is quite narrow and should be answerable. – Jacques Carette Aug 25 2011 at 16:42
@Jacques: The signature of the free algebra has nothing to do with its set of generators. Having said that, you can formally add the generator to the signature as a new constant, and in the expanded signature, the algebra will be free over an empty set of generators, as I wrote in my second comment. Is it unclear? – Emil Jeřábek Aug 25 2011 at 16:54
Jacques: Emil is suggesting that it be defined by the zeroary operations $\lbrace 0,1,x\rbrace$, unary operations $R$ (acting by scalar multiplication), and binary operations $\lbrace +,\times\rbrace$, together with the obvious identities. In that description, it is the initial algebra in a variety of algebras in the sense of universal algebra. The models of this theory are the unital $R$-algebras with a distinguished element (the image of $x$). So $R[x]$ is the initial "$R$-algebra with distinguished element". To go further, one needs to use co-operations. – Andrew Stacey Aug 25 2011 at 20:44

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.

-
(As a side question, I'm tempted to ask... what's so "plethoric" about plethories? Are they called like that because "there's a plethora of structure around"?) – Qfwfq Aug 25 2011 at 16:35
The word comes from "plethysm", which has been around in representation theory and invariant theory since forever. nLab says, quoting Richard Stanley, that the term was introduced in D. E. Littlewood, Invariant theory, tensors and group characters (1944) and that the term ‘plethysm’ was suggested to Littlewood by M. L. Clark after the Greek word plethysmos, or πληθυσμός, which means ‘multiplication’ in modern Greek (though apparently the meaning goes back to ancient Greek)... – Dan Petersen Aug 25 2011 at 17:00
The related term plethys in Greek means ‘a big number’ or ‘a throng’, and this in turn comes from the Greek verb plethein, which means ‘to be full’, ‘to increase’, ‘to fill’, etc. – Dan Petersen Aug 25 2011 at 17:00
This is definitely an answer to my question. I can't help but think that a plethory requires an awful lot of structure just to get to polynomials! Do I really want the 'algebra of plethories' (i.e. a nice axiomatization of these, preferably in a not-too powerful logic), or the 'algebra of birings' (ditto)? Thanks for the links, I am reading all that now. Definitely relevant. – Jacques Carette Aug 25 2011 at 17:01
Yay for Tall-Wraith monoids! Incidentally, I've seen James Borger around here from time to time as well. – Andrew Stacey Aug 25 2011 at 18:49

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

-
In reply to your "Actually, I suggested ..." comment above; I can't see a difference in putting the $R$ factor in as the constants versus the unary operations. We get a copy of $R$ in the constants simply by applying each unary operation to $1$, don't we? Maybe I'm missing something. Incidentally, I've seen the terms "near ring" and "composition ring" when including the composition rule; but you really need the plethory/Tall-Wraith structure to deal with composition properly. – Andrew Stacey Aug 26 2011 at 18:17
@Andrew: You are not missing anything, the presentations with constants and with unary functions are term-equivalent, as I already mentioned in the answer. It’s just that with constants it’s easier, and, especially in the noncommutative case, more natural. – Emil Jeřábek Aug 29 2011 at 11:25

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

-
This is the same as Emil's answer, in slightly different language. It should be clear by now that there is no single answer to the question; it depends on the needs of the user. – Todd Trimble Aug 27 2011 at 16:28
@Todd Trimble: Not so slightly. Emil does not mention any adjunction, and I do not mention atomic=positive diagrams and associative algebras. I posted my answer because I could not follow Emil's answer because of a couple of unfamiliar terms. (Never heard of atomic=positive diagrams before. Now I see they are probably related to $\eta(R)$, though do not see how until I find the precise definition.) And I gave the reference. It is always good to know your predecessors and not to reinvent the wheel. :) – beroal Aug 28 2011 at 10:31
@Todd Trimble: BTW, Emil's answer would be great if I could understand it. :) – beroal Aug 28 2011 at 10:36