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

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.

-
Well, you cannot have a much smaller bound since you can have $a+b=n+1$ (take $a=n$ and $b=1$). –  Seva Jul 27 '13 at 14:51
A slightly better lower bound for some $n$: Take $n=k!$, so that $n!=(n-1)!k!$ –  Kevin P. Costello Jul 27 '13 at 20:43

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

-
Would you explain more on how did you drive $\frac{b-(n-a)-1}{2} \leq \log_2(n)$ ? –  user38122 Aug 12 '13 at 6:58
@Jash: On the one hand, the exponent of 2 in the prime factorization of $\frac{b!}{(n-a)!}$ is at least $\frac{b-(n-a)-1}{2}$, because there are at least that many even numbers in the sequence $n-a+1,\dots,b$. On the other hand, the exponent of 2 in the prime factorization of $\binom{n}{a}$ is at most $\log_2(n)$ by Kummer's theorem (see the link in my original post). These two facts imply the inequality you ask about. –  GH from MO Aug 12 '13 at 7:07

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.

-
I was in the process of writing up a bound $a+b\leq n+O(n/\log n)$ when I saw your update. At any rate, I would formulate your result in the sharper form $a+b\leq n+O(\log n)$. –  GH from MO Jul 27 '13 at 15:47
I don't know if n + O(log(n)) is best possible. In view of (k! - 1)!k! |(k!)!, I would say it is pretty darn good though. –  The Masked Avenger Jul 27 '13 at 16:41

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.

-

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

-
(Unless you allow $n=0$, in which case the $v=1$ and $v=2$ records are $(0,1,0)$ and $(1,1,0)$ respectively.) –  Noam D. Elkies Jul 29 '13 at 3:16
For comparison, the $2$-adic best possibles are 1 [1, 1, 1] 2 [3, 3, 4] 3 [4, 7, 8] 4 [5, 7, 8] 5 [6,15, 16] 6 [7, 15, 16] 7 [8, 127, 128] 8 [9, 127, 128] 9 [10, 255, 256] 10 [11, 255, 256] 11 [12, 1023, 1024] 12 [13, 1023, 1024] 13 [14, 2047, 2048] 14 [15, 2047, 2048]. This is evidence against my earlier belief that one can do a lot better than just the 2-adic analysis! –  Will Sawin Jul 29 '13 at 3:30
for $\nu = 15$, the smallest is $[14335, 18458, 32778]$, and for $\nu = 16$, you get two examples for 32808. (done with SAGE, using $p$-valuations of factorials) –  S. Carnahan Jul 29 '13 at 6:28
Yes, the $v=15$ example [not $\nu$, since it stands for @Aaron Meyerowitz's "virtue"] just turned up here too, using val(m,p, m1,v) = m1=m; v=0; while(m1>0, m1\=p; v+=m1); return(v) and then test(a,b,n) = for(f=n+1,a+b,F=factor(f)[,1];for(i=1,#F,p=F[i];if(val(n,p<val(a,p)+val(b,p),ret‌​urn(0))));return(1) –  Noam D. Elkies Jul 29 '13 at 6:45
Meanwhile $v=16$ turned up: $(13106, 52447, 65536)$. Yes, $n=2^{16}$. What was that about $2$-adic analysis again? –  Noam D. Elkies Jul 29 '13 at 21:53
show 1 more comment

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

-
C code is about 10 times faster. It took my laptop about 4 hours to reach $2^{18} = 262144$, which is the first time that $v=19$ and $v=20$ appear: $(34719, 227444, 262144)$, $(109237, 152927, 262144)$. I think it should be possible to save another factor of $10$ or so to at least reach $2^{21}$; watch this space (unless somebody else does it first)... –  Noam D. Elkies Jul 30 '13 at 13:36
Update: about 100 times faster... $v=21$ and $v=22$ first appear just a bit after $2^{19}$: $(59039, 465398, 524416)$, $(230111, 294839, 524928)$. –  Noam D. Elkies Jul 30 '13 at 14:14
Great! I was just thinking that I waste too much time recomputing valuations, so I will try to make a big array of $p$-valuations of $n!$ for small $p$, and do subtractions from that. –  S. Carnahan Jul 30 '13 at 14:47
@NoamD.Elkies Okay, working in C and precomputing an array of valuations allowed me to work up to 500000 in 150 seconds. I'm getting a weird allocation error when I go above $10^6$, though. –  S. Carnahan Jul 30 '13 at 14:58
Almost all the saving is in just the stored $2$-valuation. I'm also precomputing prime factorizations (Eratosthenes). –  Noam D. Elkies Jul 30 '13 at 15:10
show 1 more comment

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.

-
I think the $p$-valuation of $x$ consecutive integers is at least $\lfloor \frac{x}{p-1} \rfloor - \lfloor \log_p(x+1) \rfloor$, so $a+b-n$ is at most $(p-1)\lfloor \log_p(n) \rfloor + (p-1) \lfloor \log_p \log_p(n) \rfloor +2p-2$. You can use $n=2^k$, $a = k+ \lceil \log_2(k) \rceil$, $b = 2^k-1$ to get close to a 2-adic solution, when $k+\lceil \log_2(k) \rceil$ has the form $2^m-1$. –  S. Carnahan Jul 29 '13 at 3:58
Yes. I think $a=v$, $b= 2^{(v!)_2 -1}$, $c=2^{(v!)_2}$ gives the best possible $2$-adic solutions to $a+b-n=v$ for any $v$, which your formula is the best closed-form approximation to. It's not clear how much more one can gain from including the other primes. –  Will Sawin Jul 29 '13 at 4:04

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.

-
There's also the old observation that $6!7!=10!$, though this has "virtue" only $3$. –  Noam D. Elkies Jul 28 '13 at 15:25
Further, 3!5!7! = 10!; I suspect a bound for the general problem is arbitraily close to 2n. (Actually I can get 2n-2 as a lower bound on the upper bound.) –  The Masked Avenger Jul 28 '13 at 18:55
$2n$ is what falls out of GH's argument in the general case. –  Will Sawin Jul 28 '13 at 19:01
I need more care. Not only do I want an upper bound on a+b+...+c when (a!b!...c!) divides n!, I need that the summands are all greater than 1. –  The Masked Avenger Jul 28 '13 at 19:03
Indeed it does Will. –  The Masked Avenger Jul 28 '13 at 19:05