Optimality of the León Sánchez bounds for coefficients of the Kolchin differential dimension polynomial

For a finite system of polynomial differential equations in $n$ unknowns over a differential field of characteristic zero with $m$ commuting derivations, with every equation of order at most $r$, León Sánchez (Mathematics of Computation, 2019) positively resolved a long-standing question of Kolchin: there is a computable bound, depending only on $r$, $m$, $n$ and the differential type $\tau$, for the typical differential dimension $a_\tau$ (the leading coefficient of the Kolchin polynomial) of any prime component of the system of type $\tau$. For $m=2$ and $\tau=0$ the bound is $a_0\le(4^n-1)r^2/3$, and for $m\ge3$ it is given by explicit Ackermann-type recursions. The paper leaves the sharpness of these bounds open: Remark 6.2 asks whether the $m=2$ bound is attained when $n\ge2$ (it is attained for $n=1$ by the system $\delta_1^r x=\delta_2^r x=0$), and Question 6.5 asks whether the $m\ge3$ bounds are optimal, the case $n=1$ being singled out as already difficult. The task is to decide, in each parameter regime, whether the constructed bounds equal the supremum of $a_\tau$ over all systems of order at most $r$.

Background

Let $(K,\Delta=\{\delta_1,\dots,\delta_m\})$ be a differential field of characteristic zero with $m$ commuting derivations (for example $K=\mathbb{Q}(t_1,\dots,t_m)$ with $\delta_i=\partial/\partial t_i$). The ring of differential polynomials $K\{x_1,\dots,x_n\}$ is the commutative polynomial ring in all derivatives $\delta_1^{u_1}\cdots\delta_m^{u_m}x_i$ of the unknowns; the order of such a monomial is $u_1+\cdots+u_m$, and a finite system $\Sigma\subset K\{x_1,\dots,x_n\}$ has order at most $r$ if every derivative appearing in it has total order at most $r$ — crucially, no bound is imposed on the degrees of the equations. A prime differential ideal containing $\Sigma$ that occurs as a component of its radical differential ideal (an irreducible component of the differential variety of $\Sigma$) is called a prime component of $\Sigma$.

Kolchin proved that for such a prime component $P$ there is a numerical polynomial $\omega_P(t)$ — a polynomial with rational coefficients taking integer values at all integers, canonically written $\omega_P(t)=\sum_{i=0}^{m}a_i\binom{t+i}{i}$ — such that, for all sufficiently large $s$, $\omega_P(s)$ equals the transcendence degree over $K$ of the field generated by all derivatives of order at most $s$ of a generic solution. This Kolchin polynomial (or differential dimension polynomial) is an algebraic form of Einstein's notion of the strength of a system of PDEs: for large $s$, $\omega_P(s)$ counts the free Taylor coefficients of order at most $s$ of a generic solution. Its degree $\tau\le m$ is the differential type of $P$ and its leading coefficient $a_\tau$ is the typical differential dimension of $P$; both are differential-birational invariants of the component.

In Chapter IV, §17 of his 1973 book, Kolchin asked: given nonnegative integers $r,m,n,\tau$, is there a computable function $B(r,m,n,\tau)$ such that $a_\tau\le B(r,m,n,\tau)$ for every prime component of differential type $\tau$ of every system of order at most $r$ in $n$ unknowns and $m$ derivations, over every differential field of characteristic zero? He proved the optimal bounds $a_m\le n$ and $a_{m-1}\le nr$, and conjectured $a_\tau\le n\binom{r-1+m-\tau}{m-\tau}$ in general; the conjecture fails already for $m=2$, $n=1$: the system $\delta_1^r x=\delta_2^r x=0$ generates a prime differential ideal of type $0$ with constant Kolchin polynomial $\omega_P\equiv r^2$, which exceeds $r(r+1)/2$ for $r>1$. Before 2017 the available bounds were far from sharp and either depended on the degrees of the equations (Kondratieva, via an Ackermann-type function) or were restricted to linear systems (Grigoriev).

León Sánchez (2019) answered Kolchin's question positively in a strong form. First, he produced a computable bound depending only on $(r,m,n)$ for the sum of the absolute values of the standard coefficients $a_m,\dots,a_{m-j}$ of $\omega_P$. Second, refining by differential type, he constructed — via a new combinatorial-structural result on characteristic sets of prime differential ideals (a characteristic set is the Ritt–Kolchin analogue, for differential ideals, of a Gröbner basis) combined with the classical theorems of Macaulay and Gotzmann on the possible growth of Hilbert–Samuel functions of graded modules — an explicit antichain $\bar\mu\subset\mathbb{N}^m\times\{1,\dots,n\}$, depending only on $(r,m,n,\tau)$, whose Hilbert–Samuel function dominates that of any prime component of type $\tau$ of a system of order at most $r$; the resulting bound for $a_\tau$ is the corresponding Hilbert–Samuel coefficient (for $\tau\ge1$) or the volume of $\bar\mu$ (for $\tau=0$).

