MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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 the stronger property a lot more, that for every fixed polynomial (not power series) $p(x)$, 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$a(x)p(x)$has density L$ of random bits, all of the joint correlation information them is expressed by the biases of sums of subsets of the bits in $1/2$. (At least I think that that's L$; these biases are a stronger propertyHadamard transform of the joint probability distribution of the bits. Anyway I conjecture both properties.) As 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 warmupbit$b$to be the expectation$E[(-1)^b]$, then these biases multiply when you add independent bits. Third, let's consider 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 asLet's suppose that the$x^n$coefficient of$b(x)$is 1 with probability$1/\ln (n+3)$(say). Then$c_n$, a_n$, the $x^n$ coefficient of $c(x)$ a(x)$is a sum of independent biased random variables in$\mathbb{Z}/2$, and when you add these variables, their biases multiplybits. (This point is clearer if you let$C_n = (-1)^{c_n}$. Then$C_n$is a product of independent random variables whose expectations multiply.) There are easily enough terms in the sum that the bias of$c_n$converges to 0 as$n \to \infty$. The same is still true if Moreover, instead of one term$a_n$you replace can look at the bias of$c(x)$by a'= a_k+a_n$ with $c(x)p(x)$ 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 polynomial$p(x)$. Now in our case 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 equationThis 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 expect 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 equally well look at take pairs of bits $b(x)a(x^2)p(x)$ for a polynomial a_n+a_k$with$p(x)$. In factn, k \gg 0$. Assuming that $n > k$, even though it $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, it could be more favorableetc.In
Of course the toy model, if you thicken above is not a rigorous argument that a random $c(x)$, b(x)$gives you can correspondingly thin$b(x)$. In a counterexample. To further support the real problempoint, I wrote a Sage program to findthe density distribution mod 32 of$a(x^2)$comes from the density bits of$a(x)$, which then further dampens the bias of later coefficients of a(x) = 1/b(x)$ out to degree $a(x)$.2^{20}$, taking$P[b_n = 1] = 1/\sqrt{n+1}$. bits = 2^20; radix = 32R.<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]*radixfor n in xrange(len(a)): if a[n]: distrib[n%radix] += 1Here 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, then 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?        2 added 406 characters in body I think that your conjecture is not true and I can outline a reason. 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 the stronger property that for every fixed polynomial (not power series)$p(x)$,$a(x)p(x)$has density$1/2$. (At least I think that that's a stronger property. Anyway I conjecture both properties.) As a warmup, let's consider 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$c_n$, the$x^n$coefficient of$c(x)$is a sum of independent biased random variables in$\mathbb{Z}/2$, and when you add these variables, their biases multiply. (This point is clearer if you let$C_n = (-1)^{c_n}$. Then$C_n$is a product of independent random variables whose expectations multiply.) There are easily enough terms in the sum that the bias of$c_n$converges to 0 as$n \to \infty$. The same is still true if you replace$c(x)$by$c(x)p(x)$for any polynomial$p(x)$. Now in our case$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 expect 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 equally well look at$b(x)a(x^2)p(x)$for a polynomial$p(x)$. In fact, even though it is more complicated, it could be more favorable. In the toy model, if you thicken$c(x)$, you can correspondingly thin$b(x)$. In the real problem, the density of$a(x^2)$comes from the density of$a(x)$, which then further dampens the bias of later coefficients of$a(x)$. If the above sketch works, then it 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? 1 I think that your conjecture is not true and I can outline a reason. 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 the stronger property that for every fixed polynomial (not power series)$p(x)$,$a(x)p(x)$has density$1/2$. (At least I think that that's a stronger property. Anyway I conjecture both properties.) As a warmup, let's consider 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$c_n$, the$x^n$coefficient of$c(x)$is a sum of independent biased random variables in$\mathbb{Z}/2$, and when you add these variables, their biases multiply. (This point is clearer if you let$C_n = (-1)^{c_n}$. Then$C_n$is a product of independent random variables whose expectations multiply.) There are easily enough terms in the sum that the bias of$c_n$converges to 0 as$n \to \infty$. The same is still true if you replace$c(x)$by$c(x)p(x)$for any polynomial$p(x)$. Now in our case$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 expect 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 equally well look at$b(x)a(x^2)p(x)$for a polynomial$p(x)$. In fact, even though it is more complicated, it could be more favorable. In the toy model, if you thicken$c(x)$, you can correspondingly thin$b(x)$. In the real problem, the density of$a(x^2)$comes from the density of$a(x)$, which then further dampens the bias of later coefficients of$a(x)\$.