Let $0<a\_1 \le a\_2 \le \cdots \le a\_n$ be positive integers such that $a\_1 + \cdots + a\_n = m$ and $\gcd(a\_1,\ldots,a\_n)=1$. Let $\mathbf a :=(a\_1,\ldots,a\_n)\in\mathbb Z^n$ and $\mathbf x:=(x\_1,\ldots,x\_n)\in\mathbb Z^n$. Consider the equation
$$
\mathbf a\cdot \mathbf x = a\_1 x\_1 + \cdots + a\_n x\_n \equiv k \pmod m~.\tag{1}\label{1}
$$
By Bézout's lemma, there are integral solutions to the above equation for any integer $k$.


**Question:** For any integer $k$, can we find integral solutions to \eqref{1} such that $|x\_i| \le c\cdot\frac{m}{n}$ for every $i=1,\ldots,n$, i.e., $\mathbf x \in [-\frac{cm}{n},\frac{cm}{n}]^n$? Equivalently, does the set $\{\mathbf a\cdot \mathbf x:\mathbf x\in[-\frac{cm}{n},\frac{cm}{n}]^n\cap\mathbb Z^n\}$ contain all congruence classes modulo $m$?


Here, $c\ge1$ is a real constant independent of all other parameters. I am fine with $c>1$ but in all the examples I have tried, $c=1$ was enough.




---


