Carries and the arithmetic progression structure of sets

Abstract

If we want to represent integers in base $m$, we need a set $A$ of digits, which needs to be a complete set of residues modulo $m$. When adding two integers with last digits $a_1,a_2\in A$, we find the unique $a\in A$ such that $a_1+a_2\equiv a$ mod $m$, and call $(a_1+a_2-a)/m$ the carry. Carries occur also when addition is done modulo $m^2$, with $A$ chosen as a set of coset representatives for the cyclic group $\mathbb{Z}/m\mathbb{Z}\subseteq \mathbb{Z}/m^2\mathbb{Z}$. It is a natural to look for sets $A$ which minimize the number of different carries. In a recent paper, Diaconis, Shao and Soundararajan proved that, when $m=p$, $p$ prime, the only set $A$ which induces two distinct carries, i. e. with $A+A\subseteq \{x,y\}+A$ for some $x,y\in \mathbb{Z}/p^2\mathbb{Z}$, is the arithmetic progression $[0,p-1]$, up to certain linear transformations. We present a generalization of the result above to the case of generic modulus $m^2$, and show how this is connected to the uniqueness of the representation of sets as a minimal number of arithmetic progression of same difference.