Subtractive Sets over Cyclotomic Rings: Limits of Schnorr-like Arguments over Lattices.

We study when (dual) Vandermonde systems of the form \(\mathbf {V} _T^{{(\intercal )}} \cdot \mathbf {z} = s\cdot \mathbf {w}\) admit a solution \(\mathbf {z}\) over a ring \(\mathcal {R}\), where \(\mathbf {V} _T\) is the Vandermonde matrix defined by a set T and where the “slack” s is a measure of the quality of solutions. To this end, we propose the notion of (s, t)-subtractive sets over a ring \(\mathcal {R}\), with the property that if S is (s, t)-subtractive then the above (dual) Vandermonde systems defined by any t-subset \(T \subseteq S\) are solvable over \(\mathcal {R}\). The challenge is then to find large sets S while minimising (the norm of) s when given a ring \(\mathcal {R}\).