Ask HN: Has this open math problem received attention from computer scientists?

2 points by impendia 14y ago ↗ HN

Define a covering to be a set of residue classes a (mod m) such that all the integers are covered.

Example: 0 (mod 2), 0 (mod 3), 1 (mod 4), 5 (mod 6), 7 (mod 12) is a covering, because every integer belongs to one of these five residue classes.

Here are two famous open problems, due to Paul Erdos and John Selfridge.

(1) For each integer N, does there exist a covering where the moduli are all distinct integers at least N?

(2) Does there exist a covering where the moduli are all distinct odd integers (excluding 1)?

I just listened to a math seminar talk on the subject. Apparently most work on the subject involves a lot of brute force and consideration of special cases, see e.g. [1].

To me, this seems like more of a CS problem than a math problem. My colleagues didn't really believe me, but my optimism wasn't deterred. That said, I only have a little CS background. I wonder if there exist algorithmic approaches to the problem, using perhaps advanced techniques from AI such as neural nets.

Do any HN readers know of any work done on this problem from an algorithmic perspective, or know enough to express optimism or pessimism with any authority?

Thanks to all.

[1] http://www.wiskundemeisjes.nl/wp-content/uploads/2009/02/sdarticle.pdf

2 comments

[ 3.4 ms ] story [ 12.1 ms ] thread

ColinWright 14y ago ↗

So looking at the first question, you do a computer search, or use some sort of neural net to find a covering for every integer up to N.

What about N+1? Or N+2? You've done finitely many cases, and there are infinitely many left to do.

So you do another 10^12 cases.

There are still infinitely many left.

How are you going to use a computer to prove that for every N there is a covering?

The second question, maybe you can find a solution using a machine, but the problem is hard. I personally doubt you can find a solution without genuine new insights, even if eventually a solution is found by a computer using a program written by someone who understands those insights.

The proof of the four color theorem was, in the end, just a big computer search, but the insights mattered.

impendia 14y ago ↗

Thanks for your replies.

First of all, it would already be interesting to find a covering with all integers > 100. Obviously, as you point out, a computer program cannot be expected to prove this for every N.

However, it is not clear that the answer to either of my questions should be yes. It seems it should be possible (?) to come up with an impossibility proof by computer.

Certainly new insights are required as you say, and nobody expects a brute force search to work. I am wondering whether the important insights might come from people with serious CS background.