This is an open thread for any topic not covered in other posts. Please feel free to discuss whatever you wish here (but keep it polite, constructive, and at least tangentially connected to the polymath enterprise.)

## 35 Comments »

RSS feed for comments on this post. TrackBack URI

I am not sure exactly where to post suggestions for polymath projects that one is not willing to run (I don’t have the time or energy to maintain one myself), but I thought I would toss out a problem in computational complexity that has always bugged me. It is a problem that is easy to state, probably will succumb to elementary methods, and probably could be solved if enough people contributed ideas. Here goes: consider the usual subset sum (or is it knapsack?) problem where you are given a list of positive integers N_1, …, N_k, and a target number T, and you must decide whether there is some subset of N_1, …, N_k that sums to T. The problem is to beat the “trivial algorithm”, which I shall describe presently.

The first thing to realize is that there is a subset sum equal to T iff there is one equal to S-T, where S=N_1 + … + N_k. Furthermore, subsets of size t summing to T correspond uniquely to subsets of size k-t summing to S-T. In this way, you only need to consider subsets of size at most k/2 (and check whether they sum of T or S-T) to solve the problem. But now you can use the usual “collision technique” to reduce the problem to subsets of size at most k/4, by forming a table of all subsets of at most this size, along with their sum of elements, until you find a disjoint pair of subsets that sums to either T or S-T. The running time of this procedure should be comparable to (k choose k/4) = c^(k+o(k)), for a certain constant c that is easy to work out. This is what I mean by the “trivial algorithm”. Now, the problem is find an algorithm — any at all — that runs in time at most d^k, where d < c. To my knowledge no such algorithm is know to exist!

Comment by Ernie Croot — July 29, 2009 @ 5:14 pm |

Thanks for the problem! We are planning to organise another polymath project beyond the primes one (which already has a strong computational complexity component to it), and this may well be a candidate if we can find people to run it (one lesson we’ve learned so far is that engaged leadership is quite important to make these things run smoothly). I do know that there is some interest in the CS community in running these things, so this may well be a good candidate.

Edit:I’ve set up a wiki page at http://michaelnielsen.org/polymath1/index.php?title=Other_proposed_projects to collect projects of this nature.Comment by Terence Tao — August 3, 2009 @ 2:20 pm |

I have developed an algorithm for this problem as well as a target range. In essence it is based on determining the largest number that can be selected without exceeding the target by the size of the smallest number selected. This technique manages to provide an efficient way of selecting subsets such that if any one of the selected numbers is deselected the result will be less than the target, (for a single target). It also is easily adapted to determining multiple subset totals from a single set. This was inspired from problems in oil delivery delivery logistics, and how to fill vehicles. As to it’s worst case performance I’m not sure how to go about determining this.

Comment by John Bufton — September 13, 2009 @ 8:15 pm |

WordPress seems to be marking some of my posts in the research thread as spam (or holding them for moderation, at minimum?) — understandable, perhaps, given a high posting rate, wordiness, and a tendency to link externally, but annoying. I suppose it’s possible that I’m the only one being affected, but it seems unlikely. Is there any way to loosen the restrictions to minimize the number of legitimate comments that aren’t immediately posted?

Comment by Harrison — August 9, 2009 @ 8:13 pm |

Unfortunately there doesn’t seem to be an option to reduce the stringency of the spam filter (other than to raise the threshold of external links, which I’ve upped to five), but I will try to check it daily.

Comment by Terence Tao — August 9, 2009 @ 8:53 pm |

I have been contacted by someone about possibly writing an article about polymath. I have some questions about how to handle this. For instance they mentioned us possibly having a spokesman and it is not clear that we have that. We might want to consider having some sort of organizational structure to deal with the media. For one thing there are a lot of potential readers for something like this and that could result in more people entering future polymath’s. Another issue that comes to mind is that they wanted to see something about people talking about their experiences with polymath and we have several threads already dealing with that but I don’t think there is one central hub for referring to all of these.

Comment by Kristal Cantwell — August 12, 2009 @ 6:49 pm |

Hmm, I’m actually a bit surprised that we have media attention at all… but if there are inquiries then certainly we could discuss them on this blog (John Baez recently did something similar when he was solicited by the Notices of the AMS to talk about blogging). Tim is probably the most obvious person to contact, being the one who originated the whole polymath idea and being involved in all of the polymath projects to date.

Comment by Terence Tao — August 12, 2009 @ 9:57 pm |

I gave Tim’s name to them. It is the Notices, I think they want to do a feature article on blogging as well as polymath in addtion to what John Baez is writing.

Comment by Kristal Cantwell — August 13, 2009 @ 1:57 am |

