Landmark math proof clears hurdle in top Erdős conjecture | Hacker News Reader

Landmark math proof clears hurdle in top Erdős conjecture

quantamagazine.org

137 pointsheadalgorithm45 comments

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

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.

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.

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

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| < epsilon n^-m for n > 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...

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

Edit: not greater than exponentially sparse sets, something a bit denser -- exponential sparsity is manageable as well, but not with the 2^-k construction I gave.

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.

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

Yes agreed! Thank you!!!

Also updated my profile

Quick comment ... I have no idea about the answer to your email riddle. I don't know anything about Basecamp, Apple, WWDC, or any ruckus. So if you want to obfuscate your email address and yet still be contactable by humans who use computers, you need not to rely on specific knowledge from that world.

Of course, a perfectly reasonable stance is that if someone really wants to contact you then they'll do their homework and solve the riddle, in which case it's fine. I just thought I'd let you know that not everyone lives in the world where that kind of knowledge is commonplace.

Ahh thanks for that. I can get rather deep in my Apple obsessions let me fix it.

Updated. I hope that’s better. I had just saw your profile and saw all the spam you got and thought I had to come up With a really obscure way to obscure it. Sorry.

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

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.

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.

I second this!

Not math-focused, but you might love The Morning Paper:

https://blog.acolyer.org/

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!

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.

> 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 matter? Maybe it must be >0 otherwise 1/n makes no sense?

2.) When you ask whether the sum of 1/n for all n in A diverges, how do you know what order to sum them in? Does it diverge regardless of the order? Since A only contains positive integers doesn't sum of 1/n for all n in A always tend towards infinity?

EDIT: I see now that sum of positive integers doesn't always tend towards infinity, thanks to ColinWright's comment about powers of 2 (for which the sum of 1/n tends towards 1).

Also, since the numbers are all positive, it doesn't matter what order you sum them in, you're basically just asking whether the sum of 1/n for all the numbers in A is finite or not.

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 sum stays the same when you arbitrarily rearrange the terms of the series. In general the answer is no (see Riemann rearrangement theorem), but as this series is only made up of positive reals, it can be rearranged arbitrarily without change in how it converges (or doesn’t).

To the second part of your question, take any geometric series, i.e. A = {1, r, r^2, ...}, then it will converge. There are other classes of series that will converge in this case, and the conjecture is basically asking to characterize sets with diverging series as needing to be “large and dense” in a certain sense.

Note that a geometric series can also be a multiple, e.g. (a, a r, a r^2, ...). It converges if and only if |r| < 1.

Good point, I was not being fully general there!

A dense APL codebase at that.

1. Yes, as you say it doesn't matter 2. Order of summation doesn't matter when all numbers are positive

> Since A only contains positive integers doesn't sum of 1/n for all n in A always tend towards infinity?

no, think for instance sum(1/n^2) EDIT: or sum(1/2^n) which solves Zeno's paradox (Achilles vs Tortoise)

Yeah, I would say that understanding conjectures often requires knowing some "background lemmas" in addition to knowing the definitions of the objects used in the definition, for this very reason. As another very simple example it can be shown that you can replace ℕ by the set of integers greater than 3, and the resulting conjecture is equivalent.

Ah, your Q&A made it much clearer for me. Thanks.

For people interested in arithmetic progression type theorems, one of my favorite theorems along those lines (though technically not actually about arithmetic progressions, but extremely closesly related), and a very under-appreciated gem, is Hindman's Theorem.

Hindman's Theorem says that if you color the natural numbers with finitely many colors, there must be some infinite subset D of the natural numbers such that every finite sum of elements of D has the same color.

The proof, asontonishingly, is an application of free ultrafilters, and is actually simple enough that someone with an advanced undergrad background in pure math can understand it with just a few hours of reading (e.g. see [1])

[1] https://web.williams.edu/Mathematics/lg5/Hindman.pdf

Very promising, although the jury is still out: "The new paper is 77 pages long, and it will take time for mathematicians to check it carefully. But many feel optimistic that it is correct. “It really looks the way a proof of this result should look,” said Katz, whose earlier work laid much of the groundwork for this new result."

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!

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.

I agree that numbers don't exist in the real world. However, we humans have an ability to perceive the world through numbers. The question then is about our perception of the world if you wish.

There is a subtle issue lurking behind. And that can be framed as a question: can one access things(say, numbers) that do not exist? If the answer is "Yes", then we don't need the Platonic world. Otherwise, we need to postulate the existence of numbers and sets in another world (Platonic world). You can also see people who are looking for Platonic love.

In other words, it is an issue between access and existence. Does access need existence? For instance, when X says 'John is charismatic', is 'charisma' like 'neurosis'? Definitely not, and X sees John's charisma. And this charisma doesn't play the causal role.

Most modern cryptography relies on number theory.

Worth noting that the Green-Tao Theorem is a very special case of this conjecture, using the (comparatively easier to prove) fact that Σ 1/p diverges.

Does it get us closer tot he twin prime conjecture?

Reply on news.ycombinator.com