Carries and the arithmetic progression structure of sets
speaker: Francesco Monopoli (Università degli Studi di Milano)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. (Joint work with Imre Z. Ruzsa)
timetable:
Tue 22 Sep, 15:30 - 15:55, Aula Russo
<< Go back