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

Agrawal (congettura di)

Congetture  Teoria dei numeri 

Manindra Agrawal avanzò la congettura che se r è primo rispetto a n e ((x – 1)nxn – 1 mod xr – 1) ≡ xn – 1 mod n) (dove la congruenza va intesa come congruenza tra polinomi), allora n è primo oppure n2 ≡ 1 mod r.

La congettura sembra solo un’affermazione stravagante, ma è importante perché se fosse vera, sarebbe possibile rendere il numero di calcoli necessari per dimostrare che un intero n è primo tramite l’algoritmo AKS (v. numeri primi) proporzionale a log3n, vale a dire al cubo delle cifre di n.

 

Dalle proprietà dei coefficienti binomiali segue che (x – 1)nxn – 1 mod n se e solo se n è primo, tuttavia è possibile che il calcolo del modulo in due passi faccia sì che qualche numero composto soddisfi la congruenza.

Si può dimostrare che congettura è vera se r > n / 2.

 

Nel 2003 Hendrik W. Lenstra Jr. and Carl Pomerance suggerirono che la congettura possa essere falsa, perché se esistono k primi p1, p2, … pk (con k dispari), tutti della forma 80m + 3, ed un intero n tale che pm – 1 divida n – 1 e pm + 1 divida n + 1 per ognuno dei primi sopra menzionati, allora la condizione della congettura varrebbe, anche se r = 5 non divide n2 – 1. Argomenti euristici supportano la possibilità dell’esistenza di un intero n con le proprietà richieste.

Questo indusse M. Agrawal, N. Kayal e N. Saxena a proporre l’anno successivo una variante, aggiungendo la condizione r > logn.

 

Tomáš Vá┼ła dimostrò nel 2009 che infiniti altri controesempi potrebbero celarsi tra i numeri di Mersenne composti.

 

Nel 2007 D.J.Bernstein verificò la congettura per n minore di 1010 e r minore di 100.

 

Roman Popovych rafforzò gli argomenti di Lenstra e Pomerance, suggerendo l’esistenza di infiniti controesempi, anche se al momento non se ne conosce nessuno. Lo stesso Popovych propose una variante, suggerendo che la congettura possa essere vera se si aggiungono le condizioni ((x + 2)nxn + 2 mod xr – 1) ≡ xn + 2 mod n.

Contattami

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