MAT 312/AMS 351
Applied Algebra

Information about the Project

Students are encouraged to do an individual special project. This could involve a historical report on material of the course, or learning a topic in algebra not discussed in the course, or writing a computer program/developing some algorithm, etc. The choice of a topic and the exact scope of the special project are to be determined after consultation with the instructor. A short list of potential project topics is enclosed below. However if you would like to work on a different project/topic please come see me during office hours to talk about it. Projects are individual and are expected to be neatly written/presented. Programs/computer code without accompanying (mathematical) explanations/description are NOT acceptable.

For any of the programming projects, please email to sorin at math.sunysb.edu the program source code + actual project (in readable form -- indented and commented), as well as hand in the program outline and a reasonable amount of program output. You can use any programming language you like (within reasonable limits - i.e., a language for which there exist easily available compilers). Preferred ones are Maple, Mathematica (yes, they are programming languages), C, OCAML and Java, but you can also use C++, Pascal, Python, Fortran, Lisp, Turing machine...

You will need to make your selection and also inform me in writing via email by 03/01, the latest. The project is due before or on 04/08/2005.

1. Let n be a positive integer, and define T(n) = n/2 if n is even, and (3n+1)/2 otherwise, so for instance T(2)=1, and T(5)=8. Form the sequence obtained by iterating T: n, T(n), T(T(n)), T(T(T(n))), .... For instance starting with n=7 we get the sequence 7,11,17,26,13,20,10,5,8,4,2,1,2,1, ... A well known conjecture asserts that the sequence obtained by iterating T always reaches 1 no matter which positive number n begins the sequence.
   • Find the sequence obtained by iterating T starting with n=39
   • Show that if we start the sequence from n=(2^2k-1)/3, k>1, one always reaches 1.
   • Write a program that verifies the above conjecture for all values of n smaller than 10000.
   • Using the above numerical evidence make conjectures concerning the number of iterations needed in the above sequence till one reaches 1.
2. Discuss and find divisibility tests for an integer n by any of the following numbers 2, 3, 5, 7, 9, 11, 13, 101. Write a program that tests such divisibilities (for very large integers). Discuss historical aspects.
3. According to the "theory" of biorhythms there are three cycles in your life that start the day you are born. These are the physical, emotional and intellectual cycles of length 23, 28 and 33 days, respectively. Each cycle follows a sine curve with period equal to the length of that cycle, starting with value 0, climbing to value 1 one quarter of the way through the cycle, dropping back to value 0 one-half of the way through the cycle, etc and getting back to value 0 at the end of the cycle.
   • For which says of your life will you be at a triple peak, where all three cycles are at maximum values?
   • For which says of your life will you be at a triple nadir, where all three cycles are at minimum values?
   • When in your life will all three cycles be at neutral position?
   • Write a program that plots biorhythm charts and finds triple peaks and triple nadirs.
4. Discuss the complexity of the euclidean algorithm for computing gcd's. Show Lam\'e's result that the number of divisions needed to find the gcd of two integers via the euclidean algorithm does not exceed the number of decimal digits in the smaller of the two integers. Write a program that checks Lam\'e's bound for various pairs of large integers of your choice. Use the numerical evidence to see how far is Lam\'e's bound from the number of actual divisions. Discuss the number needed of steps in other algorithms for finding the gcd (e.g. the least-remainder algorithm).
5. A composite number n that satisfies n | b^n-1-1 for all integers b with (b,n)=1 is called a Carmichael number.
   • Show that if n is a Carmichael number then it is squarefree.
   • Show that 2821=7*13*31 is a Carmichael number.
   • Show that if n=p₁p₂...p_n is a product of distinct primes such that p_i-1|n-1 for all i, then n is a Carmichael number. Use this to show that 564651361 is a Carmichael number. You may also try to write a program to find other Carmichael numbers.
6. Discuss Vigenere and Hill ciphers (encryption, decryption). Write a program that can perform encryption, decryption using such methods. Discuss vulnerability via statistics of blocks in the encrypted test. Write a program that does cryptanalysis for such cyphers based on statistics of blocks (for small sizes of blocks).
7. Write a program that finds all twin primes less than 20,000. Hardy and Littlewood conjectured that the number of twin primes not exceeding n is asymptotic to C n/(ln n)² for a constant C, approximately equal to 0.66016. Determine how accurate this asymptotic formula is for values of n as large as you can compute.
8. Compare the number of primes of the form 4n+1 and the number of primes of the form 4n+3 for a range of values of n. Can you make any conjectures about the relationship between these numbers?
9. Gather evidence for the following conjectures, or find counterexamples if you can:
   • Lehmer has conjectured that n is prime if φ(n) divides n-1.
   • Charmichael has conjectured that for every positive integer n there is a positive integer m distinct from n such that φ(n)= φ(m).
10. Describe a good method to
    • Find the number of zeroes at the end of the decimal expansion of n!. Write a simple program that uses your method and test it.
    • Find the prime factorization of n!. Write a simple program that uses your method and test it.
11. A short (4 to 5 typed pages) paper on the mathematical contributions of a number theorist. Note: This is not a biography - you will need to describe mathematical results, their proofs, etc.
12. A short (4 to 5 typed pages) historical report on material discussed in the course. You will need to describe mathematical results, outline proofs, etc