Krdytkyu

Let $R_q=mathbb{Z}_q[x]/langle f(x)rangle$ where $f(x)=x^n+1$, as in the ring-LWE problem.

Let $a(x)$ be chosen uniformly at random from $R_q$.

Question: Is there any theorem that lower bounds the distance between any two polynomials of the form $a(x)s_1(s)$ and $a(x)s_2(x)$?

In other words, what is the value of $d$ such that $$||a(x)s_1(x)-a(x)s_2(x)||geq d$$ except with negligible probability, for any two polynomials $s_1(x),s_2(x)in R_q$ and where $||cdot||$ is the usual $L_2$ norm?

I'm assuming $n$ is a power of $2$ and that $q$ is an odd prime larger than $n$. I'm discarding the trivial case $s_1 = s_2$.

If you consider everything $mod q$, then it is most likely over the choice of $a$ that there exists $s_1 neq s_2$ such that $|a s_1 - a s_2| = sqrt{n}$. Indeed, $a$ is invertible in $R_q$ with probability about $1 - n/q$. Take $s_2 = s_1 - a^{-1}$, then you have $a s_1 - a s_2 = 1 mod q$ and the embedding norm of $1$ is $sqrt{n}$.

If you do not consider this $mod q$, i.e. you work in $R=mathbb Z[x]/⟨f(x)⟩$, then you are precisely asking for the minimal distance $lambda_1(mathfrak I)$ of the ideal lattice $mathfrak I$ generated by $a$. For such an ideal lattice, we can estimate rather precisely this minimal distance. A simple lower bound is
$lambda_1(mathfrak I) geq Delta_K^{1/2n} cdot N(a)^{1/n}$, where $N$ denotes the algebraic norm of $a$ (that is, the product of all its embeddings), and $Delta_K$ is the discriminant of field $K = mathbb Q(x)/(x^n+1)$. The reason is that the minimal vector $x$ must generate a subideal of $mathfrak I$, so $N(x) geq N(a)$, and $|x|^n geq Delta_K^{1/2} N(x)$. An upper bound is also given by Minkowski's theorem.