All Questions
44 questions
6
votes
1
answer
560
views
Is decomposability of integer polynomials over the rational numbers an undecidable problem?
By a decomposition of a polynomial $F(x)$ over a field $K$ we mean writing $F(x)$ as
$$
F(x)=G(H(x)) \quad(G(x), H(x) \in K[x]),
$$
which is nontrivial if $\operatorname{deg} G(x)>1$ and $\...
- 310
2
votes
1
answer
158
views
Computing the minimal polynomial of roots of polynomials with algebraic coefficients
Let $p(x) = \sum_{i=0}^{n} c_i x^i$ with $c_i \in \mathbb{A}$ with $q_i(c_i) = 0$ and all $q_i \in \mathbb{Q}[x]$ being minimal polynomials of the coefficients.
Let $r$ be a zero of $p(x)$. Is there ...
- 21
13
votes
2
answers
875
views
Given an irreducible polynomial over $\mathbb{Z}$, how often is it irreducible modulo a prime?
Given a monic irreducible polynomial $f\in\mathbb{Z}[x]$, I'd like to know for how many primes p we have that $f \bmod p$ is irreducible.
In the link: How many primes stay inert in a finite (non-...
- 133
0
votes
0
answers
126
views
Nilpotent elements of $(\mathbb{Z}/n \mathbb{Z})[x_1,...,x_m]/\langle f_1(x_1,...,x_m),f_2(x_1,...,x_m),...f_k(x_1,...,x_m)\rangle$
This is generalization of the univariate case
and also related to open problem.
Let $n,k,m,B>1$ be positive integers and $f_1(x_1,...,x_m),f_2(x_1,...,x_m),...f_k(x_1,...,x_m)$ be polynomials with ...
- 25.4k
4
votes
0
answers
171
views
Nilpotent elements of $K=(\mathbb{Z}/n \mathbb{Z})[x]/f(x)$
This is related to an open problem.
Let $n$ be integer and $f(x)$ polynomial with integer coefficients and set $K=(\mathbb{Z}/n \mathbb{Z})[x]/f(x)$.
Let $S$ be the set of degree 2 nilpotent elements ...
- 25.4k
17
votes
1
answer
687
views
Multiply an integer polynomial with another integer polynomial to get a "big" coefficient
I have copied this question from StackExchange, in the hope that some experts here can provide some relevant insight. Thanks to Greg Martin for improving the question.
Given $f(x) = a_0 + a_1 x + a_2 ...
- 823
4
votes
1
answer
334
views
GCD in $\mathbb{F}_3[T]$ with powers of linear polynomials
This is a continuation of my previous question on $\gcd$s of polynomials of type $f^n - f$.
Let us call $n > 1$ simple at a prime $p$ when $p-1 \mid n-1$ but $p^k - 1 \not\mid n-1$ for all $k > ...
- 63.1k
2
votes
1
answer
131
views
Adjacent reducible polynomials
Let $P[X_1, X_2, \ldots, X_N]$ be a reducible polynomial in $\mathbb{Z}[X_1, X_2, \ldots, X_N]$ such that $P[X_1, X_2, \ldots, X_N] + 1$ is also reducible. What (if anything) can we say about $P$?
One ...
- 1,703
0
votes
1
answer
216
views
A Newton identity and the primes--the Faber partition polynomials and modular arithmetic
[Edit, July 6, 2022: Removed erroneous characterization of Faber polynomials as an Appell sequence.]
Dress and Siebeneicher in their tale of the Burnside family express an opinion (1.2) that, if I ...
- 10.5k
2
votes
0
answers
121
views
When $\gcd(P(x),Q(x))\bmod R(x)=\gcd(P(x) \bmod R(x),Q(x) \bmod R(x))$?
Let's $P,Q\in\mathbb K[x]$, with $\mathbb K$ a finite field.
On what necessary and sufficient condition on $R \in \mathbb K[x]$ is it :
$\gcd(P(x),Q(x))\bmod R(x)=\gcd(P(x) \bmod R(x),Q(x) \bmod R(x))...
- 4,074
10
votes
1
answer
327
views
Proving that polynomials belonging to a certain family are reducible
In an article, I've found the following result. Unfortunately, it was derived from a general, somewhat complicated theory, that would be cumbersome for this result alone.
Assume that $\mathbb F_p$ is ...
- 687
7
votes
1
answer
1k
views
Polynomials which are functionally equivalent over finite fields
Recall that two polynomials over a finite field are not necessarily considered equal, even if they evaluate to the same value at every point. For example, suppose $f(x) = x^2 + x + 1$ and $g(x) = 1$. ...
- 1,703
4
votes
0
answers
236
views
Is this property of polynomials generic?
Let $n \geq 2$, and consider a polynomial $f$ in $n$ variables, say over a field $K$ of characteristic 0. Recall that $f$ is geometrically irreducible if $f$ is irreducible over the algebraic closure ...
- 26.9k
6
votes
1
answer
242
views
$(q,t)$-Fibonacci polynomials: area & bounce statistics
This is related to my earlier (unanswered) MO post. Preserve notations from there.
We take advantage of the one-to-one correspondence between the $(s,s+1)$-core partitions and $(s,s+1)$-Dyck paths. ...
- 43.2k
1
vote
0
answers
57
views
Families of polynomials given by tuples of binary forms with finitely many reducible members
Let $G_1, \cdots, G_n \in \mathbb{Z}[x,y]$ be binary forms, and put $\mathbf{G} = (G_1, \cdots, G_n)$. Consider the family of monic polynomials
$$\displaystyle \mathcal{F}_\mathbf{G} = \{x^n + G_1(p,q)...
- 26.9k
15
votes
0
answers
376
views
Reducible polynomials of the shape $f(t^2)$, where $f$ is irreducible
Let $f(x) \in \mathbb{Z}[x]$ be a monic, irreducible polynomial. What are necessary and sufficient conditions for $g(t) = f(t^2)$ to be reducible over $\mathbb{Q}$?
For instance, if $f(x) = x-1$ then $...
- 26.9k
2
votes
2
answers
399
views
What fraction of polynomials with integer coefficients are indecomposable?
It is well-known that "most" integers are composite: the Prime Number Theorem tells us that only about $1/\log(N)$ of the integers in the interval $1 \ldots N$ are prime. For polynomials, ...
- 1,703
15
votes
1
answer
1k
views
Integer valued polynomials and polynomials with integer coefficients
It is well known that the subring $S$ of integer valued polynomials ${\mathbb Q}[x]$ is generated by the binomial functions $P_n={x \choose n}$. One can ask a dual question: how to characterize the ...
- 1,526
1
vote
4
answers
717
views
Given an integer $N$, find solutions to $X^3 + Y^3 + Z^3 - 3XYZ \equiv 1 \pmod{N}$
Given an integer $N > 0$ with unknown factorization, I would like to find nontrivial solutions $(X, Y, Z)$ to the congruence $X^3 + Y^3 + Z^3 - 3XYZ \equiv 1 \pmod{N}$. Is there any algorithmic way ...
- 1,703
3
votes
1
answer
195
views
Solutions to nonhomogeneous quadratic equation mod $N$
Is there any way to find non-trivial solutions to the equation $x^2 + y^2 - x \equiv 0 \mod{N}$? There are clearly several trivial solutions, for example $(x, y) = (0, 0), (1, 0), (2^{-1}, 2^{-1}), (2^...
- 1,703
1
vote
0
answers
90
views
Mod $N^2$ evaluation of a polynomial defined by first $N-1$ roots
Given a prime $N$ and integer $g$, where $g$ is able to generate the multiplicative subgroup $(\mathbb{Z}/N^2\mathbb{Z})^*$, I am interested in any results simplifying or evaluating $f\in (\mathbb{Z}/...
- 11
28
votes
1
answer
2k
views
SOS polynomials with integer coefficients
A well known theorem of Polya and Szego says that every non-negative univariate polynomial $p(x)$ can be expressed as the sum of exactly two squares: $p(x) = (f(x))^2 + (g(x))^2$ for some $f, g$. ...
- 1,703
1
vote
0
answers
53
views
On a structural decomposition of polynomials based on integral roots
Given an irreducible polynomial of structure $$f(x,y)=\sum_{\substack{i,j\in\{0,1,2\}\\i+j\leq3}}a_{i, j}x^iy^j\in\mathbb Z[x,y]$$ with $a_{2,1}a_{1,2}a_{1,1}a_{1,0}a_{0,1}a_{0,0}\neq0$ if $f(m,n)=0$ ...
- 1,826
11
votes
1
answer
475
views
Greatest common divisor in $\mathbb{F}_p[T]$ with powers of linear polynomials
Let $n>1$ and $p$ be an odd prime with $p-1 \mid n-1$ such that $p^k - 1 \mid n-1$ does not hold for any $k>1$. Notice that, since $p-1 \mid n-1$, we have $T^p - T \mid T^n-T$ in $\mathbb{F}_p[T]...
- 63.1k
2
votes
0
answers
93
views
The prime spectrume of integral-valued polynomial ring
Let $ D $ be an integral domain with quotiont field $K $ and let $Int (D) $be the set of all integral-valued polynomials on $D $, that is, $ Int (D):=\{f \in K[x]\mid f (D) \subseteq D\} $. The ...
- 21
3
votes
0
answers
222
views
Mod p reduction of geometrically irreducible polynomials
Let $f\in \mathbb Z[t,x]$ be a polynomial of positive degree that is irreducible over $\overline{\mathbb Q}[t,x]$. Is it true that for all but finitely many primes $p$ the reduced polynomial $f_p\in \...
- 101
1
vote
0
answers
289
views
gcd of polynomial values
Suppose that $f$ and $g$ are two coprime polynomials in $\mathbb Z[x]$. I'm interested in any sort of upper bound on $gcd(f(a),g(a))$, in terms of the integer $a$. Are there any results of this type?...
user47305
2
votes
1
answer
470
views
Polynomials with no multiple root
Let $a,d$ be polynomials of $\mathbb Z[X]$ with $\deg a>\deg d\ge0$ and $P$ be a polynomial of $\mathbb Z[X]$. Consider an infinite sequence of integers $(\lambda_n)_n$. Can one assert there exists ...
- 3,998
8
votes
3
answers
1k
views
Sufficient conditions for a polynomial to be reducible over the integers
There are several well-known criteria for a polynomial with integer coefficients to be irreducible over $\mathbb{Z}$, e.g., Eisenstein's criterion. I'm looking for the opposite: other than ...
- 1,703
7
votes
1
answer
230
views
Discriminant of numerator of inverse logarithmic derivative operator iteration
Let $T:\mathbb Q(x)\to \mathbb Q(x)$ be the operator of inverse logarithmic derivative, i.e. $$Tf=\frac{f}{f'}.$$ Define $$p_n(x)=T^n\left(x-\frac{x^2}{2}\right).$$ Let $f_n(x) \in \mathbb Z[x]$ be ...
- 7,193
3
votes
0
answers
95
views
Sign of bivariate polynomial evaluated over two algebraic numbers
I would like to compute the sign of a bivariate polynomial $f$ evaluated over two algebraic numbers $a$, $b$. The numbers are in "isolating interval representation" meaning that each one is defined by ...
- 151
3
votes
1
answer
336
views
If $F(x,y)$ is a polynomial which is not a square, then how often is the specialization $F(x,a)$ a square?
Suppose $F(x,y)$ is a polynomial in two variables over a field $K$, and $F(x,y)$ is not a square. When is $F(x,a)$ a square for $a\in K$? I would guess that Hilbert's Irreducibility Theorem might help ...
- 671
5
votes
0
answers
153
views
On factorization algorithms for $\mathcal{O}[x]$
We know that $\mathsf{LLL}$ algorithm provides factorization procedure that runs in poly time for polynomials in $\Bbb Z[x]$ that are primitive.
What other rings $\mathcal{O}$ can we use instead of $\...
user76479
12
votes
1
answer
3k
views
Factorization of polynomials in two variables
I have read, from the question
Irreducibility of polynomials in two variables, that all polynomials $f(x)-g(y)$, where $f, g$ are indecomposable polynomials, and there are no $a, b$ such that $g(ax+b)...
- 2,811
18
votes
5
answers
8k
views
Is $x^p-x+1$ always irreducible in $\mathbb F_p[x]$?
It seems that for any prime number $p$ and for any non-zero element $a$ in the finite field $\mathbb F_p$, the polynomial $x^p-x+a$ is irreducible over $\mathbb F_p$. (It is of course obvious that ...
- 17.9k
6
votes
0
answers
106
views
Irreducibility testing and factoring
It is a result of van Hoeij and Novicin (Algorithmica, 2012) that factoring polynomials of degree $d$ over the integers can be done in $O(d^6 + d^4 \log^2 A)$ time, where $A$ is the coefficient bound. ...
- 96.4k
33
votes
3
answers
6k
views
Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?
Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$,
decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective,
respectively, injective? --
And ...
- 19.6k
1
vote
2
answers
337
views
Transformation of a bivariate polynomial into a homogeneous one
For a given a bivariate polynomial $P(x,y)$ with rational coefficients:
Q1. How compute such (invertible) substitutions of its variables that would transform the polynomial into a homogeneous one? In ...
- 34.3k
5
votes
1
answer
2k
views
Irreducibility of some trinomials modulo $p$
Let $n>1$ be an integer. An old result of Selmer,
See Theorem 1, page 289 in
http://www.mscand.dk/article.php?id=1472,
(If the link does not work try googling: ...
- 1,641
9
votes
1
answer
792
views
Reconstructing a polynomial from resultants
I am trying to compute a monic polynomial $f(x)$ with integer coefficients and known degree $d$. I am given $n$ pairwise coprime polynomials $g_1(x),\ldots,g_n(x)$, also with integer coefficients, ...
1
vote
2
answers
340
views
Infinite collection of elements of a number field with very similar annihilating polynomials
Hello all, let $n$ be an integer $\geq 2$ and let $\alpha$ be an algebraic number
of degree $n$. Let $R$ be the ring of algebraic integers in ${\mathbb Q}(\alpha)$, and
let $B$ be the subset of $R$ ...
- 3,595
11
votes
4
answers
4k
views
Variants of Eisenstein irreducibility
In his article where he stated what we know as Eisenstein's irreducibility criterion (which actually was first proved by Schönemann, as was Scholz's reciprocity law and Hensel's Lemma), he ...
- 32.6k
1
vote
1
answer
1k
views
Unique factorization in polynomial rings
Everybody knows that polynomial rings over fields have unique factorization, and that if $R$ has unique factorization, then so does $R[X]$. And everybody knows who proved these results first.
Well, ...
78
votes
9
answers
26k
views
Irreducibility of polynomials in two variables
Let $k$ be a field. I am interested in sufficient criteria for $f \in k[x,y]$ to be irreducible. An example is Theorem A of this paper (Brindza and Pintér, On the irreducibility of some polynomials in ...
- 30.5k