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

Mathematician Hurls Structure and Disorder into Century-Old Problem

quantamagazine.org

Post reply on HN
Print view View original

11–20 of 21 posts

Re: Mathematician Hurls Structure and Disorder into Century-Old Problem

#11

Post by jacobolus »

jerf wrote: post #8
blakesterz wrote: post #2

"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 wron…

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…

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

Re: Mathematician Hurls Structure and Disorder into Century-Old Problem

#12

Post by tarentel »

unbanned wrote: post #10

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.

Re: Mathematician Hurls Structure and Disorder into Century-Old Problem

#13

Post by stolee »

paulpauper wrote: post #6
blakesterz wrote: post #2

"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 wron…

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.

Re: Mathematician Hurls Structure and Disorder into Century-Old Problem

#14

Post by jerf »

jacobolus wrote: post #11
jerf wrote: post #8

Earlier quoted context omitted.

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…

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

Re: Mathematician Hurls Structure and Disorder into Century-Old Problem

#15

Post by jacobolus »

jerf wrote: post #14
jacobolus wrote: post #11

Earlier quoted context omitted.

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

Re: Mathematician Hurls Structure and Disorder into Century-Old Problem

#16

Post by motohagiography »

unbanned wrote: post #10

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"

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.

Re: Mathematician Hurls Structure and Disorder into Century-Old Problem

#17

Post by Sniffnoy »

motohagiography wrote: post #16
unbanned wrote: post #10

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"

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…

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?

Re: Mathematician Hurls Structure and Disorder into Century-Old Problem

#18

Post by wombatmobile »

paulpauper wrote: post #6
blakesterz wrote: post #2

"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 wron…

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.

> 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?

Re: Mathematician Hurls Structure and Disorder into Century-Old Problem

#19

Post by wwalexander »

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.

Re: Mathematician Hurls Structure and Disorder into Century-Old Problem

#20

Post by Kranar »

unbanned wrote: post #10

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

Post reply on HN