Size of a linear image of a cube in $\mathbb{Z}^d$ Suppose that we have an element $v = (v_1, \dots, v_d) \in \mathbb{Z}^d$ such that $\gcd(v_1, \dots, v_d) = 1$. Then $v$ is contained in some base of $\mathbb{Z}^d$ (seen as a free-abelian group or a free module over $\mathbb{Z}$). In particular, there exists a regular integer matrix $A \in \mathop{GL}_d(\mathbb{Z})$ such that $A(v) = (1, 0, \dots, 0)$.
My question is the following: assuming that $|v_1| + \dots + |v_d| = n$, what is the smallest $\ell \in \mathbb{N}$ (taken over all possible matrices $A$) such that the image $A\left([-1, 1]^d\right)$ is contained in the cube $[-\ell, \ell]^d$? I care about asymptotics of $\ell(n)$ up to multiplicative constant.
 A: If $d$ is fixed and you care about the asymptotic behavior in $n$, then you cannot do better than linear bound because you can take the vector $(p,p,\dots,p,q)$ where $p\approx n$ is prime and $qk\equiv 1\mod p$ for some $k\approx n/2$, so the first row has to be large. Keeping this in mind, you can easily arrange the other rows of size $n$ by putting $0,\dots,0,v_{j+1},-v_j,0,\dots,0$ there (if all $v_j\ne 0$; otherwise arrange them so that the first few aren't and then do this until you hit the zeroes and add the diagonal of ones in the end).
Thus, the only problem is to come up with the first row of size comparable to $n$, i.e., with an integer vector $a$ such that $(a,v)=1$ and $|a|\le C(d)n$. The integer vectors with the property $(a,v)=1$ form a lattice in the corresponding hyperplane with determinant $\|v\|_2\le n$ and the minimal vector length $\ge 1$. Such a lattice cannot miss a ball of radius $C(d)n$, so the solution exists.
Edit Ah, yes, I should have mentioned the last step. Here goes.
We have a lattice $\Lambda$ given by $\langle a,v\rangle=0$ and you want the last $n-1$ rows to be a basis of that lattice. What I created is a set of short (length $\le n$) linearly independent vectors $a_1,\dots,a_{d-1}$ in $\Lambda$. But now just consider the lattices $\Lambda_k=\Lambda\cap L_k$ where $L_k={\rm span}(a_1,\dots,a_k)$. The basis in $\Lambda_1$ is just the primitive vector $a_1'$ in the direction of $a_1$ (so it is $\le n$). To get the basis in $\Lambda_2$, take the closest (in the Euclidean distance) to $L_1$ vector in $\Lambda_2$ that is not in $\Lambda_1$. Its distance from $L_1$ is at most $n$ (because $a_2$ competes). And its projection to $L_1$ can be brought below $|a_1'|\le n$ by adding $a_1'$ with appropriate integer coefficient. Thus we can have $|a_2'|\le 2n$. Now we have a basis in $\Lambda_2$ with the fundamental parallelogram of diameter $3n$. For $a_3'$ take the closest to $L_2$ vector in $\Lambda_3\setminus\Lambda_2$. The distance to $L_2$ is $\le n$ ($a_3$ competes) and the projection to $L_2$ can be brought into the fundamental parallelogram we constructed, so we get $|a'_3|\le 4n$ and the fundamental parallelepiped for $\Lambda_3$ of diameter $7n$. And so on. The final estimate is $2^dn$. It can, probably, be improved but I have to refresh my rather rusty knowledge of Geometry of Numbers to say how and to what. We all have read the same books anyway (Cassels, Rogers, & Co.), so you may also search the answer there yourself :-)
