mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Computer Science & Computational Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=116)
-   -   On polynomials without roots modulo small p (https://www.mersenneforum.org/showthread.php?t=20491)

 fivemack 2015-09-16 14:09

On polynomials without roots modulo small p

A friend of mine observed that the centred hexagonal numbers (3x^2+3x+1) never looked 'nice'. This is true, and the reason is that they're never divisible by 2, 3, 5 or 11.

So I've been looking for polynomials which take only values not divisible by small primes. You can construct these by the Chinese Remainder Theorem, but I'm more interested in the asymptotics of where they turn up in nature for polynomials with small coefficients.

For quadratics, going up by minimum-value-of-maximum-coefficient:

[code]
a2 a1 a0 smallest prime with root mod p
48 42 73 53
81 141 -139 59
178 74 179 67
358 222 331 73
786 912 -811 83
2106 546 3037 89
3840 1290 2089 97
[/code]

For cubics
[code]
a3 a2 a1 a0 p_min
12 3 33 -1 37
16 9 36 -1 41
4 48 -10 47 47
1 49 -52 1 53
60 52 -10 71 71
6 44 164 -131 79
[/code]

[code]
1 1415 -673 67
1 6663 -1361 71
1 8433 -8171 73
1 12431 -6079 83
1 12787 -3187 101
1 16159 -10093 107
1 41569 -19993 127
1 97195 -93463 131
1 139831 -124513 137
1 221601 -204983 149
[/code]

For quartics
[code]
2 -4 -2 4 -1 23
4 0 -6 0 1 31
3 -6 -4 7 1 41
5 6 18 15 -1 43
9 13 19 13 -1 53
29 0 -29 0 -1 61
4 22 -45 19 -1 83
3 0 85 0 1 89
7 -14 -90 97 -1 103
29 0 37 0 107 107
61 -122 -41 102 109 109
[/code]

For ax^4+bx^2+c
[code]
4 0 -6 0 1 31
19 0 19 0 -1 37
21 0 -21 0 -1 41
25 0 -27 0 1 47
29 0 -29 0 -1 61
61 0 53 0 -1 83
3 0 85 0 1 89
29 0 37 0 107 107
19 0 -139 0 -137 113
156 0 -174 0 -131 131
9 0 259 0 1 139
486 0 -6 0 -223 149
[/code]

 R.D. Silverman 2015-09-16 14:39

[QUOTE=fivemack;410466]A friend of mine observed that the centred hexagonal numbers (3x^2+3x+1) never looked 'nice'. This is true, and the reason is that they're never divisible by 2, 3, 5 or 11.

So I've been looking for polynomials which take only values not divisible by small primes. You can construct these by the Chinese Remainder Theorem, but I'm more interested in the asymptotics of where they turn up in nature for polynomials with small coefficients.

For quadratics, going up by minimum-value-of-maximum-coefficient:

[code]
a2 a1 a0 smallest prime with root mod p
48 42 73 53
81 141 -139 59
178 74 179 67
358 222 331 73
786 912 -811 83
(I have examples with 89 [387 7353 -7963] and 97 [960 330 7951] but am not sure they're smallest)
[/code]

For cubics
[code]
a3 a2 a1 a0 p_min
12 3 33 -1 37
16 9 36 -1 41
4 48 -10 47 47
1 49 -52 1 53
60 52 -10 71 71
6 44 164 -131 79
[/code]

[code]
1 1415 -673 67
1 6663 -1361 71
1 8433 -8171 73
1 12431 -6079 83
1 12787 -3187 101
1 16159 -10093 107
[/code]

For quartics
[code]
2 -4 -2 4 -1 23
4 0 -6 0 1 31
3 -6 -4 7 1 41
5 6 18 15 -1 43
9 13 19 13 -1 53
29 0 -29 0 -1 61
4 22 -45 19 -1 83
[/code][/QUOTE]

One may find a lot of useful information in:

[url]http://websites.math.leidenuniv.nl/algebra/chebotarev.pdf[/url]

 R.D. Silverman 2015-09-18 12:54

[QUOTE=R.D. Silverman;410471]One may find a lot of useful information in:

[url]http://websites.math.leidenuniv.nl/algebra/chebotarev.pdf[/url][/QUOTE]

I should have added (from elementary algebraic number theory) that f(x) will be
divisible by p for some x if

(1) p divides the discriminant and
(2) the polynomial is not constant mod p.

Such primes p ramify.

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