Distinct Sums Modulo <e1>n</e1> and Tree Embeddings

In this paper we are concerned with the following conjecture. <e2>Conjecture.</e2> For any positive integers <e1>n</e1> and <e1>k</e1> satisfying <e1>k</e1> &lt; <e1>n</e1>, and any sequence <e1>a</e1><inf>1</inf>, <e1>a</e1><inf>2</inf>, … <e1>a</e1><inf><e1>k</e1></inf> of not necessarily distinct elements of <e1>Z</e1><inf><e1>n</e1></inf>, there exists a permutation π ∈ <e1>S</e1><inf><e1>k</e1></inf> such that the elements <e1>a</e1><inf>π</inf>(<e1>i</e1>)+<e1>i</e1> are all distinct modulo <e1>n</e1>. We prove this conjecture when 2<e1>k</e1>  <e1>n</e1>+1. We then apply this result to tree embeddings. Specifically, we show that, if <e1>T</e1> is a tree with <e1>n</e1> edges and radius <e1>r</e1>, then <e1>T</e1> decomposes <e1>K</e1><inf><e1>t</e1></inf> for some <e1>t</e1>  32(2<e1>r</e1>+4)<e1>n</e1>²+1.