25
$\begingroup$

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?

$\endgroup$
17
  • 7
    $\begingroup$ For the variant where the two sets are not required to have the same number of elements, we may also waive the requirement that we're splitting the integers $1$ to $2n$, and just split the integers $1$ to $n$. That sequence is tabulated at oeis.org/A061057. That sequence is not increasing: $a_7=2<6=a_6$, $a_{10}=30<54=a_9$, $a_{13}<a_{12}$, $a_{31}<a_{30}$, $a_{34}<a_{33}$. $\endgroup$ Mar 31, 2022 at 2:19
  • 9
    $\begingroup$ Aha! A61057 allows splitting the factors of an element across the bipartition, but OP's problem does not. $\endgroup$
    – RobPratt
    Mar 31, 2022 at 3:29
  • 3
    $\begingroup$ Thoughts on asymptotics: Simply taking $X_n=1 \times 3 \times \cdots \times (2n-1)$ and $Y_n = 2 \times 4 \times \cdots \times 2n$, we have $Y_n / X_n \approx \sqrt{n}$ and $X_n Y_n = (2n)!$ so $X_n$ and $Y_n$ are roughly $\sqrt{(2n)!} n^{\pm 1/2}$ and $|X_n-Y_n| \approx \sqrt{(2n)!} n^{1/2}$. It is easy to be slightly smarter and get $|X_n-Y_n| = \sqrt{(2n)!} n^{-C}$ for various constants $C$. But I haven't found a way to achieve $\sqrt{(2n)!} e^{-Cn}$ for any $C>0$. I would guess the optimal behavior is $\sqrt{(2n)!} e^{-o(n)}$. $\endgroup$ Mar 31, 2022 at 17:19
  • 6
    $\begingroup$ The problem was inspired by a question from my 13 year old student Luciana Girón while we were learning to simplify products of fractions. We both wondered how close to 1 could we get by multiplying together six fractions whose numerators and denominators were the integers 1 to 12. The corresponding sequence should thus be called Luciana's sequence! $\endgroup$ Apr 1, 2022 at 1:31
  • 4
    $\begingroup$ A038667 is a closer match than A061057 The equal-sizing requirement is gone, but there's an actual partition going on in A038667, whereas in A061057 we may split 6 = 2 * 3 , say, if that is what it takes to get a good factoring. $\endgroup$
    – user52733
    Apr 3, 2022 at 20:06

3 Answers 3

19
$\begingroup$

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)
$\endgroup$
5
  • $\begingroup$ Still no counterexample at $n=20$, where optimal solutions at 470500040794291200 include [2, 3, 6, 9, 11, 12, 13, 15, 18, 19, 21, 23, 24, 26, 27, 29, 30, 31, 37, 39]. (I'll merge these comments into the answer at some point, but I don't want to bump every time my search program spits out another result). $\endgroup$ Mar 31, 2022 at 21:55
  • 1
    $\begingroup$ It would be better if you edited the additional computations into the answer, rather than leaving them as a list of comments. $\endgroup$ Apr 1, 2022 at 17:21
  • $\begingroup$ @GregMartin, as explicitly noted, that was always my intention. $\endgroup$ Apr 2, 2022 at 23:20
  • $\begingroup$ @MaxAlekseyev and others, if you want to add anything before I propose the current draft for publishing then it's A352813. $\endgroup$ Apr 4, 2022 at 21:02
  • $\begingroup$ @PeterTaylor: I've extended A352813 to $n\leq 70$ terms, and confirmed that the equality ${\tt A352813}(n) = {\tt A038667}(2n)$ continues to hold. There is a counterexamples along these lines with the split of 39!, where the smaller factor can be represented as the product of $\lfloor 39/2\rfloor = 19$ numbers but not of $\lceil 39/2\rceil = 20$ numbers. Similarly, the split of $51!$ does not work in the opposite way around. $\endgroup$ Jun 18, 2022 at 16:32
14
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The two objectives are equivalent since minimizing $\log \frac{(2n)!}p - \log p = \log (2n)! - 2\log p$ is equivalent to maximizing $\log p$, then to maximizing $p$, and thus to minimizing the difference $\frac{(2n)!}{p} - p$. $\endgroup$ Mar 31, 2022 at 17:03
  • $\begingroup$ A spin-off question: mathoverflow.net/q/419722 $\endgroup$ Apr 6, 2022 at 1:57
9
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ The conclusion has the same order of magnitude I suggest in my comment above, though: By Stirling's approximation, $\sqrt{(2n)!} \approx \sqrt{(2n/e)^{2n}} = 2^n (n/e)^n \approx 2^n n!$. $\endgroup$ Mar 31, 2022 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.