linear combinations of binomial coefficients

Max A. maxale at gmail.com
Thu Aug 3 04:01:38 CEST 2006


SeqFans,

It was hypothesized that for any set of n>=2 distinct positive
integers c1<c2<...<cn there exists a set integers k1,...,kn such that
the following linear combination of binomial coefficients is divisible
by p^(2n-1) for *all* large enough prime p:
k1*C(c1*p,p) + k2*C(c2*p,p) + ... + kn*C(cn*p,p)

For example, 2*C(p,p) - C(2p,p) is divisible by p^3 for all prime
p>=5. As far as I remember, this fact was given as a problem at some
International Math Olympiad.
Another example is divisibility by p^7 of 12*C(p,p) - 9*C(2p,p) +
2*C(3p,p) for all prime p>=7.

In this message I will focus on a particular case of ci=i for
i=1,...,n (as in the above two examples).

I have computed numerically corresponding "outer" coefficients for
n=2,...,15 and corresponding minimum value of prime required for
divisibility by p^(2n-1). The results are presented in the following
table:

n=2: p>=5: [2, -1]
n=3: p>=7: [12, -9, 2]
n=4: p>=11: [60, -54, 20, -3]
n=5: p>=3: [840, -840, 400, -105, 12]
n=6: p>=13: [2520, -2700, 1500, -525, 108, -10]
n=7: p>=17: [27720, -31185, 19250, -8085, 2268, -385, 30]
n=8: p>=3: [360360, -420420, 280280, -133770, 45864, -10780, 1560, -105]
n=9: p>=19: [720720, -864864, 611520, -321048, 127008, -36960, 7488, -945, 56]
n=10: p>=23: [12252240, -15036840, 11138400, -6297480, 2776032,
-942480, 238680, -42525, 4760, -252]
n=11: p>=3: [232792560, -290990700, 223839000, -134303400, 64465632,
-24622290, 7335900, -1645875, 261800, -26334, 1260]
n=12: p>=29: [232792560, -295467480, 234498000, -147733740, 75977352,
-31864140, 10759320, -2858625, 575960, -82764, 7560, -330]
n=13: p>=3: [5354228880, -6884008560, 5609192160, -3681032355,
2004461316, -907369320, 338635440, -102567465, 24601720, -4499352,
589680, -49335, 1980]
n=14: p>=3: [26771144400, -34802487720, 29002073100, -19704349665,
11259628380, -5432276850, 2201130360, -740765025, 203523320,
-44504460, 7452900, -897897, 69300, -2574]
n=15: p>=31: [80313433200, -105411381075, 89565225750, -62695658025,
37334557260, -19012968975, 8254238850, -3030402375, 929128200,
-233648415, 46953270, -7252245, 808500, -57915, 2002]

It is interesting to notice that the lowest coefficients seem to form sequence
A099996(n)=LCM(1,2,...,2n) while the highest coefficients seem to form
sequence A068550(n)=LCM(1,...,2n)/C(2n,n) with alternating signs. I
cannot find any other columns/diagonals from this table in the OEIS.

The sequence of lower bounds for prime p seems to be just a sequence
of all prime numbers with occasional "drops" to the absolute minimum
value 3 (at n=5,8,11,13,14,...)

Max






More information about the SeqFan mailing list