Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've looked through several books about computer algebra. They are surprisingly scarce about how to actually represent elementary functions.

Basically, as far as I understood elementary functions are roughly

$$\textbf{Quot}\left(\mathbb K[x, \exp x, \exp x^2 \log x, \ldots] \right)$$

that is rational functions over field $\mathbb K$, with variables (or kernels) $x$, $\exp x$, $\exp x^2$, $\log x$ and so on. Other function can be added.

However it doesn't seem possible to have a finite set of kernels to represent what is meant by elementary functions. For example it should contain all kernels of the form $\exp x^n$ or $\exp \exp \ldots \exp x$. And no way you can just enumerate an infinite set within a CAS.

Apparently the algebraic treatment of elementary functions lacks the notion of composition of functions.

How is composition introduced?

What is the algebraic treatment of elementary functions that can be fed to a computer?

share|cite|improve this question
Regarding your third paragraph, consider this: "It doesn't seem possible to a finite set of bitstrings to represent what is meant by a number. For example, it should contain all numbers of the form $0, 1, 2, \ldots$. And there is no way you can just enumerate an infinite set within a computer." – Zhen Lin Apr 30 '12 at 19:50
@ZhenLin Enumerate in the sense it is not an enumerated type. If you add generators (constructors) for kernels virtually you will have function composition. – Yrogirg Apr 30 '12 at 20:08
Represent the infinite set using a finite grammar. Also, to know the best representation for your set on a computer, you have to know first what exactly you want to do with the set or elements of the set. For instance, if you wanted to store a collection of elements (say 32-bit integers), and that's all you wanted to do, then simply use an array (a very basic data structure used by computer programs). But if you want to search for an element in your collection, you should use a sorted array, or search tree, or hash table, and so on. The same will inevitably apply to representing your set. – Enjoys Math May 1 '12 at 22:37

Typical problems such as integration and summation and solving differential and difference equations all take place in finitely-generated extensions of the constant field, so there is no need to explicitly represent such infinite sets (e.g. by using composition algebras).

For references to the theory behind the algorithms see for example Bronstein, Integration of transcendental functions, and Singer and van der Put, Galois theory of difference equations, and Bronstein, Petkovsek et. al on methods (going back to Ore) that unify the differential and difference ring cases.

share|cite|improve this answer
Could you please explain in more detail why did you mention composition algebras? – Yrogirg May 2 '12 at 7:27
I've resolved it, you meant composition ring. – Yrogirg May 3 '12 at 4:33
@Yrogirg The terminology is not standard - some use ring, some algebra, and, as you've learned, it is overloaded. – Bill Dubuque May 3 '12 at 4:39
up vote 0 down vote accepted

I've resolved the issue and my concerns in the FriCAS mailing list. I just thought one cannot define two types that would refer to each other, but I was wrong.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.