Normal projection: deterministic and probabilistic algorithms (Q2258914)

The authors of that paper consider a finite set of points \(p_1, \ldots, p_m\) in the affine space~\(k^n\) where \(k\) is a field. The points can be given explicitly by their coordinates or implicitly as the zeros of a zero-dimensional ideal in~\(k[x_1, \ldots, x_n]\). Given a subset \(S \subseteq k\), the authors ask whether there is a normal projection with coefficients in~\(S\) such that different points are mapped to different values in~\(k\), i.e.\ whether there is a linear projection \(z(x) = c_1 x_1 + \cdots + c_n x_n\) with \(c_1, \ldots, c_n \in S\) such that \(z(p_i) \neq z(p_j)\) for \(i \neq j\). The authors consider the case that~\(S\) is relatively large. If the points \(p_1, \ldots, p_m\) are given explicitly, they describe a deterministic algorithm to compute such a normal projection. If the points are given implicitly, they consider probabilistic algorithms known from the literature and give lower bounds for the success probability of these probabilistic algorithms.