Mathematics Literature Project progress January 6, 2014Posted by Scott Morrison in Uncategorized.
We’ve made some good progress over at the Mathematics Literature Project. In particular, we’ve completely analyzed the 2013 issues of five journals:
(The colour coded bars show the fractions of papers available on the arXiv, available on authors’ webpages, and not freely accessible at all; these now appear all over the wiki, but unfortunately don’t update automatically. Over at the wiki you can hover over these bars to get the numerical totals, too.)
Thanks everyone for your contributions so far! If you’ve just arrived, check out the tutorial I made on editing the wiki. Now, it’s time to do a little planning.
What questions should we be asking?
Here’s one we can start to answer right away.
What fraction of recent papers are available on the arXiv or on authors webpages?
For good generalist journals (e.g. Adv. Math. and Annals), almost everything! For subject area journals, there is wide variation (probably mostly depending on traditions in subfields): AGT is almost completely freely accessible, while Discrete Math. is at most half.
I hope we’ll soon be able to say this for many other journals, too.
Here’s the question I really want to have answers for:
Does being freely accessible correlate well with quality?
It’s certainly tempting to think so, seeing how accessible Advances and Annals are. I think to really answer this question we’re going to have to classify all the articles in slightly older issues (2010?) and then start looking at the citation counts for articles in the two pools. If we get coverage of more journals, we can also look for the correlation between, say, impact factor and the ratio of freely accessible content.
I don’t want to just list every journal on the wiki; it’s best if editors (and the helpful bots working in the background) can focus attention and enjoy the pleasures of finishing off issues and journals. Suggestions for journals to add next welcome in the comments. I’ve already included the tables of contents for the Journal of Number Theory, and the Journal of Functional Analysis. (It will be nice to be able to make comparisons between JFA and GAFA, I think.)
I’ve been working with some people on automating the entry of data in the wiki (mainly by using arXiv metadata; there are actually way more articles there with journal references and DOIs than I’d expected). Hopefully this will make the wiki editing experience more fun, as a lot of the work will have already been done, and humans just get to handle the hard and interesting cases.
Tags: mathematical literature
It would be nice to know how much of the mathematical literature is freely accessible. Here by ‘freely accessible’ I mean “there is a URL which, in any browser anywhere in the world, resolves to the contents of the article”. (And my intention throughout is that this article is legitimately hosted, either on the arxiv, on an institutional repository, or on an author’s webpage, but I don’t care how the article is actually licensed.) I think it’s going to be okay to not worry too much about discrepancies between the published version and a freely accessible version — we’re all grown ups and understand that these things happen. Perhaps a short comment field, containing for example “minor differences from the published version” could be provided when necessary.
This post outlines an idea to achieve this, via a human editable database containing the tables of contents of journals, and links, where available, to a freely accessible copy of the articles.
It’s important to realize that the goal is *not* to laboriously create a bad search engine. Google Scholar already does a very good job of identifying freely accessible copies of particular mathematics articles. The goal is to be able to definitively answer questions such as “which journals are primarily, or even entirely, freely accessible?”, to track progress towards making the mathematical literature more accessible, and finally to draw attention to, and focus enthusiasm for, such progress.
I think it’s essential, although this is not obvious, that at first the database is primarily created “by hand”. Certainly there is scope for computer programs to help a lot! (For example, by populating tables of contents, or querying google scholar or other sources to find freely accessible versions.) Nevertheless curation at the per-article level will certainly be necessary, and so whichever route one takes it must be possible for humans to edit the database. I think that starting off with the goal of primarily human contributions achieved two purposes: one, it provides an immediate means to recruit and organize interested participants, and two, hopefully it allows much more flexibility in the design and organization of the collected data — hopefully many eyes will reveal bad decisions early, while they’re easy to fix.
That said, we better remember that eventually computers may be very helpful, and avoid design decisions that make computer interaction with the database difficult.
What should this database look like? I’m imagining a website containing a list of journals (at first perhaps just one), and for each journal a list of issues, and for each issue a table of contents.
The table of contents might be very simple, having as few as four columns: the title, the authors, the link to the publishers webpage, and a freely accessible link, if known. All these lists and table of contents entries must be editable by a user — if, for example no freely accessible link is known, this fact should be displayed along with a prominent link or button which allows a reader to contribute one.
At this point I think it’s time to consider what software might drive this website. One option is to build something specifically tailored to the purpose. Another is to use an essentially off-the-shelf wiki, for example tiddlywiki as Tim Gowers used when analyzing an issue of Discrete Math.
Custom software is of course great, but it takes programming experience and resources. (That said, perhaps not much — I’m confident I could make something usable myself, and I know people who could do it in a more reasonable timespan!) I want to essentially ignore this possibility, and instead use mediawiki (the wiki software driving wikipedia) to build a very simple database that is readable and editable by both humans and computers. If you’re impatient, jump to http://tqft.net/mlp and start editing! I’ve previously used it to develop the Knot Atlas at http://katlas.org/ with Dror Bar-Natan (and subsequently many wiki editors). There we solved a very similar set of problems, achieving human readable and editable pages, with “under the hood” a very simple database maintained directly in the wiki.
From the drawers of the museum December 12, 2013Posted by Noah Snyder in fusion categories, quantum groups, subfactors, Uncategorized.
One of my amateur interests is paleontology. Paleontologists looking for new examples have two options: go out in the field and dig up a new example, or go looking through drawers of museums to find old examples that had been overlooked. In this blog post I want to give an interesting example of the latter kind of research being useful in mathematics. Namely in discussions with Zhengwei Liu, we realized that an old example of Ocneanu’s gives an answer to a question that was thought to be open.
One of the central problems in fusion categories is to determine to what extent fusion categories can be classified in terms of finite groups and quantum groups (perhaps combined in strange ways) or whether there are exceptional fusion categories which cannot be so classified. My money is on the latter, and in particular I think extended Haagerup gives an exotic fusion category. However, there are a number of examples which seem to involve finite groups, but where we don’t know how to classify them in terms of group theoretic data. For example, the Haagerup fusion category has a 3-fold symmetry and may be built from or (as suggested by Evans-Gannon). The simplest examples of these kind of “close to group” categories, are called “near-group categories” which have only one non-invertible object and have the fusion rules
for some group of invertible objects . A result of Evans-Gannon (independently proved by Izumi in slightly more generality), says that outside of a reasonably well understood case (where and the category is described by group theoretic data), we have that must be a multiple of . There are the Tambara-Yamagami categories where , and many examples (E6, examples of Izumi, many examples of Evans-Gannon) where
Here’s the question: Are there examples where n is larger than ?
It turns out the answer is yes! In fact the answer is given by the -graded part of the quantum subgroup of quantum from Ocneanu’s tables here. I’ll explain why below.
The Hoffman-Singleton graph and groupoids October 16, 2013Posted by David Speyer in Uncategorized.
The Hoffman-Singleton graph is the unique graph on vertices with the following property: Every vertex is of degree and, between any two vertices, there is either an edge or a path of length two, but not both. The Hoffman-Singleton graph has a large symmetry group — order — and there are many ways to describe it that emphasize different symmetry properties. Various constructions describe it in terms of the geometry of the affine plane , the projective space or just pure combinatorics. Here is one more that I noticed the other day when reading through the original Hoffman-Singleton paper. While turning it into a blogpost, I noticed that the same observation was made by Markus Junker in 2005.
The quest for narrow admissible tuples July 2, 2013Posted by Scott Morrison in polymath.
Tags: admissible tuples, polymath8, zhang
(A guest post by Andrew Sutherland.)
With more than 400 comments tacked on to the previous blog post, it’s past time to rollover to a new one. As just punishment for having contributed more than my fair share of those comments, Scott has asked me to write a guest post summarizing the current state of affairs. This task is made easier by Tao’s recent progress report on the polymath project to sharpen Zhang’s result on bounded gaps between primes. If you haven’t already read the progress report I encourage you to do so, but for the benefit of newcomers who would like to understand how our quest for narrow admissible tuples fits in the bounded prime gaps polymath project, here goes.
The Hardy-Littlewood prime tuples conjecture states that every admissible tuple has infinitely many translates that consist entirely of primes. Here a tuple is simply a set of integers, which we view as an increasing sequence ; we refer to a tuple of size as a -tuple. A tuple is admissible if it does not contain a complete set of residues modulo any prime . For example, 0,2,4 is not an admissible 3-tuple, but both 0,2,6 and 0,4,6 are. A translate of a tuple is obtained by adding a fixed integer to each element; the sequences 5,7,11 and 11,13,17 are the first two translates of 0,2,6 that consist entirely of primes, and we expect that there are infinitely more. Admissibility is clearly a necessary condition for a tuple to have infinitely many translates made up of primes; the conjecture is that it is also sufficient.
Zhang proved a weakened form the prime tuples conjecture, namely, that for all sufficiently large , every admissible -tuple has infinitely many translates that contain at least 2 primes (as opposed to ). He made this result explicit by showing that one may take , and then noted the existence of an admissible -tuple with diameter (difference of largest and smallest elements) less than 70,000,000. Zhang’s -tuple consists of the first primes greater than , which is clearly admissible. As observed by Trudgian, the diameter of this -tuple is actually less than 60,000,000 (it is precisely 59,874,954).
Further improvements to Zhang’s bound came rapidly, first by finding narrower admissible -tuples, then by optimizing and the critical parameter on which it depends (this means making larger; is proportional to ). Since it began on June 4, the polymath8 project has been working along three main lines of attack: (1) improving bounds on and a related parameter , (2) deriving smaller values of from a given pair , and (3) the search for narrow admissible -tuples.You can see the steady progress that has been made on these three interlocking fronts by viewing the list of world records.
A brief perusal of this list makes it clear that, other than some quick initial advances made by tightening obvious slack in Zhang’s bounds, most of the big gains have come from improving the bounds on (edit: as pointed out by v08ltu below, reducing the dependence of on from to was also a major advance); see Tao’s progress report and related blog posts for a summary of this work. Once new values of and have been established, it is now relatively straight-forward to derive an optimal (at least within 1 or 2; the introduction of Pintz’s method has streamlined this process). There then remains the task of finding admissible -tuples that are as narrow as possible; it is this last step that is the subject of this blog post and the two that preceded it. Our goal is to compute , the smallest possible diameter of an admissible -tuple, or at least to obtain bounds (particularly upper bounds) that are as tight as we can make them.
A general way to construct a narrow admissible -tuple is to suppose that we first sieve the integers of one residue class modulo each prime and then choose a set of survivors, preferably ones that are as close together as possible. In fact, it is usually not necessary to sieve a residue class for every prime in order to obtain an admissible -tuple, asymptotically an bound should suffice. The exact number of residue classes that require sieving depends not only on , but also on the interval in which one looks for survivors (it could also depend on the order in which one sieves residue classes, but we will ignore this issue).
All of the initial methods we considered involved sieving residue classes 0 mod , and varied only in where to look for the survivors. Zhang takes the first survivors greater than 1 (after sieving modulo primes up to ), and Morrison’s early optimizations effectively did the same, but with a lower sieving bound. The Hensley-Richards approach instead selects survivors from an interval centered at the origin, and the asymmetric Hensley-Richards optimization shifts this interval slightly (see our wiki page for precise descriptions of each of these approaches, along with benchmark results for particular values of interest).
But there are sound practical reasons for not always sieving 0 mod . Assuming we believe the prime tuples conjecture (which we do!), we can certainly find an optimally narrow admissible -tuple somewhere among the primes greater than , all of which survive sieving 0 modulo primes . However, the quantitative form of the prime tuples conjecture tells us roughly how far we might need to search in order to find one. The answer is depressingly large: the expected number of translates of any particular admissible -tuple to be found among the primes is thus we may need to search through the primes in an interval of size exponential in in order to have a good chance of finding even one translate of the -tuple we seek.
Schinzel suggested that it would be better to sieve 1 mod 2 rather than 0 mod 2, and more generally to sieve 1 mod for all primes up to some intermediate bound and then switch to sieving 0 mod for the remaining primes. We find that simply following Schinzel’s initial suggestion, works best, and one can see the improvement this yields on the benchmarks page (unlike Schinzel, we don’t restrict ourselves to picking the first survivors to the right of the origin, we may shift the interval to obtain a better bound).
But sieving a fixed set of residue classes is still too restrictive. In order to find narrower admissible tuples we must relax this constraint and instead consider a greedy approach, where we start by picking an interval in which we hope to find survivors (we know that the size of this interval should be just slightly larger than ), and then run through the primes in order, sieving whichever residue class is least occupied by survivors (we can break ties in any way we like, including at random). Unfortunately a purely greedy approach does not work very well. What works much better is to start with a Schinzel sieve, sieving 1 mod 2 and 0 mod primes up to a bound slightly smaller than , and then start making greedy choices. Initially the greedy choice will tend to be the residue class 0 mod , but it will deviate as the primes get larger. For best results the choice of interval is based on the success of the greedy sieving.
This is known as the “greedy-greedy” algorithm, and while it may not have a particularly well chosen name (this is the downside of doing math in a blog comment thread, you tend to throw out the first thing that comes to mind and then get stuck with it), it performs remarkably well. For the values of listed in the benchmarks table, the output of the greedy-greedy algorithm is within 1 percent of the best results known, even for , where the optimal value is known.
But what about that last 1 percent? Here we switch to local optimizations, taking a good admissible tuple (e.g. one output by the greedy-greedy algorithm) and trying to make it better. There are several methods for doing this, some involve swapping a small set of sieved residue classes for a different set, others shift the tuple by adding elements at one end and deleting them from the other. Another approach is to randomly perturb the tuple by adding additional elements that make it inadmissible and then re-sieving to obtain a new admissible tuple. This can be done in a structured way by using a randomized version of the greedy-greedy algorithm to obtain a similar but slightly different admissible tuple in approximately the same interval, merging it with the reference tuple, and then re-sieving to obtain a new admissible tuple. These operations can all be iterated and interleaved, ideally producing a narrower admissible tuple. But even when this does not happen one often obtains a different admissible tuple with the same diameter, providing another reference tuple against which further local optimizations may be applied.
Recently, improvements in the bounds on brought below 4507, and we entered a regime where good bounds on are already known, thanks to prior work by Engelsma. His work was motivated by the second Hardy-Littlewood conjecture, which claims that for all , a claim that Hensley and Richards showed is asymptotically incompatible with the prime tuples conjecture (and now generally believed to be false). Engelsma was able to find an admissible 447-tuple with diameter 3158, implying that if the prime tuples conjecture holds then there exists an (infinitely many in fact) for which , which is greater than . In the process of obtaining this result, Engelsma spent several years doing extensive computations, and obtained provably optimal bounds on for all , as well as upper bounds on for . The quality of these upper bounds is better in some regions than in others (Engelsma naturally focused on the areas that were most directly related to his research), but they are generally quite good, and for up to about 700 believed to be the best possible.
We have now merged our results with those of Engelsma and placed them in an online database of narrow admissible -tuples that currently holds records for all up to 5000. The database is also accepts submissions of better admissible tuples, and we invite anyone and everyone to try and improve it. Since it went online a week ago it has processed over 1000 submissions, and currently holds tuples that improve Engelsma’s bounds at 1927 values of , the smallest of which is 785. As I write this stands at (subject to confirmation), which happens to be one of the places where we have made an improvement, yielding a current prime gap bound of 6,712 (but I expect this may drop again soon).
In addition to supporting the polymath prime gaps project, we expect this database will have other applications, including further investigations of the second Hardy-Littlewood conjecture. As can be seen in this chart, not only have we found many examples of admissible -tuples whose diameter satisfies , one can view the growth rate of the implied lower bounds on in this chart.
More narrow admissible sets June 5, 2013Posted by Scott Morrison in polymath.
Tags: polymath8, zhang
It looks like it may be time to roll over the search for narrow admissible sets to a new blog post, as we’re approaching 100 comments on the original thread.
In the meantime, an official polymath8 project has started. The wiki page is a good place to get started. Work to understand and improve the bounds in Zhang’s result on prime gaps has split into three main areas.
1) A reading seminar on Zhang’s Theorem 2.
2) A discussion on sieve theory, bridging the gap begin Zhang’s Theorem 2 and the parameter k_0 (see also the follow-up post).
3) Efforts to find narrow admissible sets of a given cardinality k_0 — the width of the narrowest set we find gives the current best bound on prime gaps.
We started on 3) in the previous blog post, and now will continue here. I’ll try to summarize the situation.
Just recently there’s been a significant improvement in , the desired cardinality of the admissible set, and we’re now looking at . Hopefully there’s going to be a whole new round of techniques, made possible by the significantly smaller problem size.
As I write this, the narrowest admissible set of size 34,429 found so far, due to Andrew Sutherland, has width 388,118.
This was found using the “greedy-greedy” algorithm. This starts with some chosen interval of integers, in this case [-185662,202456], and then sieves as follows. First discard 1 mod 2, and then 0 mod p for , for some parameter b. (I’m not actually sure of the value of this parameter in Andrew’s best set.) After that, for each prime we pick a minimally occupied residue class, and sieve that out. Assuming we picked a sufficiently wide interval to begin with, when we’re done the resulting admissible set with still have at least elements.
More generally, there are several directions worth pursuing
1. sharpening bounds on , the maximal cardinality of an admissible set of width at most ,
2. finding new constructions of admissible sets of a given size (and also ‘almost-admissible’ sequences)
3. developing algorithms or search techniques to find narrow admissible sets, perhaps starting from a wider or smaller admissible set, or starting from an ‘almost-admissible’ set.
(If these questions carry us in different directions, there’s always more room on the internet!)
For sufficiently small sizes (at most 372), everything is completely understood due to exhaustive computer searches described at http://www.opertech.com/primes/k-tuples.html. At least for now, we need to look at much larger sizes, so obtaining bounds and finding probabilistic methods is probably the right approach.
I’m writing this on a bus, beginning 30 hours of travel. (To be followed by a short sleep then an intense 3 day conference!) So my apologies if I missed something important!
Tags: admissible-set, polymath8, primes, zhang
Everyone by now has heard about Zhang’s landmark result showing that there are infinitely many pairs of primes at most 70000000 apart.
His core result is that if a set of 3.5 * 10^6 (corrected, thanks to comment #2) numbers is admissible (see below), then there are infinitely many so that contains at least two primes. He then easily constructs an admissible set wherein the largest difference is 7 * 10^7, obtaining the stated result.
A set is admissible if there is no prime so occupies every residue class. For a given this is clearly a checkable condition; there’s no need to look at primes larger than .
(While Zhang went for a nice round number, Mark Lewko found his argument in fact gives 63374611, if you’re being overly specific about these things, which we are right now. :-)
In a short note on the arXiv yesterday, Tim Trudgian (whose office is not far from mine) pointed out another way to build an admissible set, giving a smaller largest difference, obtaining the result that there are infinitely many pairs of primes at most 59874594 apart. He considers sets of the form (where is Zhang’s constant 3.5 * 10^7). These aren’t necessarily admissible, but they are for some values of , and both Zhang and Tim noticed certain values for which this is easy to prove. Zhang used with , while Tim’s observation is that also works. (Comment #2 below points out this isn’t right, and Zhang also intended , and the slack in his estimate is coming from just looking at the largest element of , rather than the largest difference.) Thus the bound in his result is .
It turns out that checking admissibility for a given isn’t that hard; it takes about an hour to check a single value for (but if you find a prime witnessing not being admissible, it very often gives you a fast proof that is not admissible either, so searching is much faster).
I haven’t looked exhaustively, but one can check that gives an admissible , and hence there are infinitely many pairs of primes at most . (Sadly, it’s impossible to get below 59 million with this trick; no below 27000 works; all witnessed by or .)
I just couldn’t resist momentarily “claiming the crown” for the smallest upper bound on gap size. :-) Of course the actual progress, that’s surely coming soon from people who actually understand Zhang’s work, is going to be in reducing his 3.5 * 10^6. You can read more about prospects for that in the answers to this MathOverflow question.
University of Melbourne hiring May 26, 2013Posted by Scott Morrison in jobs.
Often Australian jobs don’t make it on to MathJobs.org, for various reasons, so I thought I’d help distribute this one — Melbourne is hiring, initially a full professor, and subsequently several tenure track assistant professor positions, all in pure mathematics.
Below the fold, Arun Ram’s message about this. Australia is a nice place to come and work!
Conference videos April 30, 2013Posted by Ben Webster in Uncategorized.
Well, from my perspective at least, the conference was a success. We all made it through in one piece, and no one got trapped on the subway. If any of you are looking for the videos of the talks, they can be downloaded from this page. That’s a only a temporary hosting solution, but at least they’re available for the moment.
More on shameless promotion April 23, 2013Posted by Ben Webster in Uncategorized.
As those of you who’ve scrolled down the page know, the conference I mentioned a few months ago (now sadly memorializing the life of Andrei Zelevinsky) is starting tomorrow. Of course, for those of you who don’t live in the Boston area, coming to conference isn’t an option unless you were already traveling today, but I do have a (somewhat belated) announcement. Assuming that the AV gods are kind and everything goes as planned, it should be possible to watch the talks live (of course, we’ll also make the videos available after the conference, in case you’re busy). The schedule is here; the talks start at 10am tomorrow.