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, ...

learn more… | top users | synonyms

0
votes
0answers
60 views

Upper bound on number of cells created by varieties of co-dimension 1

Say I have polynomials $p_1,p_2,\dots,p_m$ in $\mathbb{R}^n$ (ie. over $n$ variables), each of degree $d$. Is there an upper bound on the number of "regions" created by the surfaces $p_i = 0$? Let's ...
4
votes
1answer
114 views

Gauss--Lucas type theorem for tracts and higher derivatives of a polynomial

The Gauss--Lucas Theorem states that all zeros of a degree $n$ complex polynomial $p(z)$ are contained in the convex hull of the zeros of $p$. By iteration, this implies that the zeros of ...
5
votes
3answers
432 views

How to prove that two univariate polynomials are always algebraically dependent?

How to prove that two univariate polynomials(over any field) are always algebraically dependent? Also, how to prove the generalization of this question i.e if number of polynomials are more than ...
0
votes
0answers
37 views

Comparing least degrees of certain polynomials

Let $\Bbb K$ be an infinite or a finite field with $\mathsf{char\mbox{ }}\Bbb K\neq 2$ and let $M\subsetneq\Bbb K[x_1,\dots,x_n]$ be the set of multilinear polynomials. Fix $S\subsetneq\{0,1\}^n$ and ...
7
votes
1answer
579 views

Roots of a polynomial in a finite field related to Fermat's Last Theorem

In my class, we proved the following condition: define the polynomial $P_l(x)$ as $$P_l(x) = \sum_{r=1}^{l-1}{\frac{1}{r}x^{l-1-r}}$$ Then if for all $a \in \mathbb{Z}/l\mathbb{Z}-\{0,1\},$ ...
4
votes
0answers
89 views

Perturbing the constant term of a polynomial and implications to stability

Let $p(s)\in\mathbb{R}[s]$ be s.t. $p(0)=0$; $p(s)$ has at least one root in the right half complex plane $\{s\in\mathbb{C}\,:\,\Re\mathrm{e}(s)>0 \}$. Then for every ...
0
votes
0answers
92 views

Dimensions of two spaces

