patternMinor
Representing Integral domains in computer memory?
Viewed 0 times
domainscomputermemoryintegralrepresenting
Problem
Earlier I wrote this question about an algorithm computed on an integral domain. However as commented I didn't suggest any particular ways of storing an integral domain in computer memory. I set out to do this but found it a particularly difficult task.
It is in fact impossible to store all the integral domains in memory because the fields are uncountable1 and are a subset of the integral domains. However I am not concerned with fields because they don't have any primes anyway.
How might one represent non-field integral domains in computer memory? Is the set of all non-field integral domains countable? If it is uncountable is there any useful subset of them that can be represented in computer memory?
1: The rationals are a field. Every polynomial extension of a field is also a field. Thus the number of polynomial field extensions of $\mathbb{Q}$ is the powerset of the irreducible polynomials on $\mathbb{Q}$ which is uncountable.
It is in fact impossible to store all the integral domains in memory because the fields are uncountable1 and are a subset of the integral domains. However I am not concerned with fields because they don't have any primes anyway.
How might one represent non-field integral domains in computer memory? Is the set of all non-field integral domains countable? If it is uncountable is there any useful subset of them that can be represented in computer memory?
1: The rationals are a field. Every polynomial extension of a field is also a field. Thus the number of polynomial field extensions of $\mathbb{Q}$ is the powerset of the irreducible polynomials on $\mathbb{Q}$ which is uncountable.
Solution
In general this question has no precise answer: the class of integral domains is not even a set, much less a countable set! (For example, for each set $A$, we can find an integral domain $D_A$ larger than $A$, e.g. $\mathbb{Z}[A]$, which is sufficient to show that integral domains can't be all gathered into a set).
In general you need to specify something to describe the elements of the set, and how to compute multiplication and addition.
A popular choice, which covers a large portion of the interesting examples, is to take a known ring or field $R$, typically $\mathbb{Z}$ or $\mathbb{Q}$, or some finite field $\mathbb{F}_q$, and look at some quotient ring of the form $D = R[X_1,\ldots,X_n]/(P_1,\ldots,P_k)$, where the $P_i$ are polynomials in the $X_j$.
Now it's not even clear that $D$ is an integral domain, which is equivalent here to the fact that $I=(P_1,\ldots, P_k)$ is irreducible. This can be determined using the Gröbner basis method as explained here.
Now there is an obvious representation for the elements of $D$: every element is represented by a polynomial, which we know how to represent, and do addition and multiplication on. The only issue is equality, since it needs to be modulo $I$. But this also is possible using known techniques, similar to the Gröbner basis ones.
It would be great if someone had implemented all of this up somewhere, though. Oh but they have! The Sage mathematical software toolchain builds on all of these observations to offer a ton of ways to concretely work with these kinds of rings. They even have an
Sage is a fantastic piece of software that I highly recommend, which probably does a lot of what you want.
In general you need to specify something to describe the elements of the set, and how to compute multiplication and addition.
A popular choice, which covers a large portion of the interesting examples, is to take a known ring or field $R$, typically $\mathbb{Z}$ or $\mathbb{Q}$, or some finite field $\mathbb{F}_q$, and look at some quotient ring of the form $D = R[X_1,\ldots,X_n]/(P_1,\ldots,P_k)$, where the $P_i$ are polynomials in the $X_j$.
Now it's not even clear that $D$ is an integral domain, which is equivalent here to the fact that $I=(P_1,\ldots, P_k)$ is irreducible. This can be determined using the Gröbner basis method as explained here.
Now there is an obvious representation for the elements of $D$: every element is represented by a polynomial, which we know how to represent, and do addition and multiplication on. The only issue is equality, since it needs to be modulo $I$. But this also is possible using known techniques, similar to the Gröbner basis ones.
It would be great if someone had implemented all of this up somewhere, though. Oh but they have! The Sage mathematical software toolchain builds on all of these observations to offer a ton of ways to concretely work with these kinds of rings. They even have an
is_integral method for quotient rings!Sage is a fantastic piece of software that I highly recommend, which probably does a lot of what you want.
Context
StackExchange Computer Science Q#75262, answer score: 3
Revisions (0)
No revisions yet.