Splitting the integers from $1$ to $2n$ into two sets with products as close as possible

Question

For each positive integer $n$, split the integers $1$ to $2n$ into two sets of $n$ elements each, and such that the products of the elements in each of these sets are as close as possible, say they differ by $a(n)$.

It can be checked that $a(1)=1$, $a(2)=2$, $a(3)=6$, $a(4)=18$, and $a(5)=30$.

Is this sequence strictly increasing?

What about if it is not required that the two sets contain the same number of elements?

Answer 1

Original question

Is this sequence strictly increasing?

No.

n  difference     smaller half
16 16753029012720 [3, 5, 6, 7, 9, 10, 11, 13, 15, 18, 19, 21, 25, 27, 29, 30]
17 10176199188480 [4, 6, 7, 8, 9, 11, 12, 13, 14, 15, 18, 19, 21, 22, 27, 28, 33]

What about if it is not required that the two sets contain the same number of elements?

The same counterexample applies.

Further questions arising

Is the requirement for equally sizes parts at all relevant?

Rob Pratt commented that for $n \le 10$ the optimal split without the requirement for equally sized parts is attainable with equally sized parts. This continues to hold up to $n = 30$:

1                                 1 [1]
2                                 2 [1, 4]
3                                 6 [2, 3, 4]
4                                18 [2, 3, 4, 8]
5                                30 [2, 3, 5, 7, 9]
6                               576 [2, 4, 5, 6, 9, 10]
7                               840 [3, 4, 5, 6, 7, 9, 13]
8                             24480 [2, 4, 6, 8, 9, 10, 11, 12]
9                             93696 [2, 4, 5, 7, 8, 10, 14, 15, 17]
10                           800640 [3, 4, 5, 7, 8, 10, 13, 14, 15, 17]
11                          7983360 [4, 5, 6, 7, 8, 9, 11, 12, 13, 17, 19]
12                         65318400 [4, 5, 6, 7, 8, 9, 12, 14, 15, 16, 17, 19]
13                       2286926400 [3, 5, 6, 7, 9, 11, 12, 13, 14, 15, 18, 21, 26]
14                      13680979200 [3, 5, 6, 7, 9, 10, 11, 12, 15, 18, 20, 22, 23, 27]
15                     797369149440 [3, 5, 6, 8, 9, 10, 12, 13, 15, 17, 18, 20, 25, 26, 27]

18                  159943859712000 [1, 3, 5, 7, 8, 10, 11, 12, 13, 15, 16, 17, 20, 22, 24, 30, 31, 32, 33]
19                26453863460044800 [1, 3, 5, 6, 7, 8, 9, 12, 13, 14, 18, 19, 21, 24, 27, 28, 35, 36, 37, 38]
20               470500040794291200 [1, 3, 5, 6, 7, 9, 11, 12, 13, 15, 18, 19, 23, 24, 26, 27, 29, 31, 36, 37, 39]
21             20720967220237197312 [1, 3, 4, 7, 8, 9, 12, 13, 14, 16, 17, 18, 23, 24, 26, 27, 28, 29, 32, 36, 39, 41]
22             61690805562507264000 [1, 3, 5, 7, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 26, 28, 30, 31, 32, 34, 35, 42]
23           9203996481363478738944 [1, 3, 4, 6, 7, 9, 11, 12, 13, 17, 18, 19, 21, 26, 27, 29, 31, 33, 36, 37, 38, 41, 42, 43]
24         226577104515475594214400 [1, 3, 5, 6, 7, 9, 11, 12, 14, 17, 19, 21, 22, 23, 27, 28, 29, 33, 34, 35, 37, 38, 41, 42, 47]
25        4571875103611079835648000 [1, 5, 6, 7, 8, 10, 11, 12, 13, 14, 16, 19, 20, 22, 24, 26, 27, 29, 32, 36, 37, 39, 41, 43, 47, 48]
26       20218804109333464320000000 [1, 3, 5, 7, 9, 10, 13, 14, 15, 18, 19, 20, 21, 23, 24, 25, 26, 27, 29, 31, 36, 39, 41, 43, 46, 47, 52]
27     3678271958960426245017600000 [1, 3, 5, 7, 10, 11, 13, 14, 15, 17, 18, 19, 20, 22, 23, 25, 26, 29, 30, 31, 34, 39, 41, 43, 46, 48, 53, 54]
28   217018448461953024000491520000 [2, 4, 6, 8, 9, 11, 12, 15, 16, 18, 23, 24, 26, 27, 30, 32, 33, 36, 37, 38, 39, 43, 44, 45, 46, 48, 54, 55]
29 18646773190859199121234329600000 [1, 3, 5, 7, 10, 11, 13, 14, 15, 19, 20, 21, 22, 24, 25, 26, 28, 29, 30, 31, 35, 36, 38, 39, 42, 43, 48, 49, 52, 57]
30 90984319783113193178231808000000 [1, 3, 5, 7, 9, 10, 11, 14, 15, 18, 19, 20, 21, 22, 23, 27, 28, 31, 33, 35, 37, 41, 42, 43, 44, 46, 47, 49, 54, 55, 56]

