Carries and the arithmetic progression structure of sets

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

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} i n A

, we find the unique

a i n A

such that

a_{1} + a_{2} e q u i v 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

m a t h b b Z / m m a t h b b Z s u b s e t e q m a t h b b Z / m^{2} m a t h b b 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 s u b s e t e q x, y + A

for some

x, y i n m a t h b b Z / p^{2} m a t h b b 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.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Carries and the arithmetic progression structure of sets