How $a+b$ can grow when $a!b! \mid n!$

Question

Let $a,b,n$ be natural numbers such that $a!b! \mid n!$. I am looking for a (somehow best) upper bound of $a+b$ in terms of $n$ (for large values on $n$). For example it is clear to see that we must have $a+b \leq 2n$. But unfortunately I am looking for much smaller bound ! Any idea would be helpful.

Answer 1

This is a small variation of Seva's argument yielding a slightly more explicit result.

Assume that $a+b>n$ with $a!b!$ dividing $n!$. Then $$ \prod_{n-a<m\leq b}m=\frac{b!}{(n-a)!} \ \ \text{divides}\ \ \frac{n!}{(n-a)!a!}= \binom{n}{a}. $$ Looking at the exponent of $2$ in the prime decomposition of the two sides, we infer (e.g. by Kummer's theorem) $$ \frac{b-(n-a)-1}{2} \leq \log_2(n),$$ whence $$ a+b-n \leq 1+2\log_2(n). $$ Of course the same result is trivial when $a+b\leq n$.

Answer 2

One has $$ a+b < n+O(\log n), $$ which is best possible in view of $1!n!|n!$. For the proof, assuming that $a!b!|n!$ with $a+b>n$, consider the exponent of $2$ in the prime decomposition of the quotient $n!/(a!b!)$. This exponent is $$ \sum_{1\le k\le\log_2(a+b)} \big(\lfloor n/2^k\rfloor-\lfloor a/2^k\rfloor-\lfloor b/2^k\rfloor \big) = \sigma_1-\sigma_2, $$ where $$ \sigma_1 = \sum_{1\le k\le\log_2(a+b)} \big(\lfloor(a+b)/2^k\rfloor-\lfloor a/2^k\rfloor-\lfloor b/2^k\rfloor \big) $$ and $$ \sigma_2 = \sum_{1\le k\le\log_2(a+b)} \big(\lfloor(a+b)/2^k\rfloor - \lfloor n/2^k\rfloor \big). $$

We thus have $\sigma_1\ge\sigma_2$. On the other hand, it is well known that $\sigma_1\le\log_2(a+b)$ (for, every summand in $\sigma_1$ is either $0$ or $1$). The sum $\sigma_2$ can be estimated by $$ \sigma_2 \ge \sum_{1\le k\le\log_2(a+b)} \big((a+b)/2^k - n/2^k -1 \big) \ge a+b-n - \log_2(a+b) - O(1). $$ As a result, we get $$ a+b-n \le O(\log_2(a+b)), $$ implying the assertion.

Answer 3

This is really a comment, but given all the interest in the question it seemed a good idea to write it as an answer. Apparently what was discussed earlier (in the answers of Seva and GH from MO) is an old result of Erdos! The reference is Aufgabe 557, Elemente Math. (1968) 111-113, which may be found here: http://retro.seals.ch/digbib/view?rid=elemat-001:1968:23::117&id=browse&id2=browse4&id3= . I found this reference in an interesting paper of Erdos, Graham, Ruzsa and Strauss from 1975, which you can find here (see bottom of page 90): http://math.ucsd.edu/~ronspubs/75_03_prime_factors.pdf

Erdos, Graham, Ruzsa and Strauss also comment that there is a constant $c>0$ such that for all $n$ except a set of density zero we have $$ \frac{(2n)!}{n!(n+[c\log n])!} \in {\Bbb N}. $$ Thus the bound of $2n+O(\log n)$ is best possible.

This is also in Erdos's exercise linked above. Note on the history: Erdos proposed as an exercise to show the upper bound $a+b\le n+C\log n$ (part 1) and that this is best possible (part 2). Part 1 was solved by P. Bundschuh (same solution as in GH from MO's response). The solution printed for Part 2 was that sent by the proposer Erdos.

