Representing integers by multilinear polynomials (Q2221679)

The paper being reviewed here considers a class of homogeneous polynomials and a question whether or not a polynomial in this class takes all possible integer values. Under some mild conditions on the coefficients of the homogeneous polynomial, the paper obtains a positive answer and also obtains an explicit bound on the values of variables that result in the polynomial being equal to a specific integer. To be more precise, let \([n]=\{1,\ldots,n\}\), let \(d\) be a positive integer less or equal to \(n\). Let \({\mathcal I}_d(n):=\{I \subset [n]: |I|=d\}\). For each indexing set \(I=\{i_1,\ldots,i_d\} \in {\mathcal I}_d(n)\) with \(1\leq i_1 <\ldots<i_d\leq n\) define the monomial \(x_I:=x_{i_1}\ldots x_{i_d}\). An integer multilinear \((n,d)\)- form is a polynomial of the form \(F(x_1,\ldots,x_n)=\sum_{I\in {\mathcal I}_d(n)}f_Ix_I\), where \(f_I \in {\mathbb Z}\) for all \(I \subset {\mathcal I}_d(n)\). The form is called coprime if gcd\((f_I)_{I \in {\mathcal I}_d(n)}=1\). The main theorem of the paper asserts that if every pair of non-zero coefficents is coprime or \(n=d+1\) and there exists a coprime pair of coefficients, the multilinear \((n,d)\)-form represents every integer \(b\) and \(F({\mathbf a})=b\) for \(|a| \leq |b|(2|F|)^{d!e}\), where \(|{\mathbf a}|=\max_{1\leq i\leq n}|a_i|\) and \(|F|=\max_{I\in I_d(n)}|f_I|\). This paper is a contribution to a line of research attempting to describe the boundary of undecidability for polynomial equations over \(\mathbb Z\). The answer to Hilbert's Tenth Problem excluded the possibility that one could answer a question of the type considered in this paper for an arbitrary polynomial, but as it is clear from the results above and older results, there are algorithms to determine existence of solutions for some classes of polynomials.