The Aperiodical 

You're reading: Posts Tagged: proof

Not mentioned on The Aperiodical, March 2016

By Christian Lawson-Perfect. Posted March 30, 2016

There’s been a lot of maths news this month, but we’ve all been too busy to keep up with it. So, in case you missed anything, here’s a summary of the biggest stories this month. We’ve got two new facts about primes, the best way of packing spheres in lots of dimensions, and the ongoing debate about the place of maths in society, as well as the place of society in maths.

A surprisingly simple pattern in the primes

Kannan Soundararajan and Robert Lemke Oliver have noticed that the last digits of adjacent prime numbers aren’t uniformly distributed – if one prime ends in a 1, for example, the next prime number is less likely to end in a 1 than another odd digit. Top maths journos Evelyn Lamb and Erica Klarreich have both written very accessible pieces about this, in the Nature blog and Quanta magazine, respectively.

Oliver and Soundararajan’s paper on the discovery is titled “Unexpected biases in the distribution of consecutive primes”.

László Babai reckons he can decide if two graphs are isomorphic in quasipolynomial time

By Christian Lawson-Perfect. Posted November 22, 2015



László Babai in Chicago. Photo by Gabe Gaster, used with permission.

We’ve been slow to cover this, but if this week has taught us anything, it’s that taking your time over Important Maths News is always a good idea.

A couple of weeks ago, rumours started circulating around the cooler parts of the internet that László “Laci” Babai had come up with an algorithm to decide if two graphs are isomorphic in quasipolynomial time. A trio of mathematicians including Tim Gowers were on BBC Radio 4’s In Our Time discussing P vs NP while these rumours were circulating and made a big impression on Melvyn Bragg as they talked so excitedly about the prospect of something big being announced.

If Babai had done what the rumours were saying, this would be a huge advance – graph isomorphism is known to be an NP problem, so each step closer to a polynomial-time algorithm raises the P=NP excite-o-meter another notch.

Terence Tao has solved the Erdős discrepancy problem!

By Christian Lawson-Perfect. Posted September 18, 2015

Terence Tao has just uploaded a preprint to the arXiv with a claimed proof of the Erdős discrepancy problem.



Erdős’s discrepancy problem now less of a problem

By Katie Steckles. Posted February 25, 2014

Boris Konev and Alexei Lisitsa of the University of Liverpool have been looking at sequences of $+1$s and $-1$s, and have shown using an SAT-solver-based proof that every sequence of $1161$ or more elements has a subsequence which sums to at least $2$. This extends the existing long-known result that every such sequence of $12$ or more elements has a subsequence which sums to at least $1$, and constitutes a proof of Erdős’s discrepancy problem for $C \leq 2$.

Not Mentioned on the Aperiodical this month, 21 August

By Katie Steckles. Posted August 21, 2013

Here are three things we noticed this month which didn’t get a proper write-up, due to thesis/Edinburgh fringe/holidays: a big proof, a fun maths book club, and a ridiculous bit of pi-related madhattery.

Bound on prime gaps bound decreasing by leaps and bounds

By Christian Lawson-Perfect. Posted June 8, 2013

Update 17/06/2013: The gap is down to 60,744. That’s a whole order of magnitude down from where it started!

When Yitang Zhang unexpectedly announced a proof that that there are infinitely many pairs of primes less than 70 million apart from each other – a step on the way to the twin primes conjecture – certain internet wags amused themselves and a minority of others with the question, “is it a bigger jump from infinity to 70 million, or from 70 million to 2?”.

Of course the answer is that it’s a really short distance from 70 million to 2, and here’s my evidence: the bound of 70 million has in just over three weeks been reduced to just a shade over 100,000.

“Bounded gaps between primes” by Yitang Zhang now available

By Peter Rowlett. Posted May 29, 2013

To complete the story started as a rumour report in ‘Primes gotta stick together‘ and confirmed in ‘Primes really do stick together‘, here we report that Annals of Mathematics has posted the PDF of ‘Bounded gaps between primes‘ by Yitang Zhang on its ‘to appear in forthcoming issues’ page. After the seminar on 13th May, Zhang apparently submitted a revised manuscript on 16 May, which was accepted 21 May 2013. So if you’ve been itching for details, here’s your chance (assuming you have access to a subscription to Annals).

Here’s the abstract:

It is proved that \[ \liminf_{n\to \infty}\, (p_{n+1} – p_n) < 7 \times 10^7 \text{,}\] where $p_n$ is the $n$-th prime.

Our method is a refinement of the recent work of Goldston, Pintz and Yildirim on the small gaps between consecutive primes. A major ingredient of the proof is a stronger version of the Bombieri-Vinogradov theorem that is applicable when the moduli are free from large prime divisors only (see Theorem 2), but it is adequate for our purpose.

The paper: Bounded gaps between primes by Yitang Zhang, in Annals of Mathematics.