Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Landmark math proof clears hurdle in top Erdős conjecture

quantamagazine.org

Post reply on HN
Print view View original

21–30 of 46 posts

Re: Landmark math proof clears hurdle in top Erdős conjecture

#21

Post by notafraudster »

ColinWright wrote: post #18
Ar-Curunir wrote: post #15

Earlier quoted context omitted.

Hmm is there an asymptotic statement underlying this? The powers of 2 are exponentially sparse (N integers contain at most 1/logN powers of 2), whereas primes are polynomially sparse (N integers contains N/LogN primes)

I was trying to give people a sense of the statement, giving two examples of "not very dense" and "dense enough", but I don't understand what you're trying to say here. I can't work out whether you are asking a question, or making a conjecture, or ... what. Would you care to clarify? If it's a question then I'll try to answer, but if it's a conjecture, can you make it more precise?

He is asking "what is the line between too sparse and not too sparse" and attempting to characterize the example you gave of each in terms of approximate relative sparsity.

Re: Landmark math proof clears hurdle in top Erdős conjecture

#22

Post by robin_reala »

maxov wrote: post #5
jstanley wrote: post #4

Earlier quoted context omitted.

> The conjecture by Erdős is the following: if A ⊂ ℕ is such that Σ_{n ∈ A} 1/n diverges, then A contains arbitrarily long arithmetic progressions This is quite hard to understand for people who don't already know what it means (including me). I started trying to translate it but there were a few parts I didn't understand, starting with: 1.) Is ℕ integers >0 or >=0? Wikipedia says it can be either. Maybe it doesn't m…

Dense math can often be complex to decipher. Sometimes it feels like reading an esoteric codebase to me! 1) Yes in this case 0 is not included in N. I’ve seen N defined both ways depending on the context, so it can be confusing when it’s not given explicitly. 2) By definition, a series sum is based on the limit of partial prefix sums. E.g 1/a_1, 1/a_1+1/a_2, ... It is an interesting question mathematically, if the su…

A dense APL codebase at that.

Re: Landmark math proof clears hurdle in top Erdős conjecture

#23

Post by ColinWright »

notafraudster wrote: post #21
ColinWright wrote: post #18

Earlier quoted context omitted.

I was trying to give people a sense of the statement, giving two examples of "not very dense" and "dense enough", but I don't understand what you're trying to say here. I can't work out whether you are asking a question, or making a conjecture, or ... what. Would you care to clarify? If it's a question then I'll try to answer, but if it's a conjecture, can you make it more precise?

He is asking "what is the line between too sparse and not too sparse" and attempting to characterize the example you gave of each in terms of approximate relative sparsity.

Right ... understood.

I don't have an answer, it's not my area, but it does feel a lot like the condition "sum(1/n) diverges" is likely to be close, but that's just a gut feeling.

Re: Landmark math proof clears hurdle in top Erdős conjecture

#24

Post by gigatexal »

ColinWright wrote: post #3
y7 wrote: post #2

The conjecture by Erdős is the following: if A ⊂ ℕ is such that Σ_{n ∈ A} 1/n diverges, then A contains arbitrarily long arithmetic progressions. Bloom and Sisask now proved that A contains infinitely many length-3 arithmetic progressions, following from their main result which is an improved upper bound for Roth's theorem. https://arxiv.org/abs/2007.03528

And just to expand a smidgen on that, the maths expression: A ⊂ ℕ is such that Σ_{n ∈ A} 1/n diverges is one way of saying that the set A of integers is not too sparse. The set of powers of 2 does not satisfy this condition ... it's too sparse. The set of primes does satisfy this condition ... it's not too sparse, primes turn up "reasonably often".

Can you dumb it down a bit more using more English than symbols? My math skills are not the greatest but I am keen to hear more.

Re: Landmark math proof clears hurdle in top Erdős conjecture

#25

Post by RaptorJ »

notafraudster wrote: post #21
ColinWright wrote: post #18

Earlier quoted context omitted.

I was trying to give people a sense of the statement, giving two examples of "not very dense" and "dense enough", but I don't understand what you're trying to say here. I can't work out whether you are asking a question, or making a conjecture, or ... what. Would you care to clarify? If it's a question then I'll try to answer, but if it's a conjecture, can you make it more precise?

He is asking "what is the line between too sparse and not too sparse" and attempting to characterize the example you gave of each in terms of approximate relative sparsity.

Ah well there isn't one, from any divergent series you can construct a more slowly growing (but still divergent) series.

Re: Landmark math proof clears hurdle in top Erdős conjecture

#27

Post by ColinWright »

gigatexal wrote: post #24
ColinWright wrote: post #3

