There is a unique nonempty set $B$ of nonnegative integers such that
every positive integer can be written in the form
$$b + s^2, b\in B, s\ge0$$
in an even number of ways.


$B = \{0, 1, 2, 3, 5, 7, 8, 9, 13, 17, 18, 23, 27, 29, 31, 32, 35, 37,$
$ 39, 41, 45, 47, 49, 50, 53, 55, 59, 61, 63, 71, 72,$
$ 73, 79, 81, 83, 87, 89, 91, 97, 98, 101, 103, 107,$
$ 109, 113, 115, 117, 121, 127, 128, 137, 139, 149,$
$ 151, 153, 157, 159, 162, 167, 171, 173, 181, 183,$
$ 191, 193, 197,\dots\}$


Does the set $B$ have positive density?


Now for some context. Every set $A$ of nonnegative integers that contains 0 has a unique set $B$ of nonnegative integers so that
$$\left( \sum\_{a\in A} q^a \right) \, \left( \sum\_{b\in B} q^b \right) = 1$$
in the ring ${\mathbb F}\_2[[q]]$ of binary power series. We call $B$ the reciprocal of $A$.


As a consequence of a Euler's pentagonal number theorem, the reciprocal of the set $\{n(3n+1)/2 \colon n \in \mathbb{Z}\}$ is the set $\{ n \colon p(n)\equiv 1 \bmod 2\}$, where $p(n)$ is ordinary partition function. Almost nothing interesting is known about the parity of the partition function, but computationally it seems to be even and odd with equal frequency. This question arises out of an effort to put the parity of the partition function into some context.


In this article ([arxiv](http://arxiv.org/abs/math/0506496), [Int. J. Number Theory 2 (2006), no. 4, 499--522](http://www.worldscinet.com/ijnt/02/0204/S1793042106000693.html)), Josh Cooper, Dennis Eichhorn and I investigated the properties of $A$ that lead to $B$ having positive density, and all of our data and partial results can be summed up in the following conjecture:



> 
> **Conjecture**: If $A$ contains 0, 
>  is not periodic, and is uniformly 
>  distributed in every congruence class
>  modulo every power of 2, then $B$ has
>  positive density.
> 
> 
> 


Letting $A$ be the set of squares, we were able to prove that the even numbers in $B$ are exactly $\{2k^2 \colon k\ge 0\}$, and we were able to classify the $1\mod 4$ elements of $B$. 


**Update** Greg Kuperberg's answer concerning the conjecture displayed above is, while not quite a disproof, utterly convincing. So convincing, I can no longer understand how I thought the conjecture could plausibly be true. In [our paper](http://arxiv.org/abs/math/0506496), we described it as "the strongest conjecture that is consistent with our theorems, our experiments, and Conjecture 1.1", so I see we weren't too enthusiastic about its truth. We should have been even less so!


The question directly asked, the density of the reciprocal of the squares, remains unanswered. Paul Monsky has introduced a new (to me, at least) approach, and has made striking progress both in the answer below and in his answer to [this question](https://mathoverflow.net/questions/28462/why-are-there-usually-an-even-number-of-representations-as-a-sum-of-11-squares). 


I love Greg's answer to the question I didn't dare ask, and want to accept it, but Paul's is more directly relevant to the question I did ask.


Here are some computational counts of the number of elements of $B\cap[0,2^{23}]$ in particular congruence classes.



```
(1 mod 4, 371867), (3 mod 4, 760697)
(1 mod 8, 185336), (5 mod 8, 186531), (3 mod 8, 294045), (7 mod 8, 466652)
(1 mod 16, 92703), (5 mod 16, 93236), (9 mod 16, 92633), (13 mod 16, 93295),
(3 mod 16, 147232), (11 mod 16, 146813),
(7 mod 16, 204808), (15 mod 16, 261844)
(7 mod 32, 102487), (23 mod 32, 102321), 
(15 mod 32, 130895), (31 mod 32, 130949)

```

Since there was a specific request for 15 mod 32 data, here are the first 10 such numbers in $B$: (47,79,271,559,623,687,719,815,879,911). Here are the last 10 that I've computed: (8388539, 8388551, 8388559, 8388563, 8388567, 8388571, 8388581,
8388591, 8388593, 8388603, 8388607)



How thick is the reciprocal of the squares
In a related question, (Why are there usually..), O'Bryant characterized the elements of B that = 3 mod 8, and asked why the number of such that are at most X appears to be small; my
answer to his question showed that the number is O(Xloglog(X)/log(X)). In this answer I'll
sketch a proof that the same result holds for elements of B that =7 mod 16. (The remaining
case of elements that =15 mod 16 looks much harder). We need a characterization result:


Lemma : Let g in Z/2[[x]] be 1+x+x^4+x^9+.., the exponents being the squares. If n=16m+1,
the coefficient of x^n in 1/g^7 is 1 precisely when n is a square.


To see this let f=1+x+x^3+x^6+.., the exponents being the triangular numbers. Then xf^8+g=
g^4, so 1/g^7=(xf^8/g^8)+(1/g^4). Since n is odd, the coefficient in question is that of x^n
in xf^8/g^8, which is the coefficient of x^2m in f/g. My answer to my MO question, "Variations..", shows that this is 1 precisely when 2m is triangular, i.e. when n is a square.


Characterization result: Suppose k=7 (16). Then k is in B precisely when the number of ways of writing k as 2(square)+4(square)+square is odd.


Proof: 1/g=(g^2)*(g^4)*(1/g^7). So the coefficient of x^k in 1/g is the mod 2 reduction of
the number of ways to write k as 2(square)+4(square)+(the exponent,c, of a monomial
appearing non-trivially in 1/g^7). c must be odd, and since 1/g^7=g/g^8, c=1 (8). If
c=9 (16), then mod 16, 7=2(square)+4(square)+9, which is impossible. So c=1 (16), and by the lemma c is a square. Conversely if k=2(square) +4(square) +a square s, then s=1 (16), and the lemma shows that x^(s) appears non-trivially in 1/g^7.


Theorem: Suppose k in B=7(16). Then there are at most 2 primes occurring to odd exponent
in the factorization of k. So the number of such k in B that are at most X is O(Xloglog(X)/
log(X)).


(The proof is along the same lines as my answer to O'Bryants 11 square problem, but now one has to work with the ternary form x^2+y^2+2\*z^2 rather than Gauss' x^2+y^2+z^2).


