+1!

]]>Sorry for this off-topic post, but over on the polymath blog it seems a very interesting conjecture has been proposed and found to be true. It concerns the vanishing of the infinite sum of a formula involving irreducible polynomials over F2. I’m frankly bubbling over with curiosity for a better understanding of the possible consequences. I was wondering if you might have any thoughts on any of the below questions? If not or this is just simply an inappropriate comment, please feel free to moderate it out of the queue.

1) What are the implications of finding this structure among the irreducible polynomials over F2? Are the implications limited because of being over F2 and because of being polynomials?

2) Is there likely to be any structure at all among the interaction terms? If so/not, what are the implications?

3) The prime numbers are often treated as if they are distributed randomly. Is there any sense in which the terms in this problem are considered to be distributed randomly, and if so, what does the “vanishing” mean in this context?

4) Are there any immediate or indirect consequences for sums over the integers (in particular over the prime numbers)? I’m guessing not, but is there possibly a field and a formula for which the primes vanish?

5) Again back to the randomness question, and still not quite understanding how the distribution of irreducible polynomials would be represented, does a result like this have any implications for separating pseudo-random sequences from truly random sequences?

]]>I would guess that MAXCUT is generically hard, though the few examples mentioned on Wikipedia don’t get to things of that type. I’m not really surprised that 3SAT is in GenP, given what we know about phase transitions for random instances.

]]>And I am libertarian enough to say that if people want to hold conferences with only women they are harming nobody and it should be allowed, regardless of motivation. Of course, I would see it as equally legitimate with a male-only conference which I suspect would be subject to a great deal of criticism. .

I am not a full libertarian, though, for somewhat the same reasons as Scott Alexander. I think it is very difficult to justify treating private property as sacrosanct, though I think there are excellent reasons to treat it with more respect than is done at the moment, and as for the libertarian anti-paternalism we can refute it by noting that no one would apply it to children and yet nothing magical happens when we turn 18 (or 20 or 17 or whatever) that suddenly makes us fully rational and independent. I would not want the government to treat us like children but a little paternalism, sometimes, can probably be good. (I do mean a little, I would let you use drugs, sell sex and drive without a seat belt, but not all at the same time.)

]]>One thing to note is that while there aren’t results about density in that sense since as Scott notes reductions don’t preserve density, there are some very weak bounds that sort of amount to this sort of thing if one is willing to go for much weaker than a claim about density. I think it is true that if there’s an NP-complete problem where there’s an algorithm which solves the problem in polynomial time with at most O(log n) exceptions, and it responds “I don’t know” to the exceptions rather than giving wrong answers, then NP=P. The proof is essentially the same as the proof that if NP is in P/log then P=NP.

Actually, question related to that for Scott: can we get this sort of result for some function that grows faster than O(log n)? We can if we weaken the conclusion from P=NP to the polynomial hierarchy collapsing (by using that NP in P/poly makes the hierarchy collapse) and that allows us also to make the algorithm be outright wrong on the exceptional values, but if we actually want P=NP as the conclusion (and not just hierarchy collapse or breaking ETH) is there any faster growing function we can do this for? It isn’t even obvious to me that we can do so for log n log* n.

]]>