3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you asking how to represent an element of an integral domain, or how to represent an integral domain itself? $\endgroup$ – D.W. May 12 '17 at 2:15
  • $\begingroup$ @D.W. The integral domain. $\endgroup$ – Sriotchilism O'Zaic May 12 '17 at 2:18
3
+50
$\begingroup$

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 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.

$\endgroup$
  • $\begingroup$ "the class of integral domains is not even a set" why is it not a set? $\endgroup$ – Sriotchilism O'Zaic May 16 '17 at 22:08
  • $\begingroup$ @D.W. I am familiar with Rusell's paradox. Does the set of integral domains violate the Axiom of Regularity? $\endgroup$ – Sriotchilism O'Zaic May 16 '17 at 22:14
  • $\begingroup$ @EpsilonNeighborhoodWatch, OK, if you're familiar with the fact that we can't always define a set by saying "the set of everything with property X", then I'll let cody explain in more detail the justification behind his statement. $\endgroup$ – D.W. May 16 '17 at 22:18
  • $\begingroup$ I've clarified that point a bit, by hand waving that every set has some integral domain larger than it, and then you may apply the reasoning found here: math.stackexchange.com/q/226413/27659 $\endgroup$ – cody May 17 '17 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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