Return to Answer

For the order of magnitude, we have the upper bound $a_n\le 2^nn!$.

To see this, 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!$.

On the other hand, conditionally to the ABC conjecture, we have $a_n>ce^{-Cn}\sqrt{(2n)!}$ with appropriate positive constants $c$ and $C>0$. (Indeed, one can prove something like $a_n>e^{-2(1+c)n}\sqrt{(2n)!}$ for any fixed $c>0$ and $n$ sufficiently large, with a little more care). For the proof, 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 we have, say, $P_2'\le Cr^{3/2}$, where $r$ is the radical of the product $P_1'P_2'(P_2'-P_1')$, and $C>0$ is an absolute constant. The radical does not exceed the product of all primes up to  $2n$, which is $4^{2n}$ at most by a well-known result of Erdos (to avoid using heavy tools, like the PNT). 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' < C 4^{3n} $$ resulting in $D>C^{-1}4^{-3n} \sqrt{(2n)!}$. It remains to notice that $P_2-P_1\ge D$ since both $P_2$ and $P_1$ are divisible by $D$.

$\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$.

Addressing the asymptotic growth rate / the order of magnitude, we have the surprisingly sharp estimates $$ \frac C{\sqrt[4]{\pi n}}\,2^nn! \approx C\sqrt{(2n)!} < a_n\le 2^nn! $$ where $C=\sqrt2-\frac1{\sqrt2}\approx 0.707$ and the lower bound assumes that $n$ is not too small ($n\ge 10$ is probably fine). Indeed, we prove the upper bound presenting a partition into equal-sized subsets, while the proof of the lower bound does not assume the subsets to be of the same size.

Starting with the upper bound, we 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!$, proving the upper bound.

We now turn to the proof of the lower bound.

Suppose that $[1,2n]=S_1\cup S_2$ is a partition with $S_1$ and $S_2$ of possibly distinct sizes. For $i\in\{1,2\}$, let $P_i$ be the product of the elements of $S_i$. We claim that if $P_1<P_2$, then $P_1\ge \sqrt{(2n)!/2}$, as a result of which $P_2\le\sqrt{2(2n)!}$ and $P_2-P_1\le C\sqrt{(2n)!}$ where, we recall, $C=\sqrt2-\frac1{\sqrt2}\approx 0.707$.

  For the proof, suppose that the partition $[1,2n]=S_1\cup S_2$ is optimal in the sense that the difference $P_2-P_1$ is as small as possible (subject to $P_1<P_2$), over all partitions of $[1,2n]$. In view of $P_1P_2=(2n)!$, this is equivalent to $P_2$ being smallest possible. Aiming at a contradiction, we assume that $P_1<\sqrt{(2n)!/2}$ and then $P_2>\sqrt{2(2n)!}$ whence $2P_1<P_2$.

Let $M:=\max S_2$; we claim that in fact, $[1,M]\subseteq S_2$. Indeed, assuming the interval $[1,M]$ not to be entirely contained in $S_2$, denote by $k$ the largest element of $S_1$ contained in this interval, and let $S_1':=S_1\cup\{k+1\}\setminus\{k\}$. For the product $P_1'$ of the elements of $S_1'$, we then have the estimate $P_1<P_1'=\Big(1+\frac1k\Big)\le 2P_1<P_2$, contradicting optimality of the original partition.

Thus, $[1,M]\subseteq S_2$ where $M=\max S_2$. This means that, indeed, $S_2=[1,M]$, while $S_1=[M+1,2n]$. We now observe that of the numbers $M+2$ and $M+3$, one is even and thus can be written as $2K$ with $K\in[3,M]\subseteq S_2$. Replacing in $S_1$ the number $2K-1\in\{M+1,M+2\}$ with the numbers $2$ and $K$, we get a subset $S_1''\subseteq[1,2n]$ with the product of its elements exceeding $P_1$ and at most $\frac{2K}{2K-1}P_1<2P_1<P_2$. This, again, contradicts the minimality of the original partition, completing the proof.

For the order of magnitude, we have the upper bound $a_n\le 2^nn!$.

To see this, 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!$.

