For a finite system of polynomial partial differential equations, the Kolchin (differential dimension) polynomial of each minimal prime component encodes fundamental birational invariants: the differential type and the typical differential dimension. Kondratieva (2010) obtained explicit upper bounds for the minimizing coefficients of this polynomial in terms of the number of derivations, the number of differential variables, and bounds on the orders and degrees of the equations, but in the general unconstrained case her estimate necessarily embeds an Ackermann-type bound on the orders of the polynomials occurring in characteristic sets of the minimal prime components, and she explicitly leaves open the derivation of substantially sharper order estimates and the corresponding tighter coefficient bounds; the concrete growth targets named in her subsequent papers are exponential or double-exponential bounds for general nonlinear systems. This open problem remains unresolved: after the surrounding and subsequent works (Golubitsky–Kondratieva–Ovchinnikov–Szanto 2009; León Sánchez–Ovchinnikov 2016; Gustavson–Kondratieva–Ovchinnikov 2016; Gustavson–León Sánchez 2018; Gustavson–Ovchinnikov–Pogudin 2018; León Sánchez 2019; Li–Ovchinnikov–Pogudin–Scanlon 2023), all known order bounds for the general case (arbitrary number of derivations, arbitrary coefficients) remain Ackermann-type, elementary bounds are known only for one and two derivations, known lower bounds are merely exponential, and Kondratieva's own 2024 paper states that no exponential bounds are yet available for general nonlinear systems.

Background

