Ahhh! Somehow I missed that and thought you were talking about arbitrary sized cubes as well as orientations; mea culpa. Do you have a pointer to the coverings of R^3 that you mention? I'm trying to mentally grasp the mechanism there.

What would 'sharing a face' mean in the context of distinctly sized cubes? The faces being identical, or one being a subset of the other?

Isn't this exactly the same as the construction Eric Naslund gives in his answer?

Surely $S=\{\langle 0,0\rangle, \langle 1,0\rangle, \langle 3,0\rangle\}$ can't tile $\mathbb{Z}\times\mathbb{Z}$ by translation? If it could then $\{0, 1, 3\}$ would translate $\mathbb{Z}$ by translation and this is clearly impossible.

You might want 'NP complete' — there are after all no problems known to be in NP and not in P...

You might want to see if you can chase down a copy of The Sensual Quadratic Form from John Conway; it talks about reductions of quadratic forms and gives various tree/hyperbolic structures that I suspect are germane to the transformation you give. There's also en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples which may have some relevance, of course.

The question title and the body of the question refer to entirely different sequences.

Because it took me a moment to convince myself: the finiteness argument is that there's a $\epsilon$ such that for any position $P$ of the runner, a positive fraction of movement vectors $x$ have both $P+x$ and $P-x$ at least $\epsilon$ further from the origin than $P$, and therefore for any distance $d$ a positive probability of getting a sequence of moves (of length $\lceil d/\epsilon\rceil$) that force the runner to distance $d$ from the center.

I was just about to mention Löb's theorem in a comment!

(Speaking of which, I think your product in the q-Binomial theorem is slightly off? As written, the first term on the RHS is 2 which is clearly not the constant coefficient of the LHS.)

Doing the same for $n=4$ gives $(q+1)(q^2+1)(q^3+1)(q^4+1)(q^5-q+1)$ which is starting to look very suspicious. Letting $\mathrm{Bin}[n]_q$ be the q-binomial product, this looks to possibly be $\mathrm{Bin}[n+1]_q-q\mathrm{Bin}[n]_q$? (ETA: modulo a potential off-by-one error, of course)

For what it's worth, assuming I haven't typoed then plugging the $n=5$ into Wolfram Alpha, expanding out and then factoring gives the result $(q + 1)^3 (q^2 + 1) (q^2 - q + 1) (q^4 + 1) (q^4 - q^3 + q^2 - q + 1) (q^6 - q + 1)$ which certainly has a number of nice factors at least ($[3]_{-q}$ and $[5]_{-q}$ stand out); recombining these I see $(q+1)(q^2+1)(q^3+1)(q^4+1)(q^5+1)(q^6-q+1)$ which is very crisp looking. Where'd you come across this?

You're correct that the generalization is relatively straightforward, but there are two substantial complications that arise: (1) if given the convex polytope as an intersection of half-spaces rather than being explicitly given the cellular decomposition, then computing the vertex and adjacency information is known to be Hard in its own right; (2) the calculations to compute the individual simplex volumes require essentially finding the (n-1)-volume of each face and when you recurser down the simple methods for doing this take O(d!) time to handle a d-dimensional polytope.

They're definitely not equivalent — it just seems to me that the question with individual values rather than differences is a little more 'natural' and I was curious how you came to this one.

Are there specific reasons to look at a difference set rather than e.g. $\sup\min\min|\lambda x_i-n|$?

I'm about 75% sure you can encode SAT in this and that this is therefore NP-hard.

I'm hard-pressed to see the relation between primality and chirality — it's true that the representation of a number as a product exhibits a specific achiral polyomino of that number, but it's easy to show that any $N$ whether prime or not has a chiral polyomino, and likewise easy to show that any $N\gt 3$ whether prime or not has a non-trivial achiral polyomino.

Doesn't a classical algorithm per force have to look at all the points of the domain, since every boolean function on $n$ variables is representable as a degree-$n$ polynomial? That means that you can't beat $2^n$ queries and I suspect that the time to determine degree from that set is at worst polynomially bounded in the number of points, so you're looking at 'just' exponentially many operations to go with your exponentially many queries.

@Guoqing I'm not sure I see how you can integrate $f()$ without knowing $n$ — after all, it's in the very definition of $f$!