The goal of universal machine translation is to learn to translate between any pair of languages, given pairs of translated documents for some of these languages. Despite impressive empirical results and an increasing interest in massively multilingual models, theoretical analysis on translation errors made by such universal machine translation models is only nascent. In this paper, we take one step towards better understanding of universal machine translation by first proving an impossibility theorem in the general case. In particular, we derive a lower bound on the translation error in the many-to-one translation setting, which shows that any algorithm aiming to learn shared sentence representations among multiple language pairs has to make a large translation error on at least one of the translation tasks, if no assumption on the structure of the languages is made. On the positive side, we show that if the documents follow a natural encoder-decoder generative process, then we can expect a natural notion of “generalization”: a linear number of pairs, rather than quadratic, suffices. Our theory also explains what kinds of connection graphs between pairs of languages are better suited: ones with longer paths result in worse sample complexity in terms of the total number of documents per language pair needed.