Value sets of polynomials and the Cauchy-Davenport theorem. (Q1418188)

Let \((a_1,\ldots,a_n)\) be a finite sequence of elements of an arbitrary field \(F\), and let \(A=\{a_1,\ldots,a_n\}\) be the set of the sequence elements. For any function \(w:A\to F\) define \(u(w,A)\) to be the least positive integer \(r\) such that \(\sum_{i=1}^n w(a_i)a_i^r\not=0\). With tools from linear algebra, the author finds a lower bound for the size of \(A\) in terms of \(u(w,A)\). This result is used to give a new proof of the Cauchy-Davenport theorem which states a lower bound for the size of the sum of two nonempty finite subsets of a field. Another immediate consequence is the generalisation of a bound for the size of the value set \(V(f)\) of a polynomial \(f\) over a finite field given by \textit{D. Wan}, \textit{P. J.-S. Shiue}, and \textit{C. S. Chen} [Proc. Am. Math. Soc. 119, 711--717 (1993; Zbl 0784.11056)]. For \(f\in\mathbb F_q[x]\) (with \(q=p^r\)) define \(u_p(f)\) to be the smallest positive integer \(i\) such that \(\sum_{\alpha\in\mathbb F_q} f(\alpha)^i\not=0\). (The definition of \(u_p(f)\) gave the author reasons for introducing \(u(w,A)\).) Wan et al. showed that if \(u_p(f)<\infty\) then \(| V(f)| \geq u_p(f)+1\). The author verifies this bound for multivariable polynomials. Using the generalisation of the Cauchy-Davenport theorem to \(k\)-fold sumsets, another lower bound for \(| V(f)| \) is given in the special case of diagonal polynomials \(f=c_1x_1^{n_1}+\ldots+c_kx_k^{n_k}\in\mathbb F_q[x_1,\ldots,x_k]\), \(c_i\not=0\). If the multinomial coefficient \((d_1+\ldots+d_k)!/(d_1!\cdots d_k!)\) with \(d_i=(q-1)/(n_i,q-1)\) does not vanish in \(\mathbb F_q\), then \(| V(f)| \geq d_1+\ldots+d_k+1\).