The paper computes these bounds explicitly. For $m=2$ and type $\tau=0$ (Corollary 6.1):

$$a_0\le\frac{4^n-1}{3}\,r^2,$$

which for $n=1$ reduces to $a_0\le r^2$, attained exactly by the system above (so optimal in that case). For $m\ge3$ (Corollary 6.3) the bounds are given by Ackermann-type recursions. Here $A$ denotes the two-variable Ackermann function, defined by $A(0,y)=y+1$ for all $y\ge0$, $A(x,0)=A(x-1,1)$ for $x>0$, and $A(x,y)=A(x-1,A(x,y-1))$ for $x,y>0$; following the source, its domain is extended to the points $(x,-1)$ with $x>0$ by setting $A(x,-1):=1$ (only these extended values are used by the recursion for $F$ below). Define $C^0_{r,m}:=r$, $C^1_{0,m}:=0$, $C^1_{r,m}:=A(m-1,C^1_{r-1,m})$, and $C^n_{r,m}:=C^{n-1}_{C^1_{r,m},m}$ (so $C^n_{r,1}=r$, $C^n_{r,2}=2^n r$, and $C^1_{r,3}=3(2^r-1)$); then for a prime component of type $\tau$,

$$a_\tau\le B^{m-\tau}_{r,m,n}\quad(1\le\tau\le m-2),$$

where $B^1_{r,m,n}:=C^{n-1}_{r,m}$, $B^2_{r,m,n}:=C^1_{B^1_{r,m,n}-1,m}+1$, and $B^i_{r,m,n}:=A(m-i+2,\,B^{i-1}_{r,m,n}-1)+1$ for $3\le i\le m$; and for type $0$,

$$a_0\le\sum_{i=1}^{n}\nu\bigl(m,\,C^{i-1}_{r,m}\bigr),$$

where $F(0,y):=1$, $F(x,y):=\sum_{i=-1}^{y-1}F(x-1,A(x,i))$, $\nu(x,0):=0$, and $\nu(x,y):=F(x-1,\,C^1_{y-1,x})+\nu(x,y-1)$. For instance, for $m=3$ and $n=1$ the bounds read $a_1\le C^1_{r-1,3}+1=3\cdot 2^{r-1}-2$ and $a_0\le\sum_{i=0}^{r-1}(C^1_{i,3}+1)(C^1_{i,3}+2)$ with $C^1_{i,3}=3(2^i-1)$ — astronomically smaller than the earlier estimates, but of unknown sharpness. Optimality is known only in Kolchin's regimes $\tau=m$ and $\tau=m-1$ and in the case $m=2$, $n=1$; whether the bounds above are attained for $n\ge2$ (for $m=2$) or at all (for $m\ge3$) is open.

Problem Statement

Decide whether the upper bounds for the typical differential dimension constructed by León Sánchez (2019) are optimal, in the following precise sense: a bound $B(r,m,n,\tau)$ is optimal if it equals the supremum of $a_\tau(P)$ over all prime components $P$ of differential type $\tau$ of systems $\Sigma\subset K\{x_1,\dots,x_n\}$ of order at most $r$, over all differential fields $(K,\Delta)$ of characteristic zero with $m$ commuting derivations — equivalently, if systems attaining the bound exist and no strictly smaller uniform bound is possible.

(a) (Remark 6.2) For $m=2$ derivations and differential type $\tau=0$: for each $n\ge2$ and each $r$, is

$$\sup a_0=\frac{4^n-1}{3}\,r^2\,?$$

(b) (Question 6.5) For $m\ge3$ derivations: are the bounds of Corollary 6.3 — $a_\tau\le B^{m-\tau}_{r,m,n}$ for $1\le\tau\le m-2$ and $a_0\le\sum_{i=1}^{n}\nu(m,C^{i-1}_{r,m})$ for $\tau=0$, with $A$ the Ackermann function and $B$, $C$, $\nu$ defined by the recursions stated in the Background — optimal for arbitrary $m,n,r,\tau$? The author singles out the special case $n=1$ as already difficult: for instance, is $a_1\le3\cdot2^{r-1}-2$ the sharp bound for $m=3$, $n=1$, $\tau=1$, and is $a_0\le\sum_{i=0}^{r-1}(3(2^i-1)+1)(3(2^i-1)+2)$ sharp for $m=3$, $n=1$, $\tau=0$?

