You are currently browsing the tag archive for the ‘binomial coefficients’ tag.
Kaisa Matomäki, Maksym Radziwill, Xuancheng Shao, Joni Teräväinen, and myself have just uploaded to the arXiv our preprint “Singmaster’s conjecture in the interior of Pascal’s triangle“. This paper leverages the theory of exponential sums over primes to make progress on a well known conjecture of Singmaster which asserts that any natural number larger than appears at most a bounded number of times in Pascal’s triangle. That is to say, for any integer , there are at most solutions to the equation
with . Currently, the largest number of solutions that is known to be attainable is eight, with equal to Because of the symmetry of Pascal’s triangle it is natural to restrict attention to the left half of the triangle.Our main result settles this conjecture in the “interior” region of the triangle:
Theorem 1 (Singmaster’s conjecture in the interior of the triangle) If and is sufficiently large depending on , there are at most two solutions to (1) in the region and hence at most four in the region Also, there is at most one solution in the region
To verify Singmaster’s conjecture in full, it thus suffices in view of this result to verify the conjecture in the boundary region
(or equivalently ); we have deleted the case as it of course automatically supplies exactly one solution to (1). It is in fact possible that for sufficiently large there are no further collisions for in the region (3), in which case there would never be more than eight solutions to (1) for sufficiently large . This is latter claim known for bounded values of by Beukers, Shorey, and Tildeman, with the main tool used being Siegel’s theorem on integral points.The upper bound of two here for the number of solutions in the region (2) is best possible, due to the infinite family of solutions to the equation
coming from , and is the Fibonacci number.The appearance of the quantity in Theorem 1 may be familiar to readers that are acquainted with Vinogradov’s bounds on exponential sums, which ends up being the main new ingredient in our arguments. In principle this threshold could be lowered if we had stronger bounds on exponential sums.
To try to control solutions to (1) we use a combination of “Archimedean” and “non-Archimedean” approaches. In the “Archimedean” approach (following earlier work of Kane on this problem) we view primarily as real numbers rather than integers, and express (1) in terms of the Gamma function as
One can use this equation to solve for in terms of as for a certain real analytic function whose asymptotics are easily computable (for instance one has the asymptotic ). One can then view the problem as one of trying to control the number of lattice points on the graph . Here we can take advantage of the fact that in the regime (which corresponds to working in the left half of Pascal’s triangle), the function can be shown to be convex, but not too convex, in the sense that one has both upper and lower bounds on the second derivative of (in fact one can show that ). This can be used to preclude the possibility of having a cluster of three or more nearby lattice points on the graph , basically because the area subtended by the triangle connecting three of these points would lie between and , contradicting Pick’s theorem. Developing these ideas, we were able to show
Proposition 2 Let , and suppose is sufficiently large depending on . If is a solution to (1) in the left half of Pascal’s triangle, then there is at most one other solution to this equation in the left half with
Again, the example of (4) shows that a cluster of two solutions is certainly possible; the convexity argument only kicks in once one has a cluster of three or more solutions.
To finish the proof of Theorem 1, one has to show that any two solutions to (1) in the region of interest must be close enough for the above proposition to apply. Here we switch to the “non-Archimedean” approach, in which we look at the -adic valuations of the binomial coefficients, defined as the number of times a prime divides . From the fundamental theorem of arithmetic, a collision
between binomial coefficients occurs if and only if one has agreement of valuations From the Legendre formula we can rewrite this latter identity (5) as where denotes the fractional part of . (These sums are not truly infinite, because the summands vanish once is larger than .)A key idea in our approach is to view this condition (6) statistically, for instance by viewing as a prime drawn randomly from an interval such as for some suitably chosen scale parameter , so that the two sides of (6) now become random variables. It then becomes advantageous to compare correlations between these two random variables and some additional test random variable. For instance, if and are far apart from each other, then one would expect the left-hand side of (6) to have a higher correlation with the fractional part , since this term shows up in the summation on the left-hand side but not the right. Similarly if and are far apart from each other (although there are some annoying cases one has to treat separately when there is some “unexpected commensurability”, for instance if is a rational multiple of where the rational has bounded numerator and denominator). In order to execute this strategy, it turns out (after some standard Fourier expansion) that one needs to get good control on exponential sums such as
for various choices of parameters , where . Fortunately, the methods of Vinogradov (which more generally can handle sums such as and for various analytic functions ) can give useful bounds on such sums as long as and are not too large compared to ; more specifically, Vinogradov’s estimates are non-trivial in the regime , and this ultimately leads to a distance bound between any colliding pair in the left half of Pascal’s triangle, as well as the variant bound under the additional assumption Comparing these bounds with Proposition 2 and using some basic estimates about the function , we can conclude Theorem 1.A modification of the arguments also gives similar results for the equation
where is the falling factorial:
Theorem 3 If and is sufficiently large depending on , there are at most two solutions to (7) in the region
Again the upper bound of two is best possible, thanks to identities such as
(This post is mostly intended for my own reference, as I found myself repeatedly looking up several conversions between polynomial bases on various occasions.)
Let denote the vector space of polynomials of one variable with real coefficients of degree at most . This is a vector space of dimension , and the sequence of these spaces form a filtration:
A standard basis for these vector spaces are given by the monomials : every polynomial in can be expressed uniquely as a linear combination of the first monomials . More generally, if one has any sequence of polynomials, with each of degree exactly , then an easy induction shows that forms a basis for .
In particular, if we have two such sequences and of polynomials, with each of degree and each of degree , then must be expressible uniquely as a linear combination of the polynomials , thus we have an identity of the form
for some change of basis coefficients . These coefficients describe how to convert a polynomial expressed in the basis into a polynomial expressed in the basis.
Many standard combinatorial quantities involving two natural numbers can be interpreted as such change of basis coefficients. The most familiar example are the binomial coefficients , which measures the conversion from the shifted monomial basis to the monomial basis , thanks to (a special case of) the binomial formula:
thus for instance
More generally, for any shift , the conversion from to is measured by the coefficients , thanks to the general case of the binomial formula.
But there are other bases of interest too. For instance if one uses the falling factorial basis
then the conversion from falling factorials to monomials is given by the Stirling numbers of the first kind :
thus for instance
and the conversion back is given by the Stirling numbers of the second kind :
thus for instance
If one uses the binomial functions as a basis instead of the falling factorials, one of course can rewrite these conversions as
and
thus for instance
and
As a slight variant, if one instead uses rising factorials
then the conversion to monomials yields the unsigned Stirling numbers of the first kind:
thus for instance
One final basis comes from the polylogarithm functions
For instance one has
and more generally one has
for all natural numbers and some polynomial of degree (the Eulerian polynomials), which when converted to the monomial basis yields the (shifted) Eulerian numbers
For instance
These particular coefficients also have useful combinatorial interpretations. For instance:
- The binomial coefficient is of course the number of -element subsets of .
- The unsigned Stirling numbers of the first kind are the number of permutations of with exactly cycles. The signed Stirling numbers are then given by the formula .
- The Stirling numbers of the second kind are the number of ways to partition into non-empty subsets.
- The Eulerian numbers are the number of permutations of with exactly ascents.
These coefficients behave similarly to each other in several ways. For instance, the binomial coefficients obey the well known Pascal identity
(with the convention that vanishes outside of the range ). In a similar spirit, the unsigned Stirling numbers of the first kind obey the identity
and the signed counterparts obey the identity
The Stirling numbers of the second kind obey the identity
and the Eulerian numbers obey the identity
Recent Comments