Number of solutions of linear homogenous Diophantine equation inside a box

Question

Let $a_1, ..., a_d$ be positive reals and consider the linear Diophantine equation $$ \sum_i a_in_i = 0. $$

I am interested in estimating the number of integer solutions of this equation inside a box $[-N_1, N_1] \times ... \times [-N_d, N_d]$ and also the minimal basis for the corresponding integer lattice in terms of $a_1,...,a_d$. More specifically, it seems that if the number of solutions is of order $N^{d-1}$ then $(a_1, ...., a_d)$ should be proportional to some integer vector of bounded norm. Presumably, smth much more precise is known.

I believe that such kind of questions are well studied so any good reading on this topic would be highly appreciated.

Answer 1

The solution set $L$ is clearly a sublattice in $\mathbb Z^d$. If $a$ is fixed and $N$ grows, the number of lattice elements in a box grows approximately as $cN^{rank}$. So if you have your statement asymptotically for $N\to+\infty$ for a fixed $a$ then this shows that the rank of the solutions set is $d-1$, so $a$ is rational (see also Richard Stanley's answer).

To bound the size of $a$ consider the following. Suppose for simplicity that all $N_i$ are equal to $N$ and that the number of solutions is $> cN^{d-1}$. Then for $N_0=[2^{d-2}/c]+1$ the number of solutions is larger than the number of points in $(-N,N)^{d-2}$. This implies that for any $i,j=1,...,d$ there are at least two solutions of size less than $N_0$ which have the same projection to the $\mathbb Z^{d-2}$ obtained by forgetting $i$-th and $j$-th coordinates. Thus, there is a nonzero element in the lattice $L$ with nonzero coordinates at $l_i$ and $l_j$ only, and $\vert l_i\vert,\vert l_j\vert < 2N_0$. We may assume that $a_i$ are all nonzero, then this gives us a finite set of possibilities of their ratios, hence a finite set of $(a_i)$ up to common scaling.

Answer 2

Let $k$ be the dimension over $\mathbb{Q}$ of the $\mathbb{Q}$-subspace of $\mathbb{R}$ spanned by $a_1,\dots,a_d$. Then the dimension over $\mathbb{Q}$ of all $d$-tuples $(n_1,\dots,n_d)\in\mathbb{Q}^d$ such that $\sum a_in_i=0$ is $d-k$. Then by a straightforward argument the number of such $(n_1,\dots,n_d)$ that are contained in the box $[-N,N]^d$ as $N\to\infty$ is of the order $N^{d-k}$. By looking more carefully at the linear dependence relations among the $a_i$'s, e.g., the matroid they determine as points in a rational vector space, it might be possible to find explicitly a constant $c$ so that the number of such $(n_1,\dots,n_d)$ is asymptotic to $cN^{d-k}$. It might also be possible to extend this to $[-N_1,N_1]\times \cdots\times [-N_d,N_d]$ as all $N_i\to\infty$. I would be interested in seeing such results.

Answer 3

Siegel's Lemma is a famous solution to this type of problem with a system of linear forms, giving an estimate for the basis of solutions.

Answer 4

You may find something of interest in the Beck and Robins book, Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra.