2

Given a linear diophantine equation like

$$\sum_{i=1}^na_ix_i=b$$

with $x_i$ as variables and $a_i$ and $b$ as fixed integer parameters, I want to count the number of solutions that satisfy the conditions $x_i\in[\theta_L,\theta_H]$ for all $I$. Note that the interval is the same for all $i$. How can I do it?

I expect this number to be finite and countable but I don't know how to obtain it. Any help will be extremely appreciated, thanks!

EDIT: Ok I will be more specific. This is for an economic model and by assumption of the model $a_i>0$ (they are quantities). As for the upper and lower bound of the variables, if there exists some specific case of $[\theta_L,\theta_H]$ such that we can count the number of solutions, like the one you proposed $[-n;n]$ please post it! So what I mean is, if by making some restrictions in the parameters I can count the number of solutions, please propose it.

Rodrigo de Azevedo
  • 1
Riccardo
  • 83
  • Are $\theta_{L}$ and $\theta_{H}$ just upper and lower bounds? – Ethan Splaver Jan 23 '14 at 22:30
  • Yes. They are the same for all variables. For example $[\theta_L,\theta_H]$=$[1,4]$ – Riccardo Jan 23 '14 at 22:50
  • Provided that $\theta_i \ge 0$ and $a_i \ge 0$, for having at least one solution it must be that: $$\theta_L\sum a_i \ge b \ge \theta_H\sum a_i$$

    Moreover if $$\theta_L\sum a_i = b$$ or $$\theta_H\sum a_i=b$$ I have only one solution. Out of this interval there are no solutions. I also know the maximum number of solutions that is somewhere within the interval and is less or equal than $r^n$ where $r$ is the number of possible values $x_i$ can take in $[\theta_L,\theta_H]$.

     – Riccardo Jan 24 '14 at 00:28
  • You’re effectively asking to count the number of points in a lattice in a given bounded region. This is a hard problem to solve exactly, but much easier to approximate (just figure out the volume of your slice and divide by the area of a minimal cell in the lattice). Davenport formalizes this (https://people.math.sc.edu/thornef/math788g/davenport-lemma.pdf) – Eric Sep 01 '23 at 05:41

2 Answers2

0

Clearly the number of solutions is finite. The number of solutions is bounded by $r^n$ where $r$ is the number of possible values $x_i$ can take in $[\theta_L, \theta_H]$. As the number of solutions, this heavily depends on the coefficients $a_i$ and $b$.

A few examples : if $x_i\in[0,1]$ and $a_i>0$ for all $i$ and $b<0$ then it cannot have any solution as the left hand side is always positive while the right hand side is always negative.

Another example : $x_1 + x_2 = 0$ for $x_i\in[-n,n]$, then it has $2n+1$ coupled solutions of the form $(x_1,x_2) = (k,-k)$ for all $k\in[-n,n]$.

My point is that you can find an upper bound to how many solutions you have but you won't find a general formula in terms of all the parameters and possible range of $x_i$.

For specific $a_i$, $b$ and $[\theta_L, \theta_H]$, you should try to find a parametric solutions, that is in term of another variable (like I did with $k$ in my second example). If you can do so, then you will be able to count how many solutions you have as this will be the number of values your parameter can take.

user88595
  • 4,549
  • Ok I will be more specific. This is for an economic model and by assumption of the model $a_i>0$ (they are quantities). As for the upper and lower bound of the variables, if there exists some specific case of $[\theta_L,\theta_H]$ such that we can count the number of solutions, like the one you proposed $[-n;n]$ please post it! So what I mean is, if by making some restrictions in the parameters I can count the number of solutions, please propose it. – Riccardo Jan 23 '14 at 22:42
  • There are still many ways of doing this... I can't possibly write everything down. What you need to check is that $\theta_L\sum a_i \ge b$ for at least a solution to exist. Then the number of solution will depend on how much bigger the LHS is compared to the RHS. I think, if you diregard $\theta_H$ (although this needs to be checked) that the number of solution will be something like $\dfrac{n!}{(n-m)!}$ where $m = \theta_L\sum a_i - b$. You need to understand how to calculate these. I suggest you try a few easy example on your own and try to find a pattern. – user88595 Jan 23 '14 at 23:05
  • It may be that either $b$ either $\theta_H$ is not binding. I will try to check but unfortunately as an economist I'm not so familiar with number theory. - EDIT - Perhaps it should be $\theta_H\sum a_i \ge b$ for at least a solution to exist, if $a_i$ are positive? – Riccardo Jan 23 '14 at 23:19
  • Yes I think we should impose also $\theta_L \ge 0$..... – Riccardo Jan 23 '14 at 23:28
  • Yes you're right about $\theta_H$! My apology. – user88595 Jan 24 '14 at 00:07
0

I was able to derive an algorithm to extract all solutions that satisfy the constraints in the general case. However I'm still not able to count that solutions.

For simplicity let consider the case with three variables: $$ax + by + cz = z$$ with $x,y,z \in [\theta_L, \theta_H]$. If the g.c.d. condition it is satisfied, it is possible to derive a parametric solution, using various algorithms, see for example Morito (1979) or Fox (2000), of this type: $$x = x_0 + x_{F_1}k_1 +x_{F_2}k_2 $$ $$y = y_0 + y_{F_1}k_1 +y_{F_2}k_2 $$ $$x = z_0 + z_{F_1}k_1 +z_{F_2}k_2 $$ where $(x_o, y_0, z_0)$ is a solution of the diophantine equation, $(x_{F_i}, y_{F_i}, z_{F_i})$ are called generator vector and $k_1, k_2$ are any integer

Now I can replace that solution in the initial equation, and I obtain a diophantine equation in two variables, that is: $$(ax_{F₁}+by_{F₁}+cz_{F₁})k₁+(ax_{F₂}+by_{F₂}+cz_{F₂})k₂=k-ax₀-by₀-cz₀$$ For simplicity just change name to the parameters: $$a_1k_1 + a_2k_2 = a_3$$ The solution of this equation will have this form: $$k_1 = a_{01} + a_{11}k_{11}$$ $$k_2 = a_{02} +a_{12}k_{11} $$ Replace in the second diophantine equation to obtain: $$a_1(a_{01} + a_{11}k_{11}) + a_2(a_{02} +a_{12}k_{11}) = a_3$$ It is possible now to solve for $k_{11}$: $$k_{11}=(a_3 -a_1a_{01} -a_2a_{02} )/(a_1a_{11}-a_2a_{12})$$ Now replace $k_{11}$ within the equation of $k_1$ and obtain: $$k_1 = a_{01}+a_{11}*((a_3 -a_1a_{01} -a_2a_{02} )/(a_1a_{11}-a_2a_{12}))$$. In theory you could also replace $k_2$ but don't do it. Instead now we have $x, y ,z$ as a function of only one variable, that is $k_2$

The following algorithm is finite and will extract all the solutions that satisfies the constraint in $x,y,z$. However I'm still not able to count the number of solutions in the general case (the one I need, even at the cost of some restrictions in the parameters) while this algorithm make it possible this number in every practical example with numbers (and not only to count but also actually to extract all solutions).

ALGORITHM For every $i$, $i$ from $0$ to $n-1$ such that $i=1$ then $x=\theta_L$, $i=2$ then $x=\theta_L+1...$ $i=n-1$ then $x = \theta_H$

STEP 1: calculate the value of $k_2$ using $x = x_0 + x_{F_1}k_1 +x_{F_2}k_2 $

STEP 2: use $k_1$ and $k_2$ to obtain $y, z$

STEP 3: accept the solution if both $y,z \in [\theta_L, \theta_H]$, else reject.

Riccardo
  • 83