Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Zero-equivalence in function fields defined by algebraic differential equations


Author: John Shackell
Journal: Trans. Amer. Math. Soc. 336 (1993), 151-171
MSC: Primary 12H05; Secondary 13P10
DOI: https://doi.org/10.1090/S0002-9947-1993-1088022-2
MathSciNet review: 1088022
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We consider function fields obtained as towers over the field of rational functions, each extension being by a solution of an algebraic differential equation. On the assumption that an oracle exists for the constants, we present two algorithms for determining whether a given expression is functionally equivalent to zero in such a field. The first, which uses Gröbner bases, has the advantage of theoretical simplicity, but is liable to involve unnecessary computations. The second method is designed with a view to eliminating these.


References [Enhancements On Off] (What's this?)

  • [1] A. Baker, Transcendental number theory, Cambridge Univ. Press, Cambridge, 1975. MR 0422171 (54:10163)
  • [2] G. Birkoff and G. C. Rota, Ordinary differential equations, Ginn, 1962. MR 0138810 (25:2253)
  • [3] W. S. Brown, Rational exponential expressions and a conjecture concerning $ \pi $ and $ e$, Amer. Math. Monthly 76 (1969), 28-34. MR 0234933 (38:3247)
  • [4] W. S. Brown and J. F. Traub, On Euclid's algorithm and the theory of subresultants, J. Assoc. Comput. Mach. 18 (1971), 505-514. MR 0303684 (46:2820)
  • [5] B. Buchberger, Gröbner bases: an algorithmic method in polynomial ideal theory, Multidimensional Systems Theory (N. K. Böse, ed.), Reidel, Dordrecht, 1985, pp. 184-232.
  • [6] B. Buchberger and R. Loos, Algebraic simplification, Computer Algebra: Symbolic and Algebraic Computation (B. Buchberger, G. E. Collins, and R. Loos, eds.), 2nd ed., Springer-Verlag, Wien/New York, 1983, pp. 11-43. MR 728962
  • [7] B. F. Caviness, Methods for symbolic computation with transcendental functions, Proc. Conf. on Symbolic Computational Methods and Applications (A. Visconti, ed.), St. Maximin, France, 1977, pp. 16-43.
  • [8] -, On canonical forms and simplification, J. Assoc. Comput. Mach. 17 (1970), 385-396. MR 0281386 (43:7104)
  • [9] B. F. Caviness and M. J. Prelle, A note on algebraic independence of logarithmic and exponential constants, SIGSAM Bull. 12 (1978), 18-20.
  • [10] J. Denef and L. Lipshitz, Decision problems for differential equations, J. Symbolic Logic 54 (1989), 941-950. MR 1011182 (91b:03074)
  • [11] -, Power series solutions of algebraic differential equations, Math. Ann. 267 (1984), 213-238. MR 738249 (85j:12010)
  • [12] J. P. Fitch, On algebraic simplification, Comput. J. 17 (1973), 23-27. MR 0401613 (53:5440)
  • [13] O. Forster, Lectures on Riemann surfaces, Springer-Verlag, New York, 1981. MR 648106 (83d:30046)
  • [14] M. R. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of $ NP$-completeness, Freeman, New York, 1979. MR 519066 (80g:68056)
  • [15] G. H. Hardy, Orders of infinity, Cambridge Univ. Press, Cambridge, England, 1910.
  • [16] S. C. Johnson, On the problem of recognizing zero, J. Assoc. Comput. Mach. 18 (1971), 559-565. MR 0295514 (45:4580)
  • [17] S. Lang, Transcendental numbers and diophantine approximation, Bull. Amer. Math. Soc. 77 (1971), 635-677. MR 0289424 (44:6615)
  • [18] D. Lazard, Résolutions des systèmes d'equations algébriques, Theoret. Comput. Sci. 15 (1981), 77-110. MR 619687 (82i:12001)
  • [19] A. J. Macintyre, The laws of exponentiation, Model Theory and Arithmetic (C. Berline, K. McAloon, and J. P. Rossayre, eds.), Springer-Verlag, New York, 1981, pp. 185-197. MR 645003 (83f:03037)
  • [20] W. A. Martin, Determining the equivalence of algebraic expressions by hash coding, J. Assoc. Comput. Mach. 18 (1971), 549-558.
  • [21] F. Mora, An algorithm to compute the equations of tangent cones, EUROCAM '82 Proceedings, Springer-Verlag, Berlin and New York, 1982, pp. 158-165. MR 680065 (84c:13012)
  • [22] J. Moses, Algebraic simplification: a guide for the perplexed, Comm. Assoc. Comput. Mach. 14 (1971), 527-537. MR 0309355 (46:8465)
  • [23] -, Solution of a system of polynomial equations by elimination, Comm. Assoc. Comput. Mach. 9 (1966), 634-637.
  • [24] A. C. Norman, Computing in transcendental extensions, Computer Algebra: Symbolic and Algebraic Computation, 2nd ed. (B. Buchberger, G. E. Collins, and R. Loos, eds.), Springer-Verlag, Wien/New York, 1983, pp. 11-43. MR 728971
  • [25] A. Oldehoeft, Analysis of constructed mathematical responses by numeric tests for equivalence, Proc. ACM 24th Nat. Conf., 1969, pp. 117-124.
  • [26] D. Richardson, Finding roots of equations involving solutions of first order algebraic differential equations, Proc. Conf. Effective Methods in Algebraic Geometry, MEGA, 1990.
  • [27] -, Solution of identity problem for integral exponential functions, Z. Math. Logik Grundlag. Math. 15 (1969), 333-340. MR 0262068 (41:6678)
  • [28] -, Some undecidable problems involving elementary functions of a real variable, J. Symbolic Logic 33 (1968), 514-520. MR 0239976 (39:1330)
  • [29] M. Rothstein and B. F. Caviness, A structure theorem for exponential and primitive functions, SIAM J. Comput. 8 (1979), 357-367. MR 539254 (80m:12028)
  • [30] J. R. Shackell, Asymptotic estimation of oscillating functions using an interval calculus, ISSAC '88 Proceedings (P. Gianni, ed.), Springer-Verlag, Rome, pp. 481-489. MR 1034751 (91e:65067)
  • [31] -, A differential-equations approach to functional equivalence, ISSAC '89 Proceedings (G. Gonnet, ed.), A.C.M. Press, Portland, Oregon, 1989, pp. 7-10.
  • [32] M. F. Singer, Liouvillian first integrals of differential equations, (extended abstract), ISSAC '88 Proceedings (P. Gianni, ed.), Springer-Verlag, 1988, pp. 57-63. MR 1034720
  • [33] F. Ulmer, Representing functions by differential equations, private communication, 1989.
  • [34] O. Zariski and P. Samuel, Commutative algebra, vols. I, II, Van Nostrand, 1960. MR 0120249 (22:11006)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 12H05, 13P10

Retrieve articles in all journals with MSC: 12H05, 13P10


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1993-1088022-2
Keywords: Zero equivalence, functional equivalence, symbolic computation, computer algebra
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society