Divisors of the middle binomial coefficient (Pomerance)

C. Pomerance, Divisors of the middle binomial coefficient, Amer. Math. Monthly 122 (2015) 636–644, studies when n + k divides C(2n, n); for k = 1 it always does (Catalan numbers). Everything here comes from Kummer's theorem (padicValNat_choose: the p-adic valuation of a binomial coefficient counts the carries of the addition in base p).

• Theorem 1 of the paper: for every integer k ≠ 1, n + k ∤ C(2n, n) for infinitely many n.
• The key inequality (4) in the proof of Theorem 2: for a prime p ≥ 2k, v_p(n + k) ≤ v_p(C(2n, n)) (for k = 1 this is the integrality of the Catalan numbers).
• The construction behind the first half of Theorem 3, left to the reader in the paper: if p < q are primes with k < p and 3p/2 < q < 2p, then pq ∣ C(2n, n) for n = pq + k.

Main results

• MiddleBinomial.infinite_not_dvd_centralBinom: for k != 1, infinitely many n with n + k not dividing C(2n, n) (Theorem 1)
• MiddleBinomial.padicValNat_add_le: v_p(n + k) <= v_p(C(2n, n)) for primes p >= 2k (inequality (4))
• MiddleBinomial.mul_dvd_centralBinom: pq divides C(2n, n) for n = pq + k, k < p, 3p/2 < q < 2p
• MiddleBinomial.sub_dvd_centralBinom_of_primes: hence n - k divides C(2n, n) for n = pq + k (Theorem 3, first half, for one pair)

References

• C. Pomerance, Divisors of the middle binomial coefficient, Amer. Math. Monthly 122 (2015) 636–644, doi:10.4169/amer.math.monthly.122.7.636.

theorem MiddleBinomial.infinite_not_dvd_centralBinom (k : ℤ) (hk : k ≠ 1) : {n : ℕ | 0 < ↑n + k ∧ ¬↑n + k ∣ ↑n.centralBinom}.Infinite

Pomerance, Theorem 1. For every integer k ≠ 1 there are infinitely many n with n + k > 0 and n + k ∤ C(2n, n).

theorem MiddleBinomial.padicValNat_add_le {p k : ℕ} [Fact (Nat.Prime p)] (hk : 1 ≤ k) (hp : 2 * k ≤ p) (n : ℕ) : padicValNat p (n + k) ≤ padicValNat p n.centralBinom

Pomerance, inequality (4). For a prime p ≥ 2k with k ≥ 1, the power of p in n + k divides C(2n, n).

theorem MiddleBinomial.mul_dvd_centralBinom {p q k : ℕ} (hp : Nat.Prime p) (hq : Nat.Prime q) (hkp : k < p) (h₁ : 3 * p < 2 * q) (h₂ : q < 2 * p) : p * q ∣ (p * q + k).centralBinom

The construction behind Pomerance, Theorem 3 (first half): for primes p < q with k < p and 3p/2 < q < 2p, the product pq divides C(2n, n) for n = pq + k.

theorem MiddleBinomial.sub_dvd_centralBinom_of_primes {p q k : ℕ} (hp : Nat.Prime p) (hq : Nat.Prime q) (hkp : k < p) (h₁ : 3 * p < 2 * q) (h₂ : q < 2 * p) : p * q + k - k ∣ (p * q + k).centralBinom

The same in the paper's form: n - k ∣ C(2n, n) for n = pq + k.