A differential field (K,δ1,…,δm)(K,\delta_1,\dots,\delta_m) of characteristic zero carries mm pairwise-commuting derivations (the case m>1m>1 corresponds to partial differential equations, PDEs). The ring of differential polynomials K{x1,…,xn}K\{x_1,\dots,x_n\} is the polynomial ring in all derivatives δ1u1⋯δmumxi\delta_1^{u_1}\cdots\delta_m^{u_m}x_i; a differential ideal is an ideal stable under all derivations, and the radical differential ideal {F}\{F\} generated by a finite system FF is the smallest such radical ideal. For a prime differential ideal PP, Kolchin showed that the transcendence degree over KK of the derivatives of a generic solution up to total order ss is, for large ss, a numerical polynomial ωP(t)\omega_P(t) — the Kolchin polynomial (or differential dimension polynomial), a differential-algebraic analogue of the Hilbert polynomial. Its degree τ≤m\tau\le m is the differential type and its leading coefficient aτa_\tau (in the standard binomial basis) is the typical differential dimension of PP; the minimizing coefficients (bm,…,b0)(b_m,\dots,b_0) are the coefficients obtained by rewriting ωP\omega_P in the shifted binomial basis via the finite-difference recurrence, and the leading nonzero minimizing coefficients control the same invariants. For a finite system FF, the minimal prime components PiP_i of {F}\{F\} are the primes appearing in its irredundant prime decomposition, and each admits a characteristic set — a canonical autoreduced triangular generating set whose elements' orders determine how many differentiations are needed to compute ωPi\omega_{P_i}. The effective differential Nullstellensatz is the related problem of bounding the number of differentiations of a system needed to witness inconsistency or differential-algebraic consequences, which Seidenberg first addressed in 1956 without a complete solution; it is a central problem of the algebraic theory of PDEs and governs the complexity of differential elimination algorithms such as the Rosenfeld–Gröbner algorithm implemented in computer algebra systems. Kolchin's book proved that the typical differential dimension satisfies am≤na_m\le n and am−1≤nra_{m-1}\le nr (both optimal, rr the maximal order) but his conjectured general bound was refuted by examples such as δ1rx=δ2rx=0\delta_1^r x=\delta_2^r x=0, whose prime ideal has ωP≡r2\omega_P\equiv r^2. Grigoriev (2005) gave explicit bounds for linear systems, polynomial in the order for a fixed number of derivations. Golubitsky, Kondratieva, Ovchinnikov, and Szanto (2009) obtained the first explicit bound for orders in the differential Nullstellensatz for both ordinary and partial systems, t(F,f)≤A(m+8,max⁡(n,H,D))t(F,f)\le A(m+8,\max(n,H,D)) with AA the Ackermann function, the standard example of a total computable function that eventually dominates every primitive-recursive function; this bound is primitive recursive in the number of variables, orders, and degrees for fixed mm, but not elementary recursive (that is, not bounded by any fixed tower of exponentials) and not primitive recursive in the number of derivations mm, and their elimination analysis bounds the orders and degrees in characteristic sets of the prime components by A(m+7,Q−1)A(m+7,Q-1). Kondratieva (2010) combined such Ackermann-type order bounds with new combinatorial estimates for the integer multipliers in the inclusion–exclusion representation of the Kolchin polynomial of a finite set E⊂N0mE\subset\mathbb{N}_0^m, proving for a system of type k≤m−2k\le m-2 with orders and degrees bounded by hh a tower-type bound on the typical differential dimension; in the form quoted in León Sánchez (2019), ak≤222m−k−2⋅(2A(m+7,29h))(m+2)2m−k−2a_k\le 2^{2^{2^{m-k-2}}}\cdot(2A(m+7,2^{9h}))^{(m+2)2^{m-k-2}}. She observed that in the general case, without additional constraints on the original system, an estimate on the order of the systems obtained (the characteristic sets of the minimal prime components) had not been derived beyond this extremely large Ackermann-type bound. Later work sharpened the picture: for one derivation a double-exponential bound in nn and hh (polynomial in the degree, no constant coefficients needed) and for two derivations an iterated-exponential bound are known (Gustavson–Kondratieva–Ovchinnikov 2016), León Sánchez (2019) proved that computable bounds for all Kolchin-polynomial coefficients of every prime component exist depending only on the order (answering Kolchin's long-standing question affirmatively), but all known general-case bounds remain of Ackermann type while the best lower bounds are only exponential in mnmn. The known coefficient bounds arise both as corollaries of order bounds for characteristic sets (Kondratieva 2010) and, in the second construction of León Sánchez (2019), from combinatorial arguments that do not pass through such an order bound.

Problem Statement

Let (K,δ1,…,δm)(K,\delta_1,\dots,\delta_m) be a differential field of characteristic zero with mm commuting derivations, and let F⊂K{x1,…,xn}F\subset K\{x_1,\dots,x_n\} be an arbitrary finite system of differential polynomials whose orders are at most hh and whose total degrees are at most dd, with no further constraints (arbitrary coefficients, arbitrary mm and nn, nonlinear equations allowed). Let {F}=P1∩⋯∩Ps\{F\}=P_1\cap\cdots\cap P_s be the decomposition of the radical differential ideal generated by FF into minimal prime components, each given by a characteristic set. The problem, left open by Kondratieva (2010) and restated in her subsequent papers, has one objective — to make the effective estimates for the Kolchin-polynomial invariants of differential systems reasonably sized rather than Ackermann-dominated — in two parts: (1) Order bound: establish an explicit upper bound, valid in this general unconstrained case, for the orders of the differential polynomials occurring in the characteristic sets of the minimal prime components (equivalently, for the number of differentiations required in differential elimination) that is substantially sharper than the known Ackermann-type bounds; the concrete growth targets named by the author are exponential or double-exponential bounds for general nonlinear systems, and any explicit bound breaking the Ackermann barrier addresses the same open core. (2) Coefficient estimates: correspondingly sharper explicit upper bounds for the minimizing coefficients of the Kolchin polynomial ωPi\omega_{P_i} of every minimal prime component, in particular for the typical differential dimension, replacing the tower-plus-Ackermann bounds of Kondratieva (2010) and León Sánchez (2019). For context, the currently known state is: double-exponential upper bounds for one derivation, an iterated-exponential tower for two derivations, Ackermann-type bounds for three or more derivations, and lower bounds only exponential in mnmn.

References

  1. M. V. Kondratieva, An upper bound for minimizing coefficients of dimension Kolchin polynomial, Programming and Computer Software 36(2):83–86, 2010. DOI: 10.1134/S0361768810020052, https://doi.org/10.1134/S0361768810020052 (source paper)
  2. O. Golubitsky, M. Kondratieva, A. Ovchinnikov, A. Szanto, A bound for orders in differential Nullstellensatz, Journal of Algebra 322(11):3852–3877, 2009. DOI: 10.1016/j.jalgebra.2009.05.032, https://doi.org/10.1016/j.jalgebra.2009.05.032 (also arXiv:0803.0160)
  3. O. León Sánchez, Estimates for the coefficients of differential dimension polynomials, Mathematics of Computation 88(320):2959–2985, 2019. DOI: 10.1090/MCOM/3429, https://doi.org/10.1090/MCOM/3429 (also arXiv:1703.00509)
  4. R. Gustavson, M. Kondratieva, A. Ovchinnikov, New effective differential Nullstellensatz, Advances in Mathematics 290:1138–1158, 2016. DOI: 10.1016/j.aim.2015.12.021, https://doi.org/10.1016/j.aim.2015.12.021 (also arXiv:1411.1000)
  5. R. Gustavson, O. León Sánchez, Effective bounds for the consistency of differential equations, Journal of Symbolic Computation 89:41–72, 2018. DOI: 10.1016/j.jsc.2017.11.003, https://doi.org/10.1016/j.jsc.2017.11.003 (also arXiv:1601.02995)
  6. R. Gustavson, A. Ovchinnikov, G. Pogudin, New order bounds in differential elimination algorithms, Journal of Symbolic Computation 85:128–147, 2018. DOI: 10.1016/j.jsc.2017.07.006, https://doi.org/10.1016/j.jsc.2017.07.006 (also arXiv:1602.00246)
  7. O. León Sánchez, A. Ovchinnikov, On bounds for the effective differential Nullstellensatz, Journal of Algebra 449:1–21, 2016. DOI: 10.1016/j.jalgebra.2015.10.009, https://doi.org/10.1016/j.jalgebra.2015.10.009
  8. L. D'Alfonso, G. Jeronimo, P. Solernó, Effective differential Nullstellensatz for ordinary DAE systems with constant coefficients, Journal of Complexity 30(5):588–603, 2014. DOI: 10.1016/j.jco.2014.01.001, https://doi.org/10.1016/j.jco.2014.01.001 (also arXiv:1305.6298)
  9. D. Grigoriev, Weak Bézout inequality for D-modules, Journal of Complexity 21(4):532–542, 2005. DOI: 10.1016/j.jco.2004.09.006, https://doi.org/10.1016/j.jco.2004.09.006
  10. W. Li, A. Ovchinnikov, G. Pogudin, T. Scanlon, Algorithms yield upper bounds in differential algebra, Canadian Journal of Mathematics 75(1):29–51, 2023. DOI: 10.4153/S0008414X21000560, https://doi.org/10.4153/S0008414X21000560
  11. M. V. Kondratieva, A bound for a typical differential dimension of systems of linear differential equations, Journal of Mathematical Sciences 259:563–569, 2021. DOI: 10.1007/s10958-021-05647-1, https://doi.org/10.1007/s10958-021-05647-1 (also arXiv:1802.06163)
  12. M. V. Kondratieva, The typical dimension of a system of first-order differential equations, Journal of Mathematical Sciences 283(6):912–918, 2024. DOI: 10.1007/s10958-024-07319-2, https://doi.org/10.1007/s10958-024-07319-2
  13. E. R. Kolchin, Differential Algebra and Algebraic Groups, Academic Press, New York, 1973. Zbl 0264.12102, https://zbmath.org/?q=an%3A0264.12102
  14. A. Seidenberg, An elimination theory for differential algebra, University of California Publications in Mathematics, New Series 3(2):31–66, 1956. Zbl 0083.03302, https://zbmath.org/?q=an%3A0083.03302