MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose $A$ is a subset of the finite field with $p$ elements. What is the best approximation of $A$ by a sumset $B+C$ in the sense that $|A\Delta (B+C)|$ is minimal? Of course if $B=A-x$ and $C=\{x\}$ then we have equality so I would ask that both sets be non-singleton. If $A+A$ is small then there are standard covering lemmas which give an answer but this is a fairly strong assumption about $A$. If I recall correctly there are results that say $A$ is a sumset if it is almost the whole field. What about smaller $A$?

share|cite|improve this question
For small B and C I can imagine perturbing B+C in many places to get about half of it away from B+C, and likely a quarter of it from any other sumset, but I do not have a construction. It might be prudent to count the fraction of p choose 12 subsets of size 12 that are nontrivial sumsets. Gerhard "Likes Working With Small Examples" Paseman, 2013.06.10 – Gerhard Paseman Jun 10 '13 at 17:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.