Landmark math proof clears hurdle in top Erdős conjecture • Hacker News Board

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

#31

Post by gigatexal » Sun, Aug 16, 2020, 5:26 PM UTC

submeta wrote: post #28

ColinWright wrote: post #27

Earlier quoted context omitted.

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.

Yes agreed! Thank you!!!

Also updated my profile

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

#32

Post by peterlk » Sun, Aug 16, 2020, 5:27 PM UTC

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…

Thank you very much for this comment

I would like you to know that I would gladly pay a monthly fee to have at least 1 proof (per month) explained to me like this. Not sure how that could scale to varying knowledge levels, but I would love to have a slow educational drip of math explanations.

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

#33

Post by submeta » Sun, Aug 16, 2020, 5:31 PM UTC

peterlk wrote: post #32

ColinWright wrote: post #27

Earlier quoted context omitted.

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…

Thank you very much for this comment I would like you to know that I would gladly pay a monthly fee to have at least 1 proof (per month) explained to me like this. Not sure how that could scale to varying knowledge levels, but I would love to have a slow educational drip of math explanations.

+1 re paying for explanations like this

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

#34

Post by marai2 » Sun, Aug 16, 2020, 5:31 PM UTC

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…

Yes, wonderful exposition. Thank you for taking the time to explain this. For what it's worth I for one have learned something this Sunday morning when all I was doing was lazily browsing HN. This is why we come to HN, and it's contributions like yours that make this valuable!

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

#35

Post by gigatexal » Sun, Aug 16, 2020, 5:32 PM UTC

peterlk wrote: post #32

ColinWright wrote: post #27

Earlier quoted context omitted.

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…

Thank you very much for this comment I would like you to know that I would gladly pay a monthly fee to have at least 1 proof (per month) explained to me like this. Not sure how that could scale to varying knowledge levels, but I would love to have a slow educational drip of math explanations.

Agreed. I know it’s not as useful to not be able to fully use the math with the notation and the vocab and the logic and theorems behind it but as a fan of the field I too would love it.

Even a podcast would be awesome.

Have you subscribed to sixty symbols on YouTube or other math related channels? I find that helpful.

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

#36

Post by Certhas » Sun, Aug 16, 2020, 5:49 PM UTC

Ar-Curunir wrote: post #15

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

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)

So let's look at n^m. The condition is sum_n n^-m ; and that diverges for m smaller or equal 1.

If you have a sequence that grows asymptotically like n^m it means that f(n)/n^m goes to a constant asymptotically. So the question is if this implies that sum 1/f(n) converges. I feel intuitively that it should be possible to prove that.

A sketch: For every epsilon there is an N such that |1/f(n) - 1/C n^-m| N. So if we take the difference between the reciprocal partial sums, then that is bounded by eps * the partial sum. That is finite exactly if the reciprocal sums converge. Thus the convergence behaviour is the same for this case...

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

#37

Post by c1ccccc1 » Sun, Aug 16, 2020, 5:53 PM UTC

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…

Nice explanation. Another interesting point is that in some cases there may be infinitely many ESTs, even if the sum is finite. For example, if we take the set {2^n}U{3*2^n}.

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

#38

Post by ColinWright » Sun, Aug 16, 2020, 5:58 PM UTC

c1ccccc1 wrote: post #37

ColinWright wrote: post #27

Earlier quoted context omitted.

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…

Nice explanation. Another interesting point is that in some cases there may be infinitely many ESTs, even if the sum is finite. For example, if we take the set {2^n}U{3*2^n}.

Thank you.

Yes, as you say, the "unbounded sum" condition is sufficient, but not necessary. An example that's obvious "by inspection" is just to take an EST for every value of 2^n ... so take (2^n), (2^n)+1, and (2^n)+2.

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

#39

Post by roywiggins » Sun, Aug 16, 2020, 6:57 PM UTC

peterlk wrote: post #32

ColinWright wrote: post #27

Earlier quoted context omitted.

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…

Thank you very much for this comment I would like you to know that I would gladly pay a monthly fee to have at least 1 proof (per month) explained to me like this. Not sure how that could scale to varying knowledge levels, but I would love to have a slow educational drip of math explanations.

If you don't mind video content, Grant Sanderson's "3blue1brown" YouTube channel is the current reigning internet champion of this. He has a Patreon, too.

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

#40

Post by hansvm » Sun, Aug 16, 2020, 7:05 PM UTC

Ar-Curunir wrote: post #15

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

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)

There can be. Let f(n) be the count of members of the set in question which are at most n. If ε>0 and f(n)=O(n^(1-ε)) then the sum of reciprocals converges. For denser sets I'd have to think a bit longer about it.

It's probably also worth noting that weird density distributions are possible. E.g. one could imagine a kind of oscillation where you include enough values to get the total density up to that point up to some decreasing threshold (e.g. 1-2^-k if we've flip-flopped k times) then omit values to get below a different threshold (e.g. 2^-k if we've flip-flopped k times), and repeat the process indefinitely. The count up to a point n for this construction has the interesting property that it isn't greater in a big-O sense than the count for exponentially sparse sets while also not being less than the count for any sublinear density function in a big-omega sense (using the Knuth interpretation).