# Upper bound for lowest common multiple of integers with (almost) fixed sum

For a positive integer $n$, let $f(n)$ be the maximum value of $\mathrm{LCM}(S)$ among multisets $S$ of positive integers satisfying $\sum_{i \in S} (i-1) = n$.

What is known about upper bounds for $f(n)$?

The best that I can do is $\log f(n) \leq \sqrt{n/2} \log (4n/3)$ for $n \geq 6$. This comes by looking at the product of distinct elements of $S$, which is certainly greater than $\mathrm{LCM}(S)$: Let $S$ have $k$ distinct elements. Then $n \geq k(k-1)/2$ so $k \leq \sqrt{3n}$. By the AM-GM inequality, $f(n) \leq ((n+k)/k)^k \leq (2n/k)^k$. Now $k(\log (2n) - \log k)$ is increasing for $k < 2n/e$, and $\sqrt{3n} < 2n/e$ for $n \geq 6$. So $f(n) \leq (2n/\sqrt{3n})^{\sqrt{2n}}$.

The above argument ignores the fact that distinct elements of $S$ may have common factors, so it may be possible to do better than this.

### Motivation

Let $G$ be a semisimple algebraic group over $\mathbb{Q}$. Let $\rho$ be an irreducible representation of $G$ such that $D = \mathrm{End} \rho$ is a central division algebra over $\mathbb{Q}$, with $\dim D = m^2$. In other words, $\rho \otimes \bar{\mathbb{Q}}$ has one irreducible component with multiplicity $m$.

I am interested in how large $m$ can be, given that $G$ has rank $n$.

By Tits' paper in J. Reine Angew. Math 247, $D$ is in the image of a certain homomorphism $\Lambda/\Lambda_0 \to \mathrm{Br} \mathbb{Q}$, where $\Lambda$ is the group of characters of a maximal torus and $\Lambda_0$ is the subgroup of $\Lambda$ generated by roots.

Since the base field is $\mathbb{Q}$, $m$ is the same as the order of $D$ in $\mathrm{Br}\mathbb{Q}$, so $m$ is less than or equal to the exponent of $\Lambda/\Lambda_0$.

Suppose that all simple components of the root system of $G$ have type A, and let $S$ be the multiset of ranks of simple components of $G$. Then $\Lambda/\Lambda_0$ is a subgroup of $\prod_{r \in S} \mathbb{Z}/(r+1)\mathbb{Z}$. (Components of types other than A contribute factors to $\Lambda/\Lambda_0$ with exponent at most 12, so can be ignored.) So the exponent of $\Lambda/\Lambda_0$ is at most $f(n)$ as defined above.

-
It seems plausible that if n is the sum of the first k p-1 for p prime then that is best and otherwise one takes p-1 for the first few primes until getting close and then adjusts so as not to waste the last bit. If so, then the rough order is easy and the fine details depend on the gaps between primes. –  Aaron Meyerowitz Dec 16 '10 at 16:44
This problem is not far from the largest order achieved for an element of the full symmetric group on n letters. My memory says that the asymptotics look similar, but I suggest you do not trust my memory. Gerhard "Ask Me About System Design" Paseman, 2010.12.16 –  Gerhard Paseman Dec 16 '10 at 18:04
–  Qiaochu Yuan Dec 16 '10 at 18:51
Can you compute the first few of these and check in OEIS? –  Michael Lugo Dec 17 '10 at 1:49
I agree that asymptotically, this is the same as Landau's function (which I did not previously know the name of). Thanks everyone! –  Martin Orr Dec 17 '10 at 16:35

Consider Aaron's suggestion (from his comment). If $p_1,p_2,\ldots$ are the primes in order, then for $n\geq p_1+p_2+\ldots +p_k+k$, then $f(n)\geq p_1p_2\ldots p_k$. Using standard analytic number theory estimates, the log of this lower bound of $f(n)$ grows like $O(k \log k)$, while $n$ grows like $O(k^2 log k)$. So there is a lower bound of $\log f(n)$ of the form $\sqrt{n}$ times some log factors, which shows that any upper bound like the one you have is off by at most a constant factor.

Thinking about this some more, we see that the $+k$ in the bound for $n$ can be discarded in the asymptotics, so we are studying something which has the same asymptotics of Landau's function, for which asymptotics (for its logarithm) are known (and a formula for which is claimed on en.wikipedia).

-

I wanted to get an idea where the bound in Landau's function comes from.

You can do better than multiplying primes. It's better to take powers of primes.

Consider taking products of $p^\alpha$ where $\alpha$ is the largest possible so that $p^\alpha\le m$.

The product is $P(m)=\prod_{p\le m}p^{\lfloor \log m/\log p\rfloor}$. The function $\Phi(m)=\prod_{p\le m}p$ is known to be about $e^m$ (comes out of the prime number theorem). You can see $P(m)=\Phi(m)\Phi(\sqrt m)\Phi(m^{1/3})\ldots\approx e^m$. The sum $\sum_{p\le m}p^{\lfloor \log m/\log p\rfloor}$ is approximately $(m/\log m)m$ (there are $m/\log m$ primes up to $m$ and each one contributes about $m$). If you want the sum to be $n$, you solve $m^2/\log m=n$ giving $m\approx \sqrt{n\log n}$, so that $P(m)\approx \exp(\sqrt{n\log n})$.

-
True, primes and prime powers. Missed that. –  Aaron Meyerowitz Dec 17 '10 at 21:55
and the bold terms match (up to some leading 0's) largest LCM of a 5-partition of n. This sequence is not there exactly as is. However it is pretty close to largest lcm of partitions of n with a few hiccups. That is because the best partitions are the same most of the time and cosist of the first few primes with perhaps 4,8 or 9 included. Sometimes a prime near the end is skipped to get to the next prime. I imagine that after a partition like $[2,3,5,7,\cdots,89]$ things might get a bit more exciting since $91,93,95$ are all composite.