They also raise a "curious problem" in this paper: Namely it is possible that $n!/(a!b!)$ is not an integer for $a+b \ge n+c\log n$ only because of small primes. In other words for every $c$ it is asked whether there exists a $k$ such that for infinitely many (or even all sufficiently large $n$) there are suitable $a$ and $b$ with $a+b>n+c\log n$ and such that $n!/(a!b!)$ has no prime factor $>k$ in its denominator.

Answer 4

FWIW here are the first examples of $a!b! \mid n!$ with $a+b-n = v$ for each $v=1,2,3,\ldots,14$:

 1 [1, 1, 1]
 2 [3, 5, 6]
 3 [6, 7, 10]
 4 [11, 29, 36]
 5 [14, 47, 56]
 6 [47, 59, 100]
 7 [59, 110, 162]
 8 [23, 241, 256]
 9 [31, 239, 261]
10 [187, 239, 416]
11 [447, 620, 1056]
12 [239, 1853, 2080]
13 [1439, 1775, 3201]
14 [1663, 2735, 4384]

This was computed with the following gp code that recursively computes row $m=a+b=n+v$ of Pascal's triangle, reduces mod $m!/(m-v!)$, and returns $(a,b,m)$ once ${m \choose a} \equiv 0$:

allocatemem(2^28)
{
M(v, P,Q) =
  m = v;  P = vector(v+1,i,binomial(v,i-1));
  while(1,
    m++;  P = concat(0,P) + concat(P,0);  Q = P % prod(i=0,v-1,m-i);
    for(a=1,m\2, if(Q[a+1]==0, return([a,m-a,m-v])))
  )
}
for(v=1,14,print(v,M(v)))

I actually asked for $v \leq 20$, but stopped at $14$ after it took about 10 seconds to do each $v \leq 13$, then 20 seconds for $v=14$, and then no output for 15 minutes for $v=15$ $-$ apparently the binomial coefficients are getting too large even for reducing each one modulo $m!/(m-v)!$. In any case this method takes time at least $M^3$ to try all $m \leq M$; it should take time only $M^{2+\epsilon}$ to check for each $a\leq m/2$ and $m \leq M$ the divisibility of $m \choose a$ by every prime factor of $m!/(m-v)!$, but that would take longer to code...

Answer 5

First, I'd like to revisit Will Sawin's upper bound, but I make no promises about off-by-one errors (which I think I made in comments elsewhere on this page). The product of any sequence of $x$ consecutive integers has $p$-valuation at least $\lfloor \frac{x}{p-1}\rfloor - \lfloor \log_p(x+1) \rfloor$. The $p$-valuation of $\binom{n}{a}$ is the number of carries when adding $a$ to $n-a$ in base $p$, so this is bounded above by $\lfloor \log_p n \rfloor$. In other words, the product of the $v = b-(n-a)$ integers from $n-a+1$ to $b$ must satisfy $\lfloor \frac{v}{p-1}\rfloor - \lfloor \log_p(v+1) \rfloor \leq \lfloor \log_p n \rfloor$. Pushing some terms around yields the bound $$v \leq (p-1)\lfloor log_p(n) \rfloor +(p-1) \lfloor log_p log_p n \rfloor + 2p - 2.$$

In particular, $v \leq \lfloor log_2(n) \rfloor + \lfloor log_2 log_2 n \rfloor$. If we only worry about making $\frac{n!}{a!b!}$ into a 2-adic integer instead of an ordinary integer, then this bound is sharp, since the case $n=2^k, a=2^k-1, b = 2^y-1$ saturates it when $k = 2^y-y-1$.

Incidentally, there are infinitely many integers $n$ for which the virtue $v = a+b-n$ is bounded above by 1. In particular, any Mersenne number $n = 2^k-1$ satisfies $\binom{n}{a} \equiv 1 \pmod 2$, so we get a 2-adic obstruction to larger virtue.