Let me make a comment about the checks and X’s: Some kind of “Are you sure you want to Check (or X) that comment?” query needs to be added to the wordpress page. Just today I was trying to look up a last minute comment to include in my NSF grant proposal, and the mouse point moved over someones comment, and I accidentally clicked the check. I thought that if I then clicked the X, it would erase what I had done, but instead it added another X, and kept the check (or maybe there wasn’t really a check added in the first place — it seemed like there was, though).

Comment by Ernie Croot — October 1, 2009 @ 8:16 pm |

Yes, this is a problem – there should be a mechanism to “uncheck” a comment back to the neutral mode. My plan at this point is to collect a list of grievances so that when the time comes to move to a better platform, we will know what features to implement. (#1 on the list is the ability to preview and edit comments.)

Comment by Terence Tao — October 1, 2009 @ 11:27 pm |

I have suggested 3 problems to be solved collaboratively:

http://portonmath.wordpress.com/2009/08/30/proposal-conjecture-complementive-filters/

http://portonmath.wordpress.com/2009/10/17/proposal-partitioning/

http://portonmath.wordpress.com/2009/10/20/complete-lattice-generated-by-a-partitioning-of-a-lattice-element/

(note that the last two seem being closely related) and also I suggested a bigger “research writing” project:

http://portonmath.wordpress.com/2009/08/29/polymath-filters-on-posets/

I have the hope that at least one of my projects will be selected by the Admins.

However you may follow the above URLs which contain pingbacks to other my blog posts, and note that I wrote it a little messy (because of automatically generated pingback comments instead of hand-crafted comments). Is that OK?

I have the incentive and time to host and moderate the research thread and the discussion thread, but I’m unsure whether I started correctly. Please reply me with an explanation on how I may re-organize my blog posts. Maybe I should (when one of my projects will be officially selected) post two new blog posts to start the research thread and the discussion thread?

Or maybe, somebody other would host the discussion on the blogs? I feel not very important whether it will be done by myself or somebody other, but I feel I need to ask for a little guidance. Well, I feel indeed that I am able to be a good moderator for these my own projects.

Comment by porton — October 25, 2009 @ 7:20 pm |

Thanks for the contributions! Currently we are not planning any new projects on this blog in the near future, but this may change if one of the proposals picks up momentum of its own accord (this happened with the finding primes project).

The key seems to be to find a project which would already attract a significant number of interested (and capable) volunteers, but it’s not always easy to predict in advance what projects people find both (a) interesting, and (b) able to contribute to…

Comment by Terence Tao — October 27, 2009 @ 10:30 pm |

You’ve said: “The key seems to be to find a project which would already attract a significant number of interested (and capable) volunteers, but it’s not always easy to predict in advance what projects people find both (a) interesting, and (b) able to contribute to…”

My problems (see above) has the advantage that they (AFAIK) do not require any special knowledge. Every mathematician knows lattice theory. Not every mathematician knows number theory and computational complexity theory, which seem main competitors for my tasks.

Comment by porton — October 28, 2009 @ 6:09 pm |

I suspect it’s the “(a) interesting” part that an expository book on lattices will have trouble with…

Comment by Scott Morrison — October 29, 2009 @ 3:14 am |

I never suggested to write an expository book on lattices.

Among my suggestions there are a half expository half research book on filters on posets and generalizations thereof:

http://portonmath.wordpress.com/2009/08/29/polymath-filters-on-posets/

(Certainly it is related with lattices but isn’t an “expository book on lattices”.)

I’m not sure whether my theory of filters in interesting for general mathematical audience. (The theory of filters is mainly a technical not beautiful theory, however there I introduce some concepts which count to be beautiful, e.g. my theory of filtrators and related “core parts” and “dual core parts” is a beautiful part of the theory.) However the theory of filters is important for my further research “Algebraic General Topology”:

http://www.mathematics21.org/algebraic-general-topology.html

“Algebraic General Topology” is certainly a beautiful and interesting theory and I even hope to receive Abel Prize for that:

http://www.mathematics21.org/abel-prize.html

Comment by porton — October 29, 2009 @ 12:26 pm |

Hehe… from http://math.ucr.edu/home/baez/crackpot.html:

21. 20 points for suggesting that you deserve a Nobel prize.

I suppose the Abel prize will do, too.

Comment by Scott Morrison — October 29, 2009 @ 11:37 pm |

I might add that it’s not really up to Terry and me to select a project. If you want to start a project then you can. As the other replies above make clear, the main necessary condition for it to be successful is that you should attract the interest of other mathematicians. I think the best way of doing that is to give a more detailed post in which you say exactly what the project would be and what you don’t know how to do at the moment. If you have thought hard about the problems already, then you should be able to write an account that takes the reader to the point where you don’t know how to continue. Often a precisely posed problem that “ought to be doable” is exactly the hook that is needed for another mathematician to be interested. Have you got some of those?

If you do produce a detailed post, I will be happy to publicize it on my blog, and also on this blog.

Comment by gowers — October 29, 2009 @ 2:21 pm |

Dear Gowers, I’m now busy. (I work as a programmer.) When I will have free time I will write a longer explanation about “complementive filters are a complete lattice” problem

http://portonmath.wordpress.com/2009/08/30/proposal-conjecture-complementive-filters/

I’ve chosen it from the three problems because:

1) I feel it more important than two other problems, and there are other important problems to prove which it may be used (if true).

