I think that your conjecture is not true and I can outline
[Edit: I'm rewriting a reason.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 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?