When $n$ is large, $(p-1) \lfloor \log_p(n) \rfloor > \lfloor \log_2(n) \rfloor$ for odd $p$, so this suggests that it is good to check 2-adic valuations when eliminating candidate triples. Following Noam D. Elkies's suggestion, I rewrote my program in C. Also, I found an overflow bug in my valuation routine, as a result of using 32 bit integers and multiplying unnecessarily, so some of the previous results for $n>65536$ were false. You can find the original SAGE code by looking at the edit history of this answer. Since the C code is somewhat longer than the SAGE version, I put it here on my web page.

Anyway, starting with k=3 and running up to $2^{25} = 33554432$ took about 48 hours on a 12-core desktop. Here are the results in the form $a, b, n, v$:

3, 5, 6, 2
6, 7, 10, 3
11, 29, 36, 4
14, 47, 56, 5
47, 59, 100, 6
59, 110, 162, 7
23, 241, 256, 8
31, 239, 261, 9
187, 239, 416, 10
447, 620, 1056, 11
239, 1853, 2080, 12
1439, 1775, 3201, 13
1663, 2735, 4384, 14
14335, 18458, 32778, 15
9209, 23615, 32808, 16
13106, 52447, 65536, 17
26207, 39347, 65536, 18
34719, 227444, 262144, 19
109237, 152927, 262144, 20
59039, 465398, 524416, 21
230111, 294839, 524928, 22
496123, 3698204, 4194304, 23
1007871, 3186457, 4194304, 24
983546, 7405087, 8388608, 25
1029947, 7358687, 8388608, 26
527036, 33027423, 33554432, 27
2479487, 31074973, 33554432, 28

The last few entries are reasonable evidence that I don't lose much by only considering powers of two when computing optimal virtue. I computed up to $n=2^{39} = 549755813888$, and have $n=2^{40}$ in progress - this last computation will take about 42 hours. Unlike the previous case, I didn't bother to precompute valuations, due to memory constraints. Code is here - it has no input checks, so bad inputs will produce a segfault.

2, 3, 4, 1
2, 7, 8, 1
5, 14, 16, 3
9, 26, 32, 3
19, 49, 64, 4
17, 116, 128, 5
23, 241, 256, 8
53, 467, 512, 8
314, 719, 1024, 9
482, 1574, 2048, 8
1943, 2164, 4096, 11
1979, 6227, 8192, 14
3317, 13081, 16384, 14
6548, 26234, 32768, 14
26207, 39347, 65536, 18
56375, 74354, 131072, 17
109237, 152927, 262144, 20
58559, 465749, 524288, 20
117350, 931247, 1048576, 21
511613, 1585561, 2097152, 22
1007871, 3186457, 4194304, 24
1029947, 7358687, 8388608, 26
839773, 15937469, 16777216, 26
2479487, 31074973, 33554432, 28
28499711, 38609183, 67108864, 30
13640318, 120577439, 134217728, 29
26335607, 242099879, 268435456, 30
149450463, 387420479, 536870912, 30
42571871, 1031169982, 1073741824, 30
210421817, 1937061863, 2147483648, 32
808182959, 3486784371, 4294967296, 34
66684221, 8523250405, 8589934592, 34
57373109, 17122496111, 17179869184, 36
1071383543, 33288354863, 34359738368, 38
194490575, 68524986199, 68719476736, 38
722568911, 136716384599, 137438953472, 38
2908726651, 27196918033, 274877906944, 40
5820696123, 543935117807, 549755813888, 42
275025321599, 824486306219, 1099511627776, 42 (?)

The optimal virtue for $n=2^k$ hews quite close to the 2-adic upper bound, but some kind of strong height result would be necessary to find enough structure in the solutions to get a guaranteed lower bound for large $n$.

Answer 6

The product of $x$ consecutive numbers has $2$-adic valuation at least $x - \ln_2 x-1$, which means we can improve GH's explicit form of Seva's result to $a+b \leq n + \log_2 (n) + O( \log \log n)$. Improving the coefficient of $\log_2 n$ further seems to require at least a little bit of deep mathematics. I'll sketch out why.

