How thick is the reciprocal of the squares - MathOverflow

How thick is the reciprocal of the squares

2010-06-02T16:23:47Z

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)

Answer by Greg Kuperberg for How thick is the reciprocal of the squares

2010-06-21T23:24:40Z

[Edit: I'm rewriting a lot in response to comments and clear shortcomings and errors in the earlier versions of the answer.]

As in your paper, let's express the sequences as binary power series $a(x)$ and $b(x)$, so that their relationship is the equation $a(x)b(x) = 1$. (I am just changing your variable from $q$ to $x$.) My conjecture is that if you choose $b(x)$ at random with slowly decreasing density, then with probability 1, the reciprocal $a(x)$ is uniformly distributed in every congruence class modulo every $n$. In fact, I conjecture a lot more, that $a(x)$ is indistinguishable from uniformly random according to a variety of local statistical checks.

It's important to consider a few statistical principles of random bits. First, given a finite list $L$ of random bits, all of the joint correlation information them is expressed by the biases of sums of subsets of the bits in $L$; these biases are a Hadamard transform of the joint probability distribution of the bits. In particular, of all of these sums are unbiased, then the bits in $L$ are independent and unbiased. Second, if you define the bias of a bit $b$ to be the expectation $E[(-1)^b]$, then these biases multiply when you add independent bits. Third, if $L$ is a finite list of bits and the average bias of $a+b$ for a pair of bits $a$ and $b$ in $L$ is low, then about half of the bits in $L$ are 0 and about half are $1$. If the size of $L$ goes to $\infty$ and the average bias $a+b$ goes to $0$, then in the limit $L$ almost surely has density $1/2$.

Consider first a toy model in which $b(x)$ is random as in the previous paragraph, and $a(x) = b(x)c(x)$, where $c(x)$ is some specific power series such as $$c(x) = 1+x+x^4+x^9+\cdots.$$ Let's suppose that the $x^n$ coefficient of $b(x)$ is 1 with probability $1/\ln (n+3)$ (say). Then $a_n$, the $x^n$ coefficient of $a(x)$ is a sum of independent biased bits. There are easily enough terms in the sum that the bias of $c_n$ converges to 0 as $n \to \infty$. Moreover, instead of one term $a_n$ you can look at the bias of $a'= a_k+a_n$ with $k,n \gg 0$. Again, the bias is low because there are contributions from many independent bits. The relevant calculation shows that $a(x)$ has density $1/2$ almost surely. A more refined calculation shows that the bits of $a(x)$ are also equidistributed modulo $n$ for any $n$, moreover that local substrings of the coefficients of $a(x)$ of a fixed length look random.

In the real problem, $a(x)$ is given by the functional equation $$a(x) = b(x)a(x^2).$$ This is more complicated, but $a(x^2)$ can still play the role of $c(x)$. In particular, we can say that the $x^n$ coefficient of $b(x)a(x^2)$ is a sum of simple and compound terms, where by definition the simple terms use $b_k$ with $k > n/2$. These random variables do not influence $a(x^2)$. What I think happens is that the sum of the simple terms is a bit with very low bias, and the bias cannot be boosted by adding any hypothetical combination of compound terms. And, as in the toy model, you can take pairs of bits $a_n+a_k$ with $n, k \gg 0$. Assuming that $n > k$, $a_n$ contains simple terms that do not appear in $a_k$, and this is enough to give their sum a low bias. Statistics of substrings is yet another complication, but I again think that a more complicated version of the same idea should show that $a(x)$ is equidistributed, etc.

Of course the above is not a rigorous argument that a random $b(x)$ gives you a counterexample. To further support the point, I wrote a Sage program to find the distribution mod 32 of the bits of $a(x) = 1/b(x)$ out to degree $2^{20}$, taking $P[b_n = 1] = 1/\sqrt{n+1}$.

bits = 2^20; radix = 32
R.<x> = PowerSeriesRing(Integers(2))
b = R([int(random() < 1/sqrt(n+1.)) for n in xrange(bits)]) + O(x^bits)
a = list(1/b)
distrib = [0]*radix
for n in xrange(len(a)):
    if a[n]: distrib[n%radix] += 1
print distrib`

Here is the output:

[16444, 16354, 16342, 16396, 16391, 16065, 16227, 16449, 16478,
16325, 16447, 16220, 16418, 16400, 16374, 16344, 16394, 16369,
16326, 16251, 16324, 16421, 16379, 16364, 16124, 16422, 16422,
16374, 16469, 16531, 16370, 16441]

If the above sketch works, it also motivates this question: Suppose that a number $0 \le x \le 1$ is chosen at random with independent but biased digits in base $b$. For concreteness suppose that the digits are all $0$ or $1$ and that the density goes to 0 sufficiently slowly. Then is $1/x$ at $b$-normal number almost surely?

Answer by paul Monsky for How thick is the reciprocal of the squares

2010-07-09T15:28:36Z

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

Answer by paul Monsky for How thick is the reciprocal of the squares

2010-07-13T15:26:34Z

O'Bryant et. al. showed that the elements of B in 12 of the congruence classes mod 16 form a set of density 0. In my answer to this question and 2 other questions I used a result of Gauss to show that the k in B that are 3, 7 or 11 mod 16 also form sets of density 0. So only the case of k congruent to 15 mod 16 remains.

NEVERTHELESS, I believe that the above results are somewhat accidental, and that a k congruent to 15 (16) is "just as likely to be in B as out of it" so that the density of B is 1/32. Here are the back-up data, provided by Kevin, for k<2^23.

k=15 (64): 2*(65536) elements, 65446 in B

k=31 (64): 2*(65536) elements, 65247 in B

k=47 (64): 2*(65536) elements, 65449 in B

k=63 (64): 2*(65536) elements, 65702 in B

Readers are invited to make further calculations, but the above are highly suggestive.