# Representing vertices of a cube using linear combination of tensor product of smaller cubes

Let $n,N \in \mathbb{N}$ with $N \ge n^{2}$.

Let $F[i] = \square[i]$ refer to the cube which has vertices from $\{-1,0,1\}^{n^{i}}$ ($n^{i}$ tuple of alphabets from $\{-1,0,1\} = \square[0] = F[0]$)

Let $\{Q_{i}\}_{i=1}^{n^{2}}$ and $\{P_{j}\}$$_{j=1}^{N} be points over F[4] and F[2] \otimes F[2] respectively. Let Q, P and \Lambda be matrices of size n^{2} \times n^{4}, N \times n^{4} and n^{2} \times N respectively with entries from F[0]. The rows of Q and P be the points \{Q_{i}\}_{i=1}^{n^{2}} and \{P_{j}\}$$_{j=1}^{N}$ respectively.

Let $Q$ be known ($P$ and $\Lambda$ are unknowns) in the following equation:

$\Lambda P = Q$

What is the minimal size of $N$ so that one can expect a compatible $\Lambda$ and $P$ for a generic $Q$? Are there good lower and upper bounds for $N$?

What tools could be useful to study this problem?

With respect to Yemon Choi's comment: Regarding algortihms, a naive algorithm would run in worst case $3^{2Nn^{2}}$ complexity since it has to iterate over all possible values of of $F[0]$ as candidate entries of $\Lambda$ and $P$ for each given $N$ to check if there is a compatible solution. Even for $n=3$, this is formidable. Is there a faster algorithm to decide existence of compatibility for a given $N$? Could the cube to sphere relaxation help reduce complexity while giving something satisfactory?

Are there any textbooks or papers that handle something similar to this?

-
I replaced $F_{3}^{n^i}$ which is not a field by $F_{3^{n^i}}$ which is a field. Hope this is what you meant. – Mark Sapir Dec 5 '11 at 5:33
@Mark Sapir: Actually I was thinking of the former one, since I do not know how I would define a tensor product in the former one non-trivially (I may be wrong on this but I meant the former one). – user16007 Dec 5 '11 at 5:54
@unknown - if you are not using the field structure, then just stick with it being a vector space, and call it such. – David Roberts Dec 5 '11 at 6:33
Then it is not a field, right? A direct sum of fields has zero divisors. – Mark Sapir Dec 5 '11 at 6:34
"What tools could be useful to study this problem" - what did you have in mind? Algorithms? Textbooks? Papers in Inventiones? – Yemon Choi Dec 5 '11 at 10:36