### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# TOPIC MATH 788F

GPA 3.51

### View Full Document

## 39

## 0

## Popular in Course

## Popular in Mathematics (M)

This 89 page Class Notes was uploaded by Cassidy Grimes on Monday October 26, 2015. The Class Notes belongs to MATH 788F at University of South Carolina - Columbia taught by Ma Filaseta in Fall. Since its upload, it has received 39 views. For similar materials see /class/229526/math-788f-university-of-south-carolina-columbia in Mathematics (M) at University of South Carolina - Columbia.

## Reviews for TOPIC

### 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: 10/26/15

FACTORING SPARSE POLYNOMIALS Theorem 1 Schinzel Let r be a positive integer and x nonzero integers a0 ar Let F1a 933139 ar cr al1 0039 Then there exist nite sets S and T of matrices satisfying Theorem 1 Schinzel Let r be a positive integer and x nonzero integers a0 ar Let F1a 933139 ar cr al1 0039 Then there exist nite sets S and T of matrices satisfying iEachmatn39x in SorT is anr x pmatrixwith integer entries and of rank p for some p s r Theorem 1 Schinzel Let r be a positive integer and x nonzero integers a0 ar Let F1a 933139 ar cr al1 0039 Then there exist nite sets S and T of matrices satisfying iEachmatn39x in SorT is anr x pmatrixwith integer entries and of rank p for some p s 139 ii The matrices in S and T are computable iii For every set of positive integers d1 d wmmlthltwmmmMMM m pan of Fmd1 mdquot is reduc ale if and only ifthereisanr x pmatn39xNinS and integers 11 up satisfying 1 g dr 1 0 butthereisnor x p matrixMinTwith p lt p and no integers vi 1 satisfying d W caM39 1 up the nonreciprocal part of Fad1 and is reducible the nonreciprocal part of Fmd1 and is reducible F9316r arwr a11ao the nonreciprocal part of Fmd1 and is reducible F9316r arwr a11ao Fmdl m ade o u 21de a0 Theorem 2 Schinzel Let r be a positive integer and x nonzero integers a0 ar Let Fa1 3 1er o 1101 a0 Then there exist nite sets S and T of matrices satisfying Theorem 2 Schinzel Let r be a positive integer and x nonzero integers a0 ar Let Fa1 3 1er o 1101 a0 Then there exist nite sets S and T of matrices satisfying iEachmatn39x in SorT is anr x pmatrixwith integer entries and of rank p for some p s r Theorem 2 Schinzel Let r be a positive integer and x nonzero integers a0 ar Let Fa1 a 1er o 1101 a0 Then there exist nite sets S and T of matrices satisfying iEachmatn39x in SorT is anr x pmatrixwith integer entries and of rank p for some p s 139 ii The matrices in S and T are computable iii For every set of positive integers d1 d with Fad1 md39 not reciprocal and d1 lt 12 lt lt the noncyclotomz c part of Fad1 a is reducible ifand onlyifthereisanr x pmatrixNinSand integers v1 up satisfying d a in butthereisnor x p mau ixMinTwith p lt pand no integers vi vfa satisfying d1 39 v t I d39 d iii For every set of positive integers d1 d with Fccd1 5th not reciprocal and d1 lt 12 lt lt the noncyclotomz c part of Fad1 a is reducible ifand pnlyifthereisanr X puialrixNinSand integers v1 up satisfying d a in butthereisnor x p mau ixMinTwith p lt pand no integers vi vfa satisfying d1 39 v t I d39 d iii For every set of positive integers d1 d with Fad1 md39 not reciprocal and d1 lt 12 lt lt the noncyclotomz c part of Fad1 a is reducible ifand onlyifthereisanr x pmatrixNinSand integers v1 up satisfying d a in butthereisnor x p mau ixMinTwith p lt pand no integers vi vfa satisfying d1 39 v t I d39 d Theorem There is an algon39thm with the following prop erty Given a nonreciprocal x 6 Za with N non zero tenns degree n and height H the algorithm deter mines whether fm is irreducible in time cN H log n N where cN H depends only on N and H and c N depends only on N Theorem There is an algon39thm with the following prop erty Given a nonreciprocal f E ZED with N non zero tenns degree n and height H the algorithm deter mines whether fm is irreducible in time cN H log n N where cN H depends only on N and H and c N depends only on N Proof Let 0139de 39 39 39 11de a0 Proof Let armdr 39 39 Elaidl a0 Consider F39B1umr arxr01w1ao so that Fad1 wd armdquot o 01de a0 Proof Let 33 0 wdr a 391 Consider Pennmar ar33rquot39 alw1ao so that Fad1 wd tarxdquot o 01de a0 Begin the algorithm by constmcting the nite sets S and T of matrices in Schinzel s Theorem 2 Proof Let 11 1 06 arm an ao Consider F931mr ar33rquot39 alw1ao so that Fad1 wd tarxdquot o 01de a0 Begin the algorithm by constructing the nite sets S and T of matrices in Schinzel s Theorem 2 Observe that S and TdependonFandnotonthe d1dr Proof Let 11 at arm an a0 Consider Pennmar ar33rquot39 alw1ao so that Fad1 wd tarxdquot o 01de a0 Begin the algorithm by constructing the nite sets S and T of matrices in Schinzel s Theorem 2 Observe that S and TdependonFandnotonthe d1dr sothistakes running time s 61N H Next the algorithm checks each matrix N in S39 to see if d Cir quotp for some integers v1 up Next the algorithm checks each matrix N in S39 to see if d Cir quotp for some integers v1 up In other words 121 up are unknowns and elementary row operations are done to solve the above system of equations Next the algorithm checks each matrix N in S39 to see if d Cir quotp for some integers v1 up In other words 121 up are unknowns and elementary row operations are done to solve the above system of equations The rank of N is p so if a solution exists then it is unique Next the algorithm checks each main39x N in S39 to see if d d quotP for some integers v1 up In other words 121 up are unknowns and elementary row operations are done to solve the above system of equations The rank of N is p so if a solution exists then it is unique This involves performing elementary operations x and with entries in N and the d which are 3 n Next the algorithm checks each main39x N in S39 to see if d gt w d quotP for some integers v1 up In other words 121 up are unknowns and elementary row operations are done to solve the above system of equations The rank of N is p so if a solution exists then it is unique This involves performing elementary operations x and with entries in N and the d which are 3 n The running time here is g 32 N H log2 n Next the algorithm checks each matrix M in T to see if 11 1 dr 0quot p for some integers vi 11 by using elementary row operations to solve the system of equations for the 12 Next the algorithm checks each matrix M in T to see if 11 1 dr 0quot p for some integers vi 11 by using elementary row operations to solve the system of equations for the 12 The rank of M is p so if a solution exists then it is Next the algorithm checks each matrix M in T to see if d v if 0quot p for some integers vi 11 by using elementary row operations to solve the system of equations for the 12 The rank of M is p so if a solution exists then it is This involves perfonning elementary operations X and with entries in M and the d which are S n Next the algorithm checks each matrix M in T to see if 11 1 dr 0quot p for some integers vi 11 by using elementary row operations to solve the system of equations for the 12 The rank of M is p so if a solution exists then it is This involves perfonning elementary operations X and with entries in M and the dj which are S n The running time is again 3 c2 N H log2 n Schinzel s Theorem 2 now indicates to us whether f 3 has a reducfble noncyclotomic part Schinzel s Theorem 2 now indicates to us whether f 3 has a reducfble noncyclotomic part If so then we output that f 2 is reducible If not we have more work to do Recall we had the following theorem Theorem There is an algorithm that has the following property given an 291 ajmd 39 6 Zw with deg f n the algorithm determines whether f x has a cyclotomic factor and with running time lt exp 2 01N log Nlog N log log n x logH 1 as N tends to in nity where H maxlSjSN ajl Recall we had the following theorem Theorem There is an algorithm that has the following property given an 291 ajmd 39 6 Zw with deg f n the algorithm determines whether f x has a cyclotomic factor and with running time lt exp 2 01N log Nlog N log log n x logH 1 as N tends to in nity where H maxlSjSN ajl We ll come back to this exp 2 01xN log NlogN log log 12 X logH 1 exp 2 01xN log NlogN log log 72 X 10gH 1 split into two parts exp 2 01 xN log Nlog N X logH 1 exp 2 01 N log N 10g 10g quot9 exp 2 01xN log NlogN log log 72 X 10gH 1 split into two parts 33N9 H exp 2 01xN logN log log n exp 2 01xN log NlogN log log 72 X 10gH 1 split into two parts 33 N9 H log nc4N Theorem There is an algorithm that has the following property given w ZI il ajwdi e Zlm with deg f n the algorithm determines whether fa has a cyclotomic factor and with running time s cam H log WW as N tends to in nity where H maxlSjSN ajl Theorem There is an algorithm that has the following property given w ZI il ajwdi e Zlm with deg f n the algorithm determines whether fa has a cyclotomic factor and with running time s cam H log WW as N tends to in nity where H maxlSjSN ajl Algorithm Continued If the noncyclotomic part of f m irreducible then use the algorithm in the above theorem Theorem There is an algorithm that has the following propexty given fe 255 ajmdj 6 Za with deg f n the algorithm determines whether fa has a cyclotomic factor and with running time s cam H log WW as N tends to in nity where H maxlSjSN ajl Algorithm Continued If the noncyclotomic part of f m irreducible then use the algorithm in the above theorem completes the proof of the theorem I A CURIOUS CONNECTION WITH THE ODD COVERING PROBLEM Coverings of the Integers A covering of the integers is a system of congruences a E aj mod mj having the property that every integer satis es at least one of the congruences Coverings of the Integers A covering of the integers is a system of congruences a E aj mod mj having the property that every integer satis es at least one of the congruences Example 1 E 0 mod 2 a 5 1 mod 2 Example 2 350 252 951 951 53 mod 2 mod 3 mod 4 mod 6 mod 12 Example 2 a E 0 mod 2 a E 2 mod 3 a E 1 mod 4 a E 1 mod 6 a E 3 mod 12 01234567891011 Open Problem Does there exist an odd covering of the integers a oove ng consisting of distinct odd moduli gt 1 Open Problem Does there exist an odd covering of the integers a oove ng consisting of distinct odd moduli gt 1 Erd s 25 for proof none exists Open Problem Does there exist an odd covering of the integers a eove ng consisting of distinct odd moduli gt 1 Erd s 25 for proof none exists Selfridge 2000 for explicit example Sierpinski s Application There exist in nitely many even a positive proportion of positive integers k such that k x 2quot 1 is composite for all nonnegative integers n Sierpinski s Application There exist in nitely many even a positive proportion of positive integers k such that k x 2quot 1 is composite for all nonnegative integers n Selfridge s Example A 78557 smallest odd known Sierpinski s Application There exist in nitely many even a positive proportion of positive integers k such that k x 2quot 1 is composite for all nonnegative integers n Selfridge s Example I 78557 smallest odd known Polynomial Question Does there exist ux 6 Zsc such that faa 1 is reducible for all nonnegative integers n Sierpinski s Application There exist in nitely many even a positive proportion of positive integers k such that k x 2quot 1 is composite for all nonnegative integers n Selfridge s Example A 78557 smallest odd known Polynomial Question Does there exist fa 6 Za such that faa3 l is reducible for all nonnegative integers n Require f1 g l Sierpinski s Application There exist in nitely many even a positive proportion of positive integers k such that k x 2quot 1 is composite for all nonnegative integers n Selfridge s Example I 78557 smallest odd known Polynomial Question Does there exist ux 6 Zsc such that f1 a l and fzcn 1 is reducible for all nonnegative integers n Sierpinski s Application There exist in nitely many even a positive proportion of positive integers k such that k x 2quot 1 is composite for all nonnegative integers n Selfridge s Example A 78557 smallest odd known Polynomial Question Does there exist ux 6 Zsc such that f1 a 1 and faa 1 is reducible for all nonnegative integers n Answer Nobody knows Schinzel s Example 5m96m83m68m59m36m28m3aquot 12 is reducible for all nonnegative integers n Schinzel s Example 5m96m83m68m59m36m28m3aquot 12 is reducible for all nonnegative integers 11 Comment For each n the above polynomial is divisible by at least one of 1303 wherek E 2 3 4 6 12 Schinzel s Example 5m96m83m68m59m36m28m3aquot 12 is reducible for all nonnegative integers 11 Comment For each n the above polynomial is divisible by at least one of 1303 wherek E 2 3 4 6 12 n50 mod 2 gt fna 1250 moda1 Schinzel s Example 5m96m83w68m5 Qm36mz8m3mquot 12 is reducible for all nonnegative integers 11 Comment For each n the above polynomial is divisible by at least one of 1903 wherek E 2 3 4 6 12 n50 mod 2 gt fva 12 0 modm1 n52 mod 3 gt faa 1250 mod 22m1 Schinzel s Example 5m96m83w68m5 Qm36mz8m3mquot 12 is reducible for all nonnegative integers 11 Comment For each n the above polynomial is divisible by at least one of 1903 wherek E 2 3 4 6 12 n50 mod 2 gt fva 12 0 modm1 n52 mod 3 gt faa 1250 mod 22m1 n51 mod 4 gt famquot12 0 mod 2211 Schinzel s Example 5m96m83w68m5 Qm36mz8m3mquot 12 is reducible for all nonnegative integers 11 Comment For each n the above polynomial is divisible by at least one of 1903 wherek E 2 3 4 6 12 n50 mod 2 gt fva 12 0 modm1 n52 mod 3 gt faa 1250 mod 22m1 n51 mod 4 gt famquot12 0 mod 2211 n51 mod 6 gt faa 12 0 mod z2 31 Schinzel s Example 5m96m83w68m5 Qm36mz8m3mquot 12 is reducible for all nonnegative integers 11 Comment For each n the above polynomial is divisible by at least one of 1903 wherek E 2 3 4 6 12 n50 mod 2 gt fva 12 0 modm1 n52 mod 3 gt faa 1250 mod 22m1 n51 mod 4 gt famquot12 0 mod 2211 n51 mod 6 gt faa 12 0 mod z2 31 n53 mod 12 gt fmmquot12so mod z4 x31 Schinzel s Example 5m96m83w68m5 Qm36mz8m3mquot 12 is reducible for all nonnegative integers 11 Theorem There exists an 1quot 9 E Za with nonnegative memoith such that f m mquot 4 is reducible for all non negative integers n Schinzel s Example 5m96m83w68m59336328m3aquot 12 is reducible for all nonnegative integers 11 Theorem There exists an 1quot 9 E Za with nonnegative ooe cients such that f m mquot 4 is reducible for all non negative integers n Schinzel s Example 5m96m83w68m5 Qm36mz8m3mquot 12 is reducible for all nonnegative integers 11 Theorem There exists an 1quot 9 E Za with nonnegative memoith such that f m mquot 4 is reducible for all non negative integers n Schinzel s Example 5m9683m68m59m36m28213313 12 is reducible for all nonnegative integers 11 Theorem There exists an 1quot 9 E Zke with nonnegative eoe cients such that f m mquot 4 is reducible for all non negative integers 11 Comment For each n the rst polynomial is divisible by at least one Igtka where k divides 12 Schinzel s Example 5m96m83a68m5 Qm362328m3mquot 12 is reducible for all nonnegative integers 11 Theorem There exists an 1quot 9 E Zke with nonnegative eoe cients such that f at mquot 4 is reducible for all non negative integers 11 Comment For each n the second polynomial is divisible by at least one lt1 9 where k divides some integer N having more than 1017 digits Schinzel s Example 5m96m83a68m5 Qm362328m3mquot 12 is reducible for all nonnegative integers 11 Theorem There exists an 1quot 9 E Zke with nonnegative eoe cients such that f at mquot 4 is reducible for all non negative integers 11 Comment For each n the second polynomial is divisible by at least one Igtka where k divides WW3415317371 41 Schinzel s Theorem If there is an at 6 Za such that f1 96 1 and fax 1 is reducible for all nonnegative integers n then there is an odd covering of the integers TURAN S CONJECTURE Conjecture There is an absolute constant C such that if 1 it Z ajivj E Z56 i0 then there is a 39I39 ga Z bjx e Zm i0 1 irreducible over Q such that 2 b aJl g C i0 Conjecture There is an absolute constant C such that if 1 it Z ajiv E Z56 j 0 then there is a ga Z bjxj E Ze i0 1 irreducible over Q such that 2 b aJl g C i0 Comment The coojecture remains open If we take 9a Zg0 b32123 6 Za where possibly 8 gt r then the problem has been resolved by Schinzel First Attack on Thr n s Problem Old Theorem When m is large either ua 3mm vc has an obvious factorization or the nonreciprocal part of uaam 113 is irreducible First Attack on 39Dur n s Problem Old Theorem When m is large either u23em vc has an obvious factorization or the nonreciprocal part of uaam 123 is irreducible Idea Consider 9m m at If one can show gm is irreducible for some n then the conjecture of Tur n modi ed so degg gt deg f is al lowed is resolved with C 1 First Attack on 39Dur n s Problem Old Theorem When m is large either u23cm vc has an obvious factorization or the nonreciprocal part of uaam 123 is irreducible Idea Consider 93 mquot at If f 0 0 or f1 1 then consider instead 9a mquot fa l 1 If one can show gm is irreducible for some n then the conjecture of Tur n modi ed so degg gt deg f is al lowed is resolved with C 2 First Attack on 39Dur n s Problem Idea Consider 993 w f c If f0 0 or f 1 1 then consider instead 993 3quot x i 1 If one can show 93 is irreducible for some n then the conjecture of Tur n modi ed so degg gt deg f is al lowed is resolved with C 2 First Attack on 39Dur n s Problem Idea Consider 993 w f c If f0 0 or f 1 1 then consider instead 993 3quot x i 1 If one can show 93 is irreducible for some n then the conjecture of Tur n modi ed so degg gt deg f is al lowed is resolved with C 2 Problem Dealing with 93 m f m is essentially equivalent to the odd covering problem So this is hard Second Attack on limin s Problem Idea Consider gm mquotquot I a3 fa If f 0 0 then consider instead ga mm 2 m fa l 1 Theorem Schinzel For every 9quot fa Z asz E Za 339 0 there exist in nitely many ineduc ale 8 gx Z bjarquot E Za j0 such that maxra 2if0 0 g 5 jS3 Theorem Schinzel For every 9quot fa Z asz E Za 339 0 there exist in nitely many ineduc ale gx Z bjmj E Za j0 such that 39 J 3 3 always J0 One of these is such that s lt exp 5r mm 3 Ideas Behind Proof Ideas Behind Proof b Consider Fa 3 quot mquot fa with m E M 2M and n E N 2N where M and N arelalge andM gt N Ideas Behind Proof b Consider Fa mm m fa with m E M211 and n E N 2N where M and N are large and M gt N gt Apply result on ummm 03 with um 1 and vm aquot fa to reduce problem to consideration of reciprocal factors Ideas Behind Proof b Consider Fa mm m fa with m E M211 and n E N 2N where M and N are large and M gt N gt Apply result on ummm 03 with um 1 and vm aquot at to reduce problem to consideration of reciprocal factors gt Find a bound on the number of mm mquot fa with reciprocal noncyclotomic factors Ideas Behind Proof b To bound the a m f m with cyclotomic factors set A mn MltmS2MNltn2N and let Ap C A arising from when F39 0 Use a sieve argument to estimate the me of AUAP Ideas Behind Proof b To bound the a m f m with cyclotomic factors set A mn MltmS2MNltn2N and let Ap C A arising from when F39 0 Use a sieve argument to estimate the me of AUAP b Deducethatsome Fa x quotmquotfa with m E M 2M and n 6 N 2N is in39educible whereM andN are large and M gt N Current Knowledge r Theorem Given fa Z ajmj E Za thereare i0 8 in nitely many irreducible ga Z bjmj e Zm i0 such that maxr8 Z laj jl S 5 i0 One of these is such that s 5 4r exp 4f212 Current Knowledge r Theorem Given fa Z ajmj E Za thereare i0 8 in nitely many irreducible ga Z bjmj e Zm i0 such that maxr8 Z laj jl S 5 i0 One of these is such that s 5 4r exp 4f212 Current Knowledge r Theorem Given fa Z ajmj E Za thereare i0 8 in nitely many irreducible ga Z bjmj e Zm i0 such that maxr8 Z laj bjl S 3 i0 One of these is such that s 5 some polynomial in r

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.