[HN Gopher] Mathematician Hurls Structure and Disorder into Cent...
___________________________________________________________________
Mathematician Hurls Structure and Disorder into Century-Old Problem
Author : nsoonhui
Score : 63 points
Date : 2021-12-16 12:06 UTC (10 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| unbanned wrote:
| 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"
| motohagiography wrote:
| 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.
| Sniffnoy wrote:
| 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?
| tarentel wrote:
| 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.
| iandanforth wrote:
| 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.
| blakesterz wrote:
| "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.
| ianai wrote:
| 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.
| paulpauper wrote:
| 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.
| wombatmobile wrote:
| > 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?
| stolee wrote:
| 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.
| airblade wrote:
| I don't think there are many people capable of maths like this.
| jerf wrote:
| 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.
| jacobolus wrote:
| > _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.
| jerf wrote:
| My point was about "insight -> final paper" size, not
| whether or not things have a known answer or anything like
| that.
| jacobolus wrote:
| 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.
| addsidewalk wrote:
| 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.
| Benjammer wrote:
| 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.
| wwalexander wrote:
| 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.
___________________________________________________________________
(page generated 2021-12-16 23:01 UTC)