Singmaster's conjecture

Singmaster's conjecture

In combinatorial number theory, Singmaster's conjecture, named after David Singmaster, says there is a finite upper bound on the multiplicities of entries in Pascal's triangle (other than the number 1, which appears infinitely many times). It is clear that the only number that appears infinitely many times in Pascal's triangle is 1, because any other number x can appear only within the first x + 1 rows of the triangle. Paul Erdős said that Singmaster's conjecture is probably true but he suspected it would be very hard to prove.

Let N(a) be the number of times the number a > 1 appears in Pascal's triangle. In big O notation, the conjecture is:

N(a) = O(1).\,

Contents

Known results

Singmaster (1971) showed that

N(a) = O(\log a).\,

Abbot, Erdős, and Hanson (see References) refined the estimate. The best currently known (unconditional) bound is

N(a) = O\left(\frac{(\log a)(\log \log \log a)}{(\log \log a)^3}\right),\,

and is due to Kane (2007). Abbot, Erdős, and Hanson note that conditional on Cramér's conjecture on gaps between consecutive primes that

 N(a) = O\left( \log(a)^{2/3+\epsilon}\right)

holds for any ε > 0.

Singmaster (1975) showed that the Diophantine equation

{n+1 \choose k+1} = {n \choose k+2},

has infinitely many solutions for the two variables n, k. It follows that there are infinitely many entries of multiplicity at least 6. The solutions are given by

n = F_{2i+2} F_{2i+3} - 1,\,
k = F_{2i} F_{2i+3} - 1,\,

where Fn is the nth Fibonacci number (indexed according to the convention that F1 = F2 = 1).

Numerical examples

Computation tells us that

  • 2 appears just once; all larger positive integers appear more than once;
  • 3, 4, 5 each appear 2 times;
  • 6 appears 3 times;
  • Many numbers appear 4 times.
  • Each of the following appears 6 times:
{120 \choose 1} = {16 \choose 2} = {10 \choose 3}


{210 \choose 1} = {21 \choose 2} = {10 \choose 4}


{1540 \choose 1} = {56 \choose 2} = {22 \choose 3}


{7140 \choose 1} = {120 \choose 2} = {36 \choose 3}


{11628 \choose 1} = {153 \choose 2} = {19 \choose 5}


{24310 \choose 1} = {221 \choose 2} = {17 \choose 8}
  • The smallest number to appear 8 times is 3003, which is also the first member of Singmaster's infinite family of numbers with multiplicity at least 6:
{3003 \choose 1} = {78 \choose 2} = {15 \choose 5} = {14 \choose 6}

The next number in Singmaster's infinite family, and the next smallest number known to occur six or more times, is 61218182743304701891431482520.

It is not known whether any number appears more than eight times, nor whether any number besides 3003 appears that many times. The conjectured finite upper bound could be as small as 8, but Singmaster thought it might be 10 or 12.

Do any numbers appear exactly five or seven times?

It would appear from a related entry, (sequence A003015 in OEIS) in the Online Encyclopedia of Integer Sequences, that no one knows whether the equation N(a) = 5 can be solved for a. Nor is it known whether any number appears seven times.

See also

References

External links

  • (sequence A003016 in OEIS) (OEIS = Online Encyclopedia of Integer Sequences)

Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Conjecture de Singmaster — La conjecture de Singmaster, nommée ainsi en l honneur de David Singmaster, affirme qu il y a une limite supérieure finie sur les mutiplicités des termes du triangle de Pascal (autre que 1 qui aurait alors une multiplicité infinie), à savoir le… …   Wikipédia en Français

  • David Singmaster — March 2006 Born 1939 USA Occupation Retired professor of mathematics Known for …   Wikipedia

  • David Singmaster — David Breyer Singmaster, Mars 2006 Naissance 1939 (États Unis) Nationalité …   Wikipédia en Français

  • Открытые проблемы в теории чисел — Теория чисел  это раздел математики, занимающийся преимущественно изучением натуральных и целых чисел и их свойств, часто с привлечением методов математического анализа и других разделов математики. Теория чисел содержит множество проблем,… …   Википедия

  • List of conjectures — This is an incomplete list of mathematical conjectures. They are divided into four sections, according to their status in 2007. See also: * Erdős conjecture, which lists conjectures of Paul Erdős and his collaborators * Unsolved problems in… …   Wikipedia

  • List of unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Contents 1 Millennium Prize Problems 2 Other still unsolved problems 2.1 Additive number theory …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Pascal's triangle — The first six rows of Pascal s triangle In mathematics, Pascal s triangle is a triangular array of the binomial coefficients in a triangle. It is named after the French mathematician, Blaise Pascal. It is known as Pascal s triangle in much of the …   Wikipedia

  • 3000 (number) — 3000 (three thousand) is the natural number following 2999 and preceding 3001. It is the smallest number requiring thirteen letters in English (when and is required from 101 forward). In other fields In the novel The Brothers Karamazov by Fyodor… …   Wikipedia

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”