View Question
Q: Integer solutions to ax + by +cz +dw <= e ( No Answer,   9 Comments )
 Question
 Subject: Integer solutions to ax + by +cz +dw <= e Category: Science > Math Asked by: es74-ga List Price: \$45.00 Posted: 18 Jun 2006 19:47 PDT Expires: 18 Jul 2006 19:47 PDT Question ID: 739236
 ```I am interested in a formula for the number of non-trivial integer solutions (an O(1) method, not enumeration) to arbitrary equations of the form ax + by + cz + dw <= e where a,b,c,d,e,x,y,z,w are all integers greater than or equal to zero, and a, b, c, d, e are provided I have been trying to understand this in 2-dimensions (ax + by <= e), before trying to generalize to higher dimensions. So far even that has not been helpful. For example, 3x + 7y <= 23 would have 19 integer solutions I know that the equation ax + by = c with integer solutions is considered Diophantine, however I have been unable to comprehend how to generalize this to an inequality. For some sets of numbers, the number of solutions for the 2-dimensional subset can be determined by: ( (floor(C/A)+1) * (floor(C/B)+1) ) / 2 Unfortunately, this is not true even for all numbers in the two-dimensional case.``` Clarification of Question by es74-ga on 22 Jun 2006 16:16 PDT ```It appears that I underestimated the complexity of the research for this problem. I've increased the amount to compensate I suspect that this is a solved problem, it's just far enough outside of my mathematical background I don't know the terms to hunt down the proper research. I hope for results that are comprehendable with an undergraduate mathematical background.``` Clarification of Question by es74-ga on 22 Jun 2006 16:18 PDT ```The solution that I am looking for would be one that requires constant time for a given dimension, regardless of the parameterization. The summation approach does not have that property.```
 Answer
 There is no answer at this time.

 Comments
 Subject: Re: Integer solutions to ax + by +cz +dw <= e From: anhebetude-ga on 19 Jun 2006 17:46 PDT
 ```Hopefully a math-oriented researcher will find a more elegant solution or confirm (or even dispute) my offered answer. I began to solve this problem by going the long way for the first two cases, before catching on to the inductive pattern. I present only the inductive method, because the 'long way' is exceedingly cumbersome to type out. You'll probably want to rewrite everything by hand to make sure that you understand the dependent sums (and to make sure I didn't make any huge mistakes), as they seem pretty confusing typed out like this. I also suggest not moving on to the next case until you're satisfied that each one is true. Case 1 (one dimension): A*x<=E. Number of solutions: floor(E/A)+1. Case 2 (two dimensions): A*x+B*y<=E Number of solutions: Case 1 + sum(for r from 0 to floor(E/A), floor((E-r*A)/B)). Case 3 (three dimensions): A*x+B*y+C*z<=E Number of solutions: Case 2 + sum(for r_1 from 0 to floor(E/A), for r_2 from 0 to floor((E-r_1*A)/B), floor((E-r_1*A-r_2*B)/C)). Case 4: A*x+B*y+C*z+D*w=E Number of solutions: Case 3 + sum(for r_1 from 0 to floor(E/A), for r_2 from 0 to floor((E-r_1*A)/B), for r_3 from 0 to floor((E-r_1*A-r_2*B)/C), floor((E-r_1*A-r_2*B-r_3*C)/D )). Yours, anhebetude```
 Subject: Re: Integer solutions to ax + by +cz +dw <= e From: es74-ga on 21 Jun 2006 13:53 PDT
 ```anhebetude, I believe that your method with summation does give the number of solutions. Unfortunately, I cannot see how to calculate the Summation without actually calculating each term. This has complexity that scales with the number of variables - O(N) for 2 variables, O(N^2) for 3 variables and so forth I need a solution that doesn't have this behavior. What seems to indicate there is a shortcut formula is the behavior of cases like: 4x + 9y <= 31 y = 3, Floor[(31 - 27)/4] = 1 y = 2, Floor[(31 - 18)/4] = 3 y = 1, Floor[(31 - 9)/4] = 5 y = 0, Floor[(31 - 0)/4] = 7 Number of solutions is 1 + 3 + 5 + 7 ( + 4 to include the 0's), 20 However, this has the shortcut of: ( Floor(31/9)+1 * Floor(31/7)+3 )/2 = 20 There are pairs that this works for without such a nice even 1,3,5,7 pattern. What I am looking for would be something along the lines of this method that's more generalizable, both to all 2-variable cases, and then for 3 and 4 dimensions if possible Alternatively, giving me reason to believe that this is impossible would probably suffice```
 Subject: Re: Integer solutions to ax + by +cz +dw <= e From: anhebetude-ga on 22 Jun 2006 14:42 PDT
 ```I've tried playing with the properties of the floor function to reduce the sums, but doing so begins to impose conditions upon the values of a, b, c, and d. There are a number of interesting mathematical papers available under a search for properties of the floor function, but I despair of finding an elegant solution from the starting point of what I've posted above. I've begun to think that an elegant solution to this problem could exist as a sort of lattice point problem. The number of solutions would correspond to the number of integer coordinates (x,y,z,w) within a convex volume defined by a, b, c, d, and e and centered on the origin. In the one dimensional case, ax<=e, the number of solutions corresponds to the number of integers along a line segment beginning at 0 and extending to e/a. In the two dimensional case, ax+by<=e, the number of solutions corresponds to the number of integer ordered pairs (n,m) within or on the boundary of the area of an ellipse x^2/(e/a)+y^2/(e/b)=1 in the positive-positive quadrant. In the three dimensional case, the number of solutions corresponds to the number of integer ordered triplets in the positive-positive-positive octant of an ellipsoid, whose equation could be determined. A similar solution, but harder to visualize, would exist for the ordered quadruplets in a sixteenth of a four dimensional volume. Determining the number of integer coordinates within a volume is, however, something of which I am wholely ignorant. I plan to search the web for methods and I'll let you know what I find. -anhebetude```
 Subject: Re: Integer solutions to ax + by +cz +dw <= e From: anhebetude-ga on 22 Jun 2006 14:59 PDT
 ```A brief search yielded a plethora of information on integer lattices and convex geometry and estimates for points within an ellipsoid geometry has convinced me that I am out of my league. Good luck. -anhebetude```
 Subject: Re: Integer solutions to ax + by +cz +dw <= e From: es74-ga on 22 Jun 2006 16:03 PDT
 ```You have me confused when you mentioned ellipsoids? For the 2 dimensional case, I got a right-triangle at the vertex, with the hypotenuse being the line y = -ax/b - c/b (Well, not really, because it's y = Floor[-ax/b - c/b] -- it seems similar to the computer graphics mapping of an ideal line into pixels, so "lattice points" looks promising) The 3-dimensional case appears to be a pyramid (from a cube sliced by a plane) I must be missing something with this approach. I hadn't figured out such complexity from this problem - I thought it was just something I'd forgotten from math classes long ago.```
 Subject: Re: Integer solutions to ax + by +cz +dw <= e From: anhebetude-ga on 22 Jun 2006 20:47 PDT
 ```This will likely be my last post on the topic, because I need to get back to focusing on my job instead of daydreaming about math problems while I'm at work. I've had the epiphany that the number of non-negative solutions to a linear diophantine inequality of four variables (ax+by+cz+dw<=e) has a 1 to 1 correspondence with the number of non-negative solutions to a linear diophantine ^equality^ of five variables (ax+by+cz+dw+v=e). This means that any solution to your inequality must have the same level of complexity as it takes to find the numbers of solutions to a linear diophantine equation. After looking at a few methods on the web, several appear to follow the same steps as I did in my original comment, or were designed for mathematical software. This leads me to believe that there is no simpler way. Perhaps you have been thinking of the non-negative integer solutions for x+y+z+w<=e. Which does have a nice simplification of: (e+4)!/(e!*4!). At any rate, with the increased price, it is likely that the official researchers will take another look at the problem. -anhebetude```
 Subject: Re: Integer solutions to ax + by +cz +dw <= e From: anhebetude-ga on 07 Jul 2006 06:40 PDT
 ```You may want to try browsing Dr. Math at the math forum. Here he has explicitly solved for a diophantine equation in three variables using a method I hadn't thought of and that should be easily extended to your case of a diophantine equation in five variables (remembering that a diophantine inequality in 4 variables has a 1 to 1 correspondence with solutions to diopantine equalities in 5 variables). http://mathforum.org/library/drmath/view/66870.html I didn't find anything like your exact question in the math forum archives, but you may want to consider asking this question of Dr. Math. http://mathforum.org/dr.math/ Good luck, anhebetude```
 Subject: Re: Integer solutions to ax + by +cz +dw <= e From: es74-ga on 07 Jul 2006 07:20 PDT
 ```Thank you! I have submitted my question and am crossing my fingers. I am still lost on how to go from diophantine solutions in 3 dimensions to solve the inequality in 2 (for example)?```
 Subject: Re: Integer solutions to ax + by +cz +dw <= e From: anhebetude-ga on 07 Jul 2006 13:47 PDT
 ```Ax+By<=E For any x=m, y=n that satisfies the inequality, define p=E-Am-Bn. Note that Am+Bn+p=E. Therefore, for each (m,n) solution to the inequality, we have created exactly one (m,n,p) solution to the equality. This gives a 1 to 1 relationship between the (x,y) solutions of Ax+By<=E and the (x,y,z) solutions of Ax+By+z=E (notice that the coefficient of z will always be 1). Going backwards: Ax+By+z=E Ax+By=E-z Since E-z<=E, then Ax+By<=E, but the 1 to 1 relationship is best established going from the inequality to the equality. anhebetude```
 Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service. If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for

 Google Home - Answers FAQ - Terms of Service - Privacy Policy