2) I can think more about possible ways to attack this problem than the two other.

Comment by porton — October 29, 2009 @ 7:37 pm |

Trying to write an exposition on the “complementive filters are a complete lattice” problem, I was going to write a proof of its certain special case. Trying to write this I noticed that I stumble over an open problem even in this special seemingly simple case.

This is the problem over which I stumbled:

http://portonmath.wordpress.com/2009/10/31/are-principal-filters-the-center-of-the-lattice-of-filters/

So I will attempt to settle this littler problem before going to the exposition of the original problem:

http://portonmath.wordpress.com/2009/08/30/proposal-conjecture-complementive-filters/

If the little problem over which I stumbled appears to be difficult also, I may offer it for a separate polymath project.

Comment by porton — October 31, 2009 @ 4:44 pm |

Oh, well. I already solved this “little problem”. Sorry for my comment in haste that it was unsolved.

The solution:

http://portonmath.wordpress.com/2009/10/31/principal-filters-are-center-solved/

To write a longer explanation of the “complementive filters are a complete lattice” conjecture remains my priority:

http://portonmath.wordpress.com/2009/08/30/proposal-conjecture-complementive-filters/

Comment by porton — October 31, 2009 @ 7:50 pm |

Dear Gowers,

I wrote a longer exposition about “complementive filters are a complete lattice” problem:

http://portonmath.wordpress.com/2009/11/02/exposition-complementive-filters/

I’m not sure whether it is in the state ready to be publicized. You may read it in order to test whether this my writing is understandable.

Also it contains a very short reference to the problem about coinciding quasidifference and second quasidifference. Should I write a longer explanation about that problem to attract more people? Or it is OK to just mention this problem because it is not the problem we are solving now?

Please say how well I wrote this and publicize if it is OK.

Comment by porton — November 1, 2009 @ 10:45 pm |

Dear Gowers,

I updated http://portonmath.wordpress.com/2009/11/02/exposition-complementive-filters/

adding there two new formulas as conjectures in the “Intersection with a set” subsection.

It is all I know about the “complementive filters are complete lattice” conjecture. I think this may be a starting point for other mathematicians who may be interested (personally I deem this an interesting problem).

I think that is does not extensively tells about “coinciding quasidifference and second quasidifference” is not a big defect, as it is an other problem and it may be not discussed here. Wiki reference where they may look for greater details on the full current state of that problem is available in this my exposition.

I ask you to publicize this my conjecture to be known for wider cycles of mathematicians. My blog visits are pretty low but this conjecture deserves wider attention.

Comment by porton — November 7, 2009 @ 9:17 pm |

I solved a problem which earlier proposed for one of polymath projects.

The problem was at

http://portonmath.wordpress.com/2009/11/29/co-separability/

See also this comment.

http://portonmath.wordpress.com/2009/11/29/co-separability/#comment-37

How to exclude the problem from the list of polymath proposals?

Comment by porton — January 18, 2010 @ 11:09 pm |

I’m interested in the platform for polymath. Clearly wordpress + wiki is not the desired model.

Are there any discussions of list of features one want from the platform?

Is it also possible to get financial support from any institution to develop such platform?

Comment by Mgccl — August 3, 2010 @ 4:11 pm |

I hope they have something betetr in the works but if that thing even has the whiff of Wave in it nobody will go near it. We’re still healing from that heavy Wave burn. I thought Wave was supposed to be the new Universal Inbox for all Google stuff. Great idea. Would’ve loved it. Poor execution killed it, I guess

Comment by Eton — May 28, 2012 @ 11:34 pm |

Why the last Terrence Tao’s proposal triggered 19 comment and my proposal triggered zero comments (despite of my proposal is online a longer time)? Is it just because Terry is more famous than me? Your mileage may vary but my question seems more interesting that Tao’s.

Comment by porton — June 5, 2012 @ 6:17 pm |

The polymathprojects.org site is poorly designed: On the homepage http://polymathprojects.org the image from “IAS Institute Letter for fall 2010″ (with the title in it: “Mathematical Advances: Lone or Massively Collaborative Endeavors” overrides with “Top Posts” in the right sidebar. This is despite of I have a 1280 pixels wide screen. I use Firefox for Linux.

