Bounds on Bézout coefficients

Question

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 to a related question, 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 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, I gave three examples where I think my question has a positive answer.

Answer 1

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.

Answer 2

The following is likely useful, but doesn't answer your question really.

First, a standard (set of) inequalities used to bound the covering radius of a lattice is known by the name of transference. The tightest bound (up to a constant factor) is in Banaszczyk's paper New bounds in some transference theorems in the geometry of numbers. It states that $\rho(\Lambda) \leq n/\lambda_1(\Lambda^*)$, so you can (up to a factor $n$) reduce your problem to lower-bounding the shortest vector in the dual lattice.

Second, your lattice is much nicer in the case that $a = (1,1,\dots,1)$, so this is probably worth working out explicitly first. In this setting, $\Lambda$ is precisely the $A_{n-1}$ root lattice (or its dual, I get them mixed up...), so the problem should be quite simple in this setting.

Third, in the case of (general) $a$, there may not be as much structurally as you might hope. In particular, Sloane et. al's paper A Note on Projecting the Cubic Lattice. In particular, theorem 2 appears to be relevant. Let $A_a^*$ be the intersection of $\mathbb{Z}^n$ with the subspace orthogonal to the vector $a$ (which appears to be your lattice $\Lambda$.

Theorem 2: Let $\Lambda$ be an $(n-1)$-dimensional lattice with Gram matrix $A$ (with respect to some basis for $\mathbb{R}^{n-1}$). For any $\epsilon > 0$, there exists a non-zero vector $a\in\mathbb{Z}^n$, a basis $B$ for the $(n-1)$-dimensional lattice $\Lambda_a^*$, and a number $c$ such that if $A_a^*$ denotes the Gram matrix of $B$, then

$$\lVert A - cA_a^*\rVert_\infty < \epsilon.$$

I do not know the implication of this for the geometry of the Voronoi cell of $A_a^*$, but it seems plausible that this notion of closeness could mean that the Voronoi cell of $A_a^*$ can (via appropriate choice of $a$) be made to be close to that of an arbitrary $A$ in some formal sense.

Fourth, I believe that (for large enough $m$, for uniformly random $a_i\bmod m$) the closely-related lattice $\{x\in\mathbb{R}^n\mid \langle a,x\rangle \equiv 0\bmod m\}$ is actually a "random lattice" (with respect to the natural measure over lattices, often called the Siegal measure). See Seungki Kim's thesis for a nice summary of things. I believe $m$ must be incredibly large (more than exponentially large in $n$, although I don't remember precisely how much) for the claimed equidistribution to hold. This is to say that this closely-related lattice can have an arbitrary voronoi cell, which again suggests that it may be hard to get any degree of control over the voronoi cell of your lattice.

My (imperfect) understanding of these last two points is that your problem may be unexpectedly difficult, but it is plausible my interpretation of these last two points is faulty.