|
Small Doubling Modulo a Prime There are reasons to believe that a "true" combinatorial proof of the following conjecture, being properly understood and generalized for composite moduli, may result in a real progress in additive combinatorial number theory. Conjecture. Let p be sufficiently large prime number, and let A be any set of residues modulo p. Suppose that The results below would be immediate consequences. Theorem (Cauchy-Davenport). For any set of residues A, the cardinality of 2A is at least Theorem (Freiman). Let A be a finite set of integers. Suppose that Theorem (Freiman). Let A be a set of residues modulo sufficiently large prime p. Suppose that |2A| < 2.4|A|-3 and that |A| < p/35. Then A is contained in an arithmetic progression modulo p of at most |2A|-|A|+1 terms. This last result can be considered as a step towards the conjecture above. However, the analytical nature of its proof does not allow one to get the right constants or to obtain the generalizations desired. Such a heavy tool as "Freiman's theorem" implies our conjecture, provided that A satisfies the additional restriction |A|<cp (with an absolute positive constant c, which in practice is very small). Again, the proof is strongly analytical and possesses no generalizations we need. Remark. As shows the example of p=17, A={0, 1, 2, 4, 8, 16} (here |2A|=14=3|A|-4, and the shortest progression containing A is of 10 terms), the condition "p is sufficiently large" is necessary. It can happen, moreover, that the conjecture above is a bit too optimistic, and instead of p inside the min in the right-hand side we should write p-C with some constant C, or even something like p-|A|. Anyhow, we need the "true" bound here with a "true" combinatorial proof. |