Domains and number systems

A large part of number theory is built around generalizing the machinery of number systems. That is, any structure that we could reasonably call "numbers". It seems that this category should be rather limited. After all, the four most well-known number systems, integers, rational numbers (fractions), real numbers, and complex numbers, are similar enough to each other that many people just think of them as a single system. Mathematically, any one from the list can be considered a substructure of the next one. Are there other number systems out there? And if so, are they different to the familiar ones in any significant ways?

It wasn't until the 18th century that mathematicians began to run into these new number systems, many of which were minimalist chimeras of integers, Z\mathbb{Z}, and complex numbers, C\mathbb{C}. More on that later. They had initially assumed that these number systems behaved like their parent systems, even leading a high-profile mathematician to a mistaken proof of Fermat's Last Theorem. Unfortunately, many hidden assumptions about how numbers behave weren't valid in these systems. Fortunately, this was ripe ground for generalizations that eventually led to abstract algebra and ring theory.

The approach taken by abstract algebra is to highlight the common properties of closed structures in mathematics.

Closure is a key property in structures like monoids and groups. Monoids are sets of objects with an intrinsic operation, some way of combining two elements together into another element. Closure ensures that this operation combines two elements in a way that their combination is also in the monoid. An easy example of a monoid is all the powers of 2: 2,4,8,16, 2, 4, 8, 16, \dots under the operation of multiplication. To see that it's closed, take two arbitrary elements 2n2^n and 2m2^m. Multiplying gives 2n+m2^{n+m} which is also in the monoid.

Groups add an additional constraint to monoids: not only does the operation have to be closed, but it also needs to be reversibe (equivalently, there are "inverse" elements). In a loose sense, this means that all the mathematics that takes place in a group stays isolated within that group. The same logic works for rings and fields, though now with a second operation.

Rings capture most of what we consider to be number systems. Take Z \mathbb{Z} for example: this is just the set of integers (negative and positive whole numbers). Addition, subtraction, and multiplication of integers yields more integers, and addition of 00 and multiplication by 11 effectively do nothing. Both addition and multiplication are associative, and when they are mixed together they follow another ring requirement: the distributive property:

a(b+c)=ab+ac a (b + c) = ab + ac

While rings formalize the general idea of a number system, they are general enough to include objects that wouldn't be considered typical numbers. An example is the ring of polynomials with integer coefficients Z[x] \mathbb{Z}[x] , whose elements can be written as

a0xn+a1xn1++an1x+anZ[x]aZ a_0 x^n + a_1 x^{n-1} + \cdots + a_{n-1}x + a_n \in \mathbb{Z}[x] \: \: a_{*} \in \mathbb{Z}

Adding/subtracting polynomials to each other gives you another polynomial, and the same can be said for multiplication. In this ring, the 00 and 11 elements are exactly what you'd expect.

In the abstract, rings are considered groups over addition and monoids over multiplication. Being a group under addition means that the inverse operation, subtraction, is always defined. Being a monoid under multiplication, however, means that division isn't always defined. Some rings, such as Z \mathbb{Z} , have enough structure to them that we can create fields, another ring-like structure which has division defined for every element. The procedure of turning a ring into a field is really simple: any two elements aa and bb from a ring correspond to an element a/ba/b its corresponding field. For example, the rational numbers Q \mathbb{Q} are the field obtained from Z \mathbb{Z} by this process.

This isn't always possible to do, though. An example is the ring of 2x2 matrices with integer entries:

M2(Z)={(wxyz):w,x,y,zZ} M_2(\mathbb{Z}) = \{ \left( \begin{matrix} w & x \\ y & z \end{matrix} \right): w, x, y, z \in \mathbb{Z}\}

This ring has all the ring properties, it has a "zero" element, a matrix of all 0's, and a "1" element, the 2x2 identity matrix. but it's impossible to create a field of elements a/ba/b with a,bM2(Z) a, b \in M_2(\mathbb{Z}) . This isn't because a/b a/b itself is impossible to construct, but that multiplication is no longer well-defined. To see why, multiply two elements a/ba/b and c/dc/d to get ac/bd ac/bd. If bd=0bd = 0, then the product ac/bd ac/bd doesn't exist, violating the requirements to be a field. Two elements that have this property are

a=(0100),b=(0200) a = \left( \begin{matrix} 0 & 1 \\ 0 & 0\end{matrix} \right) , \: b = \left( \begin{matrix} 0 & 2 \\ 0 & 0 \end{matrix}\right)

Not only is ab=0ab = 0, but a2=0a^2 = 0 and b2=0b^2 = 0, despite neither of the two being 00 themselves. These elements, known as zero divisors, are what prevent the ring from ever being extended into a field. It's not just these two that are problematic, either, there are infinitely many zero divisors in M2(Z)M_2 (\mathbb{Z}). To distinguish rings like this one from rings like Z \mathbb{Z} that have no zero divisors, we introduce a class of rings known as integral domains.

