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<v_{i+1}$ at every $i\in\{1,\dots,n-1\}$.

My guesses at $\gamma=1$:

  1. If $k<m$ 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.