\documentclass[12pt]{article} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage[margin=1in]{geometry} \usepackage{enumitem} \usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{remark}[theorem]{Remark} \newcommand{\ZZ}{\mathbb Z} \newcommand{\NN}{\mathbb N} \newcommand{\LT}{\operatorname{LT}} \newcommand{\Des}{\operatorname{Des}} \newcommand{\des}{\operatorname{des}} \newcommand{\Hilb}{\operatorname{Hilb}} \newcommand{\spr}{\operatorname{spr}} \title{Splitting a Polynomial into Linear Factors after an Injective Ring Extension} \author{GPT-5.5, with prompting by Darij Grinberg} \date{\today} \begin{document} \maketitle \begin{quote} \textbf{Manifest.} {This is an answer to \url{https://mathoverflow.net/questions/429134}, generated by GPT-5.5 with significant shepherding and editing. I still intend to write up this argument in my own words and possibly extend it to an expository paper due to its many connections to algebraic combinatorics.}\footnote{This work is in the public domain. \\ I thank Victor Reiner and Brendon Rhoades for help with finding precedents in the literature. --Darij} \end{quote} All rings in this note are commutative and unital, and all ring homomorphisms preserve the unity. A small notational warning: if $x_1,\ldots,x_N$ are indeterminates, then $\ZZ[x_1,\ldots,x_N]$ denotes a polynomial ring. If $u_1,\ldots,u_N$ are elements of some ring $B$, then $\ZZ[u_1,\ldots,u_N]\subseteq B$ denotes the subalgebra generated by these elements. Such a subalgebra need not be a polynomial ring unless this is proved. \section{\label{sec:ABC}The universal splitting map is split} Fix a positive integer $m$. Set \[ B_m=\ZZ[a_1,b_1,a_2,b_2,\ldots,a_m,b_m], \] the polynomial ring in the $2m$ indeterminates $a_1,b_1,\ldots,a_m,b_m$ over $\ZZ$. For each subset $I\subseteq [m]:=\{1,2,\ldots,m\}$, define the monomial \[ z_I=\prod_{i\in I}a_i\prod_{i\notin I}b_i\in B_m . \] For $0\leq r\leq m$, define \[ E_r=\sum_{\substack{I\subseteq [m];\\ |I|=r}} z_I . \] For example, \begin{align*} E_0 &= z_\varnothing = b_1 b_2 \cdots b_m; \\ E_1 &= \sum_{i=1}^m z_{\left\{i\right\}} = a_1 b_2 b_3 \cdots b_m + b_1 a_2 b_3 \cdots b_m + b_1 b_2 a_3 \cdots b_m + \cdots + b_1 b_2 \cdots b_{m-1} a_m; \\ E_2 &= \sum_{1\leq iz_{I_r'}$ and $z_{I_{r+1}}>z_{I_{r+1}'}$ by the definition of leading term. Multiplicativity of the monomial order gives \[ z_{I_r}z_{I_{r+1}}>z_{I_r'}z_{I_{r+1}'}, \] a contradiction to the previous equality. This proves the claim. A chain with one $r$-element set for each $r$ is obtained by adding the elements of $[m]$ in some order. Relabeling the indices $1,2,\ldots,m$, we may therefore assume \[ I_r=\{1,2,\ldots,r\} \qquad \text{for all } 0 \leq r \leq m. \] Hence \[ \LT(E_r)=M_r:=a_1a_2\cdots a_r b_{r+1}b_{r+2}\cdots b_m . \] For $\mathbf k=(k_0,k_1,\ldots,k_m)\in\NN^{m+1}$, the leading monomial of \[ E^{\mathbf k}:=E_0^{k_0}E_1^{k_1}\cdots E_m^{k_m} \] is therefore \[ M^{\mathbf k}:=M_0^{k_0}M_1^{k_1}\cdots M_m^{k_m}. \] The exponents of the variables in $M^{\mathbf k}$ determine $\mathbf k$: namely, \[ k_0=\nu_{b_1}(M^{\mathbf k}), \] \[ k_i=\nu_{a_i}(M^{\mathbf k})-\nu_{a_{i+1}}(M^{\mathbf k}) \qquad(1\leq ia_2>\cdots>a_m>b_1>b_2>\cdots>b_m. \] Then \[ \LT(E_r)=a_1a_2\cdots a_r b_{r+1}b_{r+2}\cdots b_m \] immediately, and the distinct-leading-monomial argument for the products $E_0^{k_0}\cdots E_m^{k_m}$ goes through without the preliminary chain argument. \end{remark} \subsection{The diagonal subring and chain monomials} Give $B_m$ the $\ZZ^m$-grading determined by \[ \deg a_i=\deg b_i=\varepsilon_i, \] where $\varepsilon_1,\ldots,\varepsilon_m$ is the standard basis of $\ZZ^m$. Let \[ \delta=(1,1,\ldots,1)\in\ZZ^m. \] Each $z_I$ and each $E_r$ has multidegree $\delta$. Define the diagonal subring \[ A_m=\bigoplus_{n\geq0}(B_m)_{n\delta}, \] where $(B_m)_\gamma$ denotes the $\gamma$-th degree component of $B_m$. This is a subring of $B_m$, because the product of two homogeneous elements of multidegrees $n\delta$ and $n'\delta$ is homogeneous of multidegree $(n+n')\delta$. A monomial of $B_m$ is called \emph{diagonal of diagonal degree $n$} if it has multidegree $n\delta$. Equivalently, it has the form \[ \prod_{i=1}^m a_i^{h_i}b_i^{n-h_i} \] for a uniquely determined vector \[ h=(h_1,\ldots,h_m)\in\{0,1,\ldots,n\}^m . \] This vector $h$ is called the \emph{height vector} of the diagonal monomial, and its entries $h_i$ are called the \emph{heights} of the respective labels $i$. Thus \[ h_i=\nu_{a_i}(M) \] for a diagonal monomial $M$ of diagonal degree $n$ (where $\nu_x(M)$ denotes the exponent of a variable $x$ in $M$); equivalently, the exponent of $b_i$ in $M$ is $n-h_i$. Clearly, the diagonal monomials (of all diagonal degrees $n$) form a basis of the $\ZZ$-module $A_m$. A \emph{chain monomial} will mean a product \[ z_{I_1}z_{I_2}\cdots z_{I_n} \] where the subsets $I_1,I_2,\ldots,I_n$ form a multichain under inclusion (i.e., any $i$ and $j$ satisfy $I_i \subseteq I_j$ or $I_j \subseteq I_i$). Since the ring is commutative, the order of the factors is immaterial. When convenient, we write such a monomial in the form $z_{I_1}z_{I_2}\cdots z_{I_n}$ with \[ I_n\subseteq I_{n-1}\subseteq\cdots\subseteq I_1. \] Note that $n=0$ is allowed. \begin{lemma}\label{lem:diagonal-chain-span} The subring $A_m$ is generated, as a $\ZZ$-algebra, by the $2^m$ monomials \[ z_I\qquad(I\subseteq [m]). \] Moreover, the chain monomials are precisely the ordinary monomial basis of $A_m$ written in this generating set. In particular, they form a $\ZZ$-basis of $A_m$. \end{lemma} \begin{proof} Each $z_I$ has multidegree $\delta$, so the subring generated by the $z_I$'s is contained in $A_m$. Conversely, consider a monomial of multidegree $n\delta$. Such a monomial has the form \[ \prod_{i=1}^m a_i^{h_i}b_i^{n-h_i} \] for a unique vector \[ h=(h_1,\ldots,h_m)\in\{0,1,\ldots,n\}^m . \] For each $s\in\{1,2,\ldots,n\}$, set \[ I_s(h)=\{i\in[m]\mid h_i\geq s\}. \] Then \[ I_n(h)\subseteq I_{n-1}(h)\subseteq\cdots\subseteq I_1(h) \] and \[ \prod_{s=1}^n z_{I_s(h)} =\prod_{i=1}^m a_i^{h_i}b_i^{n-h_i}. \] Thus every diagonal monomial is a chain monomial in the $z_I$'s. Conversely, every chain monomial is visibly a diagonal monomial.\footnote{And it is easy to see that distinct chains $\left(I_1, I_2, \ldots, I_n\right)$ lead to different chain monomials $z_{I_1} z_{I_2} \cdots z_{I_n}$: indeed, the length $n$ of the chain is the diagonal degree of the chain monomial, and each exponent $h_i = \nu_{a_i}(z_{I_1} z_{I_2} \cdots z_{I_n})$ is the number of subsets $I_1, I_2, \ldots, I_n$ that contain $i$, which (because of the chain condition $I_n \subseteq I_{n-1} \subseteq \cdots \subseteq I_1$) entails that the first $h_i$ sets $I_1, I_2, \ldots, I_{h_i}$ contain $i$ while the remaining $n - h_i$ sets $I_{h_i+1}, I_{h_i+2}, \ldots, I_n$ don't. Thus, from the monomial $z_{I_1} z_{I_2} \cdots z_{I_n}$, we can tell which $i$'s lie in which $I_j$'s.} The ordinary monomials in the $a_i$'s and $b_i$'s form a $\ZZ$-basis of $B_m$, so the diagonal monomials form a $\ZZ$-basis of $A_m$. Hence the chain monomials form a $\ZZ$-basis of $A_m$. \end{proof} We shall also use the elementary straightening identity \begin{equation}\label{eq:straightening-z} z_Iz_J=z_{I\cap J}z_{I\cup J} \qquad(I,J\subseteq[m]), \end{equation} which holds directly in $A_m$, since both sides have the same exponent of each variable $a_i$ and $b_i$. \begin{remark}[Hibi-ring context, not used in the proof]\label{rem:hibi-context} One standard way to package Lemma~\ref{lem:diagonal-chain-span} and \eqref{eq:straightening-z} is by introducing the polynomial ring \[ T_m=\ZZ[y_I\mid I\subseteq[m]] \] and the ideal $J_m$ generated by \[ y_Iy_J-y_{I\cap J}y_{I\cup J} \qquad(I,J\subseteq[m]). \] Then the map \[ T_m/J_m\longrightarrow A_m, \qquad y_I\longmapsto z_I, \] is an isomorphism. This is the Hibi ring of the Boolean lattice $2^{[m]}$; see Hibi \cite{Hibi1987}. We shall not need this presentation below. \end{remark} \subsection{A bijection between monomials and pairs of permutations and tuples} Recall that the symmetric group $S_m$ consists of the permutations of $[m] := \{1,2,\ldots,m\}$. We write permutations in one-line notation; for example, $31524$ or $(3,1,5,2,4)$ is a permutation in $S_5$. (We shall occasionally omit commas and parentheses in this way.) In particular, $12\cdots m$ is the identity permutation in $S_m$. For a permutation $\pi=(\pi_1,\ldots,\pi_m)\in S_m$, set \[ \Des(\pi)=\{s\in\{1,\ldots,m-1\}\mid \pi_s>\pi_{s+1}\}, \qquad \des(\pi)=|\Des(\pi)|. \] For $0\leq j\leq m$, write \[ P_j^\pi=\{\pi_1,\pi_2,\ldots,\pi_j\}, \] so that $P_0^\pi=\varnothing$ and $P_m^\pi=[m]$. Define the Garsia--Stanton descent monomial \[ u_\pi=\prod_{s\in\Des(\pi)} z_{P_s^\pi}\in A_m . \] Thus $u_{12\cdots m}=1$. Given $\pi\in S_m$ and $\mathbf i=(i_0,i_1,\ldots,i_m)\in\NN^{m+1}$, put \begin{equation}\label{eq:M-pi-i} M_{\pi,\mathbf i} =u_\pi\prod_{j=0}^m \left(z_{P_j^\pi}\right)^{i_j}. \end{equation} This is a chain monomial, of diagonal degree \[ \des(\pi)+i_0+i_1+\cdots+i_m . \] If $h=(h_1,\ldots,h_m)\in\ZZ^m$, then the \emph{sorting permutation} of $h$, denoted $\spr(h)$, will mean the permutation in $S_m$ obtained by listing the labels $1,2,\ldots,m$ in decreasing order of their heights $h_i$, breaking ties in increasing order of the labels. That is, $\spr(h)$ is the unique permutation $\pi \in S_m$ satisfying \begin{align} h_{\pi_1}\geq h_{\pi_2}\geq\cdots\geq h_{\pi_m} \label{eq.spr.1} \end{align} and \begin{align} \text{ if $h_{\pi_s}=h_{\pi_{s+1}}$, then } \pi_s<\pi_{s+1}. \label{eq.spr.2} \end{align} (This is related to the notion of standardization in combinatorics, but not literally the same; we use the name ``sorting permutation'' to avoid confusion.) \begin{lemma}[height vector of the distinguished chain monomial]\label{lem:spr-of-M} Let $\pi\in S_m$ and $\mathbf i=(i_0,i_1,\ldots,i_m)\in\NN^{m+1}$. Let $h$ be the height vector of the chain monomial $M_{\pi,\mathbf i}$. Then \[ \spr(h)=\pi . \] \end{lemma} \begin{proof} We analyze the height vector $h = (h_1, h_2, \ldots, h_m)$ of $M_{\pi,\mathbf i}$. For $1\leq s\leq m$, put \[ d_s^\pi=\#\{q\in\Des(\pi)\mid q\geq s\}, \qquad g_s=i_s+i_{s+1}+\cdots+i_m . \] The factor $u_\pi$ contributes $d_s^\pi$ to the height of the label $\pi_s$, while the prefix factors \[ \prod_{j=0}^m \left(z_{P_j^\pi}\right)^{i_j} \] contribute $g_s$ to the height of the same label. Hence \begin{equation}\label{eq:height-of-M-pi-i} h_{\pi_s}=d_s^\pi+g_s \qquad(1\leq s\leq m). \end{equation} The sequence $g_1,g_2,\ldots,g_m$ is weakly decreasing. The sequence $d_1^\pi,d_2^\pi,\ldots,d_m^\pi$ is also weakly decreasing; more precisely, \[ d_s^\pi=d_{s+1}^\pi+1 \quad\text{if } s\in\Des(\pi), \qquad d_s^\pi=d_{s+1}^\pi \quad\text{if } s\notin\Des(\pi). \] Thus \eqref{eq:height-of-M-pi-i} gives \[ h_{\pi_1}\geq h_{\pi_2}\geq\cdots\geq h_{\pi_m}. \] Moreover, if $s\in\Des(\pi)$, then $d_s^\pi=d_{s+1}^\pi+1$, whence \[ h_{\pi_s}>h_{\pi_{s+1}}. \] If equality $h_{\pi_s}=h_{\pi_{s+1}}$ occurs, then therefore $s\notin\Des(\pi)$, so $\pi_s<\pi_{s+1}$. This is exactly the rule defining the sorting permutation: list the labels in decreasing height, and break equal-height ties increasingly. Hence $\spr(h)=\pi$. \end{proof} \begin{lemma}[labelled-antichain bijection]\label{lem:ppartition-bijection} The map \[ (\pi,\mathbf i)\longmapsto M_{\pi,\mathbf i} \] is a bijection from \[ \{(\pi,\mathbf i)\mid \pi\in S_m,\ \mathbf i\in\NN^{m+1}\} \] to the set of all chain monomials in $A_m$. More precisely, for each $n\geq0$, it restricts to a bijection from the pairs satisfying \[ \des(\pi)+i_0+i_1+\cdots+i_m=n \] to the chain monomials of diagonal degree $n$. \end{lemma} \begin{proof} \textit{Well-definedness.} For a fixed pair $(\pi,\mathbf i)$, the sets \[ P_0^\pi\subseteq P_1^\pi\subseteq\cdots\subseteq P_m^\pi \] form a chain. The additional factors appearing in $u_\pi$ are among the same sets $P_s^\pi$. Hence $M_{\pi,\mathbf i}$ is a chain monomial. Its diagonal degree is \[ \des(\pi)+i_0+i_1+\cdots+i_m, \] since each $z_I$ has diagonal degree $1$. \textit{Surjectivity.} Let a chain monomial of diagonal degree $n$ be given. By Lemma~\ref{lem:diagonal-chain-span}, it has a unique height vector \[ h=(h_1,\ldots,h_m)\in\{0,1,\ldots,n\}^m, \] where the monomial is \[ \prod_{i=1}^m a_i^{h_i}b_i^{n-h_i}. \] Let \[ \pi=\spr(h) \] be the sorting permutation of $h$. Thus $\pi$ lists the labels in decreasing order of their heights, breaking ties increasingly: \[ h_{\pi_1}\geq h_{\pi_2}\geq\cdots\geq h_{\pi_m}, \] and if $h_{\pi_s}=h_{\pi_{s+1}}$, then $\pi_s<\pi_{s+1}$. For $1\leq s\leq m$, put \[ d_s^\pi=\#\{q\in\Des(\pi)\mid q\geq s\}. \] This sequence $(d_1^\pi, d_2^\pi, \ldots, d_m^\pi)$ is the ``descent staircase'' of $\pi$: it drops by $1$ exactly at those $s$ that are descents of $\pi$. Now define \[ g_s=h_{\pi_s}-d_s^\pi\qquad(1\leq s\leq m). \] We claim that \begin{equation} g_1\geq g_2\geq\cdots\geq g_m\geq0. \label{pf.lem:ppartition-bijection.g-dec} \end{equation} Indeed, if $s\notin\Des(\pi)$, then $d_s^\pi=d_{s+1}^\pi$, and the inequality $g_s\geq g_{s+1}$ follows from $h_{\pi_s}\geq h_{\pi_{s+1}}$. If $s\in\Des(\pi)$, then $\pi_s>\pi_{s+1}$; by the tie-breaking rule this forces $h_{\pi_s}>h_{\pi_{s+1}}$, whence $h_{\pi_s}\geq h_{\pi_{s+1}}+1$. Since $d_s^\pi=d_{s+1}^\pi+1$ in this case, we again get $g_s\geq g_{s+1}$. Finally, from $d_m^\pi=0$, we obtain $g_m=h_{\pi_m}\geq0$. Thus, \eqref{pf.lem:ppartition-bijection.g-dec} is proved. Set \[ i_s=g_s-g_{s+1}\qquad(1\leq s \mathbf n$ if and only if either \[ h^\downarrow \text{ strictly dominates } k^\downarrow\text{ (i.e., dominates it and is not equal to it)}, \] or else \[ h^\downarrow = k^\downarrow \quad\text{and}\quad \spr(h) < \spr(k) \] (where the $<$ sign refers to lexicographic order of one-line notations). This is a partial order\footnote{It is easily seen to be asymmetric and transitive.}, because dominance is only a partial order. Nevertheless, the leading term statements below make sense: a monomial is a leading monomial of a polynomial if it is the unique maximal monomial among the monomials appearing in that polynomial. Not every polynomial has a leading monomial, but if it does, then this monomial is unique. For $\mathbf i=(i_0,i_1,\ldots,i_m)\in\NN^{m+1}$, put \[ E_{\mathbf i}=E_0^{i_0}E_1^{i_1}\cdots E_m^{i_m}. \] Also put \[ g_s=i_s+i_{s+1}+\cdots+i_m \qquad(1\leq s\leq m). \] Thus \[ g_1\geq g_2\geq\cdots\geq g_m\geq0. \] \begin{lemma}[dominance for terms of $E_{\mathbf i}$]\label{lem:E-i-dominance} Let $w=(w_1,\ldots,w_m)$ be the height vector of a diagonal monomial appearing in $E_{\mathbf i}$. Then \[ w^\downarrow \text{ is dominated by } (g_1,g_2,\ldots,g_m). \] Moreover, for any permutation $\rho\in S_m$, the term \[ \prod_{j=0}^m \left(z_{P_j^\rho}\right)^{i_j} \] of $E_{\mathbf i}$ has height vector $w$ given by \[ w_{\rho_s}=g_s\qquad(1\leq s\leq m). \] \end{lemma} \begin{proof} Recall that $E_{\mathbf i} = E_0^{i_0} E_1^{i_1} \cdots E_m^{i_m}$, where each $E_j$ is the sum of the $z_J$'s over all $j$-element subsets $J \subseteq [m]$. Thus, expanding this product, we obtain a sum of terms, each of which is a product of such $z_J$'s. To be more specific: A term of $E_{\mathbf i}$ is obtained by choosing, for each of the $i_j$ copies of $E_j$, a $j$-element subset $J\subseteq[m]$, and then multiplying the $z_J$'s corresponding to all the chosen $J$'s. In the height vector of this term, the height $w_x$ is then the total number of chosen subsets $J$ that contain $x$. Let $S$ be any $q$-element subset of $[m]$. Each chosen $j$-element subset meets $S$ in at most $\min(q,j)$ elements. Hence \[ \sum_{x\in S}w_x \leq \sum_{j=0}^m i_j\min(q,j) =g_1+g_2+\cdots+g_q . \] Taking the maximum over all $q$-element subsets $S$ gives the desired dominance inequality. The final assertion follows directly from the definition of the prefixes $P_j^\rho=\{\rho_1,\ldots,\rho_j\}$: the label $\rho_s$ lies in $P_j^\rho$ exactly when $j\geq s$, so it is counted $i_s+i_{s+1}+\cdots+i_m=g_s$ times. \end{proof} \begin{remark} Lemma~\ref{lem:E-i-dominance} says, in particular, that the leading term of $E_{\mathbf i}$ itself is \[ \prod_{j=0}^m\left(z_{\{1,2,\ldots,j\}}\right)^{i_j}, \] with respect to the dominance--lex order.\footnote{We have not nailed down the leading coefficient yet. (It is $1$, and this is a particular case of Lemma~\ref{lem:unique-top-contribution} below.)} Indeed, the maximal sorted height vector is $(g_1,\ldots,g_m)$, and among all terms with this sorted height vector the lexicographically smallest sorting permutation is $12\cdots m$. This is the usual triangularity underlying the fundamental theorem on symmetric polynomials (see, e.g., \cite[\S 4.3, Proposition 5]{Bosch2018}), in homogenized form. The point of the next lemmas is that, after multiplying by $u_\pi$, the relevant prefix order becomes $\pi_1,\pi_2,\ldots,\pi_m$ rather than $1,2,\ldots,m$. \end{remark} \begin{lemma}[dominance after multiplying by $u_\pi$]\label{lem:dominance-after-u} Let $\pi\in S_m$ and $\mathbf i=(i_0,\ldots,i_m)\in\NN^{m+1}$. Let $h^*$ be the height vector of \[ M_{\pi,\mathbf i}=u_\pi\prod_{j=0}^m\left(z_{P_j^\pi}\right)^{i_j}. \] Let $h$ be the height vector of any diagonal monomial appearing in \[ u_\pi E_{\mathbf i}. \] Then $h^\downarrow$ is dominated by $(h^*)^\downarrow$. \end{lemma} \begin{proof} Put \[ d_s=d_s^\pi=\#\{q\in\Des(\pi)\mid q\geq s\}, \qquad g_s=i_s+i_{s+1}+\cdots+i_m \qquad(1\leq s\leq m). \] The factor $u_\pi$ contributes height $d_s$ to the label $\pi_s$. Hence, the height vector $h^*$ satisfies \[ h^*_{\pi_s}=d_s+g_s\qquad(1\leq s\leq m), \] and $\spr(h^*)=\pi$ by Lemma~\ref{lem:spr-of-M}. In particular, \[ (h^*)^\downarrow=(d_1+g_1,d_2+g_2,\ldots,d_m+g_m) \] because $d_1 \geq d_2 \geq \cdots \geq d_m$ and $g_1 \geq g_2 \geq \cdots \geq g_m$. Now consider the diagonal monomial in $u_\pi E_{\mathbf i}$ whose height vector is $h$. Let $w = (w_1, w_2, \ldots, w_m)$ be the height vector of the corresponding monomial in $E_{\mathbf i}$. Thus, \[ h_x=d_x^{\pi,\mathrm{lab}}+w_x, \qquad\text{where }d_{\pi_s}^{\pi,\mathrm{lab}}=d_s \] (since $(d_1^{\pi,\mathrm{lab}}, d_2^{\pi,\mathrm{lab}}, \ldots, d_m^{\pi,\mathrm{lab}})$ is the height vector of $u_\pi$). Let $S$ be a $q$-element subset of $[m]$. Since $d_1\geq d_2\geq\cdots\geq d_m$, the largest possible sum of the $d$-contributions over $q$ labels is $d_1+\cdots+d_q$. Hence \begin{align} \sum_{x\in S}d_x^{\pi,\mathrm{lab}} \leq d_1+\cdots+d_q . \label{pf.lem:dominance-after-u.d-ineq} \end{align} By Lemma~\ref{lem:E-i-dominance}, applied in its proof to the same subset $S$, we also have \begin{align} \sum_{x\in S}w_x \leq g_1+\cdots+g_q . \label{pf.lem:dominance-after-u.g-ineq} \end{align} Adding these inequalities gives \begin{align} \sum_{x\in S}h_x \leq \sum_{s=1}^q(d_s+g_s) =\sum_{s=1}^q(h^*)^\downarrow_s . \label{pf.lem:dominance-after-u.d+g-ineq} \end{align} Taking the maximum over all $q$-element subsets $S$ proves the dominance claim. % This is the special rearrangement inequality needed here: sorted % $d$ plus sorted $w$ dominates the sorted sum. \end{proof} \begin{lemma}[the equality case]\label{lem:dominance-equality-case} Keep the notation of Lemma~\ref{lem:dominance-after-u}. Assume that $h^\downarrow=(h^*)^\downarrow$. Then \[ \spr(h)\geq_{\mathrm{lex}}\pi . \] Moreover, if $\spr(h)=\pi$, then $h=h^*$. \end{lemma} \begin{proof} Let \[ \sigma=\spr(h). \] For $q\in\{1,2,\ldots,m\}$, set \[ S_q=\{\sigma_1,\ldots,\sigma_q\}. \] This is a $q$-element subset on which the sum of the entries of $h$ is maximal. Since $h^\downarrow=(h^*)^\downarrow$, the dominance inequality \eqref{pf.lem:dominance-after-u.d+g-ineq} in Lemma~\ref{lem:dominance-after-u} is an equality for $S=S_q$. The two inequalities \eqref{pf.lem:dominance-after-u.d-ineq} and \eqref{pf.lem:dominance-after-u.g-ineq} that were added in the proof of that lemma therefore must both be equalities. In particular, \begin{equation}\label{eq:d-equality-for-Sq} \sum_{x\in S_q}d_x^{\pi,\mathrm{lab}} =d_1+d_2+\cdots+d_q \qquad(1\leq q\leq m). \end{equation} We now interpret this condition. Decompose the word $\pi_1,\ldots,\pi_m$ into its increasing runs\footnote{The \emph{increasing runs} of a word are its inclusion-maximal increasing contiguous subsequences. For instance, the increasing runs of the word $425816397$ are $4$, $258$, $16$, $39$ and $7$.}: \[ R_1\mid R_2\mid\cdots\mid R_t . \] The cuts occur exactly at the descents of $\pi$. The sequence $d_1,d_2,\ldots,d_m$ is constant on each run and strictly decreases when we move from one run to the next. Thus the labels in $R_1$ have the largest $d$-value, the labels in $R_2$ have the next largest $d$-value, and so on. Equation~\eqref{eq:d-equality-for-Sq}, for all $q$, says exactly that the first $q$ entries of $\sigma$ always choose $q$ labels with largest possible $d$-sum. Consequently, $\sigma$ must list all labels of $R_1$ before all labels of $R_2$, all labels of $R_2$ before all labels of $R_3$, and so on. Indeed, if a label from a later run occurred before a label from an earlier run, then for a suitable $q$ the set $S_q$ would contain the former but not the latter; replacing the former by the latter would strictly increase the left hand side of~\eqref{eq:d-equality-for-Sq}, a contradiction. Thus $\sigma$ is obtained from $\pi$ by permuting entries only inside the increasing runs of $\pi$. Each such run is already written in increasing order, and increasing order is lexicographically smallest among all orderings of the same set of labels. Therefore \[ \sigma\geq_{\mathrm{lex}}\pi . \] Finally, if $\spr(h)=\pi$, then $h$ and $h^*$ have the same decreasing rearrangement and the same sorting permutation. Thus, Lemma~\ref{lem:spr-and-rear-inj} yields $h = h^*$. % This determines the height % vector: for every $s$, the entry $h_{\pi_s}$ is the $s$-th entry of % $h^\downarrow$, and the entry $h^*_{\pi_s}$ is the $s$-th entry of % $(h^*)^\downarrow$. Hence $h_{\pi_s}=h^*_{\pi_s}$ for all $s$, so $h=h^*$. \end{proof} \begin{lemma}[coefficient of the top contribution]\label{lem:unique-top-contribution} Let $\pi\in S_m$ and $\mathbf i\in\NN^{m+1}$. In the expansion of $u_\pi E_{\mathbf i}$, the monomial $M_{\pi,\mathbf i}$ appears with coefficient $1$. \end{lemma} \begin{proof} We must show that the coefficient of the monomial \[ M_{\pi,\mathbf i} = u_\pi\prod_{j=0}^m \left(z_{P_j^\pi}\right)^{i_j} \] in \(u_\pi E_{\mathbf i}\) is \(1\). Since multiplication by the monomial \(u_\pi\) sends distinct monomials to distinct monomials, it is enough to show that the coefficient of \[ \prod_{j=0}^m \left(z_{P_j^\pi}\right)^{i_j} \] in \(E_{\mathbf i}\) is \(1\). For this proof only, we equip the polynomial ring $B_m$ with the lexicographic monomial order corresponding to \[ a_{\pi_1}>a_{\pi_2}>\cdots>a_{\pi_m}> b_{\pi_1}>b_{\pi_2}>\cdots>b_{\pi_m}. \] We claim that, for each \(j\), the leading monomial of \(E_j\) is \(z_{P_j^\pi}\), with coefficient \(1\). Indeed, among all \(j\)-element subsets \(J\subseteq [m]\), the subset \(P_j^\pi=\{\pi_1,\ldots,\pi_j\}\) is lexicographically first in the following sense: if \(J\neq P_j^\pi\), and \(t\) is the first index such that \(\pi_t\) belongs to exactly one of \(J\) and \(P_j^\pi\), then \(t\leq j\), and \(\pi_t\in P_j^\pi\setminus J\). Thus \(z_{P_j^\pi}\) has exponent \(1\) on the variable \(a_{\pi_t}\), whereas \(z_J\) has exponent \(0\) on this variable. Hence \[ z_{P_j^\pi}>z_J \] in our lexicographic order. Therefore the polynomial $E_j$ has leading monomial \[ \LT(E_j)=z_{P_j^\pi} \qquad(0\leq j\leq m), \] with leading coefficient \(1\). Since leading monomials and leading coefficients multiply in a monomial order, the product \[ E_{\mathbf i}=E_0^{i_0}E_1^{i_1}\cdots E_m^{i_m} \] has leading monomial \[ \prod_{j=0}^m \left(z_{P_j^\pi}\right)^{i_j} \] with coefficient \(1\). Thus, as we have explained above, the coefficient of \(M_{\pi,\mathbf i}\) in \(u_\pi E_{\mathbf i}\) is also \(1\). \end{proof} % \begin{proof} % We must show that the coefficient of the monomial % $M_{\pi,\mathbf i} = u_\pi\prod_{j=0}^m \left(z_{P_j^\pi}\right)^{i_j}$ % in $u_\pi E_{\mathbf i}$ is $1$ % (since we already know that this monomial appears in $u_\pi E_{\mathbf i}$, % coming from the prefix choice). % Clearly, it suffices to prove that the coefficient of the monomial % $\prod_{j=0}^m \left(z_{P_j^\pi}\right)^{i_j}$ in $E_{\mathbf i}$ is $1$ % (since multiplication by the monomial $u_\pi$ merely shifts the % coefficients). % But this can be done using monomial orders: % Equip (just for this specific proof) % the polynomial ring $B_m$ with the monomial order that is % lexicographic with respect to the following ordering of % variables: % \[ % a_{\pi_1} > a_{\pi_2} > \cdots > a_{\pi_m} % > b_{\pi_1} > b_{\pi_2} > \cdots > b_{\pi_m} . % \] % Then, each $E_j$ has leading term $z_{P_j^\pi}$ with % coefficient $1$. Since leading terms and leading coefficients % multiply, this implies that the product % $E_{\mathbf i} = \prod_{j=0}^m E_j^{i_j}$ has leading term % $\prod_{j=0}^m \left(z_{P_j^\pi}\right)^{i_j}$ with % coefficient $1$. % Thus the lemma follows. % \end{proof} % \begin{proof}[Old proof of Lemma \ref{lem:unique-top-contribution}.] % Let $h^*$ be the height vector of $M_{\pi,\mathbf i}$. Consider an arbitrary % choice of terms from the factors $E_j$ in the product $u_\pi E_{\mathbf i}$, % and assume that this choice produces a term whose height vector is $h^*$. % We shall show that this arbitrary choice must be the prefix choice % (i.e., the choice of $z_{P_j^\pi}$ from each copy of $E_j$). % More explicitly, for each copy of $E_j$, the chosen term has the form $z_J$ % for some $j$-element subset $J$ of $[m]$. Let $\mathcal J$ be the multiset of % all subsets $J$ chosen in this way, over all copies of all the $E_j$'s. Define % a vector $w=(w_1,\ldots,w_m)$ by % \[ % w_x=\#\{J\in\mathcal J\mid x\in J\} % \qquad(x\in[m]) % \] % (counted, of course, with multiplicity). % Thus $w_x$ is the contribution of the chosen $E$-terms to the height at the % label $x$. If $d_x^{\pi,\mathrm{lab}}$ denotes the contribution of $u_\pi$ % to the height at $x$, then our assumption says % \begin{equation}\label{pf.lem:unique-top.hstar-as-d-plus-w} % h_x^*=d_x^{\pi,\mathrm{lab}}+w_x % \qquad(x\in[m]). % \end{equation} % We first determine how much the vector $w$ contributes on each prefix % $P_q^\pi$. By Lemma~\ref{lem:spr-of-M}, we have $\spr(h^*)=\pi$. Hence, if % we sort the labels $1,2,\ldots,m$ by decreasing $h^*$-height, breaking ties % in increasing order of the labels, then the sorted list is % \[ % \pi_1,\pi_2,\ldots,\pi_m . % \] % Consequently, for each $q\in\{0,1,\ldots,m\}$, the $q$ largest entries of % $h^*$ are $h^*_{\pi_1}, h^*_{\pi_2}, \ldots, h^*_{\pi_q}$, % that is, the $h^*_x$ for $x \in P_q^\pi$. Therefore % \begin{align} % \sum_{x\in P_q^\pi} h_x^* % &= \sum_{s=1}^q h^*_{\pi_s} \notag\\ % &= \sum_{s=1}^q \left(d_s+g_s\right), % \label{pf.lem:unique-top.hstar-prefix-sum} % \end{align} % where the last equality is the formula for the height vector of % $M_{\pi,\mathbf i}$. % On the other hand, % \[ % \sum_{x\in P_q^\pi} d_x^{\pi,\mathrm{lab}} % =d_1+d_2+\cdots+d_q . % \] % Subtracting this equality from~\eqref{pf.lem:unique-top.hstar-prefix-sum}, % and using~\eqref{pf.lem:unique-top.hstar-as-d-plus-w}, we obtain % \begin{equation}\label{pf.lem:unique-top.w-prefix-sum} % \sum_{x\in P_q^\pi} w_x % =g_1+g_2+\cdots+g_q % \qquad(0\leq q\leq m). % \end{equation} % Now compare this equality with the elementary upper bound obtained from the % chosen subsets. Fix $q$. For each $J\in\mathcal J$, we have % \[ % |J\cap P_q^\pi|\leq \min(q,|J|). % \] % Adding these inequalities over all $J\in\mathcal J$ gives % \begin{align*} % \sum_{x\in P_q^\pi} w_x % &=\sum_{J\in\mathcal J}|J\cap P_q^\pi| \\ % &\leq \sum_{J\in\mathcal J}\min(q,|J|) % = g_1+g_2+\cdots+g_q . % \end{align*} % The last equality is the definition of the numbers $g_s$: a chosen subset of % size $j$ contributes $1$ to each of $g_1,\ldots,g_j$ and $0$ to the later % $g_s$'s, and there are $i_j$ chosen subsets of size $j$. % But the left hand side is already equal to $g_1+\cdots+g_q$ by % \eqref{pf.lem:unique-top.w-prefix-sum}. Thus equality holds in each of the % individual inequalities % \[ % |J\cap P_q^\pi|\leq \min(q,|J|) % \qquad(J\in\mathcal J) % \] % for this fixed $q$. Since $q$ was arbitrary, equality holds for every % $q\in\{0,1,\ldots,m\}$ and every $J\in\mathcal J$. % Finally, take any chosen subset $J\in\mathcal J$, and let $j=|J|$. Applying % the preceding conclusion with $q=j$, we get % \[ % |J\cap P_j^\pi|=\min(j,j)=j. % \] % Both $J$ and $P_j^\pi$ have cardinality $j$, so this forces % $J=P_j^\pi$. Thus every copy of $E_j$ contributes the prefix term % $z_{P_j^\pi}$, for every $j$. This is precisely the prefix choice producing % $M_{\pi,\mathbf i}$, and it is the only choice that can do so. Hence the % coefficient of $M_{\pi,\mathbf i}$ in $u_\pi E_{\mathbf i}$ is $1$. % \end{proof} % \begin{remark}[alternative proof of the coefficient]\label{rem:unique-top-symmetric-functions} % The coefficient-$1$ part of Lemma~\ref{lem:unique-top-contribution} can also be viewed as a homogenized form of the classical triangularity of elementary symmetric functions. % Let % \[ % \lambda=(m^{i_m},(m-1)^{i_{m-1}},\ldots,1^{i_1}) % \] % be the partition having $i_j$ parts equal to $j$. Then % \[ % \lambda^t=(g_1,g_2,\ldots,g_m), % \qquad % g_s=i_s+i_{s+1}+\cdots+i_m . % \] % In the Laurent polynomial ring obtained by inverting the $b_i$'s, put % \[ % x_i=\frac{a_i}{b_i}\qquad(1\leq i\leq m). % \] % Then % \[ % E_j=(b_1b_2\cdots b_m)e_j(x_1,\ldots,x_m), % \] % and therefore, if $N=i_0+i_1+\cdots+i_m$, then % \[ % E_{\mathbf i}=(b_1b_2\cdots b_m)^N e_\lambda(x_1,\ldots,x_m). % \] % The standard symmetric-functions triangularity says that the coefficient of % $m_{\lambda^t}$ in $e_\lambda$ is $1$. Equivalently, the coefficient of each % monomial with exponent multiset $(g_1,\ldots,g_m)$, in particular % \[ % x_{\pi_1}^{g_1}x_{\pi_2}^{g_2}\cdots x_{\pi_m}^{g_m}, % \] % is $1$ in $e_\lambda$. After homogenizing back, this says that the coefficient of % \[ % \prod_{j=0}^m\left(z_{P_j^\pi}\right)^{i_j} % \] % in $E_{\mathbf i}$ is $1$. Multiplication by the monomial $u_\pi$ is injective on monomials, so the coefficient of % $M_{\pi,\mathbf i}$ in $u_\pi E_{\mathbf i}$ is also $1$. % Since the expansion of $E_{\mathbf i}$ is obtained by choosing one positive-coefficient addend from each factor $E_j$, this coefficient-$1$ statement also implies the uniqueness of the prefix choice asserted in Lemma~\ref{lem:unique-top-contribution}. % \end{remark} \begin{lemma}[antichain triangularity]\label{lem:antichain-triangularity} Let $\pi\in S_m$ and $\mathbf i=(i_0,\ldots,i_m)\in\NN^{m+1}$. Then the polynomial \[ F_{\pi,\mathbf i}:=u_\pi E_{\mathbf i} =u_\pi E_0^{i_0}E_1^{i_1}\cdots E_m^{i_m}\in A_m \] has leading chain monomial, with respect to the dominance--lex order, equal to \[ M_{\pi,\mathbf i} =u_\pi\prod_{j=0}^m\left(z_{P_j^\pi}\right)^{i_j}. \] The coefficient of this leading chain monomial is $1$. \end{lemma} \begin{proof} Let $h^*$ be the height vector of $M_{\pi,\mathbf i}$, and let $h$ be the height vector of any monomial $M'$ appearing in $F_{\pi,\mathbf i}$. Our first goal is to prove that $M_{\pi,\mathbf i} \geq M'$ in the dominance-lex order. By Lemma~\ref{lem:dominance-after-u}, the sorted height vector $h^\downarrow$ is dominated by $(h^*)^\downarrow$. If this dominance is strict, then $M_{\pi,\mathbf i} > M'$ follows immediately. It remains to consider the case $h^\downarrow=(h^*)^\downarrow$. By Lemma~\ref{lem:dominance-equality-case}, we then have $\spr(h)\geq_{\mathrm{lex}}\pi = \spr(h^*)$ (since $\spr(h^*)=\pi$ by Lemma~\ref{lem:spr-of-M}). If this inequality is strict, then the tie-breaker in the dominance--lex order again ensures $M_{\pi,\mathbf i} > M'$. The remaining case is when $h^\downarrow=(h^*)^\downarrow$ and $\spr(h) = \spr(h^*)$. But in this case, Lemma~\ref{lem:dominance-equality-case} gives $h=h^*$, which forces $M_{\pi,\mathbf i} = M'$: the two monomials have the same height vector and the same diagonal degree, and these data determine a diagonal monomial. So we have shown that the monomial $M_{\pi,\mathbf i}$ is the leading chain monomial of $F_{\pi,\mathbf i}$. It remains to show that its coefficient is $1$. But this follows from Lemma~\ref{lem:unique-top-contribution}. \end{proof} \begin{remark} \label{rem:triangularity-not-groebner} Lemma~\ref{lem:antichain-triangularity} is not a Gr\"obner-basis statement about the elements $E_0,E_1,\ldots,E_m$. The dominance--lex order is a partial order on the diagonal monomial basis, not a multiplicative monomial order on $B_m$. % In particular, the leading choice in $E_j$ depends on the descent monomial $u_\pi$ multiplying it: in $u_\pi E_j$, the leading contribution comes from the prefix $P_j^\pi$. This dependence on $\pi$ is exactly the $P$-partition phenomenon. \end{remark} \subsection{\label{subsec:split-pf}Proof of Theorem~\ref{thm:splitting}} We now recall once again the three nested rings we are working with: \begin{align*} & \ C_m = \ZZ[E_0, E_1, \ldots, E_m] \\ \subseteq & \ A_m = \left(\text{diagonal subring of $B_m$}\right) = \bigoplus_{n \geq 0} (B_m)_{n\delta} \\ \subseteq & \ B_m = \ZZ[a_1, b_1, a_2, b_2, \ldots, a_m, b_m]. \end{align*} \begin{proposition}\label{prop:A-free-over-C} The $C_m$-module $A_m$ is free with basis \[ \{u_\pi\mid \pi\in S_m\}. \] In particular, since $u_{12\cdots m}=1$, the inclusion $C_m\hookrightarrow A_m$ has a $C_m$-linear retraction. \end{proposition} \begin{proof} Since $C_m$ is the polynomial ring $\ZZ[E_0,\ldots,E_m]$, it has a basis consisting of all monomials $E_{\mathbf i} = E_0^{i_0}\cdots E_m^{i_m}$ with $\mathbf i = (i_0, i_1, \ldots, i_m) \in \NN^{m+1}$. The products \[ F_{\pi,\mathbf i}=u_\pi E_0^{i_0}\cdots E_m^{i_m} \qquad(\pi\in S_m,\ \mathbf i\in\NN^{m+1}) \] are precisely the elements obtained by multiplying the proposed basis elements $u_\pi$ by this monomial basis of $C_m$. By Lemma~\ref{lem:antichain-triangularity}, each $F_{\pi,\mathbf i}$ has leading chain monomial $M_{\pi,\mathbf i}$ with coefficient $1$. By Lemma~\ref{lem:ppartition-bijection}, the monomials $M_{\pi,\mathbf i}$ are pairwise distinct and, in fact, run over the entire chain-monomial basis of $A_m$. Therefore, in each diagonal degree, the transition matrix from the family \[ \{F_{\pi,\mathbf i}\} \] to the chain-monomial basis of $A_m$ is unitriangular after choosing any linear extension of the partial order used in Lemma~\ref{lem:antichain-triangularity}. Hence the $F_{\pi,\mathbf i}$ form a $\ZZ$-basis of $A_m$. Equivalently, \[ A_m=\bigoplus_{\pi\in S_m} C_m u_\pi \] as a $C_m$-module. Since the identity permutation $12\cdots m$ has no descents, $u_{12\cdots m}=1$, so the summand for the identity permutation is exactly $C_m$. Projection onto this summand is a $C_m$-linear retraction $A_m\to C_m$. \end{proof} \begin{remark}[What is free after base change] \label{rem:what-is-free} The freeness part of Proposition~\ref{prop:A-free-over-C} is stronger than the retraction part: it says that the diagonal subring $A_m$ is a free $C_m$-module of rank $m!$, with a basis containing $1$. Consequently, for every $C_m$-algebra $R$, the base change \[ R\otimes_{C_m}A_m \] is a free $R$-module of rank $m!$, with basis $1\otimes u_\pi$ for $\pi\in S_m$. The analogous freeness statement for the whole ring $B_m$ is false for $m\geq2$, even if one allows an infinite basis. In fact, $B_m$ is not flat over $C_m$ for $m\geq2$. See Corollary~\ref{cor:not-flat} below for a proof of this. Thus the freeness used in this paper is precisely the freeness of the diagonal summand $A_m$, not of all of $B_m$. What we use for $B_m$ is only that $A_m$ is a $C_m$-direct summand of $B_m$ via the multidegree projection. Hence, after any base change $C_m\to R$, the $R$-algebra \[ R\otimes_{C_m}B_m \] contains the finite free $R$-module $R\otimes_{C_m}A_m$ as an $R$-module direct summand, and in particular contains the copy of $R=R\otimes_{C_m}C_m$ as a direct summand. This is what we will apply below. \end{remark} \begin{remark}[Hilbert-series consistency]\label{rem:hilbert-series-consistency} Taking Hilbert series in the free decomposition of Proposition~\ref{prop:A-free-over-C} gives again the generating-function identity of Remark~\ref{rem:eulerian-from-bijection}. Thus the algebraic basis theorem and the labelled-antichain $P$-partition count are two explanations of the same numerical identity for Eulerian numbers. \end{remark} \begin{remark}[Garsia--Stanton context]\label{rem:garsia-stanton-context} The monomials $u_\pi$ are variants of the Garsia--Stanton descent monomials (\cite[(7.21)]{GarsiaStanton1984}, \cite[(6.7)]{Garsia1980}, \cite[(2)]{Allen1994}). The idea goes back to Garsia's and Stanton's work on group actions on Stanley--Reisner rings and invariant rings \cite{Garsia1980}, \cite{GarsiaStanton1984}. In the classical coinvariant algebra of type $A$, the corresponding monomials form what is now usually called the Garsia--Stanton descent basis; see, for example, Adin--Brenti--Roichman \cite{AdinBrentiRoichman2005}. The proof above can be viewed as the labelled-antichain, diagonal-monomial shadow of this construction. A close precursor to our proof, but situated in the ordinary polynomial ring $\ZZ[x_1, x_2, \ldots, x_m]$ instead of $A_m$, appears in Allen's \cite{Allen1994}. \end{remark} \begin{remark}[Cohen--Macaulay and quotient-ring context]\label{rem:cm-context} Another standard route is to identify $A_m$ with the homogeneous coordinate ring of the Segre embedding of $(\mathbb P^1)^m$, or equivalently with the Hibi ring of the Boolean lattice. This ring is Cohen--Macaulay; the elements $E_0,\ldots,E_m$ form a homogeneous system of parameters; hence they form a regular sequence. This gives the Hilbert series of $A_m/(E_0,\ldots,E_m)A_m$, after which one can lift a basis of the quotient. The present proof avoids that quotient and proves the free $C_m$-basis directly by triangularity. For background on Stanley--Reisner rings and the Cohen--Macaulay viewpoint, see \cite{StanleyCCA}. \end{remark} \begin{proof}[Proof of Theorem~\ref{thm:splitting}] By Proposition~\ref{prop:A-free-over-C}, the inclusion $C_m\hookrightarrow A_m$ has a $C_m$-linear retraction $\rho : A_m \to C_m$. The decomposition of $B_m$ into multihomogeneous components gives a direct sum decomposition into $C_m$-submodules according to the cosets of $\ZZ\delta$ in $\ZZ^m$, because multiplication by any $E_r$ shifts multidegree by $\delta$. The summand corresponding to the coset of $0$ is $A_m$. Hence the multihomogeneous projection \[ B_m\to A_m \] is $C_m$-linear (even $A_m$-linear) and restricts to the identity on $A_m$. Composing this projection with the retraction $\rho : A_m\to C_m$ gives a $C_m$-linear retraction \[ B_m\to A_m\to C_m. \] This proves the theorem. \end{proof} \subsection{Non-freeness of the polynomial ring over the diagonal subring} This subsection is meant to establish the non-freeness (and non-flatness) of $B_m$ as a $C_m$-module, which was claimed in Remark~\ref{rem:what-is-free}. Other than this, it is inconsequential. \begin{proposition}[A root syzygy among the coefficients]\label{prop:root-syzygy} For each $i\in[m]$, we have the identity \[ \sum_{j=0}^m (-1)^j a_i^{m-j} b_i^j E_j=0 \qquad \text{in the polynomial ring $B_m$.} \] \end{proposition} \begin{proof} Fix $i\in[m]$. Recall from Proposition \ref{prop:hg-vieta} that \[ \sum_{j=0}^m E_jX^j = \prod_{r=1}^m (a_rX+b_r) \qquad \text{in the univariate polynomial ring $B_m[X]$.} \] Homogenizing this equality (by substituting $X/Y$ for $X$ and multiplying the result by $Y^m$), we obtain \[ \sum_{j=0}^m E_jX^jY^{m-j} = \prod_{r=1}^m (a_rX+b_rY) \qquad \text{in the bivariate polynomial ring $B_m[X,Y]$.} \] Now, substitute $X=-b_i$ and $Y=a_i$ here. The right hand side becomes \[ \prod_{r=1}^m (a_r(-b_i)+b_ra_i), \] which is $0$, since its $i$-th factor is $a_i(-b_i)+b_ia_i=0$. Thus the left hand side is $0$ as well; that is, \[ \sum_{j=0}^m E_j(-b_i)^j a_i^{m-j}=0. \] In other words, \[ \sum_{j=0}^m (-1)^j a_i^{m-j} b_i^j E_j=0. \] This proves the proposition. \end{proof} \begin{corollary} \label{cor:not-flat} Assume that $m \geq 2$. Then, the $C_m$-module $B_m$ is not flat. \end{corollary} \begin{proof} Taking $i=1$ in Proposition~\ref{prop:root-syzygy}, we find \[ a_1^mE_0-a_1^{m-1}b_1E_1+a_1^{m-2}b_1^2E_2- \cdots+(-1)^m b_1^mE_m=0. \] Hence \[ b_1^mE_m\in (E_0,E_1,\ldots,E_{m-1})B_m. \] However, \[ b_1^m\notin (E_0,E_1,\ldots,E_{m-1})B_m. \] Indeed, specialize $b_2=b_3=\cdots=b_m=0$. Then \[ \prod_{r=1}^m(a_rX+b_r) \mapsto (a_1X+b_1)a_2X\cdots a_mX, \] so the ideal $(E_0,E_1,\ldots,E_{m-1})B_m$ maps into the principal ideal \[ (b_1a_2a_3\cdots a_m), \] which does not contain $b_1^m$ when $m\geq2$. Thus $E_m$ is a zero-divisor modulo $(E_0,E_1,\ldots,E_{m-1})B_m$. Hence \[ E_0,E_1,\ldots,E_m \] is not a regular sequence in $B_m$. But $E_0,E_1,\ldots,E_m$ is a regular sequence in the polynomial ring $C_m=\ZZ[E_0,E_1,\ldots,E_m]$. Since flat base change preserves regular sequences, $B_m$ cannot be flat over $C_m$. \end{proof} In particular, $B_m$ is not free over $C_m$ for $m\geq2$. The case $m=1$ is exceptional and trivial: then $C_1=B_1$. \section{\label{sec:split}Application to splitting arbitrary polynomials} We now deduce some consequences for univariate polynomials. \begin{theorem}\label{thm:main} Let $R$ be a commutative ring, and let $m$ be a positive integer. Let $P = p_0 + p_1 X + \cdots + p_m X^m \in R[X]$ (with $p_0, p_1, \ldots, p_m \in R$) be a univariate polynomial of degree $\leq m$. Then there exists a commutative ring $S$ and an injective ring homomorphism $R\hookrightarrow S$ such that $P$ factors in $S[X]$ as a product of $m$ polynomials of degree at most $1$. \end{theorem} \begin{proof} % If $P=0$, choose $m=1$. If $P\neq0$, choose an integer % \[ % m\geq \max\{1,\deg P\}. % \] % Write % \[ % P=p_0+p_1X+\cdots+p_mX^m, % \] % where $p_i=0$ for $i>\deg P$. % Let $A_m$, $B_m$, $C_m$, and $E_0,E_1,\ldots,E_m$ be as in Section~\ref{sec:ABC}. By Lemma~\ref{lem:alg-independent}, $C_m=\ZZ[E_0,E_1,\ldots,E_m]$ is a polynomial ring over $\ZZ$ on the generators $E_0,E_1,\ldots,E_m$. Hence there is a unique ring homomorphism \[ \varphi:C_m\to R, \qquad E_i\longmapsto p_i. \] Define \[ S=R\otimes_{C_m}B_m, \] where $R$ is regarded as a $C_m$-algebra via $\varphi$. The inclusion $C_m\hookrightarrow B_m$ is split as a $C_m$-module map by Theorem~\ref{thm:splitting}. Tensoring this split injection with $R$ over $C_m$ yields a split injection of $R$-modules \begin{align} R=R\otimes_{C_m}C_m \hookrightarrow R\otimes_{C_m}B_m=S \label{pf:thm:main:RtoS} \end{align} (since split injections remain split injections under base change). In particular, the natural ring homomorphism $R\to S$ is injective. We identify $R$ with its image in $S$, equating each $r \in R$ with $r \otimes_{C_m} 1 \in S$. More precisely, Proposition~\ref{prop:A-free-over-C} yields that \[ R\otimes_{C_m}A_m \] is a free $R$-module of rank $m!$, with basis $1\otimes u_\pi$ for $\pi\in S_m$, and the copy of $R$ generated by $1\otimes u_{12\cdots m}=1$ is a direct summand of this free module. The splitting algebra $S=R\otimes_{C_m}B_m$ contains this module as an $R$-module direct summand. Thus the construction gives not merely injectivity of $R\to S$, but a split injection of underlying $R$-modules. The canonical ring morphism $\xi : B_m \to R \otimes_{C_m} B_m = S$ (sending each $u \in B_m$ to $1 \otimes u \in S$) sends each $E_j \in B_m$ to $1 \otimes_{C_m} E_j = \varphi\left(E_j\right) \otimes_{C_m} 1 = p_j \otimes_{C_m} 1 = p_j \in S$. Let $\alpha_i,\beta_i\in S$ be the images of $a_i,b_i\in B_m$, respectively, under this morphism $\xi$. In $B_m[X]$ we have the universal identity \[ \prod_{i=1}^m(a_iX+b_i)=\sum_{j=0}^m E_jX^j \] (a restatement of \eqref{prop:hg-vieta:1}). After tensoring with $R$ (that is, applying $\xi$), this becomes \[ \prod_{i=1}^m(\alpha_iX+\beta_i) = \sum_{j=0}^m p_jX^j =P \] in $S[X]$. Hence $P$ splits in $S[X]$ as a product of $m$ degree-$\leq1$ polynomials. \end{proof} \begin{proposition}\label{prop:explicit-S} The ring $S$ constructed in the above proof of Theorem~\ref{thm:main} can be written explicitly as \[ S\cong R[a_1,b_1,\ldots,a_m,b_m] \Big/ (E_0-p_0,E_1-p_1,\ldots,E_m-p_m), \] where now the same formula for $E_r$ is interpreted inside the polynomial ring $R[a_1,b_1,\ldots,a_m,b_m]$: \[ E_r=\sum_{\substack{I\subseteq[m];\\ |I|=r}} \prod_{i\in I}a_i\prod_{i\notin I}b_i. \] \end{proposition} \begin{proof} Let $a_{1}^{\prime},b_{1}^{\prime},a_{2}^{\prime},b_{2}^{\prime},\ldots ,a_{m}^{\prime},b_{m}^{\prime}$ be $2m$ further indeterminates, and let% \[ E_{r}^{\prime}=\sum_{\substack{I\subseteq [m];\\|I|=r}}\prod_{i\in I}a_{i}^{\prime}\prod_{i\notin I}b_{i}^{\prime}% \] over the ring $\ZZ$. Then, we claim that \begin{equation} B_{m}\cong C_{m}\left[ a_{1}^{\prime},b_{1}^{\prime},\ldots,a_{m}^{\prime },b_{m}^{\prime}\right] \Big/(E_{0}^{\prime}-E_{0},E_{1}^{\prime}% -E_{1},\ldots,E_{m}^{\prime}-E_{m})\label{pf:prop:explicit-S:1}% \end{equation} as $C_m$-algebras. Indeed, Lemma \ref{lem:alg-independent} shows that $C_{m}$ is the polynomial ring $\ZZ[E_{0},E_{1},\ldots,E_{m}]$; thus,% \begin{align*} & C_{m}\left[ a_{1}^{\prime},b_{1}^{\prime},\ldots,a_{m}^{\prime}% ,b_{m}^{\prime}\right] \Big/(E_{0}^{\prime}-E_{0},E_{1}^{\prime}-E_{1}% ,\ldots,E_{m}^{\prime}-E_{m})\\ & \cong\left( \ZZ[E_{0},E_{1},\ldots,E_{m}]\right) \left[ a_{1}^{\prime},b_{1}^{\prime},\ldots,a_{m}^{\prime},b_{m}^{\prime}\right] \Big/(E_{0}^{\prime}-E_{0},E_{1}^{\prime}-E_{1},\ldots,E_{m}^{\prime}% -E_{m})\\ & \cong\left( \ZZ\left[ a_{1}^{\prime},b_{1}^{\prime},\ldots ,a_{m}^{\prime},b_{m}^{\prime}\right] \right) \left[ E_{0},E_{1}% ,\ldots,E_{m}\right] \Big/(E_{0}^{\prime}-E_{0},E_{1}^{\prime}-E_{1}% ,\ldots,E_{m}^{\prime}-E_{m})\\ & \cong\ZZ\left[ a_{1}^{\prime},b_{1}^{\prime},\ldots,a_{m}^{\prime },b_{m}^{\prime}\right] , \end{align*} since any ring $P$ and any elements $u_{0},u_{1},\ldots,u_{m}\in P$ satisfy the $P$-algebra isomorphism \[ P\left[ E_{0},E_{1},\ldots,E_{m}\right] \Big/\left( u_{0}-E_{0}% ,u_{1}-E_{1},\ldots,u_{m}-E_{m}\right) \cong P \] (because adjoining a variable to a ring $P$ and then setting this variable equal to an element of $P$ gives back $P$). Hence,% \begin{align*} & C_{m}\left[ a_{1}^{\prime},b_{1}^{\prime},\ldots,a_{m}^{\prime}% ,b_{m}^{\prime}\right] \Big/(E_{0}^{\prime}-E_{0},E_{1}^{\prime}-E_{1}% ,\ldots,E_{m}^{\prime}-E_{m})\\ & \cong\ZZ\left[ a_{1}^{\prime},b_{1}^{\prime},\ldots,a_{m}^{\prime },b_{m}^{\prime}\right] \cong\ZZ\left[ a_{1}^{\prime},b_{1}^{\prime },\ldots,a_{m}^{\prime},b_{m}^{\prime}\right] =B_{m}, \end{align*} which proves \eqref{pf:prop:explicit-S:1}. Now,% \begin{align*} S & =R\otimes_{C_{m}}B_{m}\\ & \cong R\otimes_{C_{m}}\left( C_{m}\left[ a_{1}^{\prime},b_{1}^{\prime },\ldots,a_{m}^{\prime},b_{m}^{\prime}\right] \Big/(E_{0}^{\prime}% -E_{0},E_{1}^{\prime}-E_{1},\ldots,E_{m}^{\prime}-E_{m})\right) \\ & \qquad\qquad\left( \text{by \eqref{pf:prop:explicit-S:1}}\right) \\ & \cong\left( R\otimes_{C_{m}}C_{m}\left[ a_{1}^{\prime},b_{1}^{\prime },\ldots,a_{m}^{\prime},b_{m}^{\prime}\right] \right) \Big/(E_{0}^{\prime }-E_{0},E_{1}^{\prime}-E_{1},\ldots,E_{m}^{\prime}-E_{m})\\ & \qquad\qquad\left( \text{since quotienting by an ideal commutes with base change}\right) \\ & \cong R\left[ a_{1}^{\prime},b_{1}^{\prime},\ldots,a_{m}^{\prime}% ,b_{m}^{\prime}\right] \Big/(E_{0}^{\prime}-p_{0},E_{1}^{\prime}-p_{1}% ,\ldots,E_{m}^{\prime}-p_{m})\\ & \qquad\qquad\left( \begin{array} [c]{c}% \text{since }R\otimes_{C_{m}}C_{m}\left[ a_{1}^{\prime},b_{1}^{\prime}% ,\ldots,a_{m}^{\prime},b_{m}^{\prime}\right] \cong R\left[ a_{1}^{\prime },b_{1}^{\prime},\ldots,a_{m}^{\prime},b_{m}^{\prime}\right] \text{ as }R\text{-algebras,}\\ \text{and the isomorphism sends each }E_{j}\text{ to }p_{j}% \end{array} \right) \\ & \cong R[a_{1},b_{1},\ldots,a_{m},b_{m}]\Big/(E_{0}-p_{0},E_{1}-p_{1}% ,\ldots,E_{m}-p_{m}). \end{align*} This proves the proposition. % Let % \[ % T=\ZZ[t_0,t_1,\ldots,t_m]. % \] % By Lemma~\ref{lem:alg-independent}, the map % \[ % T\longrightarrow C_m,\qquad t_j\longmapsto E_j % \] % is an isomorphism. We identify $T$ with $C_m$ by this isomorphism. Under this identification, the $C_m$-algebra structure on $R$ used in the proof of Theorem~\ref{thm:main} is the $T$-algebra structure determined by % \[ % t_j\longmapsto p_j \qquad (0\leq j\leq m). % \] % Thus % \[ % S=R\otimes_{C_m}B_m % \cong % R\otimes_T \ZZ[a_1,b_1,\ldots,a_m,b_m], % \] % where $T$ acts on the second factor by $t_j\mapsto E_j$. % % We claim that this tensor product is naturally isomorphic to % \[ % R[a_1,b_1,\ldots,a_m,b_m] % /(E_0-p_0,E_1-p_1,\ldots,E_m-p_m). % \] % Indeed, the canonical $R$-algebra map % \[ % R[a_1,b_1,\ldots,a_m,b_m] % \longrightarrow % R\otimes_T \ZZ[a_1,b_1,\ldots,a_m,b_m] % \] % that sends each $r\in R$ to $r\otimes 1$ and sends the variables $a_i,b_i$ to % $1\otimes a_i,1\otimes b_i$ sends each $E_j-p_j$ to $0$, since % \[ % 1\otimes E_j=t_j\otimes 1=p_j\otimes 1. % \] % Hence it factors through the displayed quotient. % % Conversely, the quotient has the universal property of the tensor product. More explicitly, let $Q$ be an $R$-algebra. To give an $R$-algebra homomorphism % \[ % R[a_1,b_1,\ldots,a_m,b_m] % /(E_0-p_0,E_1-p_1,\ldots,E_m-p_m) % \longrightarrow Q % \] % is the same as to choose elements $x_i,y_i\in Q$ such that % \[ % E_j(x_1,y_1,\ldots,x_m,y_m)=p_j % \qquad(0\leq j\leq m). % \] % This is the same as to give a ring homomorphism % \[ % \psi:\ZZ[a_1,b_1,\ldots,a_m,b_m]\longrightarrow Q, % \qquad a_i\longmapsto x_i, % \quad b_i\longmapsto y_i, % \] % that is compatible with the two induced $T$-algebra structures on $Q$. Let us spell % out what this means. The polynomial $P=\sum_{j=0}^m p_jX^j$ makes $R$ into a % $T$-algebra by % \[ % t_j\longmapsto p_j \qquad(0\leq j\leq m). % \] % Since $Q$ is an $R$-algebra, with structure map say $\alpha:R\to Q$, this also % makes $Q$ into a $T$-algebra via the composite % \[ % T\longrightarrow R\xrightarrow{\alpha} Q, % \qquad % t_j\longmapsto p_j\longmapsto \alpha(p_j). % \] % On the other hand, the map $T\to \ZZ[a_1,b_1,\ldots,a_m,b_m]$ sends % $t_j$ to $E_j$, so the map $\psi$ makes $Q$ into a $T$-algebra with % \[ % t_j\longmapsto \psi(E_j)=E_j(x_1,y_1,\ldots,x_m,y_m). % \] % Thus the compatibility condition is precisely % \[ % E_j(x_1,y_1,\ldots,x_m,y_m)=\alpha(p_j) % \qquad(0\leq j\leq m), % \] % which, as usual, we write simply as $E_j(x_1,y_1,\ldots,x_m,y_m)=p_j$ inside % $Q$. This is precisely the universal property of % \[ % R\otimes_T\ZZ[a_1,b_1,\ldots,a_m,b_m]. % \] % Therefore the two $R$-algebras are naturally isomorphic. This proves the proposition. \end{proof} Note that Proposition~\ref{prop:explicit-S} gives what is probably the simplest construction of $S$. The point of Theorem~\ref{thm:splitting} is that the natural map $R\to S$ is injective for every specialization $E_i\mapsto p_i$. \begin{theorem}[Universal property of the splitting algebra]\label{thm:universal-property} Let $R$, $m$, $P$ and $p_0,\ldots,p_m$ be as in Theorem~\ref{thm:main}. Let \[ S\cong R[a_1,b_1,\ldots,a_m,b_m] \Big/ (E_0-p_0,E_1-p_1,\ldots,E_m-p_m) \] be the $R$-algebra of Proposition~\ref{prop:explicit-S}, and let $\alpha_i,\beta_i\in S$ denote the images of $a_i,b_i$ in this algebra $S$. For every $R$-algebra $T$, the map \[ \operatorname{Hom}_{R\text{-alg}}(S,T) \longrightarrow \left\{(c_1,d_1,\ldots,c_m,d_m)\in T^{2m}\ \middle|\ P=\prod_{i=1}^m(c_iX+d_i)\text{ in }T[X]\right\} \] that sends an $R$-algebra homomorphism $f:S\to T$ to \[ (f(\alpha_1),f(\beta_1),\ldots,f(\alpha_m),f(\beta_m)) \] is a bijection. Equivalently, $S$ is universal for ordered factorizations of $P$ into exactly $m$ linear-or-constant factors. \end{theorem} \begin{proof} Let $T$ be an $R$-algebra. Since $S$ is presented as a quotient of the polynomial $R$-algebra \[ R[a_1,b_1,\ldots,a_m,b_m], \] an $R$-algebra homomorphism $f:S\to T$ is the same as a choice of images \[ c_i=f(\alpha_i),\qquad d_i=f(\beta_i)\qquad(1\leq i\leq m) \] for the variables $a_i,b_i$ satisfying the defining relations of the quotient. These relations are \[ E_j(c_1,d_1,\ldots,c_m,d_m)=p_j \qquad(0\leq j\leq m), \] where \[ E_j(c_1,d_1,\ldots,c_m,d_m) = \sum_{\substack{I\subseteq[m];\\ |I|=j}} \prod_{i\in I}c_i\prod_{i\notin I}d_i . \] But these are exactly the coefficient identities obtained by expanding \[ \prod_{i=1}^m(c_iX+d_i) = \sum_{j=0}^m E_j(c_1,d_1,\ldots,c_m,d_m)X^j . \] Thus the defining relations hold if and only if \[ \prod_{i=1}^m(c_iX+d_i)=\sum_{j=0}^m p_jX^j=P \qquad\text{in }T[X]. \] This proves that the displayed map is well-defined and surjective. It remains only to note uniqueness. Once the tuple $(c_1,d_1,\ldots,c_m,d_m)$ is specified, there is a unique $R$-algebra map \[ R[a_1,b_1,\ldots,a_m,b_m]\to T \] sending $a_i\mapsto c_i$ and $b_i\mapsto d_i$. If the tuple gives a factorization of $P$, then the relations $E_j-p_j$ vanish under this map, so it factors uniquely through $S$. Hence two homomorphisms $S\to T$ with the same tuple are equal. This proves injectivity of the displayed map and completes the proof. \end{proof} A factorization with fewer than $m$ factors can be regarded as one with exactly $m$ factors by adjoining extra factors $0X+1$. \begin{thebibliography}{9} \bibitem{AdinBrentiRoichman2005} \href{https://doi.org/10.1090/S0002-9947-04-03494-4}{R. M. Adin, F. Brenti, and Y. Roichman, \textit{Descent representations and multivariate statistics}, Transactions of the American Mathematical Society \textbf{357} (2005), no.~8, 3051--3082.} \bibitem{Allen1994} \href{https://doi.org/10.1023/A:1022481303750}{E. E. Allen, \textit{The Descent Monomials and a Basis for the Diagonally Symmetric Polynomials}, Journal of Algebraic Combinatorics \textbf{3} (1994), 5--16.} \bibitem{Bosch2018} \href{https://doi.org/10.1007/978-3-319-95177-5}{Siegfried Bosch, \textit{Algebra: From the Viewpoint of Galois Theory}, Springer 2018.} \bibitem{CoxLittleOShea2025} \href{https://doi.org/10.1007/978-3-031-91841-4}{David A. Cox, John Little, Donal O'Shea, \textit{Ideals, Varieties, and Algorithms}, Undergraduate Texts in Mathematics, 5th edition, Springer 2025.} \bibitem{Garsia1980} \href{https://doi.org/10.1016/0001-8708(80)90006-7}{Adriano M. Garsia, \textit{Combinatorial Methods in the Theory of Cohen--Macaulay Rings}, Advances in Mathematics \textbf{38} (1980), 229--266.} \bibitem{GarsiaStanton1984} \href{https://doi.org/10.1016/0001-8708(84)90005-7}{A. M. Garsia and D. Stanton, \textit{Group actions on Stanley--Reisner rings and invariants of permutation groups}, Advances in Mathematics \textbf{51} (1984), no.~2, 107--201.} \bibitem{Hibi1987} \href{https://doi.org/10.2969/aspm/01110093}{T. Hibi, \textit{Distributive lattices, affine semigroup rings and algebras with straightening laws}, in \textit{Commutative Algebra and Combinatorics}, Advanced Studies in Pure Mathematics \textbf{11}, North-Holland, Amsterdam, 1987, pp.~93--109.} \bibitem{StanleyEC1} \href{https://doi.org/10.1017/CBO9781139058520}{R. P. Stanley, \textit{Enumerative Combinatorics, Volume 1}, second edition, Cambridge Studies in Advanced Mathematics \textbf{49}, Cambridge University Press, 2012.} \bibitem{StanleyCCA} \href{https://doi.org/10.1007/b139094}{R. P. Stanley, \textit{Combinatorics and Commutative Algebra}, second edition, Progress in Mathematics \textbf{41}, Birkh\"auser, Boston, 1996.} \end{thebibliography} \end{document}