Let $R=\Bbb K[x_1,\dots,x_n]/I$ and $Z=\mathsf Z(I)$ where $\Bbb K$ is any field with $char(\Bbb K)\neq 2$. Is there a way to describe space of $f_1,f_2\in R$ that satisfies $$f_1+f_2\neq 0,\mbox{ ...
2
votes
0answers
129 views

weak form of Sendov conjecture

Suppose $p$ is a polynomial of degree $n$ and all roots $z_1,\cdots,z_n $ of $p$ are inside the unit disk. Then how to show that every disk of radius $\sqrt{2}$ and centered at $z_k$ for ...
5
votes
1answer
164 views

Starshapeness of polynomial tracts with respect to the (entire collection of) critical points contained in the tract

I recently found out (Piranian, "The Shape of Level Curves") that a polynomial tract (ie a connected component of a set of the form $G=\{z:|p(z)|<\epsilon\}$ for some $\epsilon>0$) need not be ...
1
vote
0answers
92 views

Properties and name of some polynomials

I have encountered in a problem some polynomials given by $P_k(x) = \prod_{j=0}^{k-2} (kx-j)$. I need to understand if these polynomials are known, and if they have certain special properties, as ...
9
votes
1answer
236 views

Variance of the roots of a complex polynomial

Let $P\in\mathbb{C}[X]$ be a complex polynomial of degree $n\geq 2$ with complex roots $\alpha_1, \alpha_2,\ldots, \alpha_n$. My question is about the existence of a formula for the variance of the ...
3
votes
1answer
135 views

Existence of solution for this set of polynomial equations

We are given a number $n$ and a vector $p=(p_1,p_2,\ldots,p_r)$, where $$p_1\geq p_2 \geq \ldots \geq p_r > 0 ; \ \ \ \ \sum_{i\in [r]} p_i \leq 1$$ I'm interested in proving that a solution for ...
0
votes
1answer
96 views

Proving equivalence of two sums involving Krawtchuk polynomials and binomial co-efficients

I seem to have chanced upon a new characterization for Kravchuk polynomials. [http://en.wikipedia.org/wiki/Kravchuk_polynomials]. To begin with, let us define the function $\omega(n,p)$ as [Assuming ...
2
votes
0answers
96 views

counting irreducible factors

In How hard is it to compute the number of prime factors of a given integer? a question was asked on computing number of prime factors of an integer. Suppose we have a polynomial $f(X)\in \Bbb Z[X]$ ...
2
votes
0answers
52 views

Estimating polynomial approximation error in high dimension

Question Let $x \in [-1, 1]^d \subset \mathbb{R}^d$ be a $d$-dimensional variable and assume that -- given $n$ -- I have a way of computing a polynomial $p_n(x)$ of degree $n$ that approximates a ...
2
votes
0answers
125 views

bound on degree of certain polynomials

Consider $m$ polynomials $f_i$ for $i=\{1,\dots,m\}$ in $\Bbb R[x_1,\dots,x_n]$ of degree $d_i$ such that $$Z(f_i)\bigcap Z((p))\neq \emptyset$$ for the sphere $p$ passing through $\{0,1\}^n$. What is ...
5
votes
1answer
374 views

degree of polynomials in nullstellensatz

$(A)$ If $K$ is algebraically closed field, then consider $m$ polynomials $f_i$ for $i=\{1,\dots,m\}$ in $K[x_1,\dots,x_n]$ of degree $d_i$ each with no common root. We know there exists $g_i$ for ...
3
votes
1answer
353 views

Sum of two squares and implication of Bunyakovsky conjecture

Bunyakovsky's conjecture states that a polynomial with integer coefficients takes infinitely many prime values at integers, unless this is impossible for trivial reasons. Let $a_1(x), a_2(x), a_3(x), ...
1
vote
1answer
150 views

Reducible polynomials

Say one only seeks to identify whether a given polynomial over $\mathbb{Z}[x]$ is reducible, then what are the best ways known to solve this? $(1)$ If reducible, the algorithm should correctly say ...
1
vote
0answers
95 views

On reducible polynomials

Let $f(x),g(x)\in\Bbb Z[x]$ with $deg(f)>deg(g)$. Given an integer $B$, is there any algorithm that runs in $\log^c |B|$ for some fixed $c\in \Bbb R$ to find a $h(x)\in\Bbb Z[x]$ (if one exists) ...
1
vote
0answers
75 views

Does this condition imply a polynomial is a product of linear factors

Let $\Lambda$ be a lattice (i.e. $\Lambda \simeq \mathbb{Z}^n$) with a positive subcone $\Lambda^+$. Let $H: \Lambda^+ \rightarrow \mathbb{C}$ be a function such that $\forall\mu \in \Lambda^+$, ...
5
votes
1answer
443 views

Disjoint images of polynomials

Are there any $f,g \in \mathbb{Q}[x]$ such that for every root of unity $\zeta$, and every $a,b \in \mathbb{Q}(\zeta)$, $f(a) \neq g(b)?$
1
vote
0answers
46 views

Name for generalization of bivariate weighted-homogeneous polynomials

A polynomial $f = \sum_j c_j X^{\alpha_j}Y^{\beta_j}\in\mathbb K[X,Y]$ is said weighted-homogeneous if there exist $p$, $q$ and $d$ (where $p$ and $q$ are not both $0$) such that ...
7
votes
1answer
189 views

Orthogonal polynomial under linear transformation

Let $M_n(x) = x^n$ be the standard monomials. The binomial formula allows one to expand $M_n(ax+b)$ as a linear combination of $M_k(x)$, for $k \leq n$, giving $$ M_n(ax+b) = (ax+b)^n = \sum_{k=0}^n ...
0
votes
1answer
84 views

Integer-valuedness of a polynomial determined by output of first n integers? [closed]

An integer-valued polynomial is a polynomial $p(x)$ such that $\forall x \in \mathbb{Z}, p(x) \in \mathbb{Z}$. Theorem: For any $n$-degree polynomial $p$, if $p(x) \in \mathbb{Z}$ for all $x \in \{0, ...
1
vote
0answers
38 views

Distributing partially known data between n parties

Assume that $n = 2r+1$. There are $n$ elements $a_1,a_2,\ldots,a_n$ from a finite field $\mathcal{F}$, and $n$ parties. Each party knows the values of at least $r+1$ elements out of those $n$ ...
14
votes
2answers
926 views

Images of polynomials

Let $f,g \in \mathbb{Q}[x]$ be polynomials such that $\{f(a) : a \in \mathbb{Q}\} \subseteq \{g(a) : a \in \mathbb{Q} \}$. Must there be some $h \in \mathbb{Q}[x]$ such that $f(x) = g(h(x))$ for all ...
4
votes
2answers
238 views

Constructive Proof to Show that Algebraic Numbers are Algebraically Closed

EDIT2: After reading some papers, I think the question can best be rephrased as "How can the minimal polynomial for a polynomial with algebraic coefficients be calculated. I have seen papers and ...
8
votes
2answers
162 views

Polynomial-time algorithm for determining whether a polynomial is positive on $\mathbb{N}$

Does there exist a polynomial-time algorithm to determine whether a given polynomial $p(n)$ with integer coefficients is positive on $\mathbb{N}$, in the sense that $p(n) \geq 0$ for all ...
1
vote
0answers
68 views

vector space of ternary forms with real rooted property

Let $V \subseteq \mathbb{R}[x,y]_d$ be a two dimensional linear subspace of the vector space of bivariate forms of degree $d$. For each degree $d$ we can find such subspaces with the property that ...
12
votes
1answer
213 views

$\pm1$-polynomials with a maximal non-real root

For given $n$, consider a polynomial $\sum_{k=0}^na_kz^k$ with all coefficients $a_k\in\{\pm1\}$. I am interested in the following: How big can the modulus of a non-real root of such a ...
2
votes
3answers
143 views

Determining Roots of a Polynomial with Interval Estimates of Coefficients

Let $f$ be a monic univariate polynomial with real coefficients: $$f_A(x) = x^n + a_{n-1}x^{n-1} + ... + a_{0}$$ The values of $A=(a_{n-1},...,a_0)$ are unknown, but are estimated as ...
4
votes
0answers
120 views

minimal polynomial for a graph

I wonder if there is any result relating the degree $d$ of the minimal polynomial of a directed finite graph to any of its topological features - such as its diameter, or any other similar 'natural' ...
7
votes
1answer
173 views

Can Schwartz-Zippel be formulated for commutative rings instead of fields?

The polynomials which occur in the Schwartz-Zippel lemma could be defined for any commutative ring, yet the lemma is restricted to fields. This makes it inapplicable for ...
1
vote
0answers
37 views

Request for reference about bound on zeroes of the Laguerre polynomials

Consider the sequence of polynomials given as, $p^{a}_k (x) = (1 - a \frac{d}{dx})^k x^n $ for some parameter $a>0$ and $k$ being a positive integer. For any positive integer $d$ it seems to be ...
0
votes
0answers
106 views

Lower bound on number of smooth values of polynomial at primes

Given a polynomial $f$, it is known believed that the number of smooth values of $f$ has a positive proportion (for fixed $u$, $\lim_{X\rightarrow\infty} \frac{|\{ n < X\ :\ f(n)\ is\ X^u\ smooth ...
2
votes
2answers
114 views

About the roots of the matching polynomial

Can someone kindly give me an expository reference on matching polynomial and its roots? (there is a proof that they are always real?) I saw these two related discussions, Roots of matching ...
5
votes
1answer
547 views

Is the set of certain polynomials finite or infinite?

Let us consider the set of all polynomials with the following properties: i) all coefficients are integer; ii) the leading coefficient equals one; iii) all zeros are real and simple and belonging ...
9
votes
3answers
411 views

How many isolated roots can a polynomial in $z$ and $\overline{z}$ have?

This is probably well-known by I can't find it now online. My guess is that if the degree is $n$ then it's $2n$ but it's just a hunch. EDIT: This is an edited version. Before I asked about roots ...
2
votes
0answers
76 views

Behavior of elementary symmetric polynomials near zero sets

It is straightforward to show (see Characterizing intersection of zero sets of elementary symmetric polynomials on R^n) that the set of points $\Lambda_{k}$ in $x \in \mathbb{R}^{n}$ with ...
3
votes
1answer
46 views

Polynomial (non-)embedding of a simplex in euclidean space

Let $\Delta$ be a standard $k$-simplex, and let $f:\Delta\to\mathbb R^N$ be a polynomial map with known numerical coefficients. What sort of practical computational algorithms can be used to ...
2
votes
0answers
140 views

What are the minimal degrees of the real and imaginary part of an algebraic complex number? [closed]

Let $z=a+bi\in\mathbb C$ with $b\ne0$ be an algebraic complex number of minimal degree $n$. It is obvious that $a=\dfrac {z+\bar{z}}2$ and $b=\dfrac {z-\bar{z}}{2i}$ are also algebraic. For $n=3$, it ...
3
votes
1answer
117 views

Uniqueness of the maximum derivative of a rational function

This may seem like an elementary question, but bear with me; you'll find that it is actually quite hard. Consider the function $$f(x)=\frac{a_nx^n}{\sum_{i=0}^n a_ix^i}$$ with all $a_i\geq 0$ and ...
3
votes
1answer
140 views

Real points of zero-dimensional real algebraic varieties

There have been a number of discussions of zeros of random polynomials here (the most recent being: Why do roots of polynomials tend to have absolute value close to 1?). Here is a closely related ...
1
vote
1answer
78 views

Integrals involving trigonometric functions and polynomes

Let $P(x)$ be a real polynome. Specify all such $P(x)$ that one of the next integrals converge: $$ \int_0^{\infty} sin(P(x))dx, \int_0^{\infty} cos(P(x))dx ? $$ Among special cases are such ...
3
votes
1answer
174 views

A number array related to colored necklaces and the primes

I stumbled upon entry OEIS-A208535 on the enumeration of certain kinds of colored necklaces and noticed that the integers for the odd prime rows of the table there seem to be given by the Moreau ...
1
vote
1answer
332 views

A question on polynomials

Let $D=\{0,1\}$. Are there infinite values of $n\in \Bbb N$ for which there is a polynomial $p(x_1,x_2,\dots,x_n)\in \Bbb R[x_1,x_2,\dots,x_n]$ and a rational function $r(x_1,x_2,\dots,x_n)\in \Bbb ...
0
votes
1answer
180 views

Discriminant of a polynomial in two variables

I want to compute the discriminant of the following polynomial $$ F(X,Y)=X^mY^n+\sum_{i=0}^{m-1}\sum_{j=0}^{n-1}c_{ij}X^iY^j. $$ Here the discriminate means the equation $D(c_{i,j})$ in the variables ...
2
votes
1answer
150 views

Rational functions and polynomials evaluated on a set of points

Let $S$ be a collection of points on the real line. Let $\{x_i\}_{i=1}^n$ take values in $S$. Consider a polynomial $p(x_1,x_2,\dots,x_n)$ over $\mathbb R[x_1,x_2,\dots,x_n]$ of degree $d$ which ...
6
votes
1answer
122 views

For a Sum-of-Squares cost functions J(x) is it true that J(x)-j* is also SOS?

For polynomial optimization problems the sum-of-squares theory and Lasserre relaxation hierarchy provides a theoretically handy way of getting the solution. There are also results saying that finite ...