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.

634 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
164
votes
0answers
9k views

Why polynomials with coefficients $0,1$ like to have only factors with $0,1$ coefficients?

Conjecture. Let $P(x),Q(x) \in \mathbb{R}[x]$ be two monic polynomials with non-negative coefficients. If $R(x)=P(x)Q(x)$ is $0,1$ polynomial (coefficients only from $\{0,1\}$), then $P(x)$ and $Q(x)$ ...
32
votes
0answers
926 views

Cubic function $\mathbb{Z}^2 \to \mathbb{Z}$ cannot be injective

It is easy to show, with an explicit construction, that a homogeneous cubic function $f: \mathbb{Z}^2 \to \mathbb{Z}$ is not injective. I am seeking a proof of the same result without the condition ...
28
votes
0answers
581 views

Mathieu group $M_{23}$ as an algebraic group via additive polynomials

An elegant description of the Mathieu group $M_{23}$ is the following: Let $C$ be the multiplicative subgroup of order $23$ in the field $F=\mathbb F_{2^{11}}$ with $2^{11}$ elements. Then $M_{23}$ is ...
27
votes
0answers
639 views

Three real polynomials

Theorem. Let $f,g$ be two real polynomials, and suppose that their Wronskian $W(f,g)=f'g-fg'$ has only real roots. Then on any interval $I\subset\mathbf{R}$ containing no roots of $W$ every non-...
25
votes
0answers
791 views

Which sets of roots of unity give a polynomial with nonnegative coefficients?

The question in brief:   When does a subset $S$ of the complex $n$th roots of unity have the property that $$\prod_{\alpha\, \in \,S} (z-\alpha)$$ gives a polynomial in $\mathbb R[z]$ with ...
22
votes
0answers
505 views

Zero curves of Tutte Polynomials?

There is an extensive theory of the real and complex roots of the chromatic polynomial of a graph, a substantial fraction of this being due to the connections between the chromatic polynomial and a ...
20
votes
0answers
598 views

Are Erdős polynomials irreducible?