First note that this bound is best possible if one relaxes the condition $a! b! | n!$ to $(a!)_2 + (b!)_2 \leq (n!)_2$, where $x_2$ is the $2$-adic valuation of $x$. This is because $n=2^k$, $a=k+1$, $b=2^k-1$ satisfies this weaker condition, and $a+b=n+\log_2 n$.

Thus to do better we need to include divisibility by other primes in our argument. If we just use a single prime $p$, running the same argument gives us the bound $a+b-n = 1 + p \log_p n $ or $a+b-n = 1 + (p-1) \log_p n + O(\log \log n)$. This bound is worse, and it is best possible $p$-adically.

So to do better we need to include multiple primes. For instance, we might use divisibility at both $2$ and $3$. But this runs into trouble when a power of $2$ and a power of $3$ are very close together. If $2^x$ and $3^y$ are in the interval $[n-c,n]$, then setting $a=x$ and $b=n-c-1$, so we need at least a little bit of separation between powers of $2$ and $3$ to have a hope of getting a better constant by this method. So perhaps Baker's Theorem needs to be used?

On the other hand, one could combine the valuations of all primes with some appropriate weight function $w_p$, relaxing the problem to the inequality $\sum_p (a!)_p w_p + \sum_p (b!)_p w_p \leq \sum_p (n!)_p w_p$. Clearly choosing $w_p= \ln p$ gives a very bad bound, but perhaps a slower-growing function could prove effective. Controlling this kind of sum seems like an analytic number theory question, although I don't have any rigorous argument that this impression is accurate.

Answer 7

Here are a few computed examples, but first comments which move things along, although not very far.

I'll write examples as $\frac{n!}{a!b!}$ with $a \ge b.$ We might define the virtue of such an example to be $v=a+b-n.$ Then we know that $\frac{(k!)!}{(k!-1)!k!}$ has virtue $k-1.$

One can look the denominators (after reduction to lowest terms) of $\frac{n!}{a!(b+1)!},\frac{n!}{(a+1)!b!}$ and $\frac{(n-1)!}{a!b!}$ to see what primes it was which denied a slightly more virtuous example. My observation from small cases is that, perhaps unsurprisingly, is is frequently just $2$ or some few small primes.

An trivial yet helpful equivalent condition which keeps the numbers smaller is that $b!$ divide $(a+1)(a+2)\cdots(a+b-v).$ So we are looking for the product of relatively few consecutive integers to be a multiple of $b!$

I was excited by the fact that $7!=71^2-1=70\cdot 72$ giving virtue $4$ to $\frac{72!}{69!7!}$ which is ahead of $\frac{120!}{119!5!}.$ However the first examples with virtue $4$ are actually $\frac{36!}{23!17!}$ and $\frac{36!}{29!11!}.$ Observe that $\frac{35!}{23!17!},\frac{36!}{24!17!}$ and $\frac{36!}{23!18!}$ have denominators $4,8$ and $2$. The best examples seem to have $b$ much larger than $v.$

There are three more values of $n$ giving virtue $4$ before

• $\frac{56!}{47!14!}$ , the first of $5$ values of $n$ giving virtue $5$ before:
• $\frac{100!}{59!47!}$ , the first of $10$ values of $n$ giving virtue $6$ before:
• $\frac{162!}{107!62!}$ and $\frac{162!}{110!59!}$, the first of $2$ values of $n$ giving virtue $7$ before:
• $\frac{256!}{142!122!},\frac{256!}{202!62!},\frac{256!}{239!25!}$ and $\frac{256!}{241!23!}$, the only value of $n$ giving virtue $8$ before:
• $\frac{261!}{223!47!}$ and $\frac{261!}{239!31!}$ of virtue $9.$

Another example with virtue $9$ is $\frac{273!}{223!59!}.$ That is the only one for $n=273.$ I do not know if there are any other examples before the first of virtue $10.$

Note that $224=2^57$ and $240=2^43\ 5$ are just a bit too far for the denominator in more than one case.

Later

One might add that $225=15^2$ and $243=3^5$ along with $242=2\ 11^2$ are also potential obstacles in the denominator.