[Corrected, thanks – T.]Comment by porton — June 10, 2012 @ 8:46 pm |

I’ve created Math Research Trends Wiki, a wiki with the motto “research in the middle” for sharing research ideas, stuff related to open problems, etc. (the rules are not yet exactly formulated, but I added several example entries which signify which stuff may be shared on this wiki). Please publicize announcements of this new wiki in your blogs.

Comment by porton — July 30, 2012 @ 8:23 pm |

Интернет магазин кофемашин cofemanoff кофемашина lavazza

Comment by OFFcofeMAN — March 1, 2013 @ 6:44 am |

I’ve created a site where anyone may list his projects and anyone may mark which projects he is going to participate. Projects are organized into a tree. The site supports LaTeX and has “Mathematics” section: http://theses.portonvictor.org/node/2

I have posted several pages on my math research project: http://theses.portonvictor.org/node/4 – feel free to add yours also.

The site is ideal for posting possible theses topics for students as well as cutting edge research for math persons. For a topic a user may mark himself as an adviser, which could help students.

Among mathematics this site is also going to list open source software proposals and whatever general utility projects.

Well, this project needs its own domain name. Please somebody donate a domain and help with hosting.

Comment by porton — April 29, 2013 @ 11:39 pm |

15. Collaborative Large-Scale Problem-Solving — Collaboration Platform/Community With Similar Goals to Polymath

I’m working on a project called Collaborating Minds, which has a lot in common with the Polymath project. Our founders followed the original Polymath project in 2009, and it shaped a lot of their thinking on online collaboration. (You can read some of their thoughts on the Polymath project and Michael Nielsen’s book here: http://www.cminds.net/2013/10/reinventing-discovery-and-collaborating-minds/)

Collaborating Minds is trying to do two things: 1) create a cloud-based platform that facilitates group problem-solving, and 2) foster a community of collaborative problem-solvers, people who who like to help and be helped, and who are willing to offer their perspective on a wide range of problems. To get a sense of what we’re doing, you can watch a short video here: http://www.cminds.net/2013/08/a-two-minute-and-12-second-introduction-to-collaborating-minds/

It would be great to hear from people who have been though Polymath and get your feedback on our model — if you think the community needs to come with the platform, any suggestions for fostering group collaboration online, or pitfalls to avoid. You can also email me at daphna@cminds.net if you prefer. Thanks in advance and let me know if there’s more information that I can provide as well!

Comment by dgcminds — January 9, 2014 @ 6:13 pm |

Hello Polymath. I hope you don’t mind me using this as a helpline. I have a very simple question that I hope someone here will be able to answer. I’ve tried elsewhere but not found a clear answer yet. Please note that I am NOT a mathematician, not even an amateur. Just a student of the primes. So please excuse any clumsiness in my words. I’m sure there’s a better way to say this,.

I think I can show that relative to the set of all primes up to N, where N is any finite number, there is an infinite quantity of consecutive twin primes. (Adjacent pairs of twin primes). Or, to put it another way, that no finite amount of prime factors is sufficient to guarantee that there are no more consecutive pairs of twins.

My question is: Would this be trivial or interesting? I keep changing my mind, and don’t have the skills to be sure either way. Perhaps it’s easy to show this and it’s been done a thousand times. I’d be grateful if someone can set me straight. Thank you.

If there is better place to discuss this I’ll happily move there.

.

Comment by guymax — April 13, 2014 @ 10:44 am |

hi,

this message is for people who’s interesting in PRIME numbers finding algorithm , i have developed an algorithm that can find all the consecutive impair composite numbers in a given interval , we can conclude that all impairs number remaing are prime,this algorithm gives the consecutive impairs composite and then we can conclude the twin prime numbers in any interval , the algorithm has been tested and it’s so efficient.i wanted to type

Comment by Anonymous — April 21, 2014 @ 6:51 pm |

the algorithm is defined by :“”

Comment by Anonymous — April 21, 2014 @ 7:10 pm |

Hi I am not a mathematician but while solving some mathematics, I came up with this problem of trace minimization..

The problem is as follows:

$\displaystyle\min_{V}$ trace(**$V^TH^T\Phi HV$**)$\\$ s.t. $V^TV=I_d$ when $H$ is some arbitrary matrix of size $N \times M$, full column rank matrix, $V$ is a $M \times d$ matrix and $\Phi$ is $N \times N $ symmetric and positive semidefinite matrix.

When $H$ is known, the solution is given by the eigenvectors corresponding to $d$ minimum eigenvalues of $ H^T\Phi H$.

Are there any ways or techniques or ideas already solved on this in the absence of $H$? The problem may sound simple to some of you but I am sorry about that.

Thank you for your suggestions and information about the existing techniques.

Comment by Jhanak — April 14, 2015 @ 10:05 am |