# Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?

A recent eprint paper claims to bound $$\lambda_1(\Lambda^\perp(\mathbf{A}))$$ for $$\mathbf{A}\in\mathbb{Z}^{n\times m}$$, a uniformly random matrix, by $$O(1)$$, specifically by $$4$$. This has applications to solving $$\mathsf{SIS}_{n,m,q,4}$$ in $$\mathsf{P}$$.

I'm no expert in this area, but it seems to me this contradicts the common thought that $$\lambda_1(\Lambda^\perp(\mathbf{A})) = \Omega(\sqrt{n\log q})$$ (see, for example, section 2.4.2 of this paper).

As getting into the details of the recent paper is likely off topic for this forum, I'm interested instead in another question --- what concrete/experimental evidence has been collected for the asymptotics of $$\lambda_1(\Lambda^\perp(\mathbf{A}))$$? Looking into data such as this would be an easy way to gain intuition for whether we're in an $$O(1)$$ regime or $$\Omega(\sqrt{n\log q})$$ one, and I had assumed that someone had papers along these lines, but don't actually recall seeing any of it myself.

• I contacted the authors, one of whom (Jia Huiwen in particular) replied: (after translation) Currently there isn't a specific algorithm, it's only deduction on theoretical level, also there's a problem with the proof in the article which we're fixing. Jan 17, 2019 at 5:51
• @DannyNiu Their claim that $\lambda_1(\Lambda^\perp(A)) = O(1)$ shouldn't be dependent on any particular algorithm though. For a particular distribution over $A$ (with fixed $m,n,q$), we have that $\lambda_1(\Lambda^\perp(A))$ is simply a statistic, and should be able to be estimated computationally. Then, by repeating this for various $m,n,q$, you should be able to gain some intuition for the asymptotic properties of $\lambda_1(\Lambda^\perp(A))$. I'm curious if anyone has done this computational exercise, and made some paper out of it (for example), as this seems plausible.
– Mark
Jan 17, 2019 at 6:18
• @DannyNiu That being said, I appreciate your update with regards to that paper!
– Mark
Jan 17, 2019 at 6:19
• It looks like the bug is in the proof of the (false) inequality labeled "on the other hand" on page 7. E.g., a random lattice has $bl \approx \sqrt{n}$ but $\rho_1(L^*) \approx 2$. So, they're inequality says $2 \gtrsim \sqrt{n}$. Their proof of this inequality seems to boil down to an argument that the dual lattice $L^*$ always has a vector of length $1/bl$, which is false in general. It has a vector of length $1/\|\tilde{b}_n\|$, but typically not a vector of length, e.g., $1/\|\tilde{b}_1\|$. Jan 17, 2019 at 16:32

The first inequality at the bottom of page 3 of the paper is false. For example, Conway and Thompson proved the existence of "self-dual" $$n$$-dimensional lattices $$L$$ (i.e., $$L^* = L$$) where $$\lambda_1(L) = \lambda_1(L^*) = \Omega(\sqrt{n})$$, hence $$\eta_{2^{-n}}(L) = O(1)$$ but $$\tilde{bl}(L) \geq \lambda_1(L) = \Omega(\sqrt{n})$$.
Suppose that $$q$$ is prime, and suppose that the minimum distance in the 2-norm is indeed bounded by $$b=O(1)$$. There are at most $$Binom[m,b] \cdot (2b+1)^b = poly(m)$$ elements x in $$\mathbb Z^m \setminus \{0\}$$ with $$||x||^2_2 \leq b$$. But every such vector has only probability $$q^{-n}$$ to be part of the lattice over the randomness of $$A$$. By a union bound this means that the probability that any such vector is part of the lattice over the randomness of $$A$$ is at most $$poly(m) \cdot q^{-n}$$ which is negligible unless m itself is exponential in $$n$$.