if you use a poor definition such as, “Prime is a number that is only divisible by itself and 1.”
I have a fondness for this particular definition, and like to think of 1 as a “very special” prime number. To the extent that I usually give a little speech whenever an opportunity arises that (ahem) the only reason I know of that ‘1’ is excluded from the primes (more often than not) is because almost every theorem about prime numbers would have to be modified with an “except 1″ clause. But a natural definition (anything along the lines of “already completely factored”) would include it. If you disagree, which definition—or the satisfaction of which theorem—do you think is more compelling?
(Just in case you perceived you were getting too much heat about “colour”...)
I’d have to pretty strongly disagree. To me, the “essence” of primes is that you can factor any number into primes in a unique way. That’s the most natural definition. They’re the multiplicative building blocks of the natural numbers; everything can be reduced to them. If 1 were prime, you could no longer factor uniquely.
Your comment and this comment were adjacent in my message folder which I found amusing.
Thomblake wrote:
Caring about what’s right might be as arbitrary (in some objective sense) as caring about what’s prime, but we do actually happen to care about what’s right.
Hmm… I agree this is compelling. However, since I’m resistant to updating my world view about 1-the-discriminated-prime-number, I’ll continue to proffer counter-arguments:
the Fundamental Theorem of Arithmetic is pretty important, but may still not be the “essence” of what prime is
the FTA itself requires the “except 1” clause: “all natural numbers can be uniquely factored into primes except 1″ -- which would make someone thing 1 ought to be prime
the FTA already assumes ‘modulo permutations’, we could easily throw in ‘modulo 1’
Wikipedia—the first and last authority on such things—carefully writes in an entire sentence unto itself, “The number 1 is by definition not a prime number,” suggesting just how arbitrary this is. (My own emphasis added.)
The best argument I came up with for not including 1 as prime, because I tend to worry about how things are constructed, was with the seive of Eratosthenes.
The seive of Eratosthenes says that you can find the primes by starting with all the natural numbers > 1; let 2 be the first prime number, and then begin eliminating all multiples of 2 and the multiples of subsequent primes as you find them. If you included ‘1’ in the first step, then you would eliminate all the numbers in the first step.
I think you’re really failing to grasp the content of the unique factorization theorem here. Firstly we don’t think about factored numbers as products of primes up to permutation, we think of them as products of distinct prime powers (up to permutation, I suppose—but it’s probably better here to just take a commutative viewpoint and not regard “up to permutation” as worth specifying). But more importantly, you need to take a multiary view of multiplication here, not a binary one. 1 is the empty product, so in particular, it is the product of no primes, or the product of each prime to the 0th power. That is its unique prime factorization. To take 1 as a prime would be like having bases for vector spaces include 0. Almost exactly like it—if we take the Z-module of positive rationals under multiplication, the set of primes forms a free basis; 1 is the zero element.
Information and expertise like this is why hanging out at Less Wrong is worth the time. I estimate that I value the information in your comment at about $35, meaning my present self would advise my former self to pay up to $35 to read it.
So, I get it. My brain is more wired for analysis than algebra; so this isn’t the first time that linear algebra has been a useful bridge for me. I see that we could have a ‘vector space’ of infinite-dimensional vectors where each vector (a1, a2, …, an, …) represents a number N where N = (P1^a1)(P2^a2)...(Pn^an)… and Pi are the ordered primes. Clearly 1 is the zero element and would never be a basis element.
I should admit here that my background in algebra is weak and I have no idea how you would need to modify the notion of ‘vector space’ to make certain things line up. But I can already speculate on how the choice of the “scalar field” for specifying the a_i would have interesting consequences:
non-negative integer ‘scalar field’ --> the positive integers,
all integers ‘scalar field’ --> positive rational numbers,
complex integers --> finally include the negative rationals.
I’d like to read more. What sub-field of mathematics is this?
I see that we could have a ‘vector space’ of infinite-dimensional vectors where each vector (a1, a2, …, an, …) represents a number N where N = (P1^a1)(P2^a2)...(Pn^an)… and Pi are the ordered primes.
You’ve certainly convinced me that ‘1’ should not be included in the set of things that are used to uniquely factor numbers. However, how I can I know if this set is the set of “primes”?
I guess I was thinking that the essence of primes was about their irreducibility/atomic-ness. The number 5 would be considered prime because you can’t describe it multiplicatively in any way except by using the number 5. Using my preferred notion, the number 0 and the number −1 would also be “prime” (as Mr Hen guessed). Is there a different word for this concept?
See wikipedia on natural generalizations of prime numbers. In particular note that most of the definitions say “units” instead of “1″, like “Irreducible elements are ones which cannot be written as a product of two ring elements that are not units.” which rules out 0 for the integers, +, x and includes the possibility of multiple units (-1 and 1).
I don’t know offhand of any nice, commonly referenced property P(S,O) that is: A,x,y in a structure S with operation O: A is P just when if x O y = A then either x = A or y = A. Which I believe is the general property you’re thinking about?
As it happens I’m partway through “An Introduction to the Theory of Numbers” by Niven, Zuckerman, and Montgomery at the moment. Lots of problems are incredibly easy to solve given this structure. The example that springs to mind is the very straightforward proof why the combinatorial formula n! / (r! (n-r)!) always gives you an integer.
Update: Well having been scored up I feel like I should give a hint on the actual proof: for any prime p and any n, the greatest power of p that divides n is
\sigma_{i=1}^{\infty} floor( \over{n}{p^i} )
and for any real numbers a, b, floor(a + b) >= floor(a) + floor(b).
I’m enjoying it, but it touches on abstract algebra as an alternative approach rather than leaning on it for everything; I’d kind of prefer the latter.
I was wondering if there was a function f(x, y, z) so that x and z represent the left and right sides of common mathematic operators and y represents the level of operation. So f(1, 2, 4) would be 1 + 4 and f(2, 2, 4) would be 2 * 4. Better versions of f(x, y, z) would have fewer end cases hardcoded into it.
The reason behind this is to handle operator levels greater than addition, multiplication, and exponents. The casual analysis from my grade school and undergrad level math shows the pattern that multiplication is repeated addition and exponents are repeated multiplication.
My quick attempts at coming up with such a function are spiraling into greater and greater complexities. I figured someone else has to have thought about this. Do you know of a place I can start reading up on ideas similar to this? Is what I am doing even plausible?
Quick thoughts based on me playing around:
Addition may be level 0, not level 1
The sequences never really look exactly like multiplication tables, but the patterns are similar enough to appease me
Ideally, everything can be reduced to the simple concept of X + 1 so as to walk along the number line
In practical terms, I have no idea how to express “negative” levels. Division and roots are unapproachable at this point in my playing around.
Cool, thanks. It seems like one of my first tries was producing numbers similar to the Ackermann function. Knuth’s arrow notation essentially takes over after multiplication. But those two articles will give me enough to read to keep moving on. :)
Do you know of any that go the other way into smaller and smaller numbers?
EDIT: I found the right subject name through links on your links. It is called hyperoperation.
Sure, that works, but it isn’t exactly what I am looking for. Is it possible to express the division operator in a manner similar to how multiplication can be expressed using addition? My instinct is telling me probably not.
You can have inverse operations for the higher operations as well. 4^4 is 256, so you can think of 4 as the “tetrated root” of 256. Also see this
(I’m using ‘tetrating’ as a term for the operation after exponentiation: in other words, 4 tetrated to the 4th is 4^(4^(4^4))).
Two problems: there may not be a clear way to define tetrating and higher operations to fractional amounts, and exponentiation and up aren’t associative, so you need a convention for what to do with the parentheses.
Hyper operators. You can represent even bigger numbers with Conway chained arrow notation. Eliezer’s 3^^^^3 is a form of hyper operator notation, where ^ is exponentiation, ^^ is tetration, ^^^ is pentation, etc.
If you’ve ever looked into really big numbers, you’ll find info about Ackermann’s function, which is trivially convertable to hyper notation. There’s also Busy Beaver numbers, which grow faster than any computable function.
Wikipedia—the first and last authority on such things—carefully writes in an entire sentence unto itself, “The number 1 is by definition not a prime number,” suggesting just how arbitrary this is.
A measure of the arbitrariness is the history, which is that 1 was considered prime up to the 19th century and was a matter of fashion during the 19th century. That suggests that unique factorization is not, in itself, enough to motivate the definition. Perhaps its extension to the gaussian integers or the more radical version for general number rings prompted the definiton.
This reminds me. Pre-19th century it was thought that part of what it was to be a mammal was to give live birth, in addition to having mammary glands. 1 is the platypus of numbers.
natural definition: “A prime is a natural number with exactly two factors”
I’m not sure I quite understand your suggestion: we should define 1 as prime, but then write “except for 1” every time we use the word prime? Wouldn’t it be quicker just to exclude 1 in the first place (even if there were some sense in which 1 was prime)?
A factor of a number M is a number that evenly divides M with no remainder. Zero has infinitely many factors, definitely not prime.
...regarding −1, I can’t think of anything relevant that I know about the relationship between negative numbers and prime numbers.
Later edit: Then I completely changed my mind… and decided 0 and −1 should be prime relative to how I would define it’s essence. I note that you intuited what I really meant by prime better than I did!
I have a fondness for this particular definition, and like to think of 1 as a “very special” prime number. To the extent that I usually give a little speech whenever an opportunity arises that (ahem) the only reason I know of that ‘1’ is excluded from the primes (more often than not) is because almost every theorem about prime numbers would have to be modified with an “except 1″ clause. But a natural definition (anything along the lines of “already completely factored”) would include it. If you disagree, which definition—or the satisfaction of which theorem—do you think is more compelling?
(Just in case you perceived you were getting too much heat about “colour”...)
I’d have to pretty strongly disagree. To me, the “essence” of primes is that you can factor any number into primes in a unique way. That’s the most natural definition. They’re the multiplicative building blocks of the natural numbers; everything can be reduced to them. If 1 were prime, you could no longer factor uniquely.
Your comment and this comment were adjacent in my message folder which I found amusing.
Thomblake wrote:
It’s funny how we do care.
That’s awesome. Thanks for sharing.
Possibly related: my comment about paperclips.
Hmm… I agree this is compelling. However, since I’m resistant to updating my world view about 1-the-discriminated-prime-number, I’ll continue to proffer counter-arguments:
the Fundamental Theorem of Arithmetic is pretty important, but may still not be the “essence” of what prime is
the FTA itself requires the “except 1” clause: “all natural numbers can be uniquely factored into primes except 1″ -- which would make someone thing 1 ought to be prime
the FTA already assumes ‘modulo permutations’, we could easily throw in ‘modulo 1’
Wikipedia—the first and last authority on such things—carefully writes in an entire sentence unto itself, “The number 1 is by definition not a prime number,” suggesting just how arbitrary this is. (My own emphasis added.)
The best argument I came up with for not including 1 as prime, because I tend to worry about how things are constructed, was with the seive of Eratosthenes.
The seive of Eratosthenes says that you can find the primes by starting with all the natural numbers > 1; let 2 be the first prime number, and then begin eliminating all multiples of 2 and the multiples of subsequent primes as you find them. If you included ‘1’ in the first step, then you would eliminate all the numbers in the first step.
I think you’re really failing to grasp the content of the unique factorization theorem here. Firstly we don’t think about factored numbers as products of primes up to permutation, we think of them as products of distinct prime powers (up to permutation, I suppose—but it’s probably better here to just take a commutative viewpoint and not regard “up to permutation” as worth specifying). But more importantly, you need to take a multiary view of multiplication here, not a binary one. 1 is the empty product, so in particular, it is the product of no primes, or the product of each prime to the 0th power. That is its unique prime factorization. To take 1 as a prime would be like having bases for vector spaces include 0. Almost exactly like it—if we take the Z-module of positive rationals under multiplication, the set of primes forms a free basis; 1 is the zero element.
Information and expertise like this is why hanging out at Less Wrong is worth the time. I estimate that I value the information in your comment at about $35, meaning my present self would advise my former self to pay up to $35 to read it.
So, I get it. My brain is more wired for analysis than algebra; so this isn’t the first time that linear algebra has been a useful bridge for me. I see that we could have a ‘vector space’ of infinite-dimensional vectors where each vector (a1, a2, …, an, …) represents a number N where N = (P1^a1)(P2^a2)...(Pn^an)… and Pi are the ordered primes. Clearly 1 is the zero element and would never be a basis element.
I should admit here that my background in algebra is weak and I have no idea how you would need to modify the notion of ‘vector space’ to make certain things line up. But I can already speculate on how the choice of the “scalar field” for specifying the a_i would have interesting consequences:
non-negative integer ‘scalar field’ --> the positive integers,
all integers ‘scalar field’ --> positive rational numbers,
complex integers --> finally include the negative rationals.
I’d like to read more. What sub-field of mathematics is this?
Oh! And orthogonal vectors are relatively prime!
I’m not sure that the idea of orthogonality is defined for modules, is it? Is there a standard definition of an inner product for a Z-module?
Yes; the same definition works. See here.
Yay! I actually got something right!
Number theory, ne? Or is that too general?
It looks like it’s more abstract algebra (possibly applied to number theory) that byrnema is interested in. Check out Wikipedia on module.)
Precisely! Thanks also.
A second comment...
You’ve certainly convinced me that ‘1’ should not be included in the set of things that are used to uniquely factor numbers. However, how I can I know if this set is the set of “primes”?
I guess I was thinking that the essence of primes was about their irreducibility/atomic-ness. The number 5 would be considered prime because you can’t describe it multiplicatively in any way except by using the number 5. Using my preferred notion, the number 0 and the number −1 would also be “prime” (as Mr Hen guessed). Is there a different word for this concept?
See wikipedia on natural generalizations of prime numbers. In particular note that most of the definitions say “units” instead of “1″, like “Irreducible elements are ones which cannot be written as a product of two ring elements that are not units.” which rules out 0 for the integers, +, x and includes the possibility of multiple units (-1 and 1).
I don’t know offhand of any nice, commonly referenced property P(S,O) that is: A,x,y in a structure S with operation O: A is P just when if x O y = A then either x = A or y = A. Which I believe is the general property you’re thinking about?
Edit: with O commutative I do believe
Thank you. And yes, that is the property.
For some reason, I never imagined factors this way.
18 = 3^2 2^1
97,020 = 2^2 3^2 5 7^2 * 11
I suppose I have seen them printed out that way, but the deeper structure there never clicked. Cool.
As it happens I’m partway through “An Introduction to the Theory of Numbers” by Niven, Zuckerman, and Montgomery at the moment. Lots of problems are incredibly easy to solve given this structure. The example that springs to mind is the very straightforward proof why the combinatorial formula n! / (r! (n-r)!) always gives you an integer.
Update: Well having been scored up I feel like I should give a hint on the actual proof: for any prime p and any n, the greatest power of p that divides n is
\sigma_{i=1}^{\infty} floor( \over{n}{p^i} )
and for any real numbers a, b, floor(a + b) >= floor(a) + floor(b).
Oh for real TeX markup!
Do you recommend the book? If I were interested in the subject, is this good to pick up or can you think of a better option?
I’m enjoying it, but it touches on abstract algebra as an alternative approach rather than leaning on it for everything; I’d kind of prefer the latter.
You may be a good person to ask this question:
I was wondering if there was a function f(x, y, z) so that x and z represent the left and right sides of common mathematic operators and y represents the level of operation. So f(1, 2, 4) would be 1 + 4 and f(2, 2, 4) would be 2 * 4. Better versions of f(x, y, z) would have fewer end cases hardcoded into it.
The reason behind this is to handle operator levels greater than addition, multiplication, and exponents. The casual analysis from my grade school and undergrad level math shows the pattern that multiplication is repeated addition and exponents are repeated multiplication.
My quick attempts at coming up with such a function are spiraling into greater and greater complexities. I figured someone else has to have thought about this. Do you know of a place I can start reading up on ideas similar to this? Is what I am doing even plausible?
Quick thoughts based on me playing around:
Addition may be level 0, not level 1
The sequences never really look exactly like multiplication tables, but the patterns are similar enough to appease me
Ideally, everything can be reduced to the simple concept of X + 1 so as to walk along the number line
In practical terms, I have no idea how to express “negative” levels. Division and roots are unapproachable at this point in my playing around.
Ackermann function
Knuth’s arrow notation
Cool, thanks. It seems like one of my first tries was producing numbers similar to the Ackermann function. Knuth’s arrow notation essentially takes over after multiplication. But those two articles will give me enough to read to keep moving on. :)
Do you know of any that go the other way into smaller and smaller numbers?
EDIT: I found the right subject name through links on your links. It is called hyperoperation.
1 / Ackermann function.
Sure, that works, but it isn’t exactly what I am looking for. Is it possible to express the division operator in a manner similar to how multiplication can be expressed using addition? My instinct is telling me probably not.
You can have inverse operations for the higher operations as well. 4^4 is 256, so you can think of 4 as the “tetrated root” of 256. Also see this
(I’m using ‘tetrating’ as a term for the operation after exponentiation: in other words, 4 tetrated to the 4th is 4^(4^(4^4))).
Two problems: there may not be a clear way to define tetrating and higher operations to fractional amounts, and exponentiation and up aren’t associative, so you need a convention for what to do with the parentheses.
Hyper operators. You can represent even bigger numbers with Conway chained arrow notation. Eliezer’s 3^^^^3 is a form of hyper operator notation, where ^ is exponentiation, ^^ is tetration, ^^^ is pentation, etc.
If you’ve ever looked into really big numbers, you’ll find info about Ackermann’s function, which is trivially convertable to hyper notation. There’s also Busy Beaver numbers, which grow faster than any computable function.
Yes, this is exactly what I was looking for. Thank you.
A measure of the arbitrariness is the history, which is that 1 was considered prime up to the 19th century and was a matter of fashion during the 19th century. That suggests that unique factorization is not, in itself, enough to motivate the definition. Perhaps its extension to the gaussian integers or the more radical version for general number rings prompted the definiton.
This reminds me. Pre-19th century it was thought that part of what it was to be a mammal was to give live birth, in addition to having mammary glands. 1 is the platypus of numbers.
natural definition: “A prime is a natural number with exactly two factors”
I’m not sure I quite understand your suggestion: we should define 1 as prime, but then write “except for 1” every time we use the word prime? Wouldn’t it be quicker just to exclude 1 in the first place (even if there were some sense in which 1 was prime)?
How do you see 0 or −1, using this definition?
A factor of a number M is a number that evenly divides M with no remainder. Zero has infinitely many factors, definitely not prime.
...regarding −1, I can’t think of anything relevant that I know about the relationship between negative numbers and prime numbers.
Later edit: Then I completely changed my mind… and decided 0 and −1 should be prime relative to how I would define it’s essence. I note that you intuited what I really meant by prime better than I did!
Yeah, I was just curious. I like toying around with the fundamentals behind the maths and seeing what happens. :)