

Subject:
Integer solutions to ax + by +cz +dw <= e
Category: Science > Math Asked by: es74ga List Price: $45.00 
Posted:
18 Jun 2006 19:47 PDT
Expires: 18 Jul 2006 19:47 PDT Question ID: 739236 

There is no answer at this time. 

Subject:
Re: Integer solutions to ax + by +cz +dw <= e
From: anhebetudega on 19 Jun 2006 17:46 PDT 
Hopefully a mathoriented 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((Er*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((Er_1*A)/B), floor((Er_1*Ar_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((Er_1*A)/B), for r_3 from 0 to floor((Er_1*Ar_2*B)/C), floor((Er_1*Ar_2*Br_3*C)/D )). Yours, anhebetude 
Subject:
Re: Integer solutions to ax + by +cz +dw <= e
From: es74ga 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 2variable 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: anhebetudega 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 positivepositive quadrant. In the three dimensional case, the number of solutions corresponds to the number of integer ordered triplets in the positivepositivepositive 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: anhebetudega 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: es74ga on 22 Jun 2006 16:03 PDT 
You have me confused when you mentioned ellipsoids? For the 2 dimensional case, I got a righttriangle 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 3dimensional 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: anhebetudega 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 nonnegative solutions to a linear diophantine inequality of four variables (ax+by+cz+dw<=e) has a 1 to 1 correspondence with the number of nonnegative 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 nonnegative 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: anhebetudega 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: es74ga 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: anhebetudega on 07 Jul 2006 13:47 PDT 
Ax+By<=E For any x=m, y=n that satisfies the inequality, define p=EAmBn. 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=Ez Since Ez<=E, then Ax+By<=E, but the 1 to 1 relationship is best established going from the inequality to the equality. anhebetude 
If you feel that you have found inappropriate content, please let us know by emailing us at answerssupport@google.com with the question ID listed above. Thank you. 
Search Google Answers for 
Google Home  Answers FAQ  Terms of Service  Privacy Policy 