LINEAR ALGEBRA MTHSC 311
Popular in Course
Popular in Mathematics (M)
This 5 page Class Notes was uploaded by Jazmyn Braun on Saturday September 26, 2015. The Class Notes belongs to MTHSC 311 at Clemson University taught by Kevin James in Fall. Since its upload, it has received 59 views. For similar materials see /class/214280/mthsc-311-clemson-university in Mathematics (M) at Clemson University.
Reviews for LINEAR ALGEBRA
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/26/15
POSSIBLE PROBLEMS Some possible problems are outlined below One should note that each of the following subsections contains a description of a general problem and in some cases two to three possible avenues for research related to the general problem Thus it is possible that more than one team will work in the area described by one of the following subsections These teams would7 of course7 be working on different aspects of the general problem described This is especially true of subsections 17 Ill and IV 1 Average Frobenius Distributions A topic of central importance in number theory over the past decade has been the theory of elliptic curves We can think of an elliptic curve as the set of fractional solutions to an equation of the form 1 Ey2I3AacB One of the major conjectures in this area is the Lang Trotter conjecture see 10 This conjecture deals with the local behavior of a given curve7 that is the number of solutions to an equation like the one above modulo a prime p It is known that the number of solutions to such an equation modulo p counting a point at in nity is between p1723 and p12f7 and that all integers in this range are obtained by some curve modulo p Thus7 given an elliptic curve E as above7 it is quite natural to let aEp p 1 7 EGFP7 where EGFP denotes the number of solutions to our equation plus 1 to account for the point at in nity Then we are interested in determining how often aEp takes on a given value as the prime p varies For instance7 we may notice that if we consider the curve E 7f x3 17 then aE11 0 This is because when we count solutions to 7f 63 1 modulo 117 we nd that there are 11 and when we add 1 for the point at in nity7 we see that EGFP 12 which is p 1 in this case Now7 the question that we are interested in answering in this context becomes As we let p vary over all primes7 how often do we have aEp 077 The Lang Trotter conjecture asserts that if n is any integer and if E is an elliptic curve7 then as we let p vary over all primes up to some bound X the number of times that we have aEp n should grow like a constant times log X7 where the constant depends only on E and n This conjecture has been shown to be true in an average sense see 67 However7 based on some recent computations 8 and additional averaging theorems 97 there remains some doubt as to whether the conjecture holds for all curves One readily attackable computational problem is to gather more computational evidence to help us better understand this conjecture The PI has already done some computations related to this problem and could get students started gathering more data right away In addition7 students could study other algorithms for computing the aEp7s and implement these to obtain quicker code This would allow us to greatly increase the computational data related to this problem and hopefully shed more light on this mysterious conjecture In a slightly different direction7 students could be introduced to counting techniques which have been used by the PI and others 65 and to prove that some variations of the Lang Trotter conjecture are true when one averages over certain families of curves In particular7 1 2 students could study the family of elliptic curves with a point of order 5 or the family of curves with a point oforder 7 and try to show that something like the Lang Trotter conjecture holds on average for this family of curves H The distribution of the partition function modulo a prime Given a number n a partition of n is a non increasing sequence of numbers whose sum is n For instance 37171 is a partition of 5 We de ne 1701 to be the number of such partitions of n For instance7 a complete list of partitions of 4 is given by 1717171 27171 2 272 371 4 Thus 174 5 One question that has received much attention lately is how the partition function is distributed modulo a given integer m see 11 and references therein For instance7 we don t know how often 1701 is congruent to 3 modulo 11 as n varies This question is readily attackable from a computational standpoint Students could begin to investigate these distributions right away Also7 the PI and co Pl have recently developed algorithms that should allow the quick computation ofthe generating function for 1701 modulo a prime p Thus7 one should be able to obtain many values of the partition function modulo various primes The students could implement these algorithms as well as modify them to quickly compute many values of 1701 and study the distribution of this function modulo small primes Hopefully7 enough data could be gathered to make reasonable conjectures about the behavior of this function 111 Class Number Formulas For our purposes7 a binary quadratic form is a homoge neous quadratic polynomial with integer coef cients that is a polynomial of the form 3 f 1562 bxy 07f where a7b7c E Z The discriminant of the above form is given by d 62 7 4610 Two such forms fX and gX here X 0517502 are said to be equivalent if there is an integral 2 gtlt 2 matrix of determinant i1 such that fTX gX One can show that any two equivalent forms have the same discriminant So7 it is quite natural to count the number of equivalence classes of binary quadratic forms of a given discriminant We denote this number by If p is any prime then there is an amazing formula due to Kronecker which relates the values of Hk2 7 4p as k varies over the nite set of integers for which k2 7 4p lt 0 We share this amazing formula below 2p ipr11 mod 12 2p4 ipr7 mod 12 2p2 ipr5 mod 12 2p6 ipr 1 mod 12 The PI recently discovered the following related class number formula while studying elliptic curves with 3 torsion For p E 2 mod 3 a prime we have 5 Z H9k2 7 4p p 71 k2lt4p9 4 2 H k2 i 4p k2 lt4p Studies of elliptic curves with other prescribed torsion subgroups should yield similar class number formulas However7 in some cases the ideas used by the P1 in the proof of the above formula become more dif cult to implement In any case7 a computational study of curves with a given torsion subgroup should at least lead to an interesting conjecture for new class number formulas like the one above IV Eigenstructure of recursively de ned matrices ln enumeration problems7 espe cially those arising in statistical mechanics7 it is frequently desirable to understand the eigenstructure of recursively de ned matrices For example7 when counting the number of con gurations of non attacking kings on a board of size n gtlt k one is led to consider the kth power of the matrix An where An is de ned recursively by A017 A1G Anil An72 An 7 Am o gt in which the blocks A114 AW are of different sizes7 and the empty part of the matrix is padded with zeros If we knew the growth rate of the largest eigenvalue of An then we would be able to compute the asymptotics of the number of con gurations if we knew exact expressions for the eigenvalues we could compute an exact expression It is easy to show that the largest eigenvalue An of An satis es Albn a n as n a 00 so that An grows roughly like 7 This gives an approximate recursion for An and An 2 nAnA Now since An satis es and exact recursion7 and An satis es an approximate recursion7 it is natural to ask about the structure of the F robenius eigenvector7 that is7 the eigenvector gm corresponding to An Numerical experiments suggest that there is indeed a recursive structure to Q in fact7 it appears that en is very close within about 1 of the largest co ordinate to being a scaled 4 concatenation of the vectors gnil and 172 Moreover the error in this approximation also appears to be similarly recursive Students studying this phenomenon will be encouraged to study this and similar recursively de ned matrices to attempt to determine 9 Whether this phenomenon can be analyzed fully o How the phenomenon depends on the choice of recurrence 9 Whether the phenomenon extends to other eigenvectors for example to the eigen vector corresponding to the second largest eigenvalue There has been a lot of activity in the subject of eigenvalues of random matrices recently see for example 21 with many applications to statistical mechanics combinatorics and number theory in particular for many classes of random matrices having only real eigen values the distributions of eigenvalues can be shown to converge to the Wigner distribution Given this it would also be of interest to numerically study the distribution of matrices such as An to see what if any the limiting distribution of eigenvalues is V Fast algorithms for multiplying patterned matrices and other objects There are several well known algorithms for multiplying polynomials for example Fast Fourier transforms 3 Karatsuba7s algorithm 7 etc and for multiplying matrices Strassen s algorithm 12 Coppersmith and Winograd 4 etc which are signi cantly faster than naive methods but rely on the use of more complicated recursions and also on being able to use a larger set of constants For example multiplication of polynomials of degree less than n is easily seen to be 0n2 by the naive method 0n10g2 3 if subtraction is allowed as in Karatsuba7s algorithm and On log n if complex 2nth roots of unity are allowed Similarly Strassen s recursive algorithm using subtraction reduces the complexity of multiplying two n gtlt n matrices from 0n3 to 0n10g2 7 However these algorithms often fail to be improvements over naive algorithms when the objects concerned are very sparse and highly patterned such matrices often occur in study ing discretizations of differential equations for example In this project students will be encouraged to investigate Karatsuba Strassen and FFT type algorithms for sparse and pat terned objects REFERENCES 1 Neil J Calkin C Merino S Noble and M Noy Improved Bounds for the Number of Forests and Acyclic Orientations in the Square Lattice n preparation 2 Neil J Calkin and Herbert S Wilf The Number of Independent Sets in a Grid Graph SIAM Journal of Discrete Math 11 1998 Number 1 54760 3 P Chiu Transforms nite elds and fast multiplication Math Mag 63 1990 no 5 3307336 4 D Coppersmith S Winograd Matrix multiplication via arithmetic progressions J Symbolic Comput 9 1990 no 3 2517280 5 C David and F Pappalardi Average Frobenius distributions 0 f elliptic curves Internat Math Res Notices 1999 no 4 1657183 6 E Fouvry and M R Murty 0n the distribution of supersingul ar primes Canad J Math 48 1996 no 1 817104 7 von zur Gathen JoachimD PDRB Gerhard7 J7rgenDPDRB Modern computer algebra 8 K James C Mehta and V K Murty Frobenius distribution 3 and Galois representations 7 numerical evidence preprint 9 K James Average Frobenius distributions of elliptic curves with 3torsion7 preprint 10 S Lang and H Trotter7 Frobenius distributions in GLgextensions Distribution of Frobenius automor phisms in GLgextensions of the rational numbers Lecture Notes in Mathematics Vol 504 Springer Verlag BerlinNew York 1976 11 K OnoDist7ibution of the partition function modulo m Ann of Math 2 151 20007 no 1 2937307 12 Strassen7 V Relative bilinear complexity and matrix multiplication J Reine Angew Math 375376 1987 13 R Weaver New congruences for the partition function Ramanujan J 5 20017 no 1 53763
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'