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

|2A| < min {3|A|-3, p}
(where 2A stands for the set of all the residues representable as a+b with a and b in A). Then A is contained in an arithmetic progression modulo p of at most |2A|-|A|+1 terms.

The results below would be immediate consequences.

Theorem (Cauchy-Davenport). For any set of residues A, the cardinality of 2A is at least

min {2|A|-1, p}.

Theorem (Freiman). Let A be a finite set of integers. Suppose that

|2A| < 3|A|-3.
Then A is contained in an arithmetic progression of at most |2A|-|A|+1 terms.

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.

HOME    1    2    3    4    5    6    PROBLEMS PAGE