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.

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

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

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

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

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.

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

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

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)?

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