It gets quite tight, though: for $28$, once multiplicities of other primes are taken into account there's very almost a shortfall of powers of three. I need to improve my search code to take this much further.

Asymptotics

Seva and David E Speyer address the question of asymptotics. The observation that for known values the difference rarely exceeds $n!$ ($n=29$ is the only exception, with a difference of $\sim 2.1 n!$) puts it on the level of Seva's abc-conjecture-conditional lower bound, and beats David's guess that the asymptotic is $\sqrt{(2n)!} e^{-o(n)}$. I have been no more successful than David in finding a strategy which beats $\sqrt{(2n)!}n^{-C}$, but I think there's an argument in the spirit of Erdős for why it's reasonable to hope that the asymptotic is $\Theta(n!)$ (or $\sqrt{(2n)!} e^{-cn}$).

If we want a difference less than $n!$ then to first order we want the smaller half's product to be $\ge \sqrt{(2n)!} - \tfrac12 n!$. The products of half of the terms pair up, and the smaller half ranges from $n!$ to $\sqrt{(2n)!}$. There are $\frac{(2n)!}{2n!^2}$ smaller halves. If their logarithms are distributed evenly in the given range then asymptotically we expect there to be far more than one above the desired threshold. So the question is how unevenly distributed the logarithms are. Calculating that is outside my skillset, but I can build an empirical table of the number of products which fall within the required range for small $n$. The headers abbreviate asymmetric (i.e. without the requirement for parts of equal size), heuristic, and symmetric (with the requirement). I've generally rounded the heuristic down unless the fractional part is above 0.9. Note that these calculations were done on the basis of exact thresholds, not the first order approximation.

 n   asym (heur)      sym (heur)

 8     14 (9)          14 (6)
 9      2 (16)          2 (10)
10     21 (28)         21 (17)
11    312 (51)        279 (31)
12    351 (93)        319 (55)
13     64 (169)        59 (99)
14   1849 (312)      1637 (180)
15     42 (577)        39 (330)
16   2777 (1073)     2383 (606)
17    292 (2007)      258 (1119)
18  10725 (3768)     9164 (2077)
19   3829 (7099)     3215 (3870)
20    530 (13421)     459 (7237)

Answer 2

Here are optimal solutions for $n \le 10$, and the two sets happen to be equicardinal even if you don't enforce that: \begin{matrix} n & a_n & \text{solution} \\ \hline 1 & 1 & \{2\},\{1\} \\ 2 & 2 & \{2,3\},\{1,4\} \\ 3 & 6 & \{1,5,6\},\{2,3,4\} \\ 4 & 18 & \{1,5,6,7\},\{2,3,4,8\} \\ 5 & 30 & \{2,3,4,8,10\},\{1,5,6,7,9\} \\ 6 & 576 & \{1,4,7,8,9,11\},\{2,3,5,6,10,12\} \\ 7 & 840 & \{2,4,5,6,8,11,14\},\{1,3,7,9,10,12,13\} \\ 8 & 24480 & \{1,5,6,7,8,13,14,15\},\{2,3,4,9,10,11,12,16\} \\ 9 & 93696 & \{2,3,6,8,9,11,12,13,18\},\{1,4,5,7,10,14,15,16,17\} \\ 10 & 800640 & \{2,3,4,8,9,11,12,18,19,20\},\{1,5,6,7,10,13,14,15,16,17\} \\ \end{matrix}

