All Questions
37 questions
17
votes
3
answers
2k
views
About the prime divisors of values of polynomials
Let $P$ be a polynomial having integer coefficients (and degree $\geq 3$), and let $\mathscr P_P$ be the set of prime numbers dividing some value $P(n)$ with $n \in \mathbb Z$.
Is it true that $\...
- 3,866
15
votes
1
answer
495
views
Is the number of representations as the sum of two elements of a polynomial sequence always small?
Let $f(x) \in \mathbb{Z}[x]$ be a degree $d>1$ polynomial with integer coefficients. Define
$$r(n) := | \{x,y \in \mathbb{Z} : f(x)+f(y) = n \}|. $$
My question is:
Is it true that $r(n)...
- 13k
13
votes
3
answers
949
views
Polynomials vanishing modulo some integer $n$
It is well-known that a polynomial $q \in \mathbb Z[t]$ vanishes modulo $p$ only if it lies in the ideal $J_p$ generated by $p$ and $t^p-t$. This means that either the degree is large (at least $p$) ...
- 25.5k
12
votes
2
answers
902
views
Infinitely many irreducible polynomials of the form f(X^2) + X mod 3?
Are there infinitely many polynomials $f \in \mathbb{F}_3[X]$ for which $f(X^2) + X$ is irreducible?
- 11.3k
12
votes
1
answer
1k
views
Least prime $p$ such that an irreducible polynomial of degree $n$ has no root modulo $p$?
This question is inspired by an old question of Greg Kuperberg, about how small is the first prime $p$ which makes a given monic polynomial $P$ with integral coefficient have a (simple) root modulo $p$...
- 26k
9
votes
0
answers
324
views
Semi-primes represented by quadratic polynomials
According to Lemke-Oliver, irreducible quadratic polynomials $G$ with positive leading coefficient and $\rho(2)<2$, (where $\rho(m)$ denotes the number of incongruent solutions to the congruence $G(...
- 195
8
votes
1
answer
1k
views
An elementary lower bound on the number of primes
Recall the second Chebyshev function: $$\psi(x) = \sum_{p \leq x} \lfloor \log_p x \rfloor \log p$$ where $x$ is a positive integer, and $p$ runs over all primes $\leq x$.
In a hunt for an "...
- 11.3k
8
votes
0
answers
224
views
Is there an approximate formula for the discriminant of a sparse polynomial?
Consider integer polynomials $P \in \mathbb{Z}[X] \setminus \{0\}$ of a degree $D \geq 1$ and without multiple complex roots. Let me introduce a notation
$$
d(P) := \frac{1}{D} \log{|\mathrm{Disc}(P)|}...
- 13.8k
7
votes
2
answers
998
views
Upper density of the set of $n$'s such that $p(n)$ is prime, where $p$ is polynomial
The starting point for this question is the following (false) statement
$\forall n\in \mathbb{N} (n^2 + n + 41 \text{ is prime}).$
Given a polynomial function $p:\mathbb{N} \to \mathbb{N}$ ...
- 48.9k
6
votes
1
answer
665
views
On the distribution of roots modulo primes of an integral polynomial
For motivation and related questions, see below.
Rough sketch of the question.
View $\bigsqcup_{p \text{ prime}} (\mathbb{Z}/p\mathbb{Z})$ as a ‘subset’ of the unit circle, via $a\pmod{p} \mapsto e^{...
- 83
5
votes
1
answer
392
views
Divergence of primes dividing polynomials
Let $Q : \mathbb{Z} \rightarrow \mathbb{Z}$ be a polynomial. Form the set
$$M_{Q} := \{p:\text{ }p\text{ is prime, }\exists n_{p}\in \mathbb{Z}\text{ so that }p|Q(n_{p})\}$$
Is $$\sum_{s \in M_{Q}}\...
- 227
5
votes
1
answer
430
views
How many roots of polynomial in $\mathbb Z[x]$ and $\mathbb Q[x]$ are integers on average?
Given $d,B>0$ the number of polynomials in $\mathbb Z[x]$ of degree $d$ and coefficient size at most $B$ have at least one integer roots should be $B^{O(d)}f(d)$ at some function $f$ (from Random ...
- 13.9k
5
votes
0
answers
205
views
Is there a polynomial version of Wilson's theorem which can avoid Cramer flavored conjectures?
Wilson's theorem states that a natural number $n > 1$ is a prime number if and only if the product of all the positive integers less than $n$ is one less than a multiple of $n$.
Is there a version ...
- 13.9k
4
votes
1
answer
271
views
The highest power of $2$ dividing a polynomial evaluated at $x=3$
Let $\nu_2(a)$ be the $2$-adic valuation of an integer $x$, i.e. the largest power $t$ such that $2^t$ divides $x$.
Define the operator $D=x\frac{d}{dx}$ and the polynomial $\Phi_k(x)=\frac{x^{k+1}-1}{...
- 43.2k
4
votes
0
answers
134
views
$\delta$-equidistributed polynomials over finite fields
I'm trying to show that a polynomial over finite (prime) field is "close enough" to being equidistributed over its range. A polynomial $p(\cdot)$ from $\mathbb{F}^n$ to $\mathbb{F}$ is $\...
- 301
4
votes
0
answers
432
views
square-free parts of values of polynomials
Given a polynomial $f(x) \in \mathbb{Z}[x]$ of degree $d$, consider the following three sets:
$$N_1(x) = \#\{k \leq x: f(k) \text{ is square-free}\}$$
$$N_2(x) = \#\{n \leq x: n = f(k) \text{ is ...
- 585
3
votes
1
answer
372
views
How many ways can $N$ be written as a sum of terms in the form $2^i3^j$?
Given a positive integer $N$, let $f(N)$ be the number of ways $N$ can be decomposed as a sum of terms of the form $2^i3^j$, where each such term appears at most once in the sum. For example, $f(10) = ...
- 1,703
3
votes
2
answers
365
views
Largest prime factors of integer polynomials
I have a question in analytic number theory which is closely related to the open problem (Bunyakovsky conjecture and more generally, Schinzel's hypothesis H) that asks you if, any irreducible ...
- 302
3
votes
1
answer
194
views
Divergence of a series related to Schinzel's hypothesis H
The Series
Consider the series identity
$$\Phi(s) = \sum_{n=1}^\infty \frac{\mu(n) (\log n)^k}{n^s} \sum_{r \in R(n)} \zeta(s,r/n) = \sum_{n=1}^\infty \frac{\Lambda_k'(f(n))}{n^s}$$
$$R(n) = \left\...
- 33
3
votes
1
answer
344
views
Number of prime factors of a polynomial discriminant
Let $f(x)\in\mathbb{Z}[x]$ be a polynomial of degree $d$ and naive height (maximum of the absolute values of the coefficients) at most $H$. Is there anything known about the number of prime factors of ...
2
votes
2
answers
370
views
Link between Irreducible Factors and Prime Factors (or Cycles of a Permutation)
In "Anatomy of Integers and Permutations", http://www.dms.umontreal.ca/~andrew/PDF/Anatomy.pdf, Granville gives a calibration of cycles of a permutation and prime factors of an integer. "We know ...
- 329
2
votes
2
answers
208
views
On the number of values with exactly $k$ prime factors of a given polynomial
This is surely be a well studied problem. Let $f(x) \in \mathbb{Z}[x]$. Is there some $k \in \mathbb{N}$ such that there are infinitely many $n \in \mathbb{Z}$ where $f(n)$ has exactly $k$ prime ...
- 1,763
2
votes
0
answers
159
views
Large prime divisors of values of a polynomial, in a given residue class
Let $f(X) \in \mathbb{Z}[X]$ be an irreducible polynomial of degree $d \geq 2$. Let $q \in \mathbb{N}$ be an integer, and let $q \mathbb{Z} + r$ be a residue class that contains infinitely many primes ...
- 1,914
2
votes
0
answers
84
views
quadratic residues and cubic polynomials [closed]
I'm really not sure about this, but I've heard somewhere that for any prime $p$,
$|\sum_{x=0}^{p-1} (\frac{ax^3 +bx^2 +cx +d}{p} ) |\le \sqrt{2p}$ holds.
Does anyone know a proof for this inequality ...
- 141
2
votes
0
answers
67
views
Density of integral values of a rational function
Let $\mathbf{x} = (x_1, \cdots, x_n)$, and consider a rational function $F : \mathbb{R}^n \rightarrow \mathbb{R}$ be given by
$$\displaystyle F(\mathbf{x}) = \sum_{i = 1}^m \frac{Q_i(x_1, \cdots, x_{...
- 26.9k
2
votes
0
answers
121
views
How to choose a prime p s.t. n-th cyclotomic polynomial splits into as much as possible irreducible polynomials while p is almost constant size?
The reason I ask this question is that cyclotomic polynomial is critical to the construction of lattice-based cryptography. In most of the existing lattice-based cryptographic schemes, $n$ is usually ...
- 33
1
vote
0
answers
323
views
On fifth powers forming a Sidon set
We call a set of natural numbers $\mathcal S$ to be a Sidon Set if $a+b=c+d$ for $a,b,c,d\in \mathcal S$ implies $\{a,b\}=\{c,d\}$. In other words, all pairwise sums are distinct.
Erdős conjectured ...
- 791
1
vote
0
answers
88
views
Distribution of number of integer solutions in box to bivariate polynomials?
Take a bivariate polynomial of degree $d_x+d_y>\max(d_x,d_y)>1$ in $\mathbb Z[x,y]$ with coefficients bound in absolute value by $b$ ($d_x$ is $x$-degree and $d_y$ is $y$-degree).
What is the ...
- 13.9k
1
vote
1
answer
189
views
Explicit bivariate quadratic polynomials where Coppersmith is better than standard solver?
http://www.numbertheory.org/pdfs/general_quadratic_solution.pdf gives a general method to solve quadratic bivariate diophantine equation while Coppersmith introduced a method to solve bivariate ...
- 13.9k
1
vote
0
answers
276
views
Method of Coppersmith optimal for multivariate?
It is shown that Coppersmith method yields optimal integer root extraction for univariate polynomials in https://arxiv.org/abs/1605.08065 and a follow up work attempts this for bivariate polynomials ...
- 13.9k
1
vote
0
answers
202
views
Prime generating polynomials
Continuation to this previous question.
According to Lemke-Oliver, an irreducible polynomial $G$ of degree $g$ with positive leading coefficient and $\Gamma_G\neq0$ (with $\Gamma_G$ a certain factor ...
- 195
0
votes
1
answer
431
views
Reason Coppersmith fails here?
Take classic problem of finding $P,Q$ in balanced semi-prime $N=PQ$.
$P$ has a binary expansion and so does $Q$. We can set the binary $0/1$ variables to be $x_1$ through $x_{\lceil\log P\rceil}$ and $...
- 13.9k
0
votes
1
answer
356
views
A sufficient condition for a set of primes to be the set of reducibility of an integer polynomial
Let $P$ be the set of all positive primes. Let $S$ an arbitrary infinite subset of $P$ satisfying the following assumption: there exists a finite Galois extension $K$ of $\mathbb{Q}$ and a conjugacy ...
user145520
0
votes
1
answer
159
views
Parity and number of squares taken by polynomials in a range?
I have a polynomial $f(x)=a^2x^2+bx+c\in\mathbb Z[x]$ with $f(x)$ not a constant times a square and $abc\neq0$ and I want to know how many $x$ between $-a$ and $a$ the polynomial is a perfect square. ...
- 13.9k
0
votes
0
answers
115
views
Maximum number of integer solutions with some size constraints to bivariate polynomials?
Take a bivariate polynomial of total degree $d$ satisfying $d=d_x=d_y>1$ in $\mathbb Z[x,y]$ with coefficients bound in absolute value by $b$ ($d_x$ is $x$-degree and $d_y$ is $y$-degree).
Given a ...
- 13.9k
0
votes
0
answers
152
views
On the $\mathsf{LCM}$ of a set of integers defined by moduli of powers
For integers $a,b,t$ define $$\mathcal R_t(a,b)=\{q\in\mathbb Z\cap[1,\min(a^t,b^t)]: a^t\equiv b^t\bmod q\}$$ and $\mathsf{LCM}(\mathcal R_t(a,b))$ to be $\mathsf{LCM}$ of all entries in $\mathcal ...
- 1,826
-2
votes
1
answer
181
views
Polynomials of minimum degree that interpolate primes in intervals
Given an interval $[a,b]$ what is the minimum degree of univariate polynomials in $\mathbb Q[x]$ that passes through all primes between $a$ and $b$ (denoted by $\mathbb P[a,b]$ with total number of ...
- 1,826