Integral domains are rings without zero divisors. As a result, they are integer-like in the sense that they can be extended to a field of fractions. The ring of polynomials from earlier, Z[x] \mathbb{Z}[x] , is also an example of an integral domain. Its field of fractions is the field of rational functions. Since polynomials fit so well in with number systems might not be surprising: they can be thought of as representing indexed lists of numbers.

Before you get the sense that nothing interesting can really be happening between the jump from integral domain to field, let's lay out what mathematics in Z \mathbb{Z} is actually like. Despite division not always being defined, divisibility can still be talked about. For example, 1, 2, and 3 divide 6. Any number can be written as a product of its divisors, such as 30=10×330 = 10 \times 3. If a number only has 1 as a divisor, then it's known as a prime number. In general rings, this is known as a prime element instead. In Z \mathbb{Z} , every number can be written uniquely as a product of primes; this is the fundamental theorem of arithmetic. In the example above, the unique factorization of 3030 into primes is 2352*3*5.

Another key property of Z \mathbb{Z} is the ability to efficiently find the greatest common divisor (GCD) of two numbers. This is simply a matter of finding all of the common prime factors between two numbers. The most straightforward approach is to simply factor both numbers to find the GCD. This turns out being very slow since factorization comes down to brute force (guessing). In Z \mathbb{Z} , however, there is a shortcut known as the Euclidean algorithm. Only a subset of domains known as Euclidean domains have this property.

Euclidean algorithm to find the GCD of 1014 and 182 \text{Euclidean algorithm to find the GCD of 1014 and 182} 1014=5×182+104 1014 = 5 \times \underline{182 + 104} 182=1×104+78 \underline{182}= 1 \times \underline{104} + 78 104=1×78+26 104= 1 \times \underline{78 + 26} 78=3×26+0 \underline{78} = 3 \times \underline{26} + 0 \: * GCD(1014, 182) = 26 \text{GCD(1014, 182) = 26}

In Z \mathbb{Z} , to find the GCD of pp and qq where q<pq < p, write p=nq+rp = nq + r for some nn and rr. There are many ways to do this, but forcing r<qr < q will always lead to just one. This is the same as "dividing" pp by qq to get a remainder rr. In the Euclidean algorithm, simply take qq and rr, where r<qr < q, and repeat this process (notice that qq is now in pp's place and rr is now in qq's place ). This will go on until reaching either 00 or 11, where the algorithm stops. If it reaches 11, then GCD(p,q)=1GCD(p, q) = 1. Otherwise, the algorithm returns with the qq from the last step. See above for an example.

Unique factorization and the existence of the Euclidean algorithm are both ancient theorems in number theory. However, they break down in some domains. To actually construct one, we can start with Z \mathbb{Z} and add an element from C\mathbb{C}, say 5\sqrt{-5} to it. This means that we have a number system, Z[5]\mathbb{Z}[\sqrt{-5}], with elements

a+b5a,bZ a + b \sqrt{-5} \: \: a, b \in \mathbb{Z}

Not only is this a ring, but also an integral domain just as Z \mathbb{Z} is. However, number theory in Z[5]\mathbb{Z}[\sqrt{-5}] is different. For example, unique factorization no longer holds:

6=2×3=(1+5)(15) 6 = 2 \times 3 = (1 + \sqrt{-5} )(1 - \sqrt{-5})

Domains with unique factorization are called UFDs. While Z \mathbb{Z} is a UFD, Z[5]\mathbb{Z}[\sqrt{-5}] isn't.

One consequence of unique factorization failing is that the Euclidean algorithm doesn't exist in this domain either. In fact, the existence of the Euclidean algorithm implies unique factorization (so all Euclidean domains are UFDs) even though unique factorization doesn't guarantee the Euclidean algorithm's existence. An example is Z[1+192] \mathbb{Z}[ \frac{1 + \sqrt{-19}}{2} ], which is a UFD but not a Euclidean domain. The proof is here. In fact, 19,43,67,and163-19, -43, -67, \text{and} -163 are the only numbers which generate non-Euclidean UFDs in the same form as Z[1+192] \mathbb{Z}[ \frac{1 + \sqrt{-19}}{2} ]. This is deeply related to the following near-integer approximations:

eπ439603+744 e^{\pi \sqrt{43}} \approx 960^3 + 744 eπ6752803+744 e^{\pi \sqrt{67}} \approx 5280^3 + 744 eπ1636403203+744 e^{\pi \sqrt{163}} \approx 640320^3 + 744

In Z[5]\mathbb{Z}[\sqrt{-5}], the concept of a prime number also subtly breaks down to be replaced by the concept of an irreducible number (or atom). Primes and atoms both share the feature that they are only divisible by 11, but primes are defined by the additional property that whenever a prime pp divides abab, or pabp | ab, then either pap | a or pbp | b. In the example above, 2,3,1+5,and152, 3, 1 + \sqrt{-5}, \text{and} 1 - \sqrt{-5} are all irreducible, but none of them are prime.

To see why 22 isn't prime, note that 2(1+5)(15) 2 | (1 + \sqrt{-5} )(1 - \sqrt{-5}) , but neither 2(1+5) 2 |(1 + \sqrt{-5}) nor 2(15) 2|(1 - \sqrt{-5}) are true. This applies to the other three as well.