I obtained these via integer linear programming by instead minimizing the difference in log products (sum of logs) rather than difference in products.

Answer 3

$\newcommand{\sub}[1]{_{\substack{m\in[1,2n] \\ #1}}}$ $\newcommand{\td}{{\widetilde d}}$ $\renewcommand{\cP}{{\mathcal P}}$

For the growth rate, we have the upper bound $a_n\le 2^nn!$ and, conditionally to the abc conjecture, the nearly-matching lower bound $a_n>ce^{-2(1+\varepsilon)n}\sqrt{(2n)!}$, for any fixed $\varepsilon>0$, with a constant $c$ depending on $\varepsilon$. Unconditional lower bounds seem to be much subtler; in this direction, I will show that $a_n>e^{(1+o(1))(\ln n\ln\ln n)^c}$ with an absolute constant $c>0$ (one can take $c=1/5$).

The upper bound $a_n\le 2^nn!$ can be obtained as follows. Let $X_1:=1$, $Y_1:=2$, and $$ X_n:=\min\{(2n-1)Y_{n-1},2nX_{n-1}\}, \ Y_n:=\max\{(2n-1)Y_{n-1},2nX_{n-1}\}, \quad n\ge 2. $$ Clearly, one can partition $[1,2n]$ into two equal-sized subsets so that the product of all elements of the first subset is $X_n$, while for the second subset, the product is $Y_n$.

We notice that $X_n\le 2^nn!$ by a straightforward induction. Moreover, arguing inductively, we obtain $Y_n-X_n\le 2^nn!$: \begin{align*} Y_n-X_n &= |(2n-1)Y_{n-1}-2nX_{n-1}| \\ &\le (2n-1)(Y_{n-1}-X_{n-1})+X_{n-1} \\ &\le (2n-1)2^{n-1}(n-1)! + 2^{n-1}(n-1)! \\ &= 2^nn!. \end{align*} Therefore, $a_n\le Y_n-X_n\le 2^nn!$.

For a lower bound conditional to the abc conjecture, consider a decomposition $(2n)!=P_1P_2$ with $P_2>P_1$, and let $D:=\gcd(P_1,P_2)$ and $P_i':=P_i/D$. From $P_1'+(P_2'-P_1')=P_2'$, assuming the abc conjecture, for any fixed $\varepsilon>0$ we have $P_2'\le Cr^{1+\varepsilon}$, where $r$ is the radical of the product $P_1'P_2'(P_2'-P_1')$, and $C$ is a constant depending on $\varepsilon$. The radical does not exceed the product of all primes up to $2n$, which is $e^{(2+o(1))n}$ by the prime number theorem. Furthermore, from $P_1'<P_2'$ and $P_1'P_2'=(2n)!/D^2$ we conclude that $P_2'>\sqrt{(2n)!}/D$. This yields $$ \sqrt{(2n)!}/D < P_2' < Ce^{(2+o(1))(1+\varepsilon)n} < Ce^{2(1+\varepsilon)n} $$ resulting in $D>C^{-1}e^{-2(1+\varepsilon)n}\sqrt{(2n)!}$. It remains to notice that $P_2-P_1\ge D$ since both $P_2$ and $P_1$ are divisible by $D$.

For an unconditional bound, given a partition $[1,2n]=\cP_1\cup\cP_2$, let $P_i:=\prod_{m\in\cP_i}m$; thus, $P_1P_2=(2n)!$. For $i,j\in\{1,2\}$ with $i\ne j$, let $Q_i$ be the product of all primes dividing $P_i$ but not dividing $P_j$. Furthermore, let $Q_0$ be the product of all primes in $[1,2n]$ dividing both $P_1$ and $P_2$; thus, $Q_0Q_1Q_2$ is the product of all primes in $[1,2n]$.

The idea behind our argument is quite simple. Since both $P_1$ and $P_2$ are divisible by $Q_0$, we have $|P_1-P_2|\ge Q_0$; thus, it suffices to show that $Q_0$ is large. Assuming for a contradiction that $Q_0$ is small, at least one of $Q_1$ and $Q_2$, say the former, is large. This means, there are many primes dividing $P_1$ but not dividing $P_2$. For any such prime $p$, the set $P_1$ contains all multiples of $p$ in the range $[1,2n]$. But this would make $P_1$ significantly larger than $\sqrt{(2n)!}$, and hence make $P_2$ significantly smaller than $\sqrt{(2n)!}$, resulting in $|P_1-P_2|$ large.

We now work out the details.

For integer $d\in[1,2n]$ let $\td$ denote the product of all multiples of $d$ in the range $[1,2n]$; therefore writing $L:=\lfloor\frac{2n}{d}\rfloor$, we have $\td=d^L\cdot L!$ and then, from Stirling's formula, $$ \ln\td = \left(\frac 1d+\frac{\theta}{2n}\right) \,\ln((2n)!),\quad |\theta|<1. \tag{$*$} $$

The key observation is that $\cP_1$ contains only those $m\in[1,2n]$ with $\gcd(m,Q_2)=1$. Therefore, $$ P_1 \le \prod\sub{\gcd(m,Q_2)=1} m \le \prod\sub{\gcd(m,D)=1} m $$ for any divisor $D\mid Q_2$. Using the approximation ($*$), we get \begin{align*} \ln P_1 &\le \sum\sub{} \ln m \sum_{d\mid\gcd(m,D)} \mu(d) \\ &= \sum_{d\mid D} \mu(d) \ln \td \\ &\le \left( \sum_{d\mid D} \frac{\mu(d)}d + \frac{1}{2n}(2^k-1) \right) \ln((2n)!) \\ &= \left( \prod_{p\mid D}\left(1-\frac1p\right) + \frac{2^{k-1}}{n} - \frac1{2n}\right) \ln((2n)!) \end{align*} where $\mu$ is the Möbius function, and $k$ is the number of prime divisors of $D$. Assuming that $\ln P_1\ge\frac12\left(1-\frac1{n}\right)\,\ln((2n)!)$ (as we certainly can), we conclude that $$ \prod_{p\mid D}\left(1-\frac1p\right) > \frac12 - \frac{2^{k-1}}{n} \ge \frac14 $$ provided $k\le \log_2 n-1$.

To summarize, for any $D\mid Q_2$ with at most $K:=\lfloor \log_2n\rfloor-1$ prime divisors we have $\prod_{p\mid D}\left(1-p^{-1}\right)>1/4$. By symmetry, this is also true with $Q_2$ replaced with $Q_1$. Consequently, for any $D\mid(Q_1Q_2)$ with at most $K$ prime divisors we have $\prod_{p\mid D}\left(1-p^{-1}\right)>1/16$; as a result, $\sum_{p\mid D}p^{-1}<3$.

We notice that if $Q_1Q_2$ has fewer than $K$ prime divisors, then $Q_1Q_2<(2n)^K=e^{o(n)}$ whence $|P_1-P_2|\ge Q_0\ge e^{(1+o(1))n}$. Suppose therefore that $Q_1Q_2$ has at least $K$ prime divisors. We choose $D$ to be the product of the $K$ smallest prime divisors of $Q_1Q_2$, and we denote by $M$ the largest of these $K$ smallest divisors; notice that $M>(1+o(1))|K|\ln(|K|)>\ln n\ln\ln n$ by the prime number theorem. Let $m:=M^c$ with $c\in(0,1)$. If $c$ is sufficiently small, then by Mertens' second theorem, and recalling that $\sum_{p\mid D}p^{-1}<3$, we obtain $$ \sum_{\substack{m\le p\le M \\ p\nmid D}} \frac1p > \sum_{m\le p\le M} \frac1p - 3 > \ln\frac{\ln M}{\ln m} - 3 + o(1) > 1. $$ Denoting by $T$ the number of primes $p\nmid D$ in the range $[m,M]$, we thus have $T>m=M^c>(\ln n\ln\ln n)^c$. The product of these $T$ primes is at least as large as the product of the first $T$ primes, which is $$ e^{(1+o(1))T} = e^{(1+o(1))(\ln n\ln\ln n)^c}. $$ The assertion follows in view of $|P_1-P_2|\ge Q_0$ and since any prime in $[1,M]$ not dividing $D$ is a divisor of $Q_0$.