MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.