mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-02-14, 00:54   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22×79 Posts
Post Polynomial Discriminant is n^k for an n-1 degree polynomial

Is there a simple way to find an n-1 degree polynomial with discriminant D = n^k, (defined with one variable x) and n is prime?

I am not talking about the polynomials of the (simple) form(s) (a^n-b^n)/(a-b) or (a^n+b^n)/(a+b) as those polynomial forms are excluded from this thread, they can be expanded into n-1 degree polynomials already.

The property I am getting at is the n-1 degree polynomial has factors either 0 or 1 (mod n) when the polynomial is evaluated for any "x" value.

Some examples for n = 3 (which don't have the simple form(s) (a^3-b^3)/(a-b) or (a^3+b^3)/(a+b))

19x^2+7x+1

37x^2+11x+1

.....

Which come from the discriminant D = b^2-4ac for ax^2+bx+c.

Similarly, WITHOUT searching for coefficients, are there good examples of degree 4, discriminant a power of 5, and of degree 6, discriminant a power of 7. Again, these polynomial must not have any of the Generalized Mersenne form(s) (a^n-b^n)/(a-b) and (a^n+b^n)/(a+b)

The discriminant D is at:

For degree 4, integer solutions (a, b, c, d, e) such that:

256 a^3 e^3 - 192 a^2 b d e^2 - 128 a^2 c^2 e^2 + 144 a^2 c d^2 e - 27 a^2 d^4 + 144 a b^2 c e^2 - 6 a b^2 d^2 e - 80 a b c^2 d e + 18 a b c d^3 + 16 a c^4 e - 4 a c^3 d^2 - 27 b^4 e^2 + 18 b^3 c d e - 4 b^3 d^3 - 4 b^2 c^3 e + b^2 c^2 d^2 = 5^n

Computed here.

For degree 6, integer solutions (a, b, c, d, e, f, g) such that:

Too long for thread, is here.

For higher goals, for all primes n < 1000, (which is extremely complicated to do). Like always, hints, suggestions, and answers are appreciated.

Last fiddled with by carpetpool on 2017-02-14 at 00:57
carpetpool is offline   Reply With Quote
Old 2017-02-14, 01:46   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by carpetpool View Post
Some examples for n = 3 (which don't have the simple form(s) (a^3-b^3)/(a-b) or (a^3+b^3)/(a+b))

19x^2+7x+1

37x^2+11x+1

.....

Which come from the discriminant D = b^2-4ac for ax^2+bx+c.
49-(4*19) = 49-76 = -27 not technically a power of three ( only in absolute value)
121-(4*37) = -27 again not technically a power of three ( it is a power of -3 though).
science_man_88 is offline   Reply With Quote
Old 2017-02-14, 17:00   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

202618 Posts
Default

as for the property about 0 and 1 mod n only as factors we have restrictions for example:
  1. (3y+1)(3x+1) = 9xy+3y+3x+1
  2. (3y+1)(3x) = 9xy+3x
  3. (3y)(3x) = 9xy


all look fine until you realize that x or y in each case has some restriction in number 3 for example, neither x nor y can be of any other remainders except 0 and 1 mod 3 ( mod n respectively). in the second one x has to be of remainder 0 or 1 mod 3 ( mod n respectively), and in the first two cases y can't be odd ( in the first case x can also not be odd).

Last fiddled with by science_man_88 on 2017-02-14 at 17:49
science_man_88 is offline   Reply With Quote
Old 2017-02-15, 17:04   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

24·5·79 Posts
Default

Quadratics can't have discriminant 3^t for odd t, because b^2 would have to be three mod four, but for even t you can just take b any sufficiently large odd square and factor (3^2t)-b^2

E.g. 4x^2+29x+7 has discriminant 729; 2x^2+83x+41 has discriminant 3^8
fivemack is offline   Reply With Quote
Old 2017-02-16, 01:18   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·52·71 Posts
Default

The property I am getting at is the n-1 degree polynomial has factors either 0 or 1 (mod n) when the polynomial is evaluated for any "x" value.

What is important here is the number field, not the particular polynomial used to define it. By rescaling the variable, you can also sneak in finitely many primes which violate the property. For example,

x^2 + 5*x + 25 has D = -3 * 5^2

so defines the same quadratic field as x^2 + x + 1, but assumes values divisible by 5 (in fact by 25) whenever x is an integer divisible by 5. Similarly,

x^2 + 7*x + 49

has the requisite property, but discriminant D = -3 * 7^2, which has a prime factor other than 3.

Similarly, the quartic polynomial

x^4 + 5*x + 5 has D = 5^3 * 11^2,

but defines the same field as the cyclotomic polynomial x^4 + x^3 + x^2 + x + 1, and has the requisite property above. [In this case, I chose the "extraneous" factor 11 to be congruent to 1 (mod 5).]

So it is prudent to allow for finitely many exceptional primes in the above property [also for finitely many "extraneous" square factors in the discriminant]. This allows rescaling to produce a monic polynomial [lead coefficient 1] defining the same field as any given (nonzero, nonlinear, irreducible) polynomial in Z[x].

Calling the polynomial f(x), and assuming it to be irreducible, monic and in Z[x], and using p instead of n (since you want n to be a prime), one interpretation of the above property is as follows:

With at most finitely many exceptions, if q is a prime not congruent either to 1 or 0 (mod p), then the reduction f(x) (mod q) has no linear factors.

For if q is a prime dividing f(r), r a rational integer, then (x - Mod(r, q)) is a linear factor of the reduction of f(x) (mod q).

Alternatively (with possibly finitely many exceptions), if f(x) (mod q) has a linear factor, then q is congruent to 1 (mod p).

Now the cyclotomic field K of p-th roots of unity is characterized by the fact that the primes q which split into p-1 distinct prime ideal factors in K/Q are precisely those which are congruent to 1 (mod p). This property extends to the cyclotomic field of m-th roots of unity, for any m > 2. The degree over Q is phi(m), which is less than m - 1 when m is composite. Fortuitously, cyclotomic polynomials have discriminant equal to the discriminant of the number field they define -- no extraneous prime factors.

Number fields whose (field) discriminants only have one (finite) prime factor are unusal.

BTW, Stickelberger's criterion says that the discriminant of any monic polynomial in Z[x] is congruent either to 1 or 0 (mod 4). Thus, polynomial discriminants equal to an odd power of any prime congruent to 3 (mod 4) are impossible. If p is a prime congruent to 3 (mod 4), the discriminant of the cyclotomic polynomial for the primitive p-th roots of unity is

D = -p^(p - 2).
Dr Sardonicus is offline   Reply With Quote
Old 2017-02-16, 03:46   #6
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22×79 Posts
Post

Dr. Sardonicus, Thanks for solving my math problems. Your posts are greatly appreciated around here.

If you know of a degree 6 polynomial which has factors 0 or 1 mod 7, please post examples here.

Meanwhile, a degree 4 polynomial

x^4+7x^3-x^2-7x+1 with Discriminant D = 415125 = 3^4*5^3*41

is 0, 1 or 4 (mod 5) for any x value and appears to have similar properties to the cyclotomic polynomial other than factors congruent to 4 (mod 5) of x^4+2x^3+4x^2+8x+16, a generalization of x^4+x^3+x^2+x+1 of the form a^4+ab^3+a^2b^2+a^3b+b^4. Would there be an easy way to generate polynomials with number fields the same as the cyclotomic polynomial of degree 4 or more generally n-1?

EDIT: For x = 32, 1276705 = 5*19*89*151

Last fiddled with by carpetpool on 2017-02-16 at 03:52
carpetpool is offline   Reply With Quote
Old 2017-02-16, 15:55   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×52×71 Posts
Default

Would there be an easy way to generate polynomials with number fields the same as the cyclotomic polynomial of degree 4 or more generally n-1?

Yes -- given the right software [e.g. Pari-GP], and understanding what it does.

Your polynomial,

f=x^4+7*x^3-x^2-7*x+1 is irreducible with [according to Pari-GP] Galois group D4. I also used Pari to find a "reduced" polynomial defining the same field,

g = x^4 - 2*x^3 - 6*x^2 + 7*x + 11 with D = 5^3 * 41

The polynomial f (mod 3) has a repeated quadratic factor because of the "extraneous" factor 3^4 in the discriminant. The polynomial g (mod 3) splits into 2 distinct quadratic factors.

The splitting field contains the quadratic fields defined by t^2 - t - 1, t^2 - t - 10, and t^2 - t - 51 [the last being a defining polynomial for Q(sqrt(D))]

Both f and g split into quadratic factors in the field defined by t^2 - t - 1; g factors as

(x^2 - x + (-t - 3)) * (x^2 - x + (t - 4)) where t^2 - t - 1 = 0.

This means that f and g (mod p) will factor into two quadratic factors whenever 5 is a quadratic residue (mod p), i.e. p == 1 or -1 (mod 5).
However, whether either quadratic factor splits further (mod p) is a more complicated proposition; it cannot be described by rational integer congruences (this is because D4 is not an Abelian group). For example, one of the quadratic factors (mod 11) splits into linear factors; both quadratic factors (mod 31) remain irreducible; both quadratic factors (mod 131) split into linear factors.
If p is congruent to 2 or 3 (mod 5), g (mod p) either remains irreducible, or splits into irreducible quadratic factors. These cases are not describable with rational integer congruences.

I decline to generate more defining polynomials for the field of 7th roots of unity.

Last fiddled with by Dr Sardonicus on 2017-02-16 at 16:01
Dr Sardonicus is offline   Reply With Quote
Old 2017-02-17, 01:10   #8
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22·79 Posts
Default

Here is an example for quartic polynomials, using Wolfram Alpha I solved for the last three coefficients.

x^4+3x^3+4x^2+2x+1

with discriminant D = 125

has the same number field properties as the cyclotomic polynomial x^4+x^3+x^2+x+1.

Is PARI GP capable of doing exactly this for degree 6 polynomials, and finding polynomials with the same number field properties as x^6+x^5+x^4+x^3+x^2+x+1.

One way would be setting up a few queries via PARI GP to solve for:

Discriminant [ax^6+bx^5+cx^4+dx^3+ex^2+fx+g] for a = 1, 20; b = 1, 20; c = 1, 20; d = 1, 20; e = 1, 20; f = 1, 20; g = 1, 20; where 1, 20 denotes all integers 1 <= (a, b, c, d, e, f, g) <= 20.

The number of combinations of polynomials would be, 20^7 = 1280000000 such polynomials searching for discriminant = -16807 or some other related value.

Please show me a command via Pari GP which can do five variable solution for:

Discriminant of x^6+4x^5-3x^4+ax^3+bx^2+cx+d = -16807

There should be at least one set of integers which will work with the following property.

This is interesting, especially for getting into polynomials of degrees 6, 10, and 12.
carpetpool is offline   Reply With Quote
Old 2017-02-17, 01:26   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by carpetpool View Post
Here is an example for quartic polynomials, using Wolfram Alpha I solved for the last three coefficients.

x^4+3x^3+4x^2+2x+1

with discriminant D = 125

has the same number field properties as the cyclotomic polynomial x^4+x^3+x^2+x+1.

Is PARI GP capable of doing exactly this for degree 6 polynomials, and finding polynomials with the same number field properties as x^6+x^5+x^4+x^3+x^2+x+1.

One way would be setting up a few queries via PARI GP to solve for:

Discriminant [ax^6+bx^5+cx^4+dx^3+ex^2+fx+g] for a = 1, 20; b = 1, 20; c = 1, 20; d = 1, 20; e = 1, 20; f = 1, 20; g = 1, 20; where 1, 20 denotes all integers 1 <= (a, b, c, d, e, f, g) <= 20.

The number of combinations of polynomials would be, 20^7 = 1280000000 such polynomials searching for discriminant = -16807 or some other related value.

Please show me a command via Pari GP which can do five variable solution for:

Discriminant of x^6+4x^5-3x^4+ax^3+bx^2+cx+d = -16807

There should be at least one set of integers which will work with the following property.

This is interesting, especially for getting into polynomials of degrees 6, 10, and 12.
poldisc is the discriminant of a polynomial, polcoeff are the coefficients, polcyclo is the cyclotomic polynomial, polcycloreduced produces a vector of elementary divisors of some kind related to the polynomial ( looks to factor the polynomial discriminant, but I'm not an expert). edit:polsubcyclo is also one I've just played around with that may be able to do what you want if you know what quantities to input.

Last fiddled with by science_man_88 on 2017-02-17 at 01:51
science_man_88 is offline   Reply With Quote
Old 2017-02-17, 02:02   #10
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22×79 Posts
Post

Check this out sm88,

(17:57) gp > polsubcyclo(2201, 5)
%33 = [x^5 - x^4 - 880*x^3 + 176*x^2 + 179584*x + 26624, x^5 + x^4 - 28*x^3 + 37*x^2 + 25*x + 1, x^5 - x^4 - 880*x^3 + 6779*x^2 + 14509*x - 112039, x^5 + x^4 - 12*x^3 - 21*x^2 + x + 5, x^5 - x^4 - 880*x^3 + 15583*x^2 - 95541*x + 196101, x^5 - x^4 - 880*x^3 - 2025*x^2 + 49725*x - 112039]

I figured out the idea to this: polsubcyclo(n, d) will give ALL polynomials with the same number field as the cyclotomic polynomial d if and only if d | phi(n). I've organized the new polynomials. Dr. Sardonicus should take a look at these ones:

x^5 - x^4 - 880*x^3 + 176*x^2 + 179584*x + 26624
x^5 + x^4 - 28*x^3 + 37*x^2 + 25*x + 1
x^5 - x^4 - 880*x^3 + 6779*x^2 + 14509*x - 112039,
x^5 + x^4 - 12*x^3 - 21*x^2 + x + 5
x^5 - x^4 - 880*x^3 + 15583*x^2 - 95541*x + 196101
x^5 - x^4 - 880*x^3 - 2025*x^2 + 49725*x - 112039

All 5 appear to have the same number field properties as x^5+x^4+x^3+x^2+x+1

EDIT:

The mistake is the polynomials are degree 5, not 4!

Command:

(17:54) gp > ?? polsubcyclo()
polsubcyclo(n,d,{v = 'x}):

Gives polynomials (in variable v) defining the sub-Abelian extensions of
degree d of the cyclotomic field Q(zeta_n), where d | phi(n).

If there is exactly one such extension the output is a polynomial, else it
is a vector of polynomials, possibly empty. To get a vector in all cases, use
concat([], polsubcyclo(n,d)).

The function galoissubcyclo allows to specify exactly which sub-Abelian
extension should be computed.

The library syntax is GEN polsubcyclo(long n, long d, long v = -1), where v
is a variable number.

Last fiddled with by carpetpool on 2017-02-17 at 02:15
carpetpool is offline   Reply With Quote
Old 2017-02-17, 02:32   #11
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22×79 Posts
Post

One pari command I am searching for is polynomials with the same properties as their cyclotomic polynomials, and finds them based on fixed coefficients in order.

({a, b}, x) would search for a polynomial with the same properties as the cyclotomic polynomial of x, with leading coefficients a, b, c for each higher degree.

For example:

({1, 4}, 5) should find all polynomials with the same number field properties as x^4+x^3+x^2+x+1 of the form x^4+4x^3+ax^2+bx+c. That is should output the solutions, if any {a, b, c} for the degrees 2, 1, 0.

I've scoured a whole column of polynomial commands and not one serves for this purpose.
carpetpool is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Choice of SNFS polynomial degree lavalamp Factoring 15 2018-02-11 14:46
How to use my own polynomial with Msieve jordis Msieve 22 2009-04-17 10:54
109!+1 polynomial search fivemack Factoring 122 2009-02-24 07:03
GNFS polynomial degree joral Factoring 6 2008-09-26 22:15
Polynomial R.D. Silverman NFSNET Discussion 13 2005-09-16 20:07

All times are UTC. The time now is 02:49.

Wed Oct 21 02:49:34 UTC 2020 up 41 days, 32 secs, 0 users, load averages: 1.62, 1.75, 1.68

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.