2
$\begingroup$

We are given a rank $r$ matrix $B\in\Bbb Z^{k\times n}$ where $0\leq r\leq k\leq n$ holds.

We have $$\mathcal L_\Bbb Z=\{uB\in\Bbb Z^n:u\in\Bbb Z^k\}\subseteq\mathcal L_\Bbb Q=\{uB\in\Bbb Z^n:u\in\Bbb Q^k\}\subseteq\Bbb Z^n$$ $$\lambda_{i}(\mathcal L_\Bbb Q)\leq\lambda_{i}(\mathcal L_\Bbb Z)$$ where $\lambda_{i}(\mathcal L_\Bbb Z)$ and $\lambda_{i}(\mathcal L_\Bbb Q)$ are $i$th successive minima in $\infty$-norm of $\mathcal L_\Bbb Z$ and $\mathcal L_\Bbb Q$ respectively.

Can $\lambda_{i}(\mathcal L_\Bbb Z)-\lambda_{i}(\mathcal L_\Bbb Q)$ depend exponentially in $i$ and $\log \max_{m,m'}|B_{mm'}|$ only (not exponentially depend on $r,k,n$ particularly)?

I am mostly interested in the gap at $i=O(1)$ regime.

Improve this question
$\endgroup$
5
  • $\begingroup$ L_Q is dense, so it does not have any shortest vector. $\endgroup$
    – Noah Stephens-Davidowitz
    Commented Sep 14, 2017 at 5:29
  • $\begingroup$ @NoahStephens-Davidowitz it cannot be smaller than $1$ in any $p\in[1,\infty]$ norm since it is an integer vector. $\endgroup$
    – Turbo
    Commented Sep 14, 2017 at 5:37
  • $\begingroup$ Oh, sorry.. I misinterpreted the definition of L_Q. It might be more clear if you move the condition that uB must be an integer vector to after the colon? $\endgroup$
    – Noah Stephens-Davidowitz
    Commented Sep 14, 2017 at 5:43
  • $\begingroup$ What, precisely, do you mean by "not strongly depend on $r, k, n$"? $\endgroup$
    – user44191
    Commented Sep 14, 2017 at 16:25
  • $\begingroup$ @user44191 By this I mean it can be exponential in $i$ and $\log |B|$ but not exponential in $r,k,n$. $\endgroup$
    – Turbo
    Commented Sep 14, 2017 at 16:59

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .