# Extremal thresholds of balancing integer vectors by linear transformation

Take $$v$$ to a vector in $$\mathbb Z^m$$ with entries from $$0$$ to $$2^k-1$$ (there are $$2^{km}$$ possible vectors).

Define $$L(v)$$ to be difference between the largest and the smallest entries in $$v$$ and define $$v$$ to be $$d$$-balanced if $$|L(v)|\leq d$$ where $$d\in\mathbb N\cup\{0\}$$.

1. What is minimum $$t\in\mathbb Z$$ so that there is a list of unimodular matrices $$M_1,\dots,M_t\in\mathbb Z^{\lceil\gamma m\rceil\times m}$$ with entries bound in magnitude by $$2^k$$ and vectors $$q_1,\dots,q_t\in\mathbb Z^{\lceil\gamma m\rceil\times 1}$$ such that for every $$v\in\mathbb Z^m$$ with entries from $$0$$ to $$2^k-1$$ we have an $$i\in\{1,\dots,t\}$$ such that transformed vector $$M_iv+q_i$$ is $$d$$-balanced where $$\gamma\geq1$$ is fixed ($$\gamma=1$$ already appears non-trivial)?

2. What happens in $$\gamma\in[1,k]$$?

If for a $$d,\gamma$$ no such list exists then take $$t=\infty$$.

Assume $$v$$ satisfies $$v_i at every $$i\in\{1,\dots,n-1\}$$.

My guesses at $$\gamma=1$$:

1. If $$k then there is a $$d$$ with $$d=2^{o(k)}$$ (perhaps even $$d=2^{O(k^\alpha)}$$ at any fixed $$\alpha>0$$) a list of $$t=2^{O(m)}$$ such matrices suffice.

2. If $$k>m$$ then $$d=2^{\Omega(k)}$$ is needed if $$t=2^{O(m)}$$.

My guess at $$\gamma\geq k$$:

1. $$d=O(1)$$ can be taken.