## Return to Question

5 added 9 characters in body

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, Int. J. Number Theory 2 (2006), no. 4, 499--522), 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, 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.

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)

4 added some more data

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)
        ````
```
        
            
                
                    
                
            
        
    ```
```
```
```
                        
                    ```
3 Fixed statement of Conjecture, added "update" summarizing my opinion of the two posted answers

Conjecture: If $A$ contains 0, is not periodic, and is uniformly

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, 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.

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.

2 restated problem for pithiness

Let $B$ be

There is a unique set $B$ of nonnegative integers with the property such thatevery positive $k$ integer can be written in the form$b+s^2$ (with $$b + s^2, b\in B$B, $s\in \mathbb{N}\cup\{0\}$) s\ge0$$in an even number of ways.How thick can

$B$ be? Must its counting function grow like B = \{0, 1, 2, 3, 5, 7, 8, 9, 13, 17, 18, 23, 27, 29, 31, 32, 35, 37, C n/\log(n)\$?

For every pair of sets 39, 41, 45, 47, 49, 50, 53, 55, 59, 61, 63, 71, 72,$$A,B$ of nonnegative integers73, set 79, 81, 83, 87, 89, 91, 97, 98, 101, 103, 107,$$ $r_{A,B}(k)=\left|\{(a,b) \colon a+b=k109, a\in A113, b\in B\}\right|.$$Now115, it's an elementary observation that if 117, 121, 127, 128, 137, 139, 149,$$ 0\in A$151, then there is a unique 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 (which we will call the reciprocal of $A$) so that $r_{A,B}(k)$ is even for all positive contains 0 has a unique set $k$; another way B$of saying this that may be preferred on Math Overflow is nonnegative integers so that$$\sum_{a\in $\left( \sum_{a\in A} q^a$$is a unit q^a \right) \, \left( \sum_{b\in B} q^b \right) = 1$$in the ring$\mathbb{F}_2[[q]]${\mathbb F}_2[[q]]$ of binary power seriesif and only if $0\in A$. Inverses are unique, so these two statements are truly We call $B$ the same thing.

Now for some context. reciprocal of $A$.

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

1

# How thick is the reciprocal of the squares

Let $B$ be a set of nonnegative integers with the property that every positive $k$ can be written in the form $b+s^2$ (with $b\in B$, $s\in \mathbb{N}\cup\{0\}$) in an even number of ways. How thick can $B$ be? Must its counting function grow like $C n/\log(n)$?

For every pair of sets $A,B$ of nonnegative integers, set $$r_{A,B}(k)=\left|\{(a,b) \colon a+b=k, a\in A, b\in B\}\right|.$$ Now, it's an elementary observation that if $0\in A$, then there is a unique set $B$ of nonnegative integers (which we will call the reciprocal of $A$) so that $r_{A,B}(k)$ is even for all positive $k$; another way of saying this that may be preferred on Math Overflow is that $$\sum_{a\in A} q^a$$ is a unit in the ring $\mathbb{F}_2[[q]]$ of binary power series if and only if $0\in A$. Inverses are unique, so these two statements are truly the same thing.

Now for some context. 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, Int. J. Number Theory 2 (2006), no. 4, 499--522), 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$ 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 identify $B$ except in the class 3 (mod 4).
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 77, "mathjax_display_tex": 8, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9171867966651917, "perplexity_flag": "head"}