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

3
votes
0answers
174 views

When does composing polynomials reduce the degree?

Let $\mathbb{F}$ be the field of size 2. For a function $f : \mathbb{F}^n \to \mathbb{F}$, let $d(f)$ be the smallest integer such that there exists a degree-$d(f)$, $n$-variate, multilinear ...
3
votes
0answers
224 views

Bounding the degrees in a Bézout relation for integer polynomials

Let $A$ and $B$ be two polynomials in $\mathbf Z[X]$ which generate $\mathbf Z[X]$, that is assume that there exist polynomials $U$ and $V$ in $\mathbf Z[X]$ such that $$ A \cdot U + B \cdot V=1. $$ ...
4
votes
4answers
294 views

Deceptive linear algebra problem

Does anyone recognize this problem? There are $2p$ equations and $2p$ unknowns, and it feels like a classic, but I've never encountered it before: Given $d_1, d_2, \ldots d_p$, find $a_1, a_2, \ldots ...
6
votes
0answers
241 views

Zeros of polynomials related to Jensen polynomial associated with Riemann xi function $\xi(x)$

We encountered polynomials defined by the recursive relations for the coefficients $b_k>0$ as defined below: $$p_{n}(x)=\sum_{k=0}^{n}\binom{2n}{2k}b_k x^k$$ ...
6
votes
2answers
203 views

Generalized Characteristic Polynomial with Unimodular Roots

Let us define a diagonal matrix $\mathbf{D}(z) = diag(z^{m_1}, \dots, z^{m_N})$ with $z\in\mathbb{C}$ and positive integers $m_1, \dots, m_N$. The generalized characteristic polynomial of a matrix ...
3
votes
1answer
113 views

Polynomials with Unique Critical Value

My question is extremely simple to state: I am looking for a characterization of multivariate complex polynomials $f$ such that $f(Sing(f))=\{0\}$. My motivation is that I recently read somewhere that ...
10
votes
2answers
595 views

Upper density of the set of $n$'s such that $p(n)$ is prime, where $p$ is polynomial

The starting point for this question is the following (false) statement $\forall n\in \mathbb{N} (n^2 + n + 41 \text{ is prime}).$ Given a polynomial function $p:\mathbb{N} \to ...
0
votes
0answers
14 views

Decompose a multivariate polynomial into a permutation on $F_{2^n}$ and an affine transformation

Let $S(x_1,...,x_n)=(y_1,...,y_n)$ be a secret permutation on $F_{2^n}$. $L$ is a secret $F_{2^n}\rightarrow R^{m}$ affine tranformation. $m$ can be smaller than $n$, while $n$ is ususally less than ...
12
votes
2answers
414 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 ...
10
votes
1answer
401 views

When is the image of an integral polynomial contained in the image of another?

Suppose $f$ and $g$ are polynomials with integral coefficients and $f(\mathbb Z)\subset g(\mathbb Z)$. Is there any relation between $f$ and $g$? For instance, this happens if $f=g\circ h$ for some ...
1
vote
0answers
63 views

Lipschitz-like behaviour of quartic polynomials [migrated]

I have observed the following phenomenon: Let the biquadratic $q(x)=x^4-Ax^2+B$ have four real roots and perturb it by a linear factor $p(x)=q(x)+mx$, so that $m$ not too large with respect to ...
2
votes
1answer
397 views

What is the rate of convergence? [closed]

How quickly does the series defined by $$x_0 = 0, \ x_{n+1} = \frac{x_n^2+1}{2}$$ converge to $1$?
0
votes
0answers
86 views

Determing signs of Taylor coefficients in entire functions

This is a continuation of Determining when combinatorial sums are zero Suppose $f(x)$ is an entire function approximated by polynomials with only negative real zeros. Suppose further that ...
1
vote
2answers
182 views

Growth of the size of iterated polynomials

I have been working independently on a project but now I am stuck and need to seek an expert's wisdom for a part of it. I am basically looking for theorems related to growth of the size of ...
7
votes
1answer
216 views

Another name for coin-flipping polynomials

In his paper Functions arising by coin flipping (section 4), Johan Wästlund coined the term "coin-flipping polynomial" for polynomials that arise in connection with observing a finite number of coin ...
5
votes
3answers
128 views

Do the bounded isophase lines of a complex polynomial $f$ through the zeroes of $f’$ define a spanning tree?

Let $f: \mathbb{C} \to \mathbb{C}$ be a polynomial and let $\arg(f(z))$ be the phase of $f(z) = | f(z)| \exp(\mathrm{i} \arg(f(z)))$. The zeroes of $f'(z)$ are saddle points of $\arg(f(z))$, i.e. ...
11
votes
1answer
330 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 ...
12
votes
2answers
454 views
2
votes
1answer
78 views

