Mathematician Hurls Structure and Disorder Into Century-Old Problem (quantamagazine.org) 15
How many red and blue beads can you string together without making a big evenly spaced sequence of the same color? Using a semi-structured pattern of squashed circles, a mathematician shattered the previous record for how long you can keep stringing beads. From a report: The mathematician Ben Green of the University of Oxford has made a major stride toward understanding a nearly 100-year-old combinatorics problem, showing that a well-known recent conjecture is "not only wrong but spectacularly wrong," as Andrew Granville of the University of Montreal put it. The new paper shows how to create much longer disordered strings of colored beads than mathematicians had thought possible, extending a line of work from the 1940s that has found applications in many areas of computer science. The conjecture, formulated about 17 years ago by Ron Graham, one of the leading discrete mathematicians of the past half-century, concerns how many red and blue beads you can string together without creating any long sequences of evenly spaced beads of a single color. (You get to decide what "long" means for each color.) This problem is one of the oldest in Ramsey theory, which asks how large various mathematical objects can grow before pockets of order must emerge. The bead-stringing question is easy to state but deceptively difficult: For long strings there are just too many bead arrangements to try one by one.
A bit more detail (Score:5, Informative)
The central area of study are what are called van der Waerden numbers. The idea is as following: We color every positive integer either red or blue. Then van der Waerden showed that there have to be arbitrarily larger arithmetic progressions in one of the two sets. By an arithmetic progression, we mean a list of numbers where any two consecutive numbers in the list have the same difference. For example, 5, 8, 11, 14 is an arithmetic progression with four terms and common difference 3. We define w(a,b) to be the smallest positive integer such if take the first w positive integers, and we color them all red or blue then there has to be either a blue progression with a terms or a red progression with b terms. A consequence of van der Waerden's theorem is that w(a,b) exists for any a and b.
The specific conjecture of Ron Graham under discussion was that there was some absolute constant C such that for any k, w(3,k) is at most Ck^2. That is, if we are trying to take the first few numbers and color them red or blue, and we insist that we must avoid a blue arithmetic sequence of length 3 or a red arithmetic sequence of length k, then we cannot go out much more than k^2 terms. Some people were skeptical of Graham's conjecture, but thought that k^2 could be possibly replaced with some other polynomial of k, like k^3 or k^4. Green's paper shows that in fact, one can go out much further, and that the bound is almost exponential. In particular, any upper bound of the form Ck^a will be false for sufficiently large k.
Ron Graham past away last year, so it is unfortunate he didn't get to live long enough to see this result.
Re: (Score:3)
Is it like a prime number sequence kinda? The differences are ever expanding, hard to prove, but easy to test retroactively?
Re: (Score:3)
"found applications in many areas of computer... (Score:2)
Re:"found applications in many areas of computer.. (Score:5, Interesting)
I could think of one (possible) connection - in the design of communications protocols. In a highly-efficient and/or well-encrypted channel, you'll have equal numbers of 1s and 0s in the bitstream, and the likelihood of very long strings of consecutive 1s or consecutive 0s gets small pretty quickly (2^-n, where n is the number of consective bits - same as consecutive heads for a fair coin toss).
As a practical matter, when designing a communications bus, you generally don't want to encounter really long strings of 1s or 0s. Without frequent bit transitions, it can be difficult to maintain clock synchronization between nodes. Furthermore, there are plenty of situations where an intermittent connection to ground (or RF interference, or what-have-you) could introduce long strings of 0s that could otherwise be mistaken for genuine data. So: you design your protocol to permit no more than n consecutive bits before a transition.
For example: CANbus, widely used in cars and industrial settings, will insert an extra 0 or 1 into data packets after five consecutive bits of the same value, just to ensure that bit transitions occur periodically. This is referred to as bit stuffing [wikipedia.org]. This problem - ensuring that there aren't too-long strings of consecutive 1s or 0s - is not quite the same as TFA's subject matter, but I expect a mathematician or information theorist would say they are all of a piece and totally related.
Is this one of those Facebook scams? (Score:2)
This sounds suspiciously like one of those "what number comes next" Facebook scams designed to get you on a mailing list or reveal secret account questions.
Re: (Score:1)
Because you've never read any combinatorics? Isn't this the kind of thing everyone who studies computers in college gets exposed to?
Infinite (Score:2, Informative)
How many red and blue beads can you string together without making a big evenly spaced sequence of the same color?
I can just string red, blue, red, blue ad infinitum. Or until I run out of beads. Or patience.
Re:Infinite (Score:4, Informative)
Re: (Score:2)
Left for someone else to contemplate (Score:3, Funny)
This article reminded me of something. (Score:2)
Consider the following recurrence relation F(n), where F(n) generates bitstrings.of length 2n.
Let F(0)=either 0 or 1. F(n) is constructed as follows: For each bit in F(n-1), starting at the left and going to the right, append 01 to F(n) where the bit in question is 0, and append 10 to F(n) where the bit in question is 1. You can make a computer program to spit out these sequences in fewer than half a dozen lines of code in most programming languages.
It bears mentioning that although you can find man