**Attempt 1:** Using [this answer](https://mathoverflow.net/a/108723/149337) to a [related question](https://mathoverflow.net/q/108601/149337), I could show that $|x\_i|\le a\_1 \le \frac{m}{n}$ for $i=2,\ldots,n$, but I am not sure how to handle $x\_1$. In fact, when $a\_1 = 1$, this bound is too strong on $x\_2,\ldots,x\_n$.




---


**Attempt 2:** Consider the lattice $\Lambda := \{ \mathbf x\in\mathbb Z^n: \mathbf a \cdot \mathbf x = 0\}$ of rank $n-1$. If $\mathbf x\_k$ is a particular solution to \eqref{1} with $k\pmod m$ on the right hand side, then $\mathbf x\_k + \Lambda + \mathbb Z\mathbf 1$ is the set of all solutions, where $\mathbf 1:=(1,\ldots,1)\in\mathbb Z^n$. If a fundamental domain of $\Lambda$ is contained completely within the cube $[-\frac{cm}{n},\frac{cm}{n}]^n$, then it is possible to show that the answer to the above question is yes with some $c'\ge c$. I know that the volume of the fundamental domain is $\Vert \mathbf a\Vert\_2$ but I don't know how to control its shape.


One way to circumvent this is to use the *covering radius*. Let $\rho$ be the covering radius of $\Lambda$, i.e., $\rho$ is the radius of the smallest ball that always contains a lattice point of $\Lambda$ irrespective of where its center is. If $\rho = O(\frac{m}{n})$, then I know how to answer the question for some $c\ge 1$. However, I couldn't find any nice upper bounds on the covering radius. [This paper](https://link.springer.com/content/pdf/10.1007/s00454-006-1295-2.pdf) discusses several bounds but none of them seems to be strong enough. One of them, equation (30), seems promising but it involves the ratio of *successive minima* $\frac{\lambda\_{n-1}}{\lambda\_1}$ which I don't know how to bound.


I would appreciate any other approaches to answer the question in affirmative for some $c\ge 1$.




---


**Update 1:**$\DeclareMathOperator{\vol}{\operatorname{vol}}$


**Attempt 3:** Let $r\_k$ be the number of integer points in the cube $[-\frac{cm}{n},\frac{cm}{n}]^n$ that correspond to the congruence class $k\pmod m$. Say $r\_k \le R$ for each $k$. Since $\sum\_k r\_k = (\frac{2cm}{n})^n$, we have $r\_k \ge (\frac{2cm}{n})^n - (m-1)R$. If we can show that $R<\frac{1}{m-1}(\frac{2cm}{n})^n$, then we are done.


Consider the hyperplane $H:=\{\mathbf x\in\mathbb R^n: \mathbf a \cdot \mathbf x = 0\}$. It is clear that $\Lambda = H\cap \mathbb Z^n$. Consider the set of hyperplanes given by $\mathcal H\_k := H+\mathbb Z(\frac{k}{m}\mathbf 1)$. The hyperplanes in $\mathcal H\_k$ are all parallel with spacing $\frac{m}{\Vert \mathbf a\Vert\_2}$. Note that the intersection $\mathcal H\_k\cap [-\frac{cm}{n},\frac{cm}{n}]^n$ contains the $r\_k$ integer points associated with the congruence class $k\pmod m$. Since the fundamental domain of $\Lambda$ has volume $\Vert \mathbf a\Vert\_2$, the number of integer points on $\mathcal H\_k\cap [-\frac{cm}{n},\frac{cm}{n}]^n$ is upper bounded by
$$
r\_k \le \frac{\vol\_{n-1}(\mathcal H\_k\cap[-\frac{cm}{n},\frac{cm}{n}]^n)}{\Vert \mathbf a\Vert\_2}~,
$$
where the numerator is the sum of volumes of all the *layers* in $\mathcal H\_k\cap[-\frac{cm}{n},\frac{cm}{n}]^n$. For large $c$, we have more and more layers intersecting the cube. In the spirit of *Riemann sum*, we can approximate this sum in the numerator as
$$
\vol\_{n-1}\left(\mathcal H\_k\cap\left[-\frac{cm}{n},\frac{cm}{n}\right]^n\right) \approx \frac{\vol\_n([-\frac{cm}{n},\frac{cm}{n}]^n)}{m/\Vert \mathbf a\Vert\_2} = \frac{\Vert \mathbf a\Vert\_2}{m} \left(\frac{2cm}{n}\right)^n~.\tag{2}\label{2}
$$
Therefore, $r\_k \le \frac{1}{m} \left(\frac{2cm}{n}\right)^n = R$, and hence we are done.


Note that $c$ seemed to play no role in the above argument so I am definitely doing something wrong. Indeed, the approximation in \eqref{2} must have some corrections which should give an estimate of how large $c$ should be, but I don't seem to have a good way to analyze them. Any help is greatly appreciated.




---


**Update 2:**


As Fedor pointed out in the comments below, there is an equivalent reformulation of the above question:


**Reformulation:** Given any $\mathbf x\in H$, is there a $\mathbf y\in H\cap \mathbb Z^n$ such that $\Vert \mathbf x - \mathbf y \Vert\_\infty \le \frac{Cm}{n}$?


Also, in the comments below [Mark's answer](https://mathoverflow.net/a/425038/149337), I gave three examples where I think my question has a positive answer.



Bounds on Bézout coefficients
We may suppose that $-m<k\leqslant 0$ and choose integers $y\_i$ such that $\sum y\_ia\_i=k$. Next, by replacing $(y\_1,y\_i)\to (y\_1\pm a\_i, y\_i\mp a\_1)$ we may achieve $y\_i\in [0,a\_1)$ for all $i>1$. Then $y\_1=(k-\sum\_{i>1}y\_ia\_i)/a\_1\in (-2m,0]$. Denote $t=\lceil n/2\rceil$. We have $a\_i\leqslant 2m/n$ for $i\leqslant t$. For each $i=2,\ldots t$ consequently make an operation $(y\_1\to y\_1+a\_i$, $y\_i\to y\_i-a\_1)$ so many times that $y\_i$ does not become less than $-100m/n$. If on some step $y\_1$ became non-negative (for the first time), you are in a good position at this point, because $y\_1$ could not become greater than $a\_t\leqslant 2m/n$. Thus after all operations $y\_1$ is still negative. But operation with $y\_i$ is performed at least $\frac{50m}{na\_1}$ times, and $y\_1$ increased by at least $50m/n$ during these operations. Totally $y\_1$ increased at least by $(t-1)50m/n>2m$, a contradiction.


