Are you interested only in the rate of convergence of a geometric series, or in the actual computation time involved in computing $\log n$? And if the latter, with respect to relative or absolute error? Fast means of computing $\log n$ are most likely to involve division by some power of $e$, since that can be computed to high accuracy rather quickly. (Or alternately, division by some power of 2 with a high-precision computed value of $\ln 2$ serving a similar role).

Actually, a very simple (counter)example: consider $u-2v=1 \bmod 5$ and $u-4v=1\bmod 7$. Then $(0, 2)$ and $(1, 0)$ are solutions to both.

@LSpice I don't think you can run the usual matrix methods since you can't necessarily take inverses mod $CC'$ and in fact the various terms that you're going to be working with ($AC'$, etc.) are all non-invertible mod $CC'$.

Are you sure that the conditions even guarantee a unique u/v pair?

You can at least get $S_n=\Omega(n\log n)$ by a simple argument based on the rectangles.

The easiest and possibly most consistent way to test if a set of binary sequences was human-generated is to just check the distribution of the number of 1 bits; humans cluster it much more closely around the mean than randomness would.

@DanRomik That depends entirely on how many digits we need. Since as Noam Elkies's answer notes we have waves of frequency $A_i=\theta(2^n)$, then to compute $A_it\bmod \pi$ we still need (as far as we know) $\theta(2^n)$ digits — i.e. exponentially many.

For instance (to use OP's suggestion), to get sufficient resolution for Monte Carlo integration to return a 'trustable' value we would have to sample roughly $\Omega(\sum_i 2^{A_i})$ points because of the Nyquist sampling theorem.

'We know excellent approximation[s] of $\pi$' doesn't matter in the asymptotic limit; we can't assume that we have 'all of' $\pi$ written down in advance so computing it has to be part of the calculation as well.

Note that all four supertiles satisfy the Conway criterion for tiling the plane, which prompts the obvious question as to whether there's a version of the criterion that applies in three dimensions; I feel like answering that question is a good (if hardly necessary) step towards answering this one.

Do you mean $\mathbb{C}^2$ or $\mathbb{R}^2$ (or $\mathbb{C}$)? I'm not familiar with a winding number for curves in the complex plane.

Is the norm you're using to define distance the one on $\mathbb{R}^{d+1}$ or $\mathbb{S^d}$? The two are certainly equivalent, but I would imagine that values that look awkward in terms of one should be at least a little cleaner in the other.

Pedantic but important point: everywhere you say 'in NP' I presume you mean to say 'NP-complete'. Unless I'm missing something obvious all these problems are in NP, but that says nothing about their hardness except to bound it from above.

For quadratics I think this should follow from periodicity of the continued fraction for $\alpha$.

(And the proof that they generate the free group is probably the canonical example of the Ping-pong lemma. )

More references can be found by searching; the best magic words I've found are 'Discrete Kronecker Weil Convergence', which turn up for instance this paper that seems likely to have some of the answers you're looking for.

Apologies — for some reason I'd gotten it in my head that your formula for multidimensional uniform distribution had an error bound in it, but it's just a statement on the limit and not the rate of approach. It appears that explicit rates of convergence are hard to come by and depend on some very fiddly irrationality properties of the specific $a_i$; see e.g. mathoverflow.net/questions/162875/….

Have you tried starting by bounding the distance between the CDF of $X_j$ and the uniform distribution?

While I agree with Iosif's answer that it's hard to say when to stop since it's not clear what your stopping criteria really are, I think it's worth noting that this is pretty close to a generalization of the Coupon Collector's Problem.