Mathematician Hurls Structure and Disorder into Century-Old Problem | Hacker News Reader

Mathematician Hurls Structure and Disorder into Century-Old Problem

quantamagazine.org

71 pointsnsoonhui20 comments

"But in the final days of 2020, while out for a leisurely walk with his wife and children, Green suddenly had an insight: What if instead of one smallish blue circle per tile, you used many minuscule circles, scattered randomly?"

That's funny, guy writes a 68 page paper based on a random thought he had while out for a walk that shows a nearly 100-year-old combinatorics problem is not only wrong but spectacularly wrong.

Advanced mathematics stuff is just so crazy, I don't get it AT ALL, but it's so cool so many people can do it.

I don’t think there are many people capable of maths like this.

I’ve had insights into a math problem wake me up out of a hard sleep. The brain can really take up and work on stuff in a very encompassing way.

Unlike the Riemann Hypothesis or other big problems, It's not like many people are working on this problem all the time for over 100 years. It's more like a few people at any one time are working on it over a 100-year period. I am sure if someone else would have found this solution sooner if more people were working on it.

This is a really core and famous problem in extremal combinatorics and a lot of people think about this problem and many related ones. I think the biggest impediment is that too many people were looking for the upper bound instead of looking for a lower bound. The construction here is still incredibly novel and requires sophisticated mathematics to prove it is correct.

> I am sure if someone else would have found this solution sooner if more people were working on it.

How many people would you estimate were working on it?

He didn’t solve the old problem, he made a new data structure and kept an old algorithm.

If you stick with the initial pattern, the same problem in information transmission across the gaps in the structure remain.

If you fill gaps in a medium, info can cross. Whaaat

This does not highlight how clever this mathematician is so much as reveal how banal the initial problem was.

Even in college-level math education you can encounter the situation where you have a homework problem, and after pondering it for a while there's some simple insight that cracks the problem, but even bringing it up to homework standards, to say nothing of paper-publishing stardards, requires quite a bit more work.

And you may also experience the simple insight that cracks the problem, and in the process of finishing up the work to bring it up to spec you end up invalidating it.

Of course my homework never ran to 81 pages, but I suspect it's just scale.

I can certainly say I've had cases where I was presented with a business problem, and the solution was basically obvious to me in minutes, but manifesting that out in real code took weeks and actually quite a bit more than 81 pages of code. My system didn't disprove decades of conjecture that it was impossible, of course, but I think it's also more a quantitative difference than a qualitative one.

On the one hand, I don't want to disparage the excellent work done by professional mathematicians, but on the other, I do want people to understand these are humans, and I don't want you to just casually assume that you could never do anything similar. It is a delicate balance.

> my homework never ran to 81 pages, but I suspect it's just scale

Schools assign homework problems that (a) have known answers, and (b) are scoped so students can be expected to finish within a week.

There are undergraduate math theses where the novel technical part runs into the tens of pages even though the key insight is one simple idea.

My point was about "insight -> final paper" size, not whether or not things have a known answer or anything like that.

I agree! My added point is that the reason undergraduates don’t end up with very long homework papers is not that they couldn’t understand or solve very finicky problems if they put in the time, or that the prerequisite concepts involved in such problems are far beyond their understanding, but that homework is carefully designed to be digestible and scope-limited.

I remember having a babysitter when I was little who was doing her high school algebra homework. I was curious, so she tried to explain the concept of x/y variables to me and it made no sense to me at the time, kind of broke my brain briefly. Then, as an adult, I had a Math-PhD friend attempt to explain some advanced number theory concept to me and I had the exact same feeling of just completely not getting it and feeling like my brain was broken. Math has been the only subject that could consistently produce that feeling, I've always had sort of a sense of wonder and awe about it.

For anyone else confused by the problem description:

A Van der Waerden number is notated as W(r, k).

r is the number of colors that can be applied to an integer (e.g. 2 if you have blue and red beads).

A “big evenly spaced sequence” means that at least k integers of the same color form an arithmetic progression. So if n, n+1, n+2, …, or n, n+3, n+6, …, etc. all have the same color, that is considered an “evenly spaced sequence”, . “Big” means this sequence contains at least k integers, so for example, if n, n+1 and n+2 are all red, but n+3 is blue, this sequence would be “big” for a k of 3, but not for a k of 4.

The Van der Waerden number W(r, k) is then the smallest integer i such that, coloring the integers starting at 1 and ending at i, will force a “big evenly spaced sequence” to exist as defined above.

The description of this is very unclear.

"how many red and blue beads you can string together without creating any long sequences of evenly spaced beads of a single color"

The key is after, "(You get to decide what “long” means for each color.)". It's also explained better if you continue to read the article.

Was thinking the formulation sounded weird, as from this naive armchair that seems like a straight mutual information problem. https://en.wikipedia.org/wiki/Mutual_information

The red/blue beads thing is a metaphor for two random variables (red, blue) and the question seems to be about the information between them. Evenness and oddness is really a proxy for the effect of prior states on future ones. It's very likely I have a comedic misunderstanding of this, but if someone would like to provide the requisite humiliation, I'd be interested in why this interpretation is wrong.

The problem described isn't a metaphor or a proxy; it's not about some other thing like mutual information. It's about exactly what it says it is: evenly-spaced (arithmetic) subsequences.

More formally, given k, you have the set {1, ..., N}, and you want to produce a map from {1, ..., N} to a two-element set (which we can denote {blue, red}) such that there are no blue arithmetic sequences of length at least 3, and there are no red arithmetic sequences of length at least k. The question then becomes, given k, how large can N be with this remaining possible?

The explanation in the article is very poor. Luckily Wikipedia explains it perfectly with a simple example:

https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem#Ex...

I wonder if chemists or material scientists will be interested in this result. The method described sounds similar to the kind of design done to create novel types of glass.

Just because this is Ramsey theory (which is often associated with really enormous numbers), I suspect the values of r involved here are way too big to be useful in chemistry or physics. By "really enormous" I mean bigger than the iterated Ackermann function of whatever, that sort of thing. This is without my knowing anything about the actual result though.

Reply on news.ycombinator.com