Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
1  
@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
1  
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
show 4 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.