0
$\begingroup$

Let $T,M\in\mathbb{N}$ be fixed. Consider a linear Diophantine equation of the form

$a_1 x_1 + a_2 x_2 + … + a_n x_n = 0 $

with $a_i \in [-T,T] \subset \mathbb{Z}$. Is there an asymptotic formula to estimate the number of solutions $x_1,…,x_n \in [-M,M] \subset \mathbb{Z}$?

I am not necessarily interested in a precise formula, any result saying that there are exponentially few solutions would be interesting.

Another way of seeing the problem is: how many integer vectors $(x_1,…,x_n)\in[-M,M]^n$ are there orthogonal to $(a_1,…,a_n)\in [-T,T]^n$?

Improve this question
$\endgroup$
5
  • $\begingroup$ What do you mean by "exponentially few"? The number of solution is obviously at most $(2M+1)^n$, which is already an exponential bound. $\endgroup$
    – Emil Jeřábek
    Commented Jul 3, 2023 at 5:52
  • 1
    $\begingroup$ I would like to know whether a tighter bound exists. Intuition tells me that the number of solutions to the equation is exponentially small compared to the number of all vectors with the coefficients in that range. However, I have not been able to show it. $\endgroup$
    – Gotham17
    Commented Jul 3, 2023 at 6:08
  • $\begingroup$ For a fixed equation, wlog $a_n\ne0$, thus $x_n$ is uniquely determined by $(x_1,\dots,x_{n-1})$, and whether a given $(x_1,\dots,x_{n-1})$ leads to a solution is determined by congruence conditions modulo $a_n$. Thus, there is a rational constant $\gamma>0$ (depending on the equation) such that the number of solutions in $[-M,M]^n$ is asymptotic to $\gamma M^{n-1}$. $\endgroup$
    – Emil Jeřábek
    Commented Jul 3, 2023 at 6:50
  • $\begingroup$ Thanks. Can I conclude then that, given that the number of possible solution vectors is $M^n$, we have that the number solutions is upper bounded by to $\gamma/M$, with $0<\gamma\leq 1$ ? $\endgroup$
    – Gotham17
    Commented Jul 3, 2023 at 8:20
  • $\begingroup$ The proportion of solutions among the vectors in $\{-M,M\}^n$ is asymptotically equal to $\gamma/M$. $\endgroup$
    – Emil Jeřábek
    Commented Jul 3, 2023 at 8:41

0

Reset to default

You must log in to answer this question.