The distinction between prime and atomic elements doesn't exist in UFDs. In fact, they coincide in a slightly larger class of domains known as GCD domains, in which greatest common divisors always exist. The difference between UFD domains and GCD domains is small, but comes about from the fact that unique factorization always has to have finitely many factors. As a result, the ring of holomorphic functions is an example of a non-UFD GCD. First, it's an integral domain since two holomorphic functions cannot multiply to 0. The GCD between two functions can be defined as the zeroes they have in common, so it's a GCD domain. However, factorization of holomorphic functions is not always finite:

sin(z)=zk=1(1z2π2k2) sin(z) = z \displaystyle \prod_{k=1}^{\infty} \left( 1 - \frac{z^2}{\pi^2 k ^2} \right)

A different situation where prime numbers start to break down is in Z[i]\mathbb{Z}[i], but in a more literal sense. In this domain, 55 is no longer prime since 5=(2+i)(2i)=(1+2i)(12i)5 = (2 + i)(2 - i) = (1 + 2i)(1 - 2i) . 13,17,and 2913, 17, \text{and } 29 are some other primes which break down in this domain. How can we know exactly what primes lost? An element ss in Z[i]\mathbb{Z}[i] can be written as s=a+ibs = a + ib. Multiplying by its conjugate gives

ss=p=a2+b2 s^* s = p = a^2 + b^2

So all the primes that are split are the ones that can be written as the sum of two squares. Fermat proved that this happens for a prime pp iff p1mod4p \equiv 1 \: mod \: 4. However, this was in the context of classical number theory long before domains were known about. For a general domain Z[n]\mathbb{Z}[\sqrt{-n}], the primes that split are just those of the form p=a2+nb2p = a^2 + n b^2.

Since 5=(2+i)(2i)=(1+2i)(12i)5 = (2 + i)(2 - i) = (1 + 2i)(1 - 2i) , this should immediately imply that unique factorization breaks down. But it doesn't; thanks to the notion of a "unit," these two factorizations are actually the same. A unit of a ring is any element with an inverse. This makes it similar to the identity element, 11, in the sense that multiplication with units can be effectively ignored. In Z[i]\mathbb{Z}[i], the units are 1,1,i,i1, -1, i, -i. The two factorizations, (2+i)(2i)=i(12i)×(i)(1+2i)(2 + i)(2 - i) = i(1 - 2i) \times (-i) (1 + 2i) , can then be considered the same since they only differ by multiplication of units.

Since Z[i]\mathbb{Z}[i] is a UFD, it has it's own set of prime numbers. Here's what they look like on the complex plane:

Just as above for primes, in the ring Z[n]\mathbb{Z}[\sqrt{n}] all units u=a+bnu = a + b\sqrt{n} can be found from the solutions of ±1=a2nb2\pm 1 = a^2 - n b^2. For example, the units in Z[2]\mathbb{Z}[\sqrt{2}] are generated by ±1=a22b2\pm 1 = a^2 - 2 b^2. The first nontrivial solution is a=1,b=1a=1, b=1 or u=1+2u = 1 + \sqrt{2}. You can take powers of this solution to find the others:

(1+2)2=3+22 ( 1 + \sqrt{2})^2 = 3 + 2 \sqrt{2} (1+2)3=7+52 ( 1 + \sqrt{2})^3 = 7 + 5 \sqrt{2} (1+2)4=17+122 ( 1 + \sqrt{2})^4 = 17 + 12 \sqrt{2} (1+2)n=k0mod2n(nk)2k/2+2k1mod2n(nk)2(k1)/2 ( 1 + \sqrt{2})^n = \displaystyle \sum_{k \equiv 0 \: mod \: 2}^n \dbinom{n}{k} 2^{k/2} + \sqrt{2} \displaystyle \sum_{k \equiv 1 \: mod \: 2}^n \dbinom{n}{k} 2^{(k-1)/2}

Without using binomial coefficients, the unit's components follow the recursion:

un=an+bn2a1=1,b1=1 u_n = a_n + b_n \sqrt{2} \: \: a_1 = 1, b_1 = 1 an+1=an+2bn a_{n+1} = a_n + 2 b_n bn+1=an+bn b_{n+1} = a_n + b_n

Another cool property is that the ratio an/bna_n / b_n approaches 2\sqrt{2}. Since ana_n and bnb_n become larger as n grows, the equation ±1=a22b2\pm 1 = a^2 - 2 b^2 can be approximated by

0a22b2 0 \approx a^2 - 2 b^2 a/b2 a/b \approx \sqrt{2}

In general, finding the units of Z[n]\mathbb{Z}[\sqrt{n}] reduces to another problem from classical number theory: Pell's equation. This equation is also well-studied in classical number theory since it can generate rational approximations of square roots.

Note by Levi Walker
1 month, 3 weeks ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Awesome writing! I'm glad i logged in today to chance upon this

Julian Poon - 1 month, 2 weeks ago

Log in to reply

Thank you!

Levi Walker - 1 month, 1 week ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...