Dimension of a certain subspace of univariate polynomials

Let $\mathbb{F}$ be an arbitrary field. For a polynomial $f\in\mathbb{F}[x]$, we use $Z(f)$ to denote set of roots of $f$ in $\mathbb{F}$. Let $S$ and $T$ be sets of elements of $\mathbb{F}$ of size ...
9
votes
1answer
197 views

Is an explicit $c$ known to lead to a noncomputable Julia set?

Braverman & Yampolsky have shown that there exist noncomputable Julia sets, i.e., there exist $c \in \mathbb{C}$ such that the Julia set of $f(z) = c + z^2$ is not computable. "A set is ...
17
votes
1answer
478 views

Minimum value of $|p(1)|^2+|p(2)|^2 +…+ |p(n+3)|^2$ over all monic polynomials $p$

Let $n$ be a positive integer. Determine the smallest possible value of $|p(1)|^2+|p(2)|^2 +...+ |p(n+3)|^2$ over all monic polynomials $p$ of degree $n$. This question was proposed (problem ...
2
votes
0answers
76 views

Rank of a particular matrix

Denote $P_{2n}$ to be collection of homogeneous total degree $2$ real polynomials in exactly $2n$ variables such that coefficient of every monomial is either $1$ or $-1$. Split variable set into ...
0
votes
1answer
173 views

Find all possible rational pairs of a parametric sextic and all cases where it is reducible for either parameter

Find all possible rational solutions pairs $(z,a)$ of the equation $a^6 + a^4 (-18368 + 9184 z - 2912 z^2) + a^2 (61702144 - 61702144 z + 36814848 z^2 - 10694656 z^3 + 1748992 z^4) - z^2 ...
0
votes
0answers
42 views

Algebraic independence in normed spaces

A set of $n$ points in $\mathbb{R}^2$ is algebraically independent over $\mathbb{Q}$ if there is no polynomial dependency among the $2n$ coordinates. A result (Lemma 3.3) from "Globally linked pairs ...
-1
votes
2answers
320 views

What conditions imply that a function over $\mathbb{Z}$ is a polynomial? [closed]

How would one prove that a function is a polynomial? I can't seem to find anything about this on the internet. I would like to know if there are any unique properties that only polynomials can ...
-1
votes
1answer
57 views

Question on real polynomial in projective space [closed]

Hi all I was given this question and desperately in need of help as it is part of my graduate studiess I know it is true but my instructor told me to find the right way to do it and I am really ...
1
vote
0answers
60 views

About properties of polynomials with common interlacing

Say $\{a_1,a_2,..,a_n\}$ and $\{b_1,b_2,...,b_n\}$ be the real roots of two monic polynomials of degree $n$ which have a common interlacing. (say I have arranged the roots in increasing order) Can ...
0
votes
0answers
76 views

How can I keep the roots of f(x)^n+g(x)^m far away from the roots of f and g?

More specifically, suppose for example I have $h(x)=\sum_{i=1}^k (x-i)^{d_i}$. Can I get any handle on the roots of $h(x)$? Can I somehow guarantee that the roots of $h(x)$ are not arbitrarily close ...
6
votes
1answer
337 views

An S-lemma for polynomials of degree 4 in three variables

Might the following be true: Let $p,q\in\mathbb{R}[x,y,z]$ be homogeneous polynomials, with $\deg(p)\leq 4$ and $\deg(q)= 2$. Suppose $q(x,y,z)>0$ for some $x,y,z\in\mathbb{R}$. Then the ...
1
vote
1answer
73 views

Convergence of sequence of polynomials defined by boundary conditions

I'm sorry if my question sounds trivial, but analysis is not my field. Consider the interval $[a,b]\subset \mathbb{R}$. On $[a,b]$, for every $n\in\mathbb{N}$, $n\ge 3$, I define the polynomials ...
36
votes
0answers
2k views

How to prove this polynomial always has integer values at all integers?

Let $m$ be any positive integer. $$ P_m(x)=\sum_{i=0}^{m}\sum_{j=0}^{m}{x+j\choose j}{x-1\choose j}{j\choose i}{m\choose i}{i\choose m-j}\frac{3}{(2i-1)(2j+1)(2m-2i-1)}. $$ Question: $P_m(x)$ always ...
2
votes
0answers
69 views

The significance of the Parvaresh-Vardy curve

Even though this seems like a computer science question, it is purely mathematical and concerns polynomials and curves over finite fields. Consider the Parvaresh-Vardy list decoder. As I understand ...
-6
votes
1answer
230 views

Quintic Equation [closed]

Can we solve the following polynomial quintic equation by radicals x^5 + x^4 = 1 I found one real root which is algebraic solution (no approximation method ...
4
votes
1answer
124 views

Motzkin polynomials and enumeration of chord diagrams

On page 12 of the paper Enumeration of chord diagrams on many intervals and their non-orientable analogs" by Alexeev, Andersen, Penner, and Zograf is a list of polynomials which are a refinement of ...
10
votes
3answers
569 views

About the prime divisors of values of polynomials

Let $P(x)$ be a polynomial having integer coefficients (and degree $\geq 3$), and let $p_1<p_2<\dots$ be the prime divisors occurring in the set of values $\{P(n):\ n\in\mathbb{Z}\}$. Is it ...
4
votes
3answers
91 views

counting complex roots which are root of unity times a real number

Let $p(x)$ be a monic polynomial over the integers. I want to count the number of roots which have the form $\zeta \cdot r$ where $\zeta$ is a root of unity and $r$ is a real number. To count the ...
4
votes
1answer
76 views

How to realize any non-crossing matching as $\mathrm{Re}[p(z)]=0$

Asymptotically any polynomial is $p(z) = z^n + O(z^{n-1})$. Therefore $\mathrm{Re}[p(z)]= r^n \cos(2\pi i \theta)$ which vanishes at $\theta = \frac{(k+ \frac{1}{2})\pi}{n}$. Those $2n$ line ...
0
votes
0answers
56 views

An additive question on polynomials

Consider $S\cup T=\{0,1\}^n$ where $S\cap T=\emptyset$. Consider real multilinear (only monomials of form $x_ix_jx_k$) polynomials $P,Q$ such that: $$Q(S)=0\quad Q(T)\neq0\quad P(S)\neq0\quad ...
2
votes
2answers
292 views

Can one estimate the distribution of eigenvalues of a matrix by its Cauchy/Stieltje transform?

Given a real symmetric $n$ dimensional matrix $A$, with eigenvalues $\lambda_i$ I am defining its Cauchy transform as the function, $f_A(z) = \sum_i \frac{1}{z-\lambda_i}\,$ Is there any information ...
4
votes
1answer
112 views

Best polygonal approximation to a polynomial $\pm$ c

Let a planar region $R$ be defined by the vertical range bounded by a polynomial $f(x) \pm c$ with $c>0$ a constant, and with $x$ varying between the smallest and largest roots of $f(x)$. For ...
2
votes
1answer
137 views

Chebyshev Polynomials

Given $$-\frac{1}2<a<\alpha<0<\beta<b<+\frac{1}2$$ $$+\frac{1}2<c<\gamma<1<\delta<d<+\frac{3}2$$ I want to find a polynomial $f(x)\in\Bbb R[x]$ such that ...
9
votes
3answers
352 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 ...
7
votes
2answers
261 views

When is $f(x^d)$ irreducible?

Let $f(x)$ be an irreducible polynomial of degree $n$ over a finite field $\mathbb F_p$. What can we say about $f(x^d)$? When is it irreducible ?
8
votes
1answer
341 views

The space of polynomials with all real roots

The question stems from an attempt to answer a question of David Speyer. Let $R \subseteq \mathbb{R}^n$ be the space of coefficients of all polynomials of degree $n$ whose all roots are real, i.e. $R ...
7
votes
0answers
196 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. ...
35
votes
4answers
2k views

The sum of squared logarithms conjecture

I am searching for the first proof of (or counterexample to) the following conjecture. (The sum of squared logarithms conjecture) For all natural numbers $n$ and positive numbers $x_1,x_2, \ldots , ...
21
votes
0answers
432 views

Finding a path through real rooted polynomials

This is a lemma I wanted in order to solve Patrizio Neff's conjecture. It turned out to be the wrong way to think about it, but I am still curious if it is true. Let $z^n+a_{n-1} z^{n-1} + \cdots + ...
0
votes
1answer
132 views

When can two Cauchy transforms intersect?

Given two polynomials $p$ and $q$ over reals and being guaranteed that both have all roots real I want to know if there is any characterization of the solutions of the equation $\frac{p'}{p} = ...
1
vote
0answers
51 views

Multivariable polynomial interpolation via evaluations from entrywise powers of a point

I am interested in multivariate polynomial interpolation. Within computational complexity theory, I use it to create efficient reductions between counting problems. In the univariate case, there is ...
0
votes
0answers
91 views

Polynomial generated with primitive element modulo p

This question is equivalent to the question "Normal basis in cyclotomic number fields" that I asked recently. I am posing this question because maybe in this format somebody can have an answer: Let ...