On the other hand, conditionally to the ABC conjecture, we have $a_n>ce^{-Cn}\sqrt{(2n)!}$ with appropriate positive constants $c$ and $C>0$. (Indeed, one can prove something like $a_n>e^{-2(1+c)n}\sqrt{(2n)!}$ for any fixed $c>0$ and $n$ sufficiently large, with a little more care). For the proof, 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 we have, say, $P_2'\le Cr^{3/2}$, where $r$ is the radical of the product $P_1'P_2'(P_2'-P_1')$, and $C>0$ is an absolute constant. The radical does not exceed the product of all primes up to $2n$, which is $4^{2n}$ at most by a well-known result of Erdos (to avoid using heavy tools, like the PNT). 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' < C 4^{3n} $$ resulting in $D>C^{-1}4^{-3n} \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 the order of magnitude, we have the upper bound $a_n\le 2^nn!$.

To see this, 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!$.

On the other hand, conditionally to the ABC conjecture, we have $a_n>ce^{-Cn}\sqrt{(2n)!}$ with appropriate positive constants $c$ and $C>0$. (Indeed, one can prove something like $a_n>e^{-2(1+c)n}\sqrt{(2n)!}$ for any fixed $c>0$ and $n$ sufficiently large, with a little more care). For the proof, 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 we have, say, $P_2'\le Cr^{3/2}$, where $r$ is the radical of the product $P_1'P_2'(P_2'-P_1')$, and $C>0$ is an absolute constant. The radical does not exceed the product of all primes up to $2n$, which is $4^{2n}$ at most by a well-known result of Erdos (to avoid using heavy tools, like the PNT). 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' < C 4^{3n} $$ resulting in $D>C^{-1}4^{-3n} \sqrt{(2n)!}$. It remains to notice that $P_2-P_1\ge D$ since both $P_2$ and $P_1$ are divisible by $D$.

Addressing the asymptotic growth rate / the order of magnitude, we have the surprisingly sharp estimates $$ \frac C{\sqrt[4]{\pi n}}\,2^nn! \approx C\sqrt{(2n)!} < a_n\le 2^nn! $$ where $C=\sqrt2-\frac1{\sqrt2}\approx 0.707$ and the lower bound assumes that $n$ is not too small ($n\ge 10$ is probably fine). Indeed, we prove the upper bound presenting a partition into equal-sized subsets, while the proof of the lower bound does not assume the subsets to be of the same size.

Starting with the upper bound, we 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!$, proving the upper bound.

We now turn to the proof of the lower bound.

Suppose that $[1,2n]=S_1\cup S_2$ is a partition with $S_1$ and $S_2$ of possibly distinct sizes. For $i\in\{1,2\}$, let $P_i$ be the product of the elements of $S_i$. We claim that if $P_1<P_2$, then $P_1\ge \sqrt{(2n)!/2}$, as a result of which $P_2\le\sqrt{2(2n)!}$ and $P_2-P_1\le C\sqrt{(2n)!}$ where, we recall, $C=\sqrt2-\frac1{\sqrt2}\approx 0.707$. 

For the proof, suppose that the partition $[1,2n]=S_1\cup S_2$ is optimal in the sense that the difference $P_2-P_1$ is as small as possible (subject to $P_1<P_2$), over all partitions of $[1,2n]$. In view of $P_1P_2=(2n)!$, this is equivalent to $P_2$ being smallest possible. Aiming at a contradiction, we assume that $P_1<\sqrt{(2n)!/2}$ and then $P_2>\sqrt{2(2n)!}$ whence $2P_1<P_2$.

Let $M:=\max S_2$; we claim that in fact, $[1,M]\subseteq S_2$. Indeed, assuming the interval $[1,M]$ not to be entirely contained in $S_2$, denote by $k$ the largest element of $S_1$ contained in this interval, and let $S_1':=S_1\cup\{k+1\}\setminus\{k\}$. For the product $P_1'$ of the elements of $S_1'$, we then have the estimate $P_1<P_1'=\Big(1+\frac1k\Big)\le 2P_1<P_2$, contradicting optimality of the original partition.

Thus, $[1,M]\subseteq S_2$ where $M=\max S_2$. This means that, indeed, $S_2=[1,M]$, while $S_1=[M+1,2n]$. We now observe that of the numbers $M+2$ and $M+3$, one is even and thus can be written as $2K$ with $K\in[3,M]\subseteq S_2$. Replacing in $S_1$ the number $2K-1\in\{M+1,M+2\}$ with the numbers $2$ and $K$, we get a subset $S_1''\subseteq[1,2n]$ with the product of its elements exceeding $P_1$ and at most $\frac{2K}{2K-1}P_1<2P_1<P_2$. This, again, contradicts the minimality of the original partition, completing the proof.