Questions tagged [polynomials]
Questions in which polynomials (single or several variables) play a key role. It is typically important that this tag is combined with other tags; polynomials appear in very different contexts. Please, use at least one of the top-level tags, such as nt.number-theory, co.combinatorics, ac.commutative-algebra, in addition to it. Also, note the more specific tags for some special types of polynomials, e.g., orthogonal-polynomials, symmetric-polynomials.
2,543
questions
15
votes
0
answers
257
views
Irreducibility of q-factorial plus 1
Let $q$ be a formal variable and for every positive integer $n$ let
$$[n]_q! = 1 (1 + q)(1 + q + q^2) \dotsm (1 + q + \dotsb + q^{n-1})$$
be the $q$-factorial.
Is it true that $[n]_q! + 1$ is an ...
15
votes
0
answers
699
views
Solving polynomial systems with homotopy. Where is the bottleneck?
I have a polynomial system with $n+k$ unknowns ($n+k$ can be greater than 8), that is known to have a limited number of isolated solutions.
I want to solve this system numerically, but if I plug it ...
14
votes
3
answers
9k
views
Can you efficiently solve a system of quadratic multivariate polynomials?
Given a system of 2nd-degree polynomials, $P=\{p_1,\dots,p_m\}$ where $p_i: \mathbb{R}^n \rightarrow \mathbb{R}$, can you efficiently find a common zero of all of these polynomials? In other words, ...
14
votes
3
answers
3k
views
Truncated Exponential Series Modulo $p$: Deeper meaning for a Putnam Question.
Apparently B6 of the Putnam this year asked:
Suppose $p$ is an odd prime. Prove that for $n\in \{0,1,2...p-1\}$, at least $\frac{p+1}{2}$ of the numbers $\sum^{p-1}_{k=0} k! n^{k}$ are not divisble ...
14
votes
5
answers
971
views
How can I write down polynomial relations that define when a polynomial is a square?
It's easy to tell when a polynomial is squarefree (or not): that's just the question of the vanishing of the discriminant, which can be dealt with as the resultant of $f$ and $f'$. However, given a ...
14
votes
2
answers
1k
views
Minimal polynomial with a given maximum in the unit interval
Find the lowest degree polynomial that satisfies the following constraints:
i) $F(0)=0$
ii) $F(1)=0$
iii)The maximum of $F$ on the interval $(0,1)$ occurs at point $c$
iv) $F(x)$ is positive ...
14
votes
6
answers
3k
views
On Polynomials dividing Exponentials
EDIT, May 2015: in the second edition of the relevant book, the question was corrected, a single number had been mis-typed. The corrected question (thanks to Max) is to find all positive integer pairs ...
14
votes
3
answers
2k
views
When does $P(a−b)=0$ for $a≠b$ ensure $P(0)=0$? (Continued.)
As a natural (and expectable) extension of my earlier question:
How large must be a set $A\subset F_2^n$ to ensure that if $P$ is a cubic polynomial in $n$ variables over the field $F_2$, vanishing ...
14
votes
2
answers
2k
views
Polynomial values are powers of two
The initial question comes from Komal in 1999.
Namely it asks to show that for infinitely many $n$ there is a polynomial $f\in\mathbb{Q}[X]$ of degree $n$ such that $f(0),f(1),\dotsc,f(n+1)$ are ...
14
votes
1
answer
2k
views
Real polynomials that go to infinity in all directions: how fast do they grow?
Let $f(x_1, \cdots, x_n) \in \mathbb{R}[x_1, \cdots, x_n]$ be a polynomial. Define property $\mathbf{P}$ to be the property that there exists a compact set $K \subset \mathbb{R}^n$ and a positive ...
14
votes
4
answers
2k
views
Is a polynomial with 1 very large coefficient irreducible?
I am asking for some sort of generalization to Perron's criterion which is not dependent on the index of the "large" coefficient. (the criterion says that for a polynomial $x^n+\sum_{k=0}^{n-1} a_kx^k\...
14
votes
3
answers
2k
views
Polynomials that are sums of squares
Is any algorithm known for determining whether or not a multivariate polynomial with integer coefficients can be written as a sum of squares of such polynomials?
By way of background, if we one ...
14
votes
1
answer
961
views
Positive roots of a polynomial
Let $a_i>0$, $i=1,\dots,n$, and put $\overline{a}:=\frac{1}{n}\sum_{i=1}^n a_i$. Assuming not all $a_i$'s are equal, take
$$
p(x):=\sum_{i=1}^n a_i (a_i-\overline{a})\prod_{k=1,\dots,n\;k\neq i} (x+...
14
votes
3
answers
1k
views
Probability of coprime polynomials
Given positive integer $N$, we choose $m_1, m_2, n_1, n_2$ independently and with equal probabilities from $\{0,1,\ldots,N\}$, and let
$f_1 = x^{m_1} + (1+x)^{n_1}$ and $f_2 = x^{m_2} + (1+x)^{n_2}$ ...
14
votes
3
answers
907
views
Sets that can be mapped onto R^n by a polynomial
The question was edited several times. Most recent version, suggested by Fedja:
Does there exist an open set $U\subset \mathbb R^n$ (n>1) that contains balls ...
14
votes
2
answers
1k
views
Number of nonzero terms in polynomial expansion (lower bounds)
Let $f(x) = a_1x^{z_1} + a_2x^{z_2} + \cdots + a_kx^{z_k}$ be a polynomial with coefficients $(a_1, \ldots, a_k) \in \mathbb{F}_q^*$ and $z_i$ are distinct positive integers. If I need to compute the ...
14
votes
1
answer
1k
views
Do almost all systems of quadratic equations have solutions?
If I have a system of linear equations, $A x = c$, with $A$ an $n\times n$ complex matrix, it is relatively easy to see that the set of matrices $A$ for which there is no (complex) solution has ...
14
votes
1
answer
463
views
Polynomials for which $f''$ divides $f$
Let $n \geq 2$ and let $a < b$ be real numbers. Then it is easy to see that there is a unique up to scale polynomial $f(x)$ of degree $n$ such that
$$f(x) = \frac{(x-a)(x-b)}{n(n-1)} f''(x).$$
...
14
votes
1
answer
497
views
Is a polynomial group law on $\mathbb{R}^n$ automatically nilpotent?
I was told that a polynomial group law on (all of) $\mathbb{R}^n$ gives automatically a nilpotent (Lie, of course) group.
Is it true? Where can I find a proof?
A counterexample for open subsets of $...
14
votes
2
answers
571
views
Curious identity between the two kinds of Chebyshev polynomials
I have found, by accident, an identity that relates a sum of Chebyshev polynomials of the first kind to a Chebyshev polynomial of the second kind. It goes as follows:
Given an integer partition of $n$...
14
votes
4
answers
2k
views
Two questions about discriminants of polynomials in ℚ[x]
Suppose $f \in \mathbb{Q}[x]$ is monic, with roots $\alpha_1,\dotsc,\alpha_n$. Define the discriminant of $f$ to be the number $ \Delta = \prod_{i<j} (\alpha_i - \alpha_j)^2$. Let $D(f) = \sqrt{\...
14
votes
1
answer
427
views
Converse of the Lee-Yang circle theorem for polynomials with unitary roots
The Lee-Yang circle theorem states that if $\left( a_{ij} \right)$ is a Hermitian square $n \times n$ matrix whose entries are in the closed unit disc, then the polynomial $$ P\left(Z \right) = \sum_{...
14
votes
4
answers
2k
views
Computing minimal polynomials using LLL
I would like to use the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL algorithm) to compute the minimal polynomial of a (real) algebraic number $\alpha$ from a decimal approximation $a$...
14
votes
2
answers
532
views
regular polygon question
Let $a_1,a_2,\ldots,a_n$ be distinct points on the complex plane $\mathbb{C}$ and $L$ be a circle in $\mathbb{C}$ such that
$$f(z):=\sum_{i=1}^n|z-a_i|^{2n-2}$$
is constant on $L.$ Could somebody ...
14
votes
1
answer
765
views
Theorems proved using combinatorial nullstellensatz that have no other known proof
Alon's (or Alon and Tarsi's?) combinatorial nullstellensatz is a powerful algebraic tool with many applications in combinatorics and number theory. See this, this, this and this mathoverflow question. ...
14
votes
1
answer
500
views
Hyperbolic polynomials and group representations
Recall that a homogeneous polynomial $P\in{\mathbb R}[X_1,\ldots,X_d]$ of degree $n$ is hyperbolic in the direction of a vector $V\ne0$ if for every vector $W$, the univariate polynomial $t\mapsto P(W+...
14
votes
1
answer
2k
views
Elementary proof for Hilbert's irreducibility theorem
I have tried to find a complete proof for Hilbert's irreducibility theorem, but everything I found was way beyond my level of understanding.
I am only interested in the simple case where the ...
14
votes
2
answers
1k
views
Symmetric group action on squarefree polynomials
The following dynamical system on polynomials comes mostly from idle curiosity, but I hope it is of some interest.
Background Fix some natural number $n$. Let $P$ be the quotient of the polynomial ...
13
votes
2
answers
1k
views
Is irreducibility of polynomials $\in \mathbb{Z} [X]$ over $\mathbb{Q}$ an undecidable problem?
There are a number of criteria for determining whether a polynomial $\in \mathbb{Z} [X]$ is irreducible over $\mathbb{Q}$ (the traditional ones being Eisenstein criterion and irreducibility over a ...
13
votes
5
answers
3k
views
A geometric proof of the Gauss-Lucas theorem
Motivated by a geometric proof of the Fundamental Theorem of Algebra we ask:
Is there a geometric proof for the Gauss-Lucas theorem? Since we are working on a half plane, can one imagine a possible ...
13
votes
2
answers
2k
views
About irreducible trinomials
This question was inspired by this one. For every $n>m>0$ consider the polynomial $p_{m,n}=x^n-x^m-1$.
For which $m,n$ is $p_{m,n}$ irreducible over $\mathbb Q$?
In particular, if $m$ is odd,...
13
votes
2
answers
2k
views
Irreducible polynomial over number field with roots in every completion?
Let K/Q be a field, probably not a finite extension. Is it possible for a polynomial to be irreducible over K but have a root in every completion of K? What about all but finitely many completions?
...
13
votes
5
answers
3k
views
Application of polynomials with non-negative coefficients
Question 1: Are there any deeper applications (in any field of mathematics) of polynomials (with possibly more than one variable) over the real numbers whose coefficients are non-negative? So far I ...
13
votes
5
answers
5k
views
Number of spanning forests in a graph
Hello,
I have two questions that have been bugging me recently. The first is about the number of spanning forests in a graph and the second is about enumerating these with edge labels.
Q1: I am ...
13
votes
3
answers
1k
views
Height of cyclotomic polynomials
Recall that the cyclotomic polynomial of order $n$ is
$$\Phi_n(X)=\prod_{gcd(k,n)=1}(X-e^{2ik\pi/n}).$$
Its degree is $\phi(n)$ (Euler's indicator). Inversion of
$$X^n-1=\prod_{d|n}\Phi_d(X)$$
by the ...
13
votes
3
answers
444
views
Proportion of polynomials of a fixed degree with a certain number of real roots
For a polynomial $f(x) = \sum_{i=0}^dc_ix^i \in \mathbb Z[x]$ of degree $d$, let
$$
H(f):=\max\limits_{i=0,1,\ldots, d}\{|c_i|\}
$$
denote the naive height. Further, define
$$
R(M, r, d) := \#\{f(x)...
13
votes
3
answers
704
views
Supremum of $ a_n = a_{n-1}^3 - a_{n-2} $
Let $a_1=0$ and let $ - \ln(2) < a_2 < \ln(2) $
Define
$$ a_n = a_{n-1}^3 - a_{n-2} $$
Then
$$ \sup_{n>2} a_n = a_2 $$
And
$$ \inf_{n>2} a_n = - a_2 $$
How to prove that ?
13
votes
1
answer
776
views
Is there a ring for which the reducibility of a polynomial is undecidable?
Let $R$ be a ring such that all of its elements have a finite number of divisors, ie $\forall r\in R\, |\{x\in R: x|r\}|<\infty$.
Then we can decide whether a polynomial in $R[t]$ is reducible ...
13
votes
4
answers
1k
views
Showing that a family of polynomials has positive and real roots.
Hi everybody, for my research I am dealing with the following function:
$$\alpha_n(x):=\left.\frac{\partial^{2n+1}}{\partial z^{2n+1}}\frac{\sinh(z)}{\cosh(z)-1+x}\right|_{z=0},\quad n\in \mathbb{N},...
13
votes
1
answer
3k
views
When are complex polynomial maps almost surjective?
Consider a complex polynomial map $f: \mathbb{C}^n \rightarrow \mathbb{C}^n$.
For $n = 1$, the fundamental theorem of algebra says that, for any $y \in \mathbb{C}$ there exists $x \in \mathbb{C}$ ...
13
votes
1
answer
980
views
Is -1 a sum of 2 squares in a certain field K?
Consider the field of fractions $K$
of the quotient algebra $\mathbb{R}[x,y,z,t]/(x^2+y^2+z^2+t^2+1)$,
where $\mathbb{R}$ is the field of real numbers and $x,y,z,t$ are variables.
Clearly $-1$ is a ...
13
votes
2
answers
1k
views
Families of quintics in $\mathbb{Q}[x]$ with Galois group $A_5$
Theorem. The Galois group of a quintic polynomial $f\in\mathbb{Q}[x]$ is $A_5$ if and only if its discriminant is a rational square and its Weber sextic resolvent has no rational root.
Question. What ...
13
votes
3
answers
834
views
Effective algorithm to test positivity
Let $f(x_1,\ldots, x_n)$ be a real polynomial in several variables. Is there an effective algorithm to test whether $f$ is positive (or nonnegative) on the whole of ${\mathbb{R}}^n$?
13
votes
2
answers
495
views
Roots of lacunary polynomials over a finite field
If $P$ is a polynomial over the field $\mathbb F_q$ of degree at most $q-2$ with $k$ nonzero coefficients, then $P$ has at most $(1-1/k)(q-1)$ distinct nonzero roots.
Does this fact have any standard ...
13
votes
2
answers
537
views
$f$ real-rooted forbid truncated $\frac1f$ to be so?
Let $f(x)$ be a polynomial in the ring $\mathbb{R}[x]$, the roots are all real and $f(0)=1$. Write the Taylor series of $1/f(x)$ around the origin as
$$\frac1{f(x)}=\sum_{k=0}^{\infty}a_kx^k,$$
and ...
13
votes
3
answers
2k
views
Which polynomials are determinants of a symmetric matrix with linear entries?
Let $k$ be a field. Can each degree $n$ polynomial $P(t) \in k[t]$ be written as the determinant of the matrix $A + tB$, where $A$ and $B$ are two symmetric $(n \times n)$-matrices with entries in $k$?...
13
votes
3
answers
3k
views
Density of Irreducible Polynomials in $\mathbb{Z}[x]$
Recently I was thinking about some questions concerning $\mathbb{Z}[x]$ and realized that they might be a bit easier if I knew the relative densities of reducible polynomials.
Let $P_d$ denote the ...
13
votes
3
answers
914
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$) ...
13
votes
1
answer
1k
views
Irreducibility of Schur polynomials
A natural question covering both this and this question would be
Let $n>2$. Describe Young diagrams $\lambda$ with at most $n$ nonempty rows (or equivalently non-increasing sequences $\lambda=(\...
13
votes
3
answers
1k
views
When are Ehrhart functions of compact convex sets polynomials?
Given a lattice $L$ and a subset $P\subset \mathbb R^d$, we define for each positive integer $t$ $$f_P(L,t)=|(tP\cap L)|$$ the number of lattice points in $tP$. Let's say $P$ is nice if $f_P(L,t)$ is ...