Don't take life too seriously: it's just a temporary situation

Singmaster (congettura di)

Congetture  Teoria dei numeri 

Nel 1971 David Breyer Singmaster avanzò la congettura che vi sia un massimo per le occorrenze di ogni coefficiente binomiale maggiore di 1. Chiaramente 1 = C(n, 0) = C(n, n) ha infinite occorrenze e ogni altro valore di n può comparire solo nelle prime n righe del triangolo di Tartaglia, quindi un numero finito di volte; la congettura afferma però che esista un massimo valido per ogni n.

 

Tutti i coefficienti binomiali centrali C(2 * m, m) = n hanno almeno 3 occorrenze, perché C(2 * m, m) = C(n, 1) = C(n, n – 1) = n.

Se p è un primo maggiore di 3, C(p, 2) = C(p * (p – 1) / 2, 1) = p * (p – 1) / 2 ha 4 occorrenze.

Singmaster dimostrò che l’equazioneC(m + 1, k + 1) = C(m, k + 2) = C(n, 1) = n ha infinite soluzioni e che quindi, dato che C(n, k) = C(n, n – k), esistono infiniti valori con 6 occorrenze. In particolare prendendo m = F2r + 2F2r + 3 – 1, k = F2rF2r + 3 – 1 per ogni intero r maggiore di 1 si trovano numeri con 6 occorrenze.

I primi valori di n che si ottengono in questo modo sono: 3003, 61218182743304701891431482520 e 3537835171522765057006983148520718494957187357011427136691375227388082606684583032666088334962061461901090477513197821330000906170565587040820236444389470701575515092325417606033095416151914090271577807800.

Lo stesso matematico verificò che gli unici interi tra 2 e 248 con 6 occorrenze sono: 120, 210, 1540, 7140, 11628 e 24310 (v. coefficiente binomiale) e l’unico con 8 occorrenze è 3003 = C(16, 6) = C(14, 8) = C(14, 8) = C(15, 5) = C(15, 10) = C(78, 2) = C(78, 76) = C(3003, 1) = C(3003, 3002).

Non si conoscono numeri con esattamente 5 o 7 occorrenze, né con più di 8 occorrenze.

 

Negli anni sono stati dimostrati limiti via via inferiori per il numero occorrenze di n come coefficiente binomiale:

  • Singmaster stesso dimostrò nel 1971 che sono al massimo clogn volte, per una costante c;

  • H.L. Abbott, P. Erdös e D. Hanson dimostrarono nel 1974 che n sono al massimo c * 2 * ω(n) * log(n) / (log(n) – ω(n) * log(log(n))) e c * log(n) / log(log(n)), per una costante c e che se vale la congettura di Cramér il limite può essere ridotto a c * log(n)^(2 / 3 + ε) per qualsiasi ε positivo;

  • Daniel M. Kane dimostrò nel 2004 che sono al massimo c * log(n) * log(log(n)) / log(log(n))^2 e nel 2007 che sono al massimo c * log(n) * log(log(n)) / log(log(n))^3, sempre per una costante c.

Questi limiti sono però stati ottenuti con raffinate tecniche, basate sulla stima dei fattori primi di n, quindi inevitabilmente portano a limiti dipendenti da n, non universali, come asserito dalla congettura.

La dimostrazione di Singmaster ci dice che il numero massimo di occorrenze è almeno 8 e almeno 6 per n abbastanza grande.

Bibliografia

  • Abbott, H.L.;  Erdös, Paul;  Hanson, D.;  "On the number of times an integer occurs as a binomial coefficient" in American Mathematical Monthly, Vol. 81, N. 3, 1974, pag. 256 – 261.
  • Kane, Daniel M.;  "Improved bounds on the number of ways of expressing t as a binomial coefficient" in Electronic Journal of Combinatorial Number Theory, Vol. 7, 2007.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.