Skip to main content
Loading Explore guides…
Erdős Primitive Set Conjecture · Acedra
Home
Explore
Mathematics
Erdős Primitive Set Conjecture
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
54 segments
Copy
Hide video
0:00
So there's this conjecture due to Paul Erdős, one of the great mathematicians of the 20th century, he's uh, like everyone, interested in the prime numbers and posed a very uh beautiful conjecture to do with primitive sets; this conjecture is now a full theorem. - (Brady: Why is it a full theorem? It's because) (of you!) - Yeah, yeah I recently proved it. Before we get into primitive sets I just wanted to start with a nice quote of Gauss that I always love:
0:24
'Mathematics is the queen of the sciences and number theory is the queen of mathematics'. Let me see if an analogy will hit with you: we have the queen here in England I guess, and her majesty has the crown jewels right? There are these beautiful diamonds; number theory is the queen of mathematics, then I would say that the primes kind of are these kind of precious diamonds, these glistening and beautiful objects. If uh the queen has a whole horde a whole hoard of crown
0:51
jewels like what would be the the full collection of jewels in this analogy with number theory? And my proposal is that this would be the class of primitive sets. We say a set is primitive if it satisfies a certain property, and the collection of all such sets are the primitive sets; but a good thing to keep in mind is that for example with a prime number, that is a property of a number - so it, a number is prime if it has no uh factors uh other than one and itself - so
1:17
this is a property about numbers. And by contrast primitive sets are properties about sets or properties about collections of numbers, so it has less to do with an individual number but rather kind of the whole family, and so this is maybe where this uh analogy is coming in of looking at like the whole uh hoard of crown jewels. - (So are all the even numbers a set?) Yes, the set of even numbers, odd numbers, numbers that have no sevens in them, the squares, the cubes
1:43
etcetera. This is maybe one level of abstraction away where instead of looking at numbers individually we're interested in collections and looking at the properties that these collections may satisfy. Let's start with a definition, so we'll say that a set s is primitive if
1:59
no number in s is divisible or divides any other. So that's just saying that if we have two numbers in our set that are different, say a and b, that means the ratio a over b and b over a are never a whole number. - (So if 4 and 2 are in the set, the set is not primitive?) - Right right because 4 is a multiple of 2 - or 2 divides 4. - (I'm imagining there are a lot of primitive sets.) (I'm imagining there are an infinite number of primitive sets!)
2:23
- Yeah I mean this is- so so one of the things we like about prime numbers is that the definition is very basic and kind of- so the primes are like the basic building blocks of arithmetic because you can build all the numbers kind of in a unique way out of the primes. And similarly if you're now instead of looking at individual numbers and you're looking at sets of numbers, a primitive set- so this definition is almost the simplest you can kind of come up with in the same spirit.
2:46
- (All the prime numbers is an example of a primitive set.) Yeah right exactly, so- - (Is that the only set that has an infinite number of members?) Oh no, that's a good question; so let's look at some examples. So let's consider the set of numbers 4, 6, 9, 10, 15 etc. So these are going to be the numbers with two prime factors and here- - (Two and only two?) Yeah exactly two. With- so for example with 4 we have a 2 and a 2 so if the same prime
3:14
occurs twice we still count it as being in the set. So you know you have 2 times 2, 2 times 3, 3 times 3, 2 times 5, 3 times 5 etc; and so this is an infinite set of numbers and I'm claiming that no number will divide any other. Take the number 10 right? So 10 is 2 times 5. The divisors of 10 are therefore 1, 2, 5 and itself, so we'll ignore the number itself, but we see the kind of list of all divisors of 10 are not falling in any of this list,
3:41
so this will have, you know, no prime factors, one prime factor, one prime factor. And more generally if you take any number, let's say p times q, so any any number in this set is going to be exactly the form p times q where p and q are primes and q might equal p but it may not, but if we play the same game the divisors of p times q are 1, p, q and then p times q itself. But we see in particular if you have two numbers with two prime factors you're never going
4:07
to get one lying in the list of the other. So so in general if a number has k prime factors then all its its divisors will have fewer prime factors, so fewer than k, and all of its multiples will have more than k prime factors. We've produced another family so example two: for any k the set of numbers with k prime factors is primitive. - (So all the numbers) (with three prime factors, all the numbers with-) - Exactly yeah. - (Why are they called primitive? Because)
4:32
(obviously they don't have to be prime numbers.) - Primitive is also kind of the idea of uh like a basic building block. At the end of the day these are just English words that have been kind of chosen but this is meant to convey some idea of these being a very simple definition that's containing some of the basic structure. We have these nice examples of just the primes themselves, we have numbers with two prime factors, three prime factors, four prime factors - for any
4:56
your favorite k - and these are kind of building some intuition for what these primitive sets are. But in general the definition of a primitive is very uh simple and so it emits a very broad class of sets. Paul Erdős was interested in these sets and he proved the following result: 1935 Erdős showed that there is a constant c such that for any primitive set, let's say s, the sum of 1 over n log n for n ranging in your set is at most this constant c for any primitive set s.
5:28
(What does that mean?) - This is saying that we have a series that converges. In other words for any set you throw at me I'll spit back at you a number; particularly this conversion series. We've come up with a rule that assigns every set a number, the claim- - (Like a unique number?) Yeah, so this is this is going to be a unique series. So for example with the primes we already knew about
5:47
the primes in particular, we knew that the series- so this is going to be 1 over p log p which is nothing more than the sum of 1 over 2 log 2, plus 1 over 3 log 3, plus 1 over 5 log 5,
6:03
plus 1 over 7 log 7...So this is an infinite series, one term for every prime and the claim is that this is finite. So if you kind of ran some uh computations on Mathematica for example, this comes out to a number that's about 1.6366. - (So are you telling me every set has like) (almost like a fingerprint?) - Yeah exactly, so it's like a way to reduce the complexity of a very uh jumbled uh object and just come out spit out just a simple number to
6:31
yeah to kind of gauge the the size of the set. - (Can you reverse engineer that too? If I gave you the c could you tell me) (what the set is?) - Not necessarily. So it's not- it's not an exact DNA match. By contrast, the sum of all numbers, 1 over n log n, over all numbers or between 1 and infinity - so this is just - okay so let's let's ignore 1 because uh that'll get us problems already. But even just starting at 2 or any finite place,
6:59
3 log 3 - so so far we're starting off the same but now we're going to include 4, plus 5 log 5, but 6 log 6 etc. This actually diverges and goes to infinity. So Erdős is telling us that for primitive sets, that we have this nice sum that gives us information about the size of the set, but in general for most sets uh this sum will diverge and then kind of uh give us junk that we don't know how to handle. - (So we've got all these these)
7:23
(numbers that- these constants, these numbers that can be attached to various sets) - Yeah, so this is a way of kind of assigning an index number to every set and one should have the intuition is that this is saying something about the size of a set. So the Erdős primitive set conjecture says that in the theorem we can take c to be the sum of primes. So that is to say, for any primitive set, this sum of 1 over n log n, for n ranging in your set, is at most
7:52
this sum over primes, 1 over p log p. So that's just 1 over 2 log 2, plus 1 over 3 log 3, 1 over 5 log 5... - (That 1.63-)
8:01
Yeah and it comes out, and this comes out to a finite number, 1.6366. So the conjecture is that every sum for primitive- uh over a primitive set is at most about 1.6. (Okay and so there's no primitive set you could create that would have one of those fingerprint) (numbers above 1.6366) - Right exactly, this is the upper limit, you can't do any better by being as clever as you want, this is this is as good as it gets.
8:28
And so another way of kind of thinking about this conjecture and the reason why I particularly think it's a very beautiful conjecture is that even though primitive sets are very- so the definition of a primitive set is very simple, so there could be all these chaotic sets satisfying the simple condition, and nevertheless there's this nice condition saying in some sense that this kind of measure
8:51
of complexity is being maximized by the primes. In other words that the primes are the largest primitive set among all primitive sets as measured by this uh uh nice statistic. (That kind of like- I can feel why intuitively that would be true, it would like it would feel right) (that all the primes is the king of primitive sets.) - Yeah so so that's- I mean uh for those kind of who who love the channel, I mean, in our hearts we we all feel that the primes are
9:18
special and it's hard it's sometimes hard to articulate why uh we we love something but at least in this conjecture Erdős is giving us one particular way of articulating uh in a quantitative rigorous way why the primes are special, at least in kind of the broader context of its family of larger sets. So to go back to this analogy, we are saying that kind of the primitive sets are the diamonds uh that are kind of the- you know,
9:45
if you go if you go to a jeweller and get them appraised the diamonds will always fetch the the most sum as compared to the emeralds of the rubies and the sapphires. They're also going to perhaps be very valuable, but this is giving us some consolation in our hearts that these are really the the most brilliant jewels. - (That analogy falls down because) (rubies are often worth more than diamonds but-) - Oh, okay. That tells you that tells you how
10:06
much I know about uh jewellery. - (Okay, so I guess the reason it may not have been the case is because you showed) (me that non-prime numbers can be in primitive sets. So you can imagine a world where you) (could have built some pretty impressive primitive sets, but you'll never get one- you'll never get) (one as good.) - Yeah, that's the point. And so uh this was a beautiful conjecture that Erdős and others had worked on in the 90s and there wasn't really much
10:28
progress; so when I heard this problem back in my undergraduate I was just- absolutely fell in love with the problem because it's saying that these primes are very special uh in a precise way, but I never really expected to- This- this question is like one of those uh kind of dreams you have in the back of your mind that, oh it wouldn't be great if uh something like this were true and I just uh never kind of uh really gave up on the problem. - (This was your Fermat's last
10:52
theorem was it?) You could say that, uh I just I just found this uh such a beautiful uh statement. - (What did you do? What did you see? What did you think of that no one else had thought of?) Okay so the first thing to say is that this is now a theorem, so uh so this is in 2022:
11:12
the Erdős primitive set conjecture. - (Don't you get your name on it now?) - Uh I guess if if you - (Shouldn't be the Lichtman primitive set conjecture?) - If you say so? I don't know, I feel that uh it's it's not necessarily my place to call it that but if if you want to say I won't uh I won't uh uh argue with that. - (What's the key? I mean I'm imagining it might be a bit more advanced than I) (can understand but-) - Yeah so it really goes back
11:42
to ideas of Erdős back in the 1930s. So he had proved that for any primitive set you throw at me, I'll spit back a sum that'll converge. And the ideas that Erdős really developed back in the 1930s turned out to be quite relevant to proving the full conjecture. I should say that the later work that Erdős did was in a very different direction so it was not at all clear that this- these ideas were relevant. But essentially uh what I was doing was essentially looking at
12:08
the the proposal that Erdős had, and a beautiful argument that kind of reinterpreted what this uh series is in a more uh probabilistic way, and kind of gave some more probability interpretation for for these sets to really give the idea that this series is measuring the size. There are a few key ingredients in this argument that are a little bit inefficient, and by identifying these steps and kind of tuning them up and tightening the screws and putting some oil
12:37
it turns out that Erdős' ideas could really be continued a lot further than initially thought. - (So in your proof did you sort of think, gosh Erdős you were so close to doing) (it yourself. Did he- did he did not quite see it?) - Yeah I mean, I also had been thinking about other ideas uh that he had gone off and done so I really came to this uh his original argument much later and uh it was a quite surprising to me that these sort of ideas uh could be relevant um but it
13:07
was it was a really uh a really beautiful moment. - (Where's- has your proof been published) (yet or what happens now?) - The first step in letting other- your your friends and other mathematicians know is you upload uh your proof to the archive and then there's a more formal process of getting it kind of submitted to a journal and getting it reviewed meticulously, but I had also kind of shared my proof with my advisor and other
13:28
people to kind of make sure that I wasn't thinking wrongheadedly about some things. - (What did your advisor say when you when you sent it through?) So uh he actually didn't know I was working on this problem so uh I kind of half was thinking that he'd be angry at me for not working on the problem that he'd set for me, and this was like something I'd been doing by candlelight at night surreptitiously. But so I'd let him know back in
13:48
uh this winter that I'd solved the- or I'd come up with this proof and he uh so he he took time over several months to look at it and kind of vet all the steps there, you know, dot all the i's and uh cross all the t's, uh but he he was uh also very uh happy for me and I was it was it was just a very nice moment. A natural question to ask is, so if you're interested in primitive sets but
14:13
you're throwing away the primes now; suppose your- all the numbers in your set will be composite.
14:18
Then you can ask a similar question, so we know that there's still some upper bound but if we're looking at fewer sets then these uh series could be even smaller. So the question is, if you're looking at primitive sets of composite numbers, what is the largest the sum can be? Do you- do you have? - (I'm going to guess that number over 2.)
14:43
(No, I don't know. Half that number? Or is it is it vanishingly close to that number?)
14:50
That's actually a good question and that relates to some of the ideas that I'd been thinking about uh in the course of the proof. - (Has that number got a name, that like that upper bound?)
15:00
So this is just one of these uh so so they're- - (How about the Lichtman constant?)
15:08
I won't argue with you there. So this particular sum over primes- so there are many uh sums, you know, uh for example uh there's a famous sum 1 over p squared which uh may be familiar to some uh fans of the channel. This also converges, converges actually quite a bit faster than the series, but yeah so it turns out that this sum converges but just barely. The the conjecture is that if you're looking at all primitive sets,
15:34
the primes are maximizing. But if you throw out the primes, the numbers with two prime factors is conjecturally the largest within this restricted family of composite numbers. And more generally - so this is also one example of a much broader conjecture which says if you're looking at numbers with at least k prime factors, for any k, that are primitive, this should be maximized by the set of numbers with exactly k prime factors.
16:01
- (The one with two prime factors that you tell me is the next) (biggest after the primes-) - Yeah, this this is an open problem. We don't know, this is the conjecture, this is a conjecture that's been put forward. - (What is- what is the fingerprint) (number for the the two prime factors?) - If you look at- so this is - (I'm calling it the) (fingerprint number.) - Yeah the fingerprint numbers, after fingerprint. Usually we denote by P as the set of primes,
16:24
and if you just look at the set, let's say p to the 2 power, this will be the set of number of two prime factors. So this is a sum, this will be 1 over 4 log 4 plus 1 over 6 log 6 etc and you can kind of play this game where you increase the exponent and these numbers get smaller and smaller. One of the aspects of this conjecture is that you'd want uh every step that you increase k you'd want this corresponding fingerprint number to go down. And so you'd have
16:51
this kind of chain of inequalities saying that the primes are the largest, the numbers with two prime factors are the second largest, numbers of three prime factors. And so this is in some sense going back to your comment earlier about trying to uh recover some structure within this very chaotic class of primitive sets and just kind of carve out some nice decomposition in some kind of prime way that we've seen before. - (So if I had all of the numbers
17:19
with two prime factors in a set,)
17:23
(is it impossible I could throw one extra number into that bowl? Or would that break-) (That would break the set's primitiveness would it?) - Yeah yeah, so so so- - (Because- because) (then I could upp my fingerprint number if I could find another number.) - Right exactly. So so let's let's take your example. So if we have- we're starting with the numbers with just two prime factors and you want to throw in another number.
17:41
So that number is either going to be 1, which will divide all numbers, it'll be either a prime which will divide, or it'll have at least three prime factors. But so let's say this number is p times q times r, you throw away any prime of these and then you'll have a number with two prime factors, but that's already in our list. So the set of numbers with two prime factors can't be increased anymore while still being primitive; so this is sometimes known
18:07
as a maximum- maximal primitive set. So you can't increase it anymore artificially. More generally, and for any k the set of numbers with exactly k prime factors is going to be maximal in the way that you can't increase the set anymore. And you can just see this by trying to uh throw a number that either has fewer than k prime factors - and so in particular will divide a number on our list -
18:30
or it will have more than k prime factors and it will be a multiple of a number in our list. So that- that that really shows that these are maximal. But so in particular for this conjecture, I've lied to a little bit Brady. So it turns out these numbers with exactly k prime factors are a very special class of primitive sets and the set of all primitive sets is much larger. So this is- this is the hope that you can have this kind of nice way of saying something about
18:55
a very large class, but it turns out if you uh plug these uh numbers in for for larger k, it turns out that after k goes past 6 the numbers start increasing again.
19:09
So- - (The fingerprint numbers? The fingerprint numbers start to go down from 1, 2, 3, 4, 5, 6 and then at 6 they seem to go up again. But it's actually also a theorem due to myself that these numbers tend to 1 as k goes to infinity. So they're really wedged in this thin strip. There may be some other kind of super exotic set with uh- of composite numbers that conjecturally could pass this threshold but
19:33
we believe that this is the best case. So what I just described with k equal 6 being the minimum is actually breaking the original conjecture of Banks and Martin but there's a way of slightly tweaking their conjecture by getting rid of even numbers that can conjecturally recover uh this nice picture. So if you're looking at primitive sets of odd numbers then there is still a glimmer of hope that we can get a nice decomposition into odd primitive sets this way.
20:02
...these numbers. So by introducing this kind of seemingly abstract definition his work introduced this definition and really opened up this field and today we know kind of the statistic...
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat