Another question that seems like it would be interesting to ask is about the 'balanced' version of this; $2-3+5-\ldots+\frac{(-1)^n}{2}P_n$ - or, essentially, removing the (almost-certain) first-order term from your estimate. It's unlikely that the result has any specific limiting behavior (for instance, I would be surprised if it doesn't alternate sign infinitely often), but it might be possible to talk about almost-everywhere bounds and/or smoothed behavior.

For the most part; the one concern I see is in the spacing, since there's no guarantee of uniformity across the range. Still, it looks like the core concept - there are only polynomially many numbers in an exponentially-sized range, so you can't expect any sort of density of the sort needed here - is a solid one.

(Wait, silly mistake on my part - the dyadics aren't a subgroup under multiplication, only addition, as e.g. the inverse of $\frac32$ isn't in this group. The group of powers of 2, of course, isn't dense in $\mathbb{Q}^+$.)

This doesn't make sense to me - it seems like the measure has to be at least $1$, since for every $q$ there's some $p$ with $\left|\frac pq-x\right|\lt\frac1q$. Certainly this holds for e.g. the dyadics.

As a note, you might try this over at cstheory.SE

@TheMaskedAvenger On the contrary, BBP is quate practical for arbitrary digits - I believe it was a spigot-style algorithm that was used to compute around the quadrillionth bit (see bbc.com/news/technology-11313194 for more details)

@ChrisGerig you're thinking too quick again: $\mathbb{Z}_2\times\mathbb{Z}_2$ works because the rotations (by $\pi$, of course) on the two axes commute with each other; when you go to $\mathbb{Z}_3\times\mathbb{Z}_3$ this no longer holds for the rotations by $\frac{2\pi}{3}$, and so e.g. products like $abab$ don't correspond to $a^2b^2$. (In fact, I believe the group you provide is actually the octahedral group $O$, of even order.)

Your $B$ is not a convex set; in fact, for any two points $a, b\in B$ the line between $a$ and $b$ is not contained within $B$. If you instead define $B=\{(x, y) x\geq 0 \wedge y\geq 0\wedge xy\geq c\}$ then $B$ is convex, but that definition may not satisfy your needs.

In your 'random configuration' comment, I think you mean either $0.61$ or $61\%$, but $0.61\%$ is a very small number indeed...

@SamHopkins Obviously, it's possible that there's some magic construction that helps in arbitrary dimensions; OTOH, the problem definitely gets 'harder' in the sense that there are more adjacencies, both relative to the grid size $n$ but also relative to the total number of cells $N=n^d$, as $d$ increases; this implies that there are more 'chances' for things to go wrong.

@Konrad Ahh! Your last statement has actually clarified something for me: the difference between $\leq_0$ and $\leq_1$ is qualitatively different than the difference between $\leq_1$ and $\leq_2$. You're missing an implicit 'exists' in $\leq_1$; $\leq_0$ is (I believe) the statement that "if a cardinal $c$ is a $\theta$ then it is also a $\sigma$", but $\leq_1$ an existential statement: "the consistency of ZFC + 'there exists a $\theta$' implies the consistency of ZFC + 'there exists a $\sigma$'". This is structurally different despite the abuse of notation that makes them look similar.

How do you iterate your Con() operator past $\omega_1^{\mathrm{CK}}$? My understanding is that there's no clearly-defined notion past about that point; mathoverflow.net/questions/153272/… isn't quite the same, but the iterated-consistency operator there should be much stronger than even the one here...

This seems very likely to be related to the continued fraction representation of the two numbers, possibly with periodicity related to their periodicity?

Another version of this is the 'batting average' problem, as it appears in Knuth's The Art of Computer Programming (vol. 2): what's the fewest number of at bats a baseball player can have if their average (rounded to 3 decimals) is .334? (The solution proceeds by computing the CFs for $.3335 = 667/2000 = [0; 2, 1, 666]$ and $.3345 = 669/2000 = [0; 2, 1, 94, 1, 1, 3]$ - the correct answer is then found by finding the fraction for the 'simplest' number in that range, $[0; 2, 1, 95]$ - namely, $\frac{96}{287}\approx 0.334495$.)

You might have more luck over on CSTheory, but at least one starting point: AFAIK, the proof of IP=PSPACE (and in particular, the inclusion of PSPACE in IP) doesn't relativize; it works by finding an interactive proof for a specific PSPACE-complete problem.

@PeterShor Maybe I'm missing something (and my references are at home), but does the fact that the braid groups are automatic give an efficient solution to this problem? (e.g. by chopping the knots up suitably and using the various results on neighborhoods of words in automatic groups)

Avoiding the exponential explosion here is commonly known as stratified sampling and you might have some luck searching under that term.

I think the source of that perspective may be that ordinals somehow 'feel' much tamer than other sets - we have a clean well-ordering on them, etc - even though of course in practice they can be remarkably complicated themselves.

FWIW, for practical purposes I'd compute normals approximately 'by hand', using the central approximation to each of the partial derivatives and evaluating $C(x_0\pm h, y_0)$ and $C(x_0, y_0\pm h)$.