1
$\begingroup$

Standard apology in case this is something simple, as I'm not a number theorist.

Let $E_1, \dots, E_n$ be disjoint finite sets of natural numbers, such that for any $a_1 \in E_1, \dots, a_n \in E_n$, we have $a_i | a_j$ iff $i = j$.

I am interested in maximizing the reciprocal sums over the product $E_1 \times \cdots \times E_n$, subject to an upper bound on the lcm of the union $E = E_1 \cup \cdots \cup E_n$. That is, I want to maximize $$ \sum_{a_1 \in E_1, \dots, \, a_n \in E_n} \sum_{i=1}^n \frac{1}{a_i} = \sum_{i = 1}^n \left( \sum_{a \in E_i} \frac{1}{a} \right) \prod_{j \neq i} |E_j| $$ subject to $$ \mathrm{lcm}\left( \bigcup_{i=1}^n E_i \right) \leq C = C_n $$ The idea is that $C$ is going to have to be huge, so you choose it large enough that you at least have a fair number of possible $(E_1, \dots, E_n)$'s, then see how large you can make the sum for that choice of $C$.

As an example, consider the singleton case. If $|E_i| = 1$ for each $i$, say $E_i = \{ a_i \}$, then we are just maximizing the single sum $$ \sum_{i=1}^n \frac{1}{a_i} $$ subject to $$ \mathrm{lcm}(a_1, \dots, a_n) \leq C $$ In this case, I believe (though I may be wrong, as I haven't quite worked the proof out) that $$ \sum_{i=1}^n \frac{1}{a_i} \leq \sum_{i=1}^n \frac{1}{p_i} \sim \log \log n $$ with $p_i$ the $i$th prime, whenever $a_1, \dots, a_n$ are such that $a_i | a_j$ only when $i = j$. Now, $$\mathrm{lcm}(p_1, \dots, p_n) = p_1 \dots p_n \sim (n \log n)^n $$ so for the general case you should choose $C = n^{10n}$ or something like that. (That kind of thing is fine in the pure mathematical setting where this number theory problem arose, although, unsurprisingly, it's totally unusable in the applied setting that was the original motivation.)

I suspect that in general, the best one can do is to take the union $E = E_1 \cup \dots \cup E_n$ to be the set of the first $m$ primes for the greatest $m > n$ such that $(m \log m)^m \leq C$, and then choose the partition into $E_1, \dots, E_n$ that optimizes the reciprocal sums. But it may well be possible to do better than that.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ It might be possible to consider all numbers of a form like $2^a 3^b 5^c$ with $a+b+c$ being some constant number. None of these divide each other, and there are quite a few, but their LCM is fairly small. $\endgroup$
    – Daniel Weber
    Commented Mar 15 at 20:52
  • $\begingroup$ You know, I tried that in the singleton case, and I don't think it helps there, at least when $C$ is not much larger than $(n \log n)^n$, but when $C$ can be bigger and the $|E_j|$'s can be bigger, too, it looks like it may help. I'll either revise or answer the question if I get anywhere with this. Thanks! $\endgroup$
    – Sophie M
    Commented Mar 15 at 21:29
  • 1
    $\begingroup$ Am I understanding correctly that within each $E_i$ one element may divide another? If so, there may be interesting ideas where each $E_i$ is something like $\{m_i x : x \in X\}$ where $X$ is something like squarefree $k$-smooth numbers. $\endgroup$
    – Peter Taylor
    Commented Mar 16 at 14:26

0

Reset to default

You must log in to answer this question.