View source for Algebraic decidability of local classification problems

The notion related to local classification of singularities of differential maps and local dynamical systems. A local property (the type of extremum of a smooth function, stability of a [[Local normal forms for dynamical systems#Local_normal_forms_for_dynamical_systems#Local_dynamical_systems_and_their_equivalence|local dynamical system]], structural stability of the mapping) is ''algebraically decidable'' if, very roughly, it can be determined by finite number of equality- and inequality-type constraints imposed on the Taylor polynomial of the object under investigation.
== Paradigm: extremum of a $C^\infty$-smooth function of one variable ==
Let $u:(\R^1,0)\to\R$ be the germ of a $C^\infty$-smooth function of one real variable with the Taylor series
$$
u(t)=u_0+u_1t+u^2\,t^2+\cdots+u_n\,t^n+\cdots,\qquad u_0,u_1,\dots,u_n\in\R.
$$
We are interested in the conditions guaranteeing that the origin $t=0$ has an isolated minimum, isolated maximum or monotonously increases (resp., decreases) in a sufficiently small neighborhood $(\R^1,0)$. The following answer is universally known:

::{|
|-
|$u_1\ne 0$ || local monotinicity (increase for $u_1>0$, decrease for $u_1<0$)
|-
|$u_1=0$, $u_2\ne 0$ || local extremum (minimum for $u_2<0$, maximum for $u_2>0$)
|-
|$u_1=u_2=0$, $u_3\ne 0\quad$ || local monotonicity depending on $\operatorname{sign}u_3$
|-
|$u_{1,2,3}=0$, $u_4\ne 0$ || local extremum  (maximum or minimum, depending on $\operatorname{sign}u_3$)
|-
|$\cdots$ || $\cdots$
|}
The conditions determining the local type of the critical point form a tree. On each level one has strict inequalities guaranteeing the type, which, when "degenerate" into the equalities, require consideration of higher order terms (thus passing on the next level of the tree). 

The ultimate answer ("what happens if all Taylor coefficients vanish") can be given if $u$ is analytic (then $u(t)\equiv0$ has a non-strict extremum) and cannot for just $C^\infty$-smooth functions (one can have extremum of any type or monotonicity in any direction).

== Formal definition ==
Consider the set of objects $\mathscr M$ defined by one or several smooth ($C^\infty$ or analytic) germs of functions on $(\R^n,0)$ with an equivalence relation $\sim$ defined by a smooth action of change of variables (see [[normal form]]). Assume that $\mathscr M$ is represented as a disjoint union of two subsets $\mathscr M_-$ and $\mathscr M_+$, each formed by union of equivalence classes. By $J^k\mathscr M$ we denote the $k$-[[jet space]] of objects from $\mathscr M$: points in $J^k\mathscr M$ can be identified with the Taylor polynomials of order $k$ of objects from $\mathscr M$. Note that these jet approximations are affine finite-dimensional spaces (the Talyor coefficients up to order $k$ can be considered as coordinates on them).  

The ''alternative'' (''dichotomy'') $\mathscr M_-/\mathscr M_+$ is to decide, whether a given element $f\in\mathscr M$ belongs to $\mathscr M_-$ or $\mathscr M_+$, by inspection of its jets $j^k f\in J^k\mathscr M$ of increasing orders.

;Examples.
* '''Local minimum'''. $\mathscr M=\{u:(\R^1,0)\to\R\}$, $\mathscr M_+$ consists of germs with a strict minimum, $\mathscr M_-=\mathscr M\smallsetminus\mathscr M_+$. This is a version of the motivation example above;
* '''Lyapunov stability of vector fields'''. $\mathscr M$ consists of germs of $C^\infty$-smooth vector fields on $(\R^n,0)$, $\mathscr M_+$ consists of Lyapunov stable germs, $\mathscr M_-$ being the complement; 
* '''Center-focus alternative'''. $\mathscr M$ is the germs of real analytic vector fields on the plane, $\mathscr M_+$ is the germs exhibiting [[Centre and focus problem|centre]]-type phase portrait (all nonstationary trajectories are closed), $\mathscr M_-$ again the complement;
* '''Constrained center-focus alternative'''. $\mathscr M$ consists of vector fields with the "rotational" linear part $\dot x=-y$, $\dot y=x$, $\mathscr M_+$ is the fields with center, $\mathscr M_-$ the complement, which in this case necessary must consist of foci.

;Definition
The dichotomy $\mathscr M_-/\mathscr M_+$ is said to be ''algebraically decidable'' {Cite|IY|Sect. 10}}, if each jet space $M^k=J^k\mathscr M$ can be represented as the disjoing union of three subsets, $M^k=M_-^k\sqcup M_+^k\sqcup M_0^k$, $k=0,1,2,\dots$ with the following properties.
# All sets $M^k_\pm,M^k_0$ are semialgebraic (defined by finitely many polynomial equalities and inequalities);
# The subsets $M^k_\pm$ are sufficient for decision: $j^kf\in M^k_\pm\implies f\in\mathscr M_\pm$;
# The ''neutral subset'' $M_0^k$ which requires additional study, is relatively small: $\operatorname{codim}M^k_0$ in $M^k$ tends to $+\infty$ as $k\to+\infty$.

This definition was first suggested by V. Arnold in {{Cite|Ar70a}}.

== Algebraically decidable and algebraically undecidable alternatives ==

The local minimum alternative is algebraically decidable in one variable, as was shown above. In fact, it is algebraically decidable in all dimensions, although the explicit equalities and inequalities are increasingly cumbersome. 

The Lyapunov stability problem is not algebraically decidable {{Cite|Ar70b}}, {{Cite|Ar70c}}. The same applies to the (unrestricted) center-focus alternative: in both cases the "equality-type" conditions "separating" the sufficient inequality-type conditions, are non-algebraic (involve exponentials, logarithms and eventually integrals of polynomial 1-forms over algebraic ovals). However, these non-algebraic conditions apply only to the ''principal Taylor part'' of the vector fields: in the restricted problems where this part is fixed, the stability (resp., centrality) conditions imposed on the higher order terms, are algebrabraic {{Cite|Il72}}, {{Cite|IY|Sect. 10}}.

== References ==


{|
|-
                 
|valign="top"|{{Ref|Ar70a}}|| valign="top"|Arnold, V. I.  ''Local problems of analysis''. (Russian)  Vestnik Moskov. Univ. Ser. I Mat. Meh.  '''25'''  1970  no. 2 52--56. {{MR|0274875}} 
|-
                 
|valign="top"|{{Ref|Ar70b}}|| valign="top"| Arnold, V. I.  ''Algebraic unsolvability of the problem of Ljapunov stability and the  problem of the topological classification of the singular points of an  analytic system of differential equations''. (Russian)  Funkcional. Anal. i Priložen.  '''4'''  1970  no. 3 1--9. {{MR|0273108}}  
|-
                 
| valign="top"|{{Ref|Ar70c}}|| Arnold, V. I.  ''Algebraic unsolvability of the problem of stability and the problem of  the topological classification of the singular points of analytic systems of  differential equations''. (Russian)  Uspehi Mat. Nauk  '''25'''  1970  no. 2 (152) 265--266. {{MR|0261080}} 
|-
                 
|valign="top"|{{Ref|I72}}||valign="top"| Ilyashenko, Yu. S.  ''Algebraic unsolvability and almost algebraic solvability of the problem  for the center-focus''. (Russian)  Funkcional. Anal. i Priložen.  6  (1972),  no. 3, 30--37.                 {{MR|0315200}} 
|-
|valign="top"|{{Ref|IY}}||valign="top"|  Yu. Ilyashenko, S.    Yakovenko, ''Lectures on analytic differential  equations''. Graduate    Studies in Mathematics, '''86'''. American  Mathematical Society,    Providence, RI,  2008 {{MR|2363178}}
|}