On the number of solutions of a linear equation over finite sets

摘要

The largest possible number of representations of an integer in the k-fold sumset kA = A + ... + A is maximal for A being an arithmetic progression. More generally, consider the number of solutions of the linear equation c(1)a(1) + ... +c(k)a(k) = lambda, where c(i) not equal 0 and lambda are fixed integer coefficients, and where the variables a(i) range over finite sets of integers A(1),..., A(k). We prove that for fixed cardinalities n(i) = A(i), this number of solutions is maximal when c(1) = ... c(k) = 1, lambda= 0 and the A(i) are arithmetic progressions balanced around 0 and with the same common difference. For the corresponding residues problem, assuming c(i), lambda is an element of F-p and A(i) subset of or equal to F-p (where F-p is the set of residues module prime p), the number of solutions of the equation above does not exceed [GRAPHICS] as k ---> infinity and under some mild restrictions on n(i). This is best possible save for the constant in the second term: we conjecture that in fact 8 can be replaced by 6. (C) 1998 Academic Press. [References: 8]