On the Number of Solutions of a Linear Equation over Finite Sets

✍ Scribed by Vsevolod F. Lev

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 300 KB
• Volume: 83
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1998.2878

✦ Synopsis

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

where c i {0 and * 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

this number of solutions is maximal when c 1 = } } } =c k =1, *=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 , * # F p and A i F p (where F p is the set of residues modulo prime p), the number of solutions of the equation above does not exceed

as k Ä 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.