Project Proposals

Math 413, Spring 2003

Projects are not (generally) expected to contain extensive original work but can be expository or can apply existing methods. The project will be prosented both as a paper and orally. Expected as part of the paper is an abstract and references.

Carmichael Numbers

N composite with a^N-1=1 (mod N) for all a with gcd(a,N)=1. This is equivalent to λ(N) | (N-1) [Guy81, A13]
Related Conjecture: There is no composite N with φ(N) | (N-1) [Guy81, B37]

• There are Infinitely many Carmichael Numbers by Alford, Granville & Pomerance, Annals of Math., v139 (1994), pp 703-722
• A New Algorithm for Constructing Large Carmichael Numbers by Loh & Niebuhr, Math Comp., 65 (1996), pp 823-836

Carmichael's Conjecture

If N(n)=#{k | φ(k)=n} then there is no number n other than n=1 such that N(n)=1. [Reisel85] [Ribe89] [Guy81, B39]

• Carmichael's "Empirical Theorem" (in the column "The Evidence") by S. Wagon, Math Intelligencer, v8 (1986), pp 61-63
• A Surprise Regarding the Equation φ(x)=2(6n+1) by Dence & Dence, College Math. J, v26 (1995)
• Carmichael's Conjecture is valid below 10^10,000,000 by A. Schlafly & S. Wagon, Mathematics of Computation, v63 (1994)

Goldbach's Conjecture

If N>4 and even then for some odd primes p, q we have N=p+q. [Guy81, B39]

• A Reformulation of the Goldbach Conjecture by Gerstein, Math. Mag., v66 (1993)
• Uncle Petros and Goldbach's Conjecture (novel) by Apostolos Doxiades, Bloomsbury, 2000
• MathWorld [http://mathworld.wolfram.com/GoldbachConjecture.html]

Catalan's Conjecture

The only successive powers are 8=2³ and 9=3². [Guy81, D9]

• MathWorld [http://mathworld.wolfram.com/CatalansConjecture.html]
• Catalan's Conjecture by P. Ribenboim, Amer. Math Monthly, v103, 1996
• My Numbers, My Friends (Chap 7: Consecutive Powers), by P. Ribenboim, Springer, 2000

Twin Prime Conjecture

If d_n is the difference between the n^th and the (n+1)^st primes, then d_n=2 for an infinite number of values of n. [Guy81, A8] [Reisel85, pp64-70] [Ribe89, pp199-204] [Shanks93, pp29-31]
Related conjectures apply to "Constellations" of more than two primes.

• Twin Primes and their Applications, J-C Evard
  [http://www.math.utoledo.edu/~jevard/Page012.htm]
• A Formula Concerning Twin Primes by Kostis & Page, Math. Mag., v37 (1964), pp193-194

Lucas Sequences

Connect the p+1 primality test and factorization method, Lucas sequences, and elements of Q[√-1](?)

• Recounting Fibonacci and Lucas Identities by Benjamin & Quinn, College Math. J., v30 (1999)

Riemann Hypothesis

Define ζ(s) as the analytic extension of ∑_n=1^∞1/(n^s). The Riemann Conjecture is that the only zeros of ζ(s) are at s=-2, -4, -6, ... and on the line Re(s)=1/2.

• Elementary Number Theory, Jones & Jones, 1998, Chap 9
• http://www.utm.edu/research/primes/notes/rh.html (notes in Chris Caldwell's Prime Pages)
• Riemann's Zeta Function, H. M. Edwards
• http://match.stanford.edu/rh/ (Dan Bump's notes)

Prime is P

The recent (2002) proof that primality testing can be done deterministically in polynomial time. How does this differ from previous results? Do there seem to be practical implications?

• Primes is in P by Agrawal, Kayal & Saxena, preprint, Aug 2002, (www.cse.iitk.ac.in/primality.pdf)
• PRIMES is in P Announcement, (http://www.cse.iitk.ac.in/news/primality.html)
• The PRIMES is in P little FAQ by A. Stiglic, (http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html)
• A New Primal Screen by Carl Pomerance, Focus, v22 (2002)

Mersenne Primes

M_n=2ⁿ-1 is a Mersenne Number. The factorization of M_n is of interest, if only for work in finite fields of characteristic 2. Currently a Mersenne number is the largest known prime. [Guy81] [Reisel85] [Ribe89] [Shanks93]

• GIMPS (Great Internet Mersenne Prime Search) (www.mersenne.org)
• Prime Pages ( www.utm.edu/research/primes/mersenne/)

Fermat Primes

Fermat conjectured (erroneously) that all numbers of the form F_n=2^{2^n}+1 are prime. [Guy81] [Reisel85] [Ribe89] [Shanks93]

• Primes Pages (http://primes.utm.edu/glossary/page.php?next=Fermat%20number)

Linear Error Correcting Codes

(An application of finite fields)

Implementations

Implement an appropriate algorithm. Document the algorithm and choices made in the implementation. Indicate the growth of work factors for large problems, and how implementation choices will affect the work.

References

[CP01] Prime Numbers, R. Crandall & C. Pomerance, Springer, 2001

[Guy81] Unsolved Problems in Number Theory, Richard Guy, Springer, 1981

[Reisel85] Prime Numbers and Computer Methods of Factorization, Hans Riesel, Springer, 1985

[Ribe89] The Book of Prime Number Records, Paulo Ribenboim, Springer, 1989

[Shanks93] Solved and Unsolved Problems in Number Theory, 4^th Ed, Daniel Shanks, Chelsea, 1993