Earlier quoted context omitted.

And just to expand a smidgen on that, the maths expression: A ⊂ ℕ is such that Σ_{n ∈ A} 1/n diverges is one way of saying that the set A of integers is not too sparse. The set of powers of 2 does not satisfy this condition ... it's too sparse. The set of primes does satisfy this condition ... it's not too sparse, primes turn up "reasonably often".

Can you dumb it down a bit more using more English than symbols? My math skills are not the greatest but I am keen to hear more.

OK, let's have a go.

We are looking for set of three numbers that are "equally spaced". So {4, 7, 10} are equally spaced, differing by 3 each time. Another set might be {20, 30, 40}, this time differing by 10. We'll call such a set "Equally Spaced Triples", or "EST" for short.

If you have the positive even integers - 2, 4, 6, 8, ... - then clearly you can find infinitely many ESTs. You have {2,4,6}, {6,10,14}, and so on. However, we can show that if you take the powers of 2 - 1, 2, 4, 8, 16, 32, 64, ... - then we cannot find an EST.

So, when can we do this? When can we be guaranteed always to find infinitely many ESTs? Suppose you have a set of numbers - n0, n1, n2, n3, n4, ... - is there a test to see if we are guaranteed to have infinitely many ESTs?

The answer is yes, and that's the result that has been proved. The result says this:

Take any set of positive integers, take their inverses, and add them all together. If the result has an upper bound, then the set might not have infintely many ESTs. However, if the sum grows without bound, then you are guaranteed to have infinitely many ESTs.

Unpacking that with our examples, taking the inverses of the powers of two and adding them up we get 1/1 + 1/2 + 1/4 + 1/8 + 1/16 + ... and we can show that the total never exceeds 2. In fact, the total never reaches 2. So since the total is bounded, we do not have infinitely many ESTs.

Now look at the primes. There is a standard result that says that the sum 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + 1/13 + 1/17 + ... is unbounded above. You give me a desired total, and I can tell you how many terms you need to take to exceed that number. So the sum of the inverses is unbounded, and hence the primes will have infinitely many ESTs.

So, in summary, if a set of positive integers is dense enough - if there are enough of them in some technical sense - then there are infinitely many ESTs. The test for density is to ask that the sum of the reciprocals (inverses) is unbounded.

Does that help?

Edit: I wanted to contact you out-of-band, but you only have a LinkedIn link in your profile, and I don't use LinkedIn. If you're interested in discussing this further then I'd be happy to help, but better by email. My contact details are in my profile.

Edit 2: Thank you everyone for your kind comments. You've made me think about my write-ups. I already do a lot of writing ... I might re-visit what and how. I appreciate the kind words.

Re: Landmark math proof clears hurdle in top Erdős conjecture

#28

Post by submeta »

ColinWright wrote: post #27
gigatexal wrote: post #24

Earlier quoted context omitted.

Can you dumb it down a bit more using more English than symbols? My math skills are not the greatest but I am keen to hear more.

OK, let's have a go. We are looking for set of three numbers that are "equally spaced". So {4, 7, 10} are equally spaced, differing by 3 each time. Another set might be {20, 30, 40}, this time differing by 10. We'll call such a set "Equally Spaced Triples", or "EST" for short. If you have the positive even integers - 2, 4, 6, 8, ... - then clearly you can find infinitely many ESTs. You have {2,4,6}, {6,10,14}, and so…

That is a brilliant explanation for non-mathematicians. Thank you very much.

Re: Landmark math proof clears hurdle in top Erdős conjecture

#29

Post by renaicirc »

imglorp wrote: post #14
dmch-1 wrote: post #11

I find the existence of number theoretic problems quite puzzling. I wonder what are the implications about the world we can make from them.

Math is the formal study of patterns. The universe is built on patterns. The universe is beautiful. Math is beautiful. Maybe we don't know today if there's an application, but notice that proof mentioned using Fourier Transforms to study a set, the same way you might use it to study a radio signal. There was probably a time when people asked what use is FT?

Good point, but bad example. Fourier developed his transform for the sole purpose of attacking the heat equation, which is definitely quite a physically important problem!

Re: Landmark math proof clears hurdle in top Erdős conjecture

#30

Post by renaicirc »

raincom wrote: post #17
dmch-1 wrote: post #11

I find the existence of number theoretic problems quite puzzling. I wonder what are the implications about the world we can make from them.

Aha, it’s an ontological question. Most mathematicians believe that numbers, sets, etc don’t exist in the world we live in, but exist in a special world called “Platonic world”. That’s what Platonism in philosophy of mathematics is about.

I strongly doubt that "most" mathematicians are Platonists.
Post reply on HN