0
$\begingroup$

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.
$\endgroup$

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.