Define the Erdős polynomial to be $f_n(x):= \sum \limits_{0 \leq i,j \leq n}^{}{x^{ij}}$ (the name is motivated by http://oeis.org/A027424). For example for $n=5$, the polynomial is given by $x^{25}+...
20
votes
0answers
637 views

Polynomials with roots in convex position

Let $\mathcal P_n$ denote the set of all monic polynomials of degree $n$ with real or complex coefficients such that $P\in\mathcal P_n$ if for all $k\in\lbrace 0,1,\dots,n-2\rbrace$ the $n-k$ roots of ...
19
votes
0answers
463 views

univariate integer version of Hilbert's 17th problem

Let $f(x)$ be a polynomial of degree $d$ with integer coefficients such that $f(x)\geqslant 0$ for all real $x$. Is it necessarily true that there exists an integer $N(d)$ such that $N(d)\cdot f$ is a ...
17
votes
0answers
284 views
+500

Existence of a polynomial $Q$ of degree $\geq (p-1)/4$ in $\mathbb F_p[x]$ such that $QQ'$ factorizes into distinct linear factors

For all primes up to $p=89$ there exists a product $Q=\prod_{j=1}^d(x-a_j)$ involving $d\geq (p-1)/4$ distinct linear factors $x-a_j$ in $\mathbb F_p[x]$ such that $Q'$ has all its roots in $\mathbb ...
17
votes
0answers
211 views

GPS calculations under $L^p$ norms

GPS calculations require finding a sphere externally tangent to four given spheres, an Apollonian problem in $\mathbb{R}^3$. The center of that fifth sphere is one of the $16$ possible solutions to ...
16
votes
0answers
469 views

Aligned roots of irreducible polynomials

It is well known from this famous question that the roots of a random polynomial tend to be close to the unit circle. So I was wondering in a somewhat converse sense: for an irreducible polynomial, is ...
16
votes
0answers
398 views

Do the coefficients of these irreducible polynomials always become periodic?

Fix $n\in\mathbb N$ and a starting polynomial (or seed) $p_n=a_0+a_1x+\dots+a_nx^n$ with $a_k\in\mathbb Z\ \forall k$ and $a_0a_n\ne0$. Define $p_{n+1},p_{n+2},\dots$ recursively by $p_r = p_{r-1}+...
16
votes
0answers
525 views

Catalan objects associated to a univariate polynomial

Given a monic degree $n$ polynomial $f(z)$ with no double roots, and a phase $0\leq \theta < \pi$, there are natural constructions which associate to this data: a noncrossing matching on $2n$ ...
16
votes
0answers
892 views

Polynomials with presumably positive coefficients

After seeing that some positivity problems get their solutions on MO, I am quite enthusiastic of posing my (and not only) problem of positive flavour. In order to state it, I have to introduce the ...
15
votes
0answers
355 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 $...
15
votes
0answers
224 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
0answers
617 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 ...
13
votes
0answers
229 views

Galois groups of special polynomials

This question is motivated by long experiments with GAP. Call a monic polynomial with integer coefficients special in case it is irreducible and has only coefficients $-1$, $0$ or $1$. Let $n \geq 5$....
13
votes
0answers
196 views

Galois group of polynomials related to Fibonacci and Catalan numbers

Let $F_n$ be the Fibonacci and $C_n$ the Catalan numbers. Define a polynomial by $F_n(x):=\sum\limits_{k=1}^{n}{F_k x^{n-k}}$. For example $F_8(x)=x^7+x^6+2x^5+3x^4+5x^3+8x^2+13x+21$. And another ...
13
votes
0answers
442 views

Descartes rule of signs for a noncommutative polynomial in matrix variables

Recently, while studying certain notions of "averaging" a set of input matrices, I obtained a nonlinear polynomial in matrix variables. A simple example is \begin{equation*} \mathcal{G}(X) := X^n - \...
13
votes
0answers
359 views

Are the zeros of Tutte polynomials dense in $\mathbb C^2$?

For the chromatic polynomials of graphs we have two nice theorems which describe the behavior of their zeros: Thomassen proved that the set of real zeros of all chromatic polynomials is the union of $\...
12
votes
0answers
158 views

Are there efficient algorithms to factorise in $\mathbb{N}[X]$?

One way to do factorisation in $\mathbb{N}[X]$ is to use an algorithm to factorise in $\mathbb{Z}[X]$ and then to combine some factor to find a factorisation in $\mathbb{N}[X]$. Note that the ...
11
votes
0answers
307 views

Is there yet an example of a non-negative convex polynomial that cannot be written as a sum-of-squares?

I have read that it remains an open question, whether an example can be constructed of a non-negative convex polynomial that cannot be written as a sum-of-squares. My reading includes the following ...
11
votes
0answers
415 views

A congruence involving roots of unity

Let $f(x) \in \mathbb{Z}[x]$ and suppose $f(\omega^j) \in \mathbb{Z}$ for all $j= 1, \dots, n$ where $\omega = e^{2 \pi i/n}$ is a primitive $n^{\text{th}}$ root of unity. Computational evidence ...
11
votes
0answers
590 views

Evaluating products of cyclotomic polynomials at roots of unity

Are there general non-trivial conditions on $p(\cdot)$ and $n$, where $p(\cdot)$ is a product of cyclotomic polynomials and $n$ is a positive integer, such that all the coefficients of $p(\cdot)$ are ...
11
votes
0answers
351 views

Positivity of polynomial sequences via generating series

In this question I address the problem of proving the nonnegativity of a numerical sequence $a_0,a_1,a_2,\dots$ via generating series technique. In the notation $A(x)=\sum_{n=0}^\infty a_nx^n\ge0$ ...
10
votes
0answers
268 views

Are polynomials with non-($S_n$ or $A_n$) Galois groups discrete?

There are various results, beginning with van der Waerden, on the asymptotic number of integral polynomials with bounded coefficients, whose Galois group is $S_n$. Some of these results also include $...
10
votes
0answers
241 views

Expressing every algebraic number using roots of trinomials?

This question is a continuation of Is every polynomial a factor of a trinomial? We say that $T(X) \in \mathbb{Q}[X]$ is a trinomial if there exist $A,B,C \in \mathbb{Q}$ such that $T(X) = AX^n + BX^m ...
10
votes
0answers
499 views

Reciprocal polynomials with roots off the unit circle

A polynomial is called reciprocal if its coefficients read forwards are the same as those read backward - there is an obvious translation of reciprocal polynomials into cosine polynomials (since a ...
10
votes
0answers
261 views

Symmetric Polynomials generating squares

For some n>4, can one find two symmetric polynomials $S_1$ and $S_2$ in $\mathbb{Q}[x_1,...,x_n]$ such that $S_1+x_1S_2$ is a square in $\mathbb{Q}[x_1,...,x_n]$? I have such a construction for the ...
10
votes
0answers
992 views

Dissecting trapezoids into triangles of equal area

[Lightly edited for copy and proper formatting of mathematics. -- Pete L. Clark] The Background: Let $T$ be a trapezoid. Sherman Stein, using valuation theory, showed that if $T$ is dissectible into ...
9
votes
0answers
181 views

A generalization of the Casas-Alvero conjecture

The Casas-Alvero conjecture claims that over a characteristic 0 field, any degree $d$ polynomial $f(x)$ such that, for all $0 \leq i \leq d-1$, $$\gcd(f,f^{(i)}) \neq 1$$ must have exactly one root in ...
9
votes
1answer
777 views

What are ways to compute polynomials that converge from above and below to a continuous and bounded function in $[0,1]$?

We're given a coin that shows heads with an unknown probability, $\lambda$. The goal is to use that coin (and possibly also a fair coin) to build a "new" coin that shows heads with a ...
9
votes
0answers
262 views

Polynomials vanishing almost everywhere

Suppose that $f$ is a function from the prime-order field $\mathbb F_p$ to the field itself. Considering the evaluation map $P\mapsto P(x,f(x))$ and comparing the dimensions, it is easy to show that ...
9
votes
0answers
247 views

Is $[JK:(x)][JK:(y,z)]\subseteq JK$ in $k[x,y,z]$?

Let $k$ be a field and $S=k[x,y,z]$. Let $m=(x,y,z)$ and $J,K\subseteq m$ be proper homogeneous ideals in $S$. Is this true that we always have: $$[JK:(x)][JK:(y,z)]\subseteq JK \ ?$$ Some ...
9
votes
0answers
200 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(...
9
votes
0answers
283 views

Is this a possible strengthening of the Lehmer conjecture?

Here is another possible refinement of the Lehmer conjecture. For $\alpha \in \overline{\mathbb{Q}}^{\times}$, let $C_{\alpha} \subseteq \mathbb{Q}(\alpha)$ be the maximal cyclotomic field contained ...
9
votes
0answers
242 views

Which polynomials in the minors of a matrix are invariant under conjugation?

$\newcommand{\Cof}{\operatorname{cof}}$ This is a cross-post. Let $1<k<n$ be a fixed integer. I am trying to understand "what can be said" about the $k$-degree minors of a linear map $T:V \to ...
9
votes
0answers
233 views

Reference request: integral formula for $\sum_{\text{roots }\lambda}e^{-|\lambda|^2}$

Consider a polynomial $f(z)=c\prod_m(z-\lambda_m)\in\mathbb{C}[z]$. I am mostly interested in the case where this actually lies in $\mathbb{R}[z]$, but that is not essential. I wanted to find a nice ...
9
votes
0answers
174 views

Generating functions of real-rooted polynomials

Suppose $f_n(t)$ is a degree $n$ polynomial. Let $F(t,u) = \sum_n f_n(t)u^n$. What conditions on $F(t,u)$ tell us that the $f_n(t)$ are real-rooted? Similarly, are there any conditions on $F(t,u)$ ...
9
votes
0answers
163 views

Is there a ``Ladner's Theorem" for the PH-vs-PSPACE scenario?

Like a statement of the kind, ``If the Polynomial Hierarchy (PH) $\neq$ PSPACE then there exists $L \in PSPACE \backslash PH$ which is not PSPACE-complete"? Or is there something else that states ...
9
votes
0answers
505 views

Getting a bound via polynomial equations

When studying the existence problem of power residue deference sets, I came across the following system of polynomial equations over $\mathbb{C}$, \begin{cases} &\sum\limits_{j=0}^{m-1}x_jx_{2k-j}=...
8
votes
0answers
172 views

Unit polynomial vector fields on the sphere

Let $\mathbb{S}^3 \subset \mathbb{R}^4$ be the unit $3$-sphere. Is there a classification available for $3$-homogeneous polynomial, unit norm, vector fields on $\mathbb{S}^3$? More explicitly, a $3$-...
8
votes
0answers
463 views

Iterating Diophantine equations over Q to quickly get a large interval with just integer solutions

Hilbert's Tenth Problem was whether there is an algorithm which will answer whether any Diophantine equation has solutions (where we want integer solutions). Hilbert's Tenth has a negative solution by ...
8
votes
0answers
588 views

Van der Pol's identity for the sum of divisors and a quartic polynomial equation for odd perfect numbers

In Touchard (1953) it is mentioned that the sum of divisors $\sigma(n)$ satisfies the following recurrence relation ($n>1$): $$n^2(n-1) = \frac{6}{\sigma(n)} \sum_{k=1}^{n-1}(3n^2-10k^2)\sigma(k)\...
8
votes
0answers
305 views

Factorisation of a polynomial from the Boolean algebra

Let $B_n$ denote the Boolean algebra of a set with $n \geq 2$ elements and $C_n$ the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else, where $i,j\in B_n$. Let $M_n:=C_n+C_n^T$ and $...
8
votes
0answers
504 views

Again, polynomial bijection $f:{\mathbb Q}\times{\mathbb Q}\times{\mathbb Q}\to {\mathbb Q}$

Assume that there is no polynomial $f(x,y)\in{\mathbb Q}[x,y]{}$ such that $f\colon {\mathbb Q}\times{\mathbb Q}\to {\mathbb Q}$ is a bjiection. Does this imply that there is no polynomial $f(x,y,z)\...
8
votes
0answers
116 views

Approximating zero sets of real polynomials with "less complicated" polynomials

Let $K \subset \mathbb{R}^n$ be a compact subset, and let $P(x_1,\dots,x_n)$ be a real multivariable polynomial of degree $d$, whose vanishing set we denote by $Z_P$. Is it plausible to approximate $...
8
votes
0answers
271 views

Computing coefficients of polynomials from roots in $O(n\log{n})$ time

Suppose I have a univariate polynomial $p$ over a prime-order finite field $\mathbb{F}_q$ whose roots I know. Suppose that the roots of $p$ are always an $n$-sized subset of $R=\{1,2,\dots,N\}, N <...

1
2 3 4 5
13