 View Question
Q: Math problem: integer based folding ( Answered ,   22 Comments ) Question
 Subject: Math problem: integer based folding Category: Science > Math Asked by: fouyang-ga List Price: \$50.00 Posted: 01 Oct 2002 16:48 PDT Expires: 31 Oct 2002 15:48 PST Question ID: 71364
 ```In an N-dimensional space, given N vectors v_i, i=1, 2, ... N. Consider a hyper-cube bounded by surfaces -0.5<=x_i<=0.5, i=1,2, ...N. (In the case of 2-dimensional, this would be a square of side length 1, centered at the origin.) What is the necessary-and-sufficient condition for the vectors {v_i}, so that any point p at the surface of such hyper-cube can be translated to be an interior point of the same hyper-cube, by adding a sum(d_i*v_i) to that point p. Here d_i is an integer (obviously cannot be all zero), depending on the point p. Note that the answer should be such that given a set of the vectors {v}, one should be able to tell if the condition is met by a computer program or an analytical method, with the number of operation steps proportional to N^k, with k being a small number. For example, an exhaustive search (even in a limited range) is not acceptable.``` Request for Question Clarification by haversian-ga on 03 Oct 2002 11:50 PDT ```What is your burden of proof for the proposed solution? Do you require a mathematical proof? Is there any style of proof you would prefer, vis induction, proof by contradiction, etc.? You mentioned an algorithm or computer program. Will you be designing this algorithm or program yourself, or do you require a step-by-step algorithm as part of the answer?``` Clarification of Question by fouyang-ga on 03 Oct 2002 14:13 PDT ```Clarification addressed to request from haversian-ga: The result should be proved mathematically. The result can be in the analytical form, which I prefer. If that is impossible, I can also take an algorithm or program approach, on the condition that it is not based on exhaustive search, and the number of steps is limited to a finite power of N. If you have a solution but cannot prove it, let me know and I will try to either verify it by simulation or prove it. If I am satisfied that the solution is correct, I will accept it.``` Subject: Re: Math problem: integer based folding Answered By: smudgy-ga on 03 Oct 2002 16:23 PDT Rated: ```Hi, Before approaching the problem, let's set up some notational conveniences: P=(x_1, x_2,.. x_n), an n-dimensional point on the surface of the hypercube. Note that for a point to be on the surface of a hypercube, at least one of these dimensions x_1 .. x_n must have value of .5 or -.5 and the others must be -.5<=x_i<=.5 N={1, 2, .. n}, the set of integers from 1 to n. V={v_1, v_2, .. v_n}, the set of n "candidate vectors" which we hope in some combination will move our point from the surface to the interior. D={d_1, d_2, .. d_n}, the set of integer coefficients which will multiply each corresponding vector, when translating the point P. Given a hypercube of dimension n of side length 1 centered about the origin, and given a set of "candidate vectors" V, it is our task to determine whether there exists a set D such that Sum(d_i*v_i), i=1..n will translate point P to the interior of the hypercube. Specifically we wish to know for which sets of candidate vectors V such a set D exists. Condition 1: It is a necessary condition that the set of vectors V be linearly independent. Proof: Assume (for purposes of contradiction) that any set of non-linearly independent vectors can do the task. An example should suffice to prove that this is not true: In the two-dimensional case, consider a point P at the coordinates (0, .5). Given the set of 2 vectors V={(.5, 0), (.25,0)}, it is clear that any linear combination of scalar multiples of these vectors will move point P only horizontally. As P is on the "top" edge of the square, it can never move into the interior through horizontal translation alone. Therefore, a non-linearly independent set of matrices is insufficient to translate a point to the interior. Computing analysis: To decide whether a set of n vectors is linearly independent in n dimensions, we create an n by n matrix A with the ith row of A being the ith vector in V. By either calculating the determinant of A or by putting A into row echelon form, we can decide whether A represents a set of linearly independent vectors. (If any rows of A, once put into echelon form, consist entirely of zeros, the system of vectors is not linearly independent.) According to reference (1), putting a matrix into row-echelon form is of the order n^3. Several other sources indicate that echelon-forming is a polynomial operation but do not give estimates as to the degree. Condition 2: No vector in V may have any dimension greater than .5 or less than -.5 I am having a harder time proving this condition. Proof idea: Let P be at any coordinates such that all but one of its coordinates is 0. The remaining coordinate is .5 (see the note about P at the beginning of this message). This is the most "difficult" point to move to the interior of the hypercube: the points at the center of each face of the hypercube will be the hardest ones to move to the interior. While, say, a point at a corner can move nearly 1 unit in each direction, the points at the center of the faces are limited to .5 unit movement in all but one dimension (see below). Without loss of generality assume that in the first dimension the coordinate's value is .5; i.e., P=(.5, 0, 0.. 0). Note that while P's final displacement can be -1 in the x_1 direction, it can move no more than +-.5 in any other orthogonal direction. Note that this statement generalizes to any P at the center of any face of the hypercube, with the appropriate dimension in place of x_1. Therefore the set of vectors we use must be able to move any of these hypothetical face-centered P points less than +-.5 in all directions. (In other words, the freedom of the vectors to move a particular face-centered point one full unit in some particular direction is negated by the necessity that another face-centered point may move no more than .5 in that direction) We could say that the vectors need the "finesse" to move a point (any point) no more than .5 in any direction. It is our task to decide what combination of vectors can acheive that. Lemma: I shall prove below that given n linearly independent n-dimensional vectors whose dimensions are all +-1 or 0, I can acheive a net translation of exactly 1 in any direction (or 1 in each of any combination of directions) I choose. Arrange the vectors into a matrix so that each row of the matrix represents a vector. Since the vectors are linearly independent, this matrix is nonsingular and through Gauss-Jordan elimination it can be reduced to the identity matrix. Note that since all entries in this matrix are 1 or 0, we will not have to multiply any row by a non-integer (in fact, we will not have to multiply any row by anything but -1 or 1) in the process of our reduction. By keeping track of the elementary row operations that lead to Reduced Echelon Form, we can come up with vector sums of the given vectors that yield the n unit vectors. By combining the "new" unit vectors (perhaps multiplied by -1) we can move our point exactly 1 unit in any dimension or dimensions that we wish. By "dividing everything" by 2, we will see that given proof will work for vectors whose dimensions are all +-.5 or 0. Therefore, we will be able to move .5 in any direction or directions we choose. So when the dimensions of the vector are each less than +-.5, we can move the point in any direction we choose in an amount less than .5 (although this proof does not provide a mechanism for calculating the proper vector sum in this case). By the lemma we have shown that vectors whose dimensions are each less than .5 can move any point P to the interior of the hypercube. It is my assertion (although I cannot prove it) that if any of the vectors have any dimension that is greater than or equal to .5, there exists a point P that cannot be moved into the interior of the hypercube -- any sum of integer products of the vectors will "overshoot" the interior of the hypercube. Computing analysis: The task of taking an inequality of each entry of n, n-dimensional vectors is n*n=n^2. I believe these are the only two conditions on V. Condition 1 guarantees that P can be moved in any direction necessary. Condition 2 guarantees that the vectors in V don't "overshoot" the interior of the hypercube. Total computing analysis: n^3 for checking linear independence of your vectors. n^2 for checking length of your vectors n^3+n^2-2x+3y-4z>1 which does not match the pattern for our inequalities: the inequality symbols must be "pointing" the same direction for us to add two of our inequalities together. To rectify this, we can simply rewrite the inequality as -1<-2x+3y-4z<0 represented in the matrix by the row -1 -2 3 -4 0 Hence, if we need to multiply a row by a negative in the process of RREFing our "vector matrix", we simply need to swap the first and last positions of the row after multiplying by -1 to make our new inequality fit the pattern of our other inequalities. This resolves most of my concerns about the solvability of the matrix described in the third algorithm. However, a few tests of this algorithm would certainly be in order to see if it behaves the way we expect it to.``` Request for Answer Clarification by fouyang-ga on 10 Oct 2002 05:32 PDT ```smudgy, I don't quite understand the details of your three solutions yet. But I'll try to make some comments on each one, as my contribution. The first solution: I don't understand what "intesection" means. Is it the cornor points of the parallelgram, or is it where the lines of the unit square meet the lines of the parallelgram? Perhaps a clarification would help me to understand the rest. The second solution: I agree that in higher dimensional case, we will need to consider all possible combinations. This is probably not a good course. The third solution: I'll have to go back to my textbook and think about the details. But intuitively it sounds too good to be true. I will be tied up tonight, so probably by Saturday morning I will have something more to say. I have two more suggestions for your consideration. First, is there a relationship between the area of the parallelgram (or volumn, in higher dimension case) and the determinant of the matrix formed by the vectors? If there is, that might help us. Second, notice that all linear combinations (with integer coefficients) of the orginal vectors are junction points of a parallelgram grid spaned by the original vectors. All we need to know is whether there are n linearly independent junction points inside the unit square. This can be done by actually constructing the grid and test each junction point. In n dimensional case, the complexity is still k^n. However, if we find a good way to construct the grids and to decide when to stop (i.e., all remaining grids won't be inside the unit square), then k can be a quite small number and we can still manage the complexity. Is this similar to your solution 1?``` Clarification of Answer by smudgy-ga on 10 Oct 2002 08:42 PDT ```fouyang, The algorithm you describe is essentially what I had in mind for algorithm 1. My use of the word "intersection" is intended to be the same as your use of the term "junction point". I cannot come up with a good method to correctly characterize the appropriately-sized parallelogram grid necessary to contain the square. But the size of each dimension of the grid (i.e., the number of copies of each vector that form the sides of the parallelogram) will be somehow related to the dimensions of the vectors. If we have, say, n=2, and vector v_1 is the shorter of the two vectors in the x-direction (say, 4*v_1 is greater than 1 in the x-direction but not 3*v_1) then we will need the v_1 dimension of our parallelogram grid to be 4 units long, probably longer. Likewise if, say, v_2 is shortest in the y-direction and 6*v_2 is greater than 1 in the y-direction (but not 5*v_2) We will need at absolute minimum the v_2 dimension of our parallelogram grid to be 6 units long. This is further complicated by the fact that v_1 and v_2 may form a very small angle between them, and to guarantee that the square will fit in the grid, we will need significantly more than 4 copies of v_1 and 6 copies of v_2. A little complication arises if a particular vector is the shortest in both dimensions, but the basic idea is the same overall, I think. Clearly, if vector v_1 is shortest in both the x and y directions, and it takes 6 v_1's to be bigger than 1 in the x direction, and 4 v_1's to be bigger than 1 in the y direction, we will need a minimum of 6 v_1's. Now the number of v_2's that would be necessary at minimum would be the number of v_2's it takes to be greater than 1 in both the x-direction and the y-direction. In practice, though, as mentioned above, you will need more than these minimum numbers in order to actually have your parallelogram grid contain the square. How much more than these minimums are necessary I'm not sure. In any case, there will certainly be a minimum number k for each vector that the grid needs to be larger than. Unless the vectors are all significantly long and almost perpendicular(possibly long enough and perpendicular enough to make it an impossible system), the size of the grid will have to be at least 2 for each vector (several examples have shown this to be the case to me, for sure). Now that means that for each edge of the parallelogram grid there will be at least 3 junction points, which means that we're talking a minimum of 3^n points to check, which isn't bad as exponential growth goes, but it's still exponential growth. Another complication comes in the fact that our square must be placed with one of its corners at a junction point of the grid. Not every parallelogram that contains the square will necessarily be the same as a parallelogram grid that contains the square with one of the square's corner at a junction point. As for your other query: There is a relationship between the area of a parallelogram and the determinant of a matrix: From Google's cache of http://www-math.mit.edu/~djk/18_013a/chapter04/section01.html (google search terms: determinant area parallelogram; google result #1) "Given three vectors in three dimensions we can form a 3 by 3 matrix of their components, and we will see that the absolute value of the determinant of that matrix is the volume of the parallelepiped whose edges are determined by the three vectors." and later, "In fact an analogous results holds for k k-vectors [including the 2d case - smudgy]: the absolute value of the determinant of the matrix of their components is the k-volume of the figure they bound." I am not sure how we can use the area of the parallelogram to our benefit. Certainly the area of the parallelogram must be greater than 1. However (similar to the problems listed above) a parallelogram can be very skewed and still have an area greater than 1. It may still be impossible to fit the square inside this parallelogram. I believe the computation time of the determinant should be on the order of n^3, as it is with gauss-jordan elimination. If we reduce our matrix, we get the identity matrix, which has determinant 1. Working backwards through our elementary row operations, we should be able to see how the determinant changes with each step and calculate the determinant of our original matrix. I agree that the last algorithm sounds a little too good to be true. If it works, we've reduced our search to testing inequalities for integer solutions. But this might serve the original hope I had intended for an algorithm -- that we don't need to find the actual linear combinations that yield the points to know whether the points exist, and that in not actually finding these combinations we might have eliminated the part of the search that was taking exponential time. I will continue to work on both of these algorithms. Here's hoping the last one is successful. PS: I have a lead on an "algorithms" textbook which should list the operation time of many of these operations (e.g., calculating determinant, RREF, etc) to give you a better idea of running time.``` Clarification of Answer by smudgy-ga on 16 Oct 2002 18:58 PDT ```Fouyang, Sorry about the lengthy response time. This is the official word from the higher-ups if you need to reference and attribute this answer in a publication: "The appropriate procedure, if the author wants to cite the question/answer, would be for him/her to email us so that we can clear this through appropriate channels. We'd need to know the nature of the publication and how the answer would be cited. Of course, he would have to include appropriate citation." Once you emailed the editors, they would clear it with me, and then they would respond to you with the go-ahead to use the citation. The email address for the editors of this forum is answers-editors@google.com It's been a pleasure working on this problem with you. Good luck with your work!``` Request for Answer Clarification by fouyang-ga on 17 Oct 2002 18:32 PDT ```Hi, smudgy, sorry to raise you again. But I think I found a very simple solution, and I'd like to share it with you. Make the original problem more general (actually one can prove that this is equivalent to the origninal problem): Given an N by N matrix V, find the condition for V such that for any vector x, one can find a vector d(x), with all components being integers, satisfying the inequalities 0<(Vd-x)_i<1 for each component. Convert the matrix V into a lower triangular matrix L: V=QL. We can convert the inequality to u<(Ld-y)1. Then we can use the second row of U to do the same, to find d_2, and so on and so forth. Therefore, the final necessary and sufficient condition is that for U, the inverse of V, the sum of the absolute value of the component in each row is larger than 1. This solution is inspired by your handling of the Gaussian elimination. So my thanks again. Do you know what other properties a matrix would have, if it has the above property?``` Request for Answer Clarification by fouyang-ga on 19 Oct 2002 06:05 PDT ```smudgy: Please ignore my two previous posts. I was completely wrong. One cannot linear-combine the inequalities like we did. A simple argument: if one inequality is strongly met (such as 0<100), the other is weakly violated (such as (0<-0.001), we can easily find two linearly independent linear combinations (such as (1)*1+(2)*2, (1)*1+(2)*3) that result in valid inequalities. However, this doesn't mean the original inequalities are satisfied. This also means the part of your solution, the Gaussian elemination, is invalidated as well. However, I think you've done enough for this problem. I don't think you are obligated to continue. By the way, you asked about my formal proof on the squares filling the parallelogram part. As you can see, I was side-tracked. Besides, I am still having problem with the necessary part of the proof. I believe there is an counter example in two-dimensional case. If we have two vectors (0.999,-0.5) and (0.01, 0.999), we can move any points into the unit square. However, we cannot construct two linearly independent vectors inside the square bounded by (0,0) and (1,1). In fact, I sort of believe that it is sufficient to have two vectors are in a square of side one. But the square does not have to have one corner at (0,0). As I said, you are officially off the case. But if you have a quick answer to my doubt, I'd appreciate.``` Clarification of Answer by smudgy-ga on 19 Oct 2002 07:28 PDT ```fouyang, First I will deal with your counterexample to our condition: I'm pretty sure you can't move every point on the edge of the square to the edge/interior with this pair of vectors. Consider a point on the square that is ,4 units up from the bottom-left corner. As you stated, there are no linear combinations of the vectors that will move any surface point to the interior, but your first vector will move your point .1 unit below the square, and your second vector will move it .599 units above the square.So your vectors V are not sufficient to move all points of the surface to the interior. I still have a lot of faith in our condition as stated. However, in trying a couple of examples with the inequality method of solving for D, I agree that it doesn't seem to work. I feel like there must be some way to make a similar method work. The problem seems to be that (in the two-dimensional case) choosing a value for d_1 sets further boundaries on the value of d_2, beyond those determined by the inequalities. Though maybe this method has another use-- perhaps it can help us determine the size of the parallelogram grid we need to search, though in what way I am not sure (this is a totally intuitive leap...). I am pretty certain that our condition on V is valid both in the necessary and sufficient directions. I'd love to hear about further successes/complications.```
 fouyang-ga rated this answer: ```The problem turned out to be more difficult than both of us (the researcher and I) thought originally. However the researcher persisted. After several tries, we eventually arrived at a satisfactory answer. Besides his knowledge and skill, the researcher deserves commendation for his dedication and friendliness.``` Subject: Re: Math problem: integer based folding From: math_zip_at_yahoo-ga on 02 Oct 2002 20:05 PDT
 ```I know the result. However, I am not a Researcher of Google, but a mathematician. Dr. math_zip```
 Subject: Re: Math problem: integer based folding From: rbnn-ga on 03 Oct 2002 16:32 PDT
 ```Condition 2 in the answer provided is incorrect. The simplest counterexample occurs for N=1 and V={v_1} where v_1= [ 0.8 ] . Each point on the surface of the given 1-d hypercube (namely the points -.5 and .5) can be translated to the interior by translating by 1 v_1 or -1 v_1 .```
 Subject: Re: Math problem: integer based folding From: smudgy-ga on 03 Oct 2002 18:19 PDT
 ```I know that there are certain specific instances where my conditions can be looser, but I am pretty sure that, particularly in the higher dimensions, the conditions (as given) are necessary for an arbitrary P. Though the counterexample does give pause for thought.```
 Subject: Re: Math problem: integer based folding From: rbnn-ga on 03 Oct 2002 21:14 PDT
 ```Not sure then what the claim is, as there are counterexamples to the claim as stated. I've spent some time thinking about this problem and it looks tricky to me!```
 Subject: Re: Math problem: integer based folding From: rbnn-ga on 03 Oct 2002 21:24 PDT
 ```Specifically, if by statement: "I am pretty sure that, particularly in the higher dimensions, the conditions (as given) are necessary for an arbitrary P." answerer intends to imply that condition 2 (that all the coordinates be less than or equal to .5) is necessary in order for the translation property on surface hypercube points to hold in higher dimensions, then this new claim is also incorrect, and for the same reason as the original claim was incorrect, which I described in my comment. The counterexample I gave in my comment was chosen as the simplest one, hence I chose it for one dimension. That is why I said it was "the simplest counterexample". If you want counterexamples in higher dimensions, just extend the reasoning in the same way. For example, the simplest counterexample in higher dimensions to the condition you state is when v_1= .8 e_1 and v_k = .1 e_k for k>1, where e_k is a unit vector parallel to the k'th coordinate axis.```
 Subject: Re: Math problem: integer based folding From: smudgy-ga on 04 Oct 2002 04:47 PDT
 ```rbnn-ga: Is there an exception that does not rely on vectors orthogonal to the axes? If not, we could add a condition stating "If the vectors are orthogonal to the axes and of length less than 1, then it works. Otherwise..." The orthogonal cases are almost "degenerate" -- they are clearly a lot simpler to solve than non-orthogonal cases. Or perhaps the orthogonal case implies a modification to the statement in my clarification (not proven or used in my proof), "the sum of all elements of V had to have a total of less than .5 in each dimension". Maybe the limit on the dimensions should be 1. I'm still working on this one.```
 Subject: Re: Math problem: integer based folding From: rbnn-ga on 04 Oct 2002 08:39 PDT
 ```smudgy-ga asks: "Is there an exception that does not rely on vectors orthogonal to the axes? " Yes, the claim of condition 2 fails also for nonorthogonal sets of vectors.```
 Subject: Re: Math problem: integer based folding From: rbnn-ga on 07 Oct 2002 14:00 PDT
 ```fouyang - I'm still looking into this. Personally I doubt that such an algorithm exists; however, did you ever hear from math_zip and, if he had a correct answer, could you post it here? Also, I would be interested in how this problem arose; this might assist in finding the answer.```
 Subject: Re: Math problem: integer based folding From: rbnn-ga on 10 Oct 2002 22:47 PDT
 ```This is an interesting problem but I don't quite understand what's going on. I think the latest theorem is that posted on 04 Oct 2002 23:00 PDT I do not understand the claim in the "Theorem" or the subsequent algorithms and proof. What does the phrase "where each dimension of each of the linear combinations is less than or equal to 1" mean? Even if the stated theorem were well-defined or correct, I don't understand the discussion in the following (*); that is, I don't understand what specific claim is being made about what characterization of the set V is necessary in order to determine whether all points on the surface can be moved to the interior. I do agree however that an exponential solution of this problem is possible.```
 Subject: Re: Math problem: integer based folding From: smudgy-ga on 11 Oct 2002 07:59 PDT
 ```rbnn, So we are trying to decide whether a particular set of n vectors V can translate an arbitrary point on the surface of an n-hypercube to its interior, under integer linear combinations only; that is, the translations can only be comprised of integer multiples of the vectors. So far we have decided that it is a necessary and sufficent condition that for the n-dimensional case, there must exist n linearly independent integer linear combinations of elements of V that move one corner of the hypercube to the interior. We believe that if this is the case, then any point on the surface of the hypercube will be able to be moved to the interior. Hopefully our proofs bear that out. (Perhaps fouyang can post more details about his version of the proof for those interested?) The notion that this is the case is motivated by the idea of a "parallelogram grid". If we form a grid of copies of the vectors of V, and we overlay this grid on the hypercube, then if there is always at least one junction point of the grid on the strict interior of the hypercube, then we will definitely be able to perform the translation. For if the point P is placed at a junction point of the parallelogram grid, there must be one junction point of the grid on the interior of the hypercube. We can then clearly translate P to this point through integer linear combinations. The last remaining question is to determine whether it is possible to decide whether n such integer linear combinations of V exist, if we are handed the set of vectors V. Hopefully given the set V we can decide whether there are enough linear combinations in polynomial time. Hopefully fouyang's proof of the condition will nullify the need for (*) and subsequent parts of my version of the proof; my proof was turning out to be very inelegant. The concentration now is on finding an algorithm to determine whether the necessary linear combinations exist. I hope this resolves some of your questions. If not, please reply by all means.```
 Subject: Re: Math problem: integer based folding From: rbnn-ga on 11 Oct 2002 12:32 PDT
 ```I'm still confused. You write: "So far we have decided that it is a necessary and sufficent condition that for the n-dimensional case, there must exist n linearly independent integer linear combinations of elements of V that move one corner of the hypercube to the interior." This statement, however, is false. For n>1, let V consist of the multiples .8 *e_i, where e_i is the i'th unit vector for i=1,...,N. Then any point on the surface of the hypercube can be translated to the interior by an integer linear combination of elements of V, but for any corner point there is exactly 1 integer linear combination of V that translates that corner to the interior. Therefore, it is false that the given condition is necessary. Can you repost a correct formulation of your claim?```
 Subject: Re: Math problem: integer based folding From: fouyang-ga on 11 Oct 2002 15:39 PDT
 ```rbnn-ga and math_zip_at_yahoo: rbnn-ga asked me whether I have heard from math_zip about his solution. It seems to me that he does not want to post it here in public. But I don't know how to contact him directly. I posted a comment with my contact info and asked him to contact me. However that was deleted by Gooble "to protect my privacy". Do you have any ideas? You also asked about where did the problem come from. This problem rose when I am doing some research in data communications techniques. It has to do with generalizing a commonly used precoding technique. I don't mind telling you and everyone of interest what the original problem is. However, it is hard to do without graphic capability. Perhaps we can exchange the information -- or even cooperate -- on the subject. But again, we need a way to communicate directly.```
 Subject: Re: Math problem: integer based folding From: smudgy-ga on 11 Oct 2002 16:03 PDT
 ```rbnn: I believe a simple change from "n linear combinations sending it to the interior" to "1 to the interior and n-1 to the interior or edge" (or something along those lines) will suffice. But you raise a good point. Clearly some playing around with loose inequalities/strict inequalities is in order.```
 Subject: Re: Math problem: integer based folding From: fouyang-ga on 11 Oct 2002 17:53 PDT
 ```rbnn and smudgy: It is actually my fault concerning the loose and strict inequalities. The orginal problem should have been stated as "moving to interior OR SURFACE" of the hypercube. The reason I didn't mention surface was to avoid the trivial solution of not moving at all. Looking back, there are better ways to exclude the trivial solution. So we should restate the problem and make our lives easier.```
 Subject: Re: Math problem: integer based folding From: rbnn-ga on 11 Oct 2002 19:53 PDT
 ```Ah; I suspected the problem came from coding theory; although I'd have expected we'd be dealing with discrete and not real coordinate values. (I've written a few papers in which hypercube geometry played a major role, but that was a long time ago). I doubt that the change of allowing nonzero translations of a point to the surface will make the problem easier, however.```
 Subject: Re: Math problem: integer based folding From: rbnn-ga on 11 Oct 2002 19:54 PDT
 ```smudgy-ga: Thank you for explaining a bit your comment. However, I am still not sure what your exact claim is.```
 Subject: Re: Math problem: integer based folding From: smudgy-ga on 12 Oct 2002 08:21 PDT
 ```rbnn: OK, thanks to fouyang's revised version of the problem (move any point on the surface to some point on the interior or surface, not the trivial transformation) then I believe that we can state the necessary and sufficient requirements precisely: Given a set of n linearly independent vectors V, there exists an integer linear combination of the elements of V (not all 0*v_i) which translate arbitrary point P on the surface of the n-hypercube to another point on the surface or in the interior of the hypercube if and only if there exist n or more linearly independent integer linear combinations of V that translate a given vertex of the hypercube to another point on the surface or in the interior of the hypercube. That is, the integer linear combinations of V that we find to translate the corner point (call such a resulting vector w and each of its dimensions w_i) has to have each of its components w_i follow the inequality 0<=w_i<=1, w_i!=0 for at least one value of i. (Up to multiplication of w by -1). This condition automatically eliminates any translation that would send P to itself. By the condition that not all coefficients of v_i are 0, then we can't simply use the trivial transformation. By the condition that v_i are linearly independent, none of the elements of V can be the 0 vector (and thus get around the "not all coefficients of v_i are 0" condition) since there are only n of these vectors. This condition (because of the modified problem conditions) also eliminates your counterexample in R_2, because not only would the linear combination v_1+v_2 send the lower-left corner point of the square to the interior, but v_1and v_2 would each independently send the corner point to another point on the edge of the square. fouyang: The inequalities mentioned in the third algorithm should now have loose inequalities on both "sides." (I missed the loose inequalities on the left before.) Afterwards you will need to check that one of your solutions is not "multiply each vector by 0".```
 Subject: Re: Math problem: integer based folding From: fouyang-ga on 12 Oct 2002 11:59 PDT
 ```MISSION ACCOMPLISHED!!! smudgy, I think the Gaussian elimination is good. The solution is still of complex k^n, because one need to go over all possible integers that satisfy an inequality, in the search of an integer set that satisfies all inequalities. However, as I hoped, k is probably small, and we can probably terminate many trellises at early stages. So I will accept the solution. My next step is to find a way to find a way to pinpoint the solution. Namely, given a vector set of N vectors v_1, v_2, .. v_n, and a point p=sum(a_i*v_i), 0<=a_i<=1 is a scalar. I need to find a set of integers {d_i}, so that p-sum(d_i*v_i) is in the unit hypercell. So far we have the conditions for {d} to exist. Next, I will need to find it. Doing this will also provide a regorious proof of the sufficiency of the condition (wish you credited to me, but I still think it is a little hand-waving). Of course this is beyand what I originally asked for. So I don't expect you to work on it. However, if you have any off-hand suggestions, I'd appreciate it. smudgy, I just wish to thank you for the persistent work which brings along the results. I am going to give the best rating to this answer. It was a pleasure working with you. As I mentioned before, I will use the result in one of my research projects (outside of my employment). If it results in a paper or something, is there a way to credit you fo it?```
 Subject: Re: Math problem: integer based folding From: rbnn-ga on 12 Oct 2002 23:53 PDT
 ```smudgy-ga: Thank you for the latest comment of the characterization of admissible V; I think I understand it now, and it does seem to be a useful characterization, and I couldn't find any counterexamples. I appreciate your taking the time to explain it, as it's a nice problem.```
 Subject: Re: Math problem: integer based folding From: rbnn-ga on 01 Nov 2002 01:30 PST
 ```Happened to see this paper (actually thesis) on the shortest vector problem in lattices; it's relevant: http://citeseer.nj.nec.com/rd/38894833%2C263966%2C1%2C0.25%2CDownload/http://citeseer.nj.nec.com/compress/0/papers/cs/12112/http:zSzzSzwww.matha.mathematik.uni-dortmund.dezSz~fvzSzdiplom_izSzmic98b.ps.gz/micciancio98hardnes.ps```
 Subject: Re: Math problem: integer based folding From: fouyang-ga on 02 Nov 2002 12:37 PST
 ```rbnn, Thanks for the pointer. I started reading it, it does sound relevant. Thanks again.```
 Subject: Re: Math problem: integer based folding From: fouyang-ga on 12 Nov 2002 18:00 PST
 ```rbnn and smuggy: I contacted the author of the thesis that rbnn pointed out for me. It turns out that this problem is a classical math problem, called minimum covering radius. It is frequently encounted in coding research (along with the packing radius problem). It seems from my search of the web, that there is no general solution. People are still working on upper bound and lower bound for specific types of lattices. Just thought you might be interested to known.``` 