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.

510 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
124
votes
0answers
6k 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)$ ...
34
votes
0answers
435 views

Is there a notion of polynomial ring in “one half variable”?

Let $C$ be the category of commutative rings. Is there a functor $F :C \to C$ such that $F(F(R)) \cong R[X]$ for every commutative ring $R$ ? (Here, we may assume those isomorphisms to be natural ...
27
votes
0answers
547 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 ...
25
votes
0answers
746 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 ...
24
votes
0answers
469 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-...
22
votes
0answers
471 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 ...
19
votes
0answers
541 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 ...
17
votes
0answers
203 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
456 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
507 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
876 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
594 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
0answers
387 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}+...
13
votes
0answers
206 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
169 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
431 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
346 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 $\...
11
votes
0answers
118 views

Irreducibility of root-height generating polynomial

The height $ht(\alpha)$ of a positive root $\alpha$ in a (finite, crystallographic) root system $\Phi$ is $\sum_{i=1}^n c_i$ where $\alpha = \sum_{i=1}^n c_i \alpha_i$ is its decomposition as a sum of ...
11
votes
0answers
398 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
156 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
552 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 ...
10
votes
0answers
334 views

Integrability property of polynomials in several variables

This might be very trivial, or not. Let $p\colon\mathbb{R}^n\to \mathbb{R}$ be a polynomial of even degree, at most $n-2$. Assume that $p(x)\leq 0$ for any $x\in\mathbb{R}^n$. Assume that there ...
10
votes
0answers
470 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
255 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
345 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
967 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
241 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
244 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
186 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
185 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
227 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
240 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 $...
9
votes
0answers
159 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
234 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 ...
9
votes
0answers
149 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
503 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
113 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
203 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 <...
8
votes
0answers
130 views

A factorization game

This is a toy version of a problem I have posted recently. Imagine playing the following game. You choose a polynomial $B$ over a finite field $\mathbb F_p$, of degree $\deg B\le p-1$ (where $p$ is a ...
8
votes
0answers
237 views

How localized can a polynomial be in the L1 norm?

Let $0<s<2$ be a parameter, $\Omega = [-1,1]$, and $\Omega_s\subset \Omega$ be a set of measure $s$. I would like to bound the following ratio from above: $$\sup_{p\in\mathcal{P}_n} \frac{\...
8
votes
0answers
135 views

An Ehrhart positivity question related to Schur polynomials

Consider the Schur polynomial $s_\lambda(x_1,\dotsc,x_k)$. It is easy to see from the hook-content formula for counting the number of semi-standard tableaux, that the function $$ n \to s_{n \lambda}(1,...
8
votes
0answers
257 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 ...
8
votes
0answers
137 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)|}...
8
votes
0answers
153 views

Nonzero subdeterminants conjecture: has anybody seen this anywhere?

I already posted this question on Mathematics StackExchange. A user there suggested that I rather post it on mathoverflow, since it is a research question. So here it is. Let $m\geq2$, $n\geq1$ be ...
8
votes
0answers
162 views

The density of minimal polynomials

Let $K$ be a number field, i.e., a finite extension of $\mathbb{Q}$. By the primitive element theorem there exists $\alpha \in K$ such that $K = \mathbb{Q}(\alpha)$. Let $$\displaystyle S_K = \{\...
8
votes
0answers
131 views

Order of zeros for sparse polynomials mod $p$

It is a fairly well known fact that sparse polynomials $f(x)$ cannot have large order zeros other than at $x=0$. If $f(x)=a_1x^{r_1}+\cdots+a_kx^{r_k}$ then at $c \neq 0$, $f$ has a zero of order at ...
8
votes
0answers
607 views

How prove this polynomial inequality from a book

Question: Let $$f(X)=(X-x_{1})(X-x_{2})\cdots (X-x_{n})$$ be an irreducible polynomial over the field of rational numbers,with integer coefficients and real zeros. Prove that $$\prod_{1\le i<j\le ...
8
votes
0answers
180 views

What is the probability of interpolating the Tutte polynomial of a planar graph from the values at the two hyperbolas?

The Tutte polynomial is a bivariate polynomial with positive integer coefficient which is a graph invariant and can be defined recursively. Evaluating it is $\#P$-complete even when restricted to (...
8
votes
0answers
341 views

When does the Lloyd polynomial have only integral roots?

For a $t$-error correcting code of length $n$ over the finite field $\mathbb{F}_q$, the Lloyd polynomial is given by $$ L_t(n,x):=\sum_{j=0}^t(-1)^j\binom{x-1}{j}\binom{n-x}{t-j}(q-1)^{t-j}. $$ A well-...
8
votes
0answers
583 views

Does anyone know this sequence of polynomials?

A referee on a paper of mine showed me the following recurrence for polynomials $P_{n,k}\in\mathbb Q[q,q^{-1}]$ for $n\geq 0$ and $0\leq k\leq n/2$. \begin{align} P_{0,0}&=1\\ \text{for $n\geq 1$}...

1
2 3 4 5
11