The polynomial method and restricted sums of congruence classes. (English) Zbl 0861.11006

Alon, Noga; Nathanson, Melvyn B.; Ruzsa, Imre

J. Number Theory 56, No. 2, 404-417 (1996).

Recently J. Dias da Silva and Y. O. Hamidoune [Bull. Lond. Math. Soc. 26, 140–146 (1994; Zbl 0819.11007)] proved an old conjecture of Erdős and Heilbronn [P. Erdős and H. Heilbronn, Acta Arith. 9, 149–159 (1964; Zbl 0156.04801)] proving there are at least \(\min \{p,2k - 3\}\) congruence classes that can be written as the sum of two distinct elements of a \(k\)-element subset of \(\mathbb{Z}_p\) \((p\) is prime). The authors gave a simple and nice proof for this statement using an algebraic technique [Adding distinct congruence classes modulo a prime, Am. Math. Mon. 102, 250–255 (1995; Zbl 0849.11081)]. In this paper they give an application of a general algebraic technique for obtaining results in additive number theory.
Let \(p\) be a prime. Let \(h(x_0,x_1, \dots, x_k) \in \mathbb{Z}_p[x]\). For nonempty subsets \(A_0\), \(A_1, \dots, A_k\) of \(\mathbb{Z}_p\), define \(\oplus_h \sum^k_{i=0} A_i= \{a_0+a_1+ \cdots + a_k :a_i \in A_i, h(a_0, \dots, a_k) \neq 0\}\). As the main statement of the paper the authors prove: Let \(|A_i |= c_i+1\) and let \(m= \sum^k_{i=0} c_i- \deg(h)\). If the coefficient of \(\prod^k_{i= 0} x_i^{c_i}\) in \((x_0+x_1+ \cdots +x_k^m) h(x_0, \dots, x_k)\) is nonzero in \(\mathbb{Z}_p\) then \[ \Biggl|\oplus_h \sum^k_{i=0} A_i \Biggr|\geq m+1. \] From this result they derive the following: if \(A_0\), \(A_1, \dots, A_k\) are nonempty subsets of \(\mathbb{Z}_p\), then for every \(g\in \mathbb{Z}_p\) \[ \left |\left\{ a_0+ \cdots +a_k:a_i \in A_i,\;\prod^k_{i=0} a_i\neq g\right\} \right|\geq\min \left\{p, \sum^k_{i= 0} |A_i |-2k-1 \right\}. \] This result is a generalization of a corollary of the Cauchy-Davenport theorem.
There is a misprint in Proposition 4.2; the summation runs up to \(k\) (instead of \(p)\).

Reviewer: Norbert Hegyvári (Budapest)

MSC:

11B13	Additive bases, including sumsets
11B83	Special sequences and polynomials

Keywords:

restricted sums of congruence classes; general algebraic technique for additive problems; Erdös-Heilbronn conjecture; Cauchy-Davenport theorem

Citations:

Zbl 0849.11081; Zbl 0156.04801; Zbl 0819.11007