\documentstyle[11pt,mm,amsmath,amssymb]{article}
%\documentclass[11pt]{article}
%\usepackage{mathbbold}
%\usepackage{amsmath}
%\usepackage{amssymb}
%\usepackage{mm}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{define}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{problem}[theorem]{Problem}
\def\qed{\hfil {\vrule height5pt width2pt depth2pt}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This is a sample to use the MM style file "MM.sty". %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Following \def\startpage{} and \def\endpage{} is filled by the editor.
% \vol{24} is the volume of this issue
% \year{2005} is the year of publication
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\startpage{1} % set start page number. This is filled by the editor
\def\endpage{19} % set end page number. This is filled by the editor
\def\vol{25} % Volume of this issue
\def\year{2006} % Year
\setcounter{page}{\startpage}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% runauthor is the author(s) marked on the head of the even pages
% In this example authors are B. Apple, S. Orange and W. Grape
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\runauthor{R. Feng and X.S. Gao}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% runtitle is the title put on the head of the odd page. Should be written
% briefly. In this example runtitle is " Nice fruits "
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\runtitle{Polynomial General Solutions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Never forget to put "mm.sty" in a proper directory. It is recommended to
% put mm.sty just in the same directory where your draft your_paper.tex is
% located.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% The title of your paper should be filled here. In this example the title
% is "How to eat nice fruits".
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\title{Polynomial General Solution for First Order ODEs with Constant Coefficients
\thanks{\quad Partially supported by a
National Key Basic Research Project of China and
by a USA NSF grant CCR-0201253. }}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Here you fill author name(s) and his(their) institution(s) as
% \author{ Author NAME\affil{ His Institution} } If more than three author
% names are filled, please don't forget to put camma and "and" as in the
% following example
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\author{Ruyong Feng and Xiao-Shan Gao\\
Key Laboratory of Mathematics Mechanization\\
Institute of Systems Science, AMSS,
Academia Sinica\\
Beijing 100080, China\\
(ryfeng,xgao)@mmrc.iss.ac.cn}
\date{}
\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% We need a short abstract.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
We give a necessary and sufficient
condition for an ODE to have polynomial
type general solution. For a first order ODEs of degree $n$ with constant
coefficients, we give an algorithm of complexity $O(n^5)$ to
decide whether it has a polynomial general solution or not and to compute one if it exists.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%
%%%%%% From here the main part of your paper begins
%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec-0}
Trying to find elementary function solutions for differential
equations may be traced back to the work of Liouville. As a consequence, such
solutions of differential equations are called {\it Liouvillian
solutions}. In a pioneering paper \cite{u-c}, Risch gave an
algorithm for finding Liouvillian solutions for the simplest
differential equation $y' = f(x)$, that is, to find elementary function solutions
to integration $\int{f(x){\rm d}x}$.
In \cite{u-c}, Kovacic presented a method for
solving second order linear homogeneous differential equations. In
\cite{u-c}, Singer proposed a method to find Liouvillian
solutions of general linear differential equations. Many other interesting results
on finding Liouvillian solutions of linear ODEs are given in
\cite{u-c}.
In \cite{u-c}, Li and Schwarz gave a method to find rational
solutions for a class of partial differential equations.
The paper is organized as follows.
In section 2, we give a brief introduction to the characteristic
set method. In section 3, a criterion for an ODE to have
polynomial general solution is given. In section 4, we give the degree bound
of solutions of first order ODEs with constant coefficients and an algorithm. In section 5, we
analyse the structure of first order ODEs which have polynomial general solution. In section 6, we present
a polynomial-time algorithm to find polynomial general
solution of first order ODEs and some examples.
%The rest of the paper is organized as follows. In Section 2, we
%introduce some notations. In Section 3, we show how to find
%polynomial solutions with Wu-Ritt's zero decomposition algorithm.
%In Section 4, we treat the binomial case. In Section 5, we treat
%the trinomial case.
\section{A brief introduction to the characteristic set method}
\label{sec-2}
%
In this section, we introduce some concepts and notations on the
characteristic set method. More details can be found in
\cite{u-c,wu}.
The paper is organized as follows.
In section 2, we give a brief introduction to the characteristic
set method. In section 3, a criterion for an ODE to have
polynomial general solution is given. In section 4, we give the degree bound
of solutions of first order ODEs with constant coefficients and an algorithm. In section 5, we
analyse the structure of first order ODEs which have polynomial general solution. In section 6, we present
a polynomial-time algorithm to find polynomial general
solution of first order ODEs and some examples.
%The rest of the paper is organized as follows. In Section 2, we
%introduce some notations. In Section 3, we show how to find
%polynomial solutions with Wu-Ritt's zero decomposition algorithm.
%In Section 4, we treat the binomial case. In Section 5, we treat
%the trinomial case.
\section{A brief introduction to the characteristic set method}
\label{sec-2}
%
In this section, we introduce some concepts and notations on the
characteristic set method. More details can be found in
\cite{u-c,wu}.
The paper is organized as follows.
In section 2, we give a brief introduction to the characteristic
set method. In section 3, a criterion for an ODE to have
polynomial general solution is given. In section 4, we give the degree bound
of solutions of first order ODEs with constant coefficients and an algorithm. In section 5, we
analyse the structure of first order ODEs which have polynomial general solution. In section 6, we present
a polynomial-time algorithm to find polynomial general
solution of first order ODEs and some examples.
The paper is organized as follows.
In section 2, we give a brief introduction to the characteristic
set method. In section 3, a criterion for an ODE to have
polynomial general solution is given. In section 4, we give the degree bound
of solutions of first order ODEs with constant coefficients and an algorithm. In section 5, we
analyse the structure of first order ODEs which have polynomial general solution. In section 6, we present
a polynomial-time algorithm to find polynomial general
solution of first order ODEs and some examples.
The paper is organized as follows.
In section 2, we give a brief introduction to the characteristic
set method. In section 3, a criterion for an ODE to have
polynomial general solution is given. In section 4, we give the degree bound
of solutions of first order ODEs with constant coefficients and an algorithm. In section 5, we
analyse the structure of first order ODEs which have polynomial general solution. In section 6, we present
a polynomial-time algorithm to find polynomial general
solution of first order ODEs and some examples.
The paper is organized as follows.
In section 2, we give a brief introduction to the characteristic
set method. In section 3, a criterion for an ODE to have
polynomial general solution is given. In section 4, we give the degree bound
of solutions of first order ODEs with constant coefficients and an algorithm. In section 5, we
analyse the structure of first order ODEs which have polynomial general solution. In section 6, we present
a polynomial-time algorithm to find polynomial general
solution of first order ODEs and some examples.
The paper is organized as follows.
In section 2, we give a brief introduction to the characteristic
set method. In section 3, a criterion for an ODE to have
polynomial general solution is given. In section 4, we give the degree bound
of solutions of first order ODEs with constant coefficients and an algorithm. In section 5, we
analyse the structure of first order ODEs which have polynomial general solution. In section 6, we present
a polynomial-time algorithm to find polynomial general
solution of first order ODEs and some examples.
\section{Conclusion}
We give a polynomial-time algorithm to compute a polynomial
general solution of first order ODEs with constant coefficients.
Our experiments show that the algorithm can be used to solve
very large ODEs.
It is interesting to see whether the result can be extend to the
case when the coefficients of first order ODEs are not
constant or the case of high order ODEs with constant coefficients.
\begin{thebibliography}{99}
\bibitem{u-c}
Ulmer, F., Calmet, J., {\it On Liouvillian Solutions of
Homogeneous Linear Differential Equations}, {\em Proc. ISSAC1990},
236-243, ACM Press, 1990.
%%
\bibitem{wu}
Wu, W.T., {\em Mathematics Mechanization}, Science Press/Kluwer,
Beijing, 2000.
\end{thebibliography}
\end{document}