9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Do you have averaging over $a_i$? $\endgroup$ Feb 10, 2014 at 0:56
  • $\begingroup$ What do you mean by averaging? since the equation is homogeneous one can of course assume that $a_i$ sum up to $1$. $\endgroup$
    – DmitryZ
    Feb 10, 2014 at 8:20
  • $\begingroup$ I mean that original problem can give you a set of linear equations with different coefficients $a_i$. In the worst case you can get an asymptotic formula with bad error term (if reduced basis has very long vectors). But in average (over $a_i$) the error term will be better. $\endgroup$ Feb 10, 2014 at 13:45

4 Answers 4

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the nice answer. In fact, it works for all boxes larger than some constant which depend only on $d$ and $c$, which is important since in my case $a_i$ may depend on $N$ but not on the dimension and $c$. $\endgroup$
    – DmitryZ
    Feb 10, 2014 at 8:40
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks, but after a quick look it seems that they always assume the coefficients are at least rational, don't they? $\endgroup$
    – DmitryZ
    Feb 8, 2014 at 11:53
  • $\begingroup$ You may be right. I'm home, the book's in my office. $\endgroup$ Feb 8, 2014 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.