The question is the general one over all $(m,n,r,\tau)$ in the stated ranges. The regimes already settled — Kolchin's optimal bounds $a_m\le n$ and $a_{m-1}\le nr$ for $\tau=m$ and $\tau=m-1$, and $m=2$, $\tau=0$, $n=1$ — are not part of what is asked.

References

1. Omar León Sánchez, 'Estimates for the coefficients of differential dimension polynomials', Mathematics of Computation 88 (2019), 2959–2985. DOI: 10.1090/mcom/3429, https://doi.org/10.1090/mcom/3429 (author's final version: arXiv:1703.00509, https://arxiv.org/abs/1703.00509)
2. E. R. Kolchin, 'Differential Algebra and Algebraic Groups', Pure and Applied Mathematics 54, Academic Press, New York, 1973. Zbl 0264.12102, https://zbmath.org/?q=an%3A0264.12102
3. M. V. Kondratieva, 'An upper bound for minimizing coefficients of dimension Kolchin polynomial', Programming and Computer Software 36 (2010), 83–86. DOI: 10.1134/S0361768810020052, https://doi.org/10.1134/S0361768810020052
4. D. Grigoriev, 'Weak Bézout inequality for D-modules', Journal of Complexity 21 (2005), 532–542. DOI: 10.1016/j.jco.2004.09.006, https://doi.org/10.1016/j.jco.2004.09.006
5. James Freitag, Omar León Sánchez, Wei Li, 'Effective definability of Kolchin polynomials', Proceedings of the American Mathematical Society 148 (2020), 1455–1466. DOI: 10.1090/proc/14869, https://doi.org/10.1090/proc/14869
6. Wei Li, Alexey Ovchinnikov, Gleb Pogudin, Thomas Scanlon, 'Algorithms yield upper bounds in differential algebra', Canadian Journal of Mathematics 75 (2023), 29–51. DOI: 10.4153/S0008414X21000560, https://doi.org/10.4153/S0008414X21000560
7. M. V. Kondratieva, 'A bound for a typical differential dimension of systems of linear differential equations', Journal of Mathematical Sciences 259 (2021), 563–569; translation from Fundam. Prikl. Mat. 22, No. 5 (2019), 259–269. DOI: 10.1007/s10958-021-05647-1, https://doi.org/10.1007/s10958-021-05647-1 (preprint arXiv:1802.06163, posted under the title 'A bound for a typical differential dimension of system of linear differential equations', https://arxiv.org/abs/1802.06163)
8. M. V. Kondratieva, 'Generalized typical dimension of a graded module', Journal of Mathematical Sciences 262 (2022), 691–701; translation from Fundam. Prikl. Mat. 23, No. 2 (2020), 147–161. DOI: 10.1007/s10958-022-05847-3, https://doi.org/10.1007/s10958-022-05847-3
9. M. V. Kondratieva, 'Some Properties of Coefficients of the Kolchin Dimension Polynomial', Journal of Mathematical Sciences 269 (2023), 725–733. DOI: 10.1007/s10958-023-06309-0, https://doi.org/10.1007/s10958-023-06309-0 (preprint arXiv:2202.02542, https://arxiv.org/abs/2202.02542)
10. M. V. Kondratieva, 'The Typical Dimension of a System of First-Order Differential Equations', Journal of Mathematical Sciences 283 (2024), 912–918; translation from Fundam. Prikl. Mat. 24, No. 3 (2023), 129–138. DOI: 10.1007/s10958-024-07319-2, https://doi.org/10.1007/s10958-024-07319-2
11. Alexander Levin, 'Some properties of multivariate differential dimension polynomials and their invariants', in Proceedings of ISSAC 2020 (International Symposium on Symbolic and Algebraic Computation), ACM, 2020. DOI: 10.1145/3373207.3404013, https://doi.org/10.1145/3373207.3404013
12. Alexander Levin, 'Bivariate Differential Dimension Polynomials via Bigraded Rees Construction', in Proceedings of ISSAC 2026 (International Symposium on Symbolic and Algebraic Computation), ACM, 2026, 264–271. DOI: 10.1145/3815436.3815456, https://doi.org/10.1145/3815436.3815456