I said:
That proves the observation above: u(2p) = 2^p+2.
I have to go and do other things now. Anyone want to finish this off? :-)
Apparently not! I can prove a slight generalization: if p,q are distinct primes then u(pq) = 2^p+2^q-2. Proof: constructing that many 0-sum sets is easy: take any set of things mod p, add every multiple of q, giving 2^p sets; likewise with p,q interchanged, giving 2^q more; but we've counted {nothing} and {everything} twice, so we've found 2^p+2^q-2 different sets. It remains to show that that's all of them. As before, split any 0-sum set A into A(0), ..., A(p-1) according to the vertex number mod p. I'm claiming that we get two sorts of 0-sum set: ones where all the A(j) look the same, and ones where all the A(j) are either {nothing} or {everything}. Write a(j) = sum of A(j), and generally adopt the notation of my earlier comments. Then from a(0)+a(1)w+...+a(p-1)w^{p-1}=0 we see that w(pq) satisfies a polynomial of degree at most p-1 over F(q). The degree of w(pq) over F(q) is p-1, so this isn't terribly hard. But, aha, there's only one polynomial (up to multiplication of the whole thing by a constant) of degree p-1 with coeffs in F(q) of which w(pq) is a root. You can find it by taking the minimal polynomial for w(pq) and collecting together terms whose exponents are equal mod p. Hence, we have two possibilities. - Each a(j) could be 0. There are u(q)^p = 2^p ways to do this. - The a(j) could be proportional to the coefficients of the minimal polynomial of w(pq) over F(q). How can that second possibility actually occur? Let's suppose the following is true (which it is): - The only instance in which two subsets of P(q) have the same sum is the familiar one: {nothing} and {everything} both have sum 0. (Proof of this lemma: if two such subsets have equal sum then that gives us a polynomial of degree <= p-1, with coefficients in {-1,0,+1}, that vanishes at w(p); there is only one such polynomial even if we allow coefficients to be arbitrary rationals, namely 1+w+...+w^{p-1}; this indeed produces the sets {nothing} and {everything}.) Then pick any non-zero coefficient in that minimal polynomial; say it's the coefficient of w^j. Choose the set A(j) freely, except that it can't be {nothing} or {everything}; then all the other A(k) have known non-zero sum and there's therefore at most one choice for each. We're done, *provided* we always can find a choice for each other A(k). Well, the minimal polynomial of w(pq) is well known by those who know such things. I'm not really such a person, but Google knows everything (all hail Google!) and it turns out that the coefficients are always 0, +1 or -1. So all we need to know is that if any number is achievable as the sum of some vertices of P(q) then so its its negative, which is straightforward since the sum of *all* vertices of P(q) is 0. So, indeed, we are done, and u(pq) = 2^p+2^q-2 when p,q are distinct primes. Noting that the first n whose cyclotomic polynomial has coefficients other than -1,0,+1 is 105, I conjecture that u(105) might have a value one wouldn't predict from naive extrapolation from earlier values. Not that I'm sure what value one *would* predict from naive extrapolation. This all seems like harder work than it should be. Isn't there some straightforward line of attack that just does all values of n at once? :-) -- g