Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
13 views

Stability analysis with minimal spectral norm

Let $A \in \mathbb{R}^{n \times n}$ with $$ s(A) = \inf_{D \textrm{ is diagonal}} \| D^{-1} A D \|_2 > 1 $$ Does there exists $m \in \mathbb{N}^n$ and $z \in \mathbb{C}$ with $|z| > 1$ such ...
4
votes
1answer
204 views

How many roots of polynomial in $\mathbb Z[x]$ and $\mathbb Q[x]$ are integers on average?

Given $d,B>0$ the number of polynomials in $\mathbb Z[x]$ of degree $d$ and coefficient size at most $B$ have at least one integer roots should be $B^{O(d)}f(d)$ at some function $f$ (from Random ...
1
vote
0answers
60 views

Testing polynomials irreducible over the integers

Let $f\in\operatorname{int}(\mathbb Z)$, the ring of integer-valued rational polynomials. Define $\operatorname{P}^+(f)$ as the number of primes $>0$ that $f$ assumes at distinct integral arguments....
2
votes
0answers
84 views

Does linear independence imply algebraic independence for partitioned homogeneous polynomials?

Define a partitioned homogeneous polynomial of degree $d$ to be a polynomial in $$\mathbb Z[x_{11},\dots,x_{1n},\dots,x_{d1},\dots,x_{dn}]$$ with monomials from entries in (polynomials that are $d$-...
-1
votes
1answer
109 views

If $p_n(a,b)$ is a rational number (or integer) for 3 consecutive values of $n$ then every $p_n(a,b)$ is

Let $a$ and $b$ be two real numbers and $p_n(x,y)$ the polynomial: $$p_n(x,y)=\sum_{i=0}^{n-1}x^{n-1-i}y^{i},$$ where $n$ is a positive integer. In a previous post I asked if $p_n(a,b)$ was a ...
13
votes
1answer
1k 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 ...
0
votes
0answers
105 views

Does Coppersmith technique suffice to factor?

Take classic problem of finding $P,Q$ in balanced semi-prime $N=PQ$. Is there evidence that no extension of Coppersmith technique will accomplish factoring $N=PQ$ in polynomial time? Technically I am ...
1
vote
2answers
178 views

Function on two variables that restricts to a polynomial

Lets say that I have a function $F(x,y)$ that is defined on nonnegative integers (or at least those are the values I care about) and is symmetric, so that $F(x,y)=F(y,x)$. Moreover, I know that for ...
3
votes
0answers
50 views

Biggest Cartesian Product Included in a Real Plane Curve

Suppose an irreducible smooth $p \in \mathbb{R}[x_1,x_2]$ is given, and we would like to find finite sets $S_1 , S_2 \subset \mathbb{R}$ such that $p(S_1 \times S_2)=0$ and $|S_1 \times S_2|$ is as ...
3
votes
1answer
188 views

A certain generalisation of the golden ratio

Consider a real number $a \ge 1$, and let $g(a)$ be the unique positive solution $x>0$ of $x^a - x^{a-1} - 1 = 0.$ We have $g(1) = 2$, $g(2) = {1+\sqrt{5}\over2}$ (the golden ratio), and $g$ is ...
2
votes
1answer
161 views

Integer valued polynomials over several variables

For simplicity this is about polynomials in just two variables. Any $f\in\mathbb Q[X,Y]$ can be written as a linear combination of monomials $X^iY^j$ and therefore as a sum of polynomials $p_{ij}\...
0
votes
0answers
104 views

Probability of degree $0$ gcd between every pair of random homogeneous polynomials shifted by random primes?

Take $n,d,B\in\mathbb Z_{>0}$ with $d<n$ and denote $\mathcal M_{n,d}$ to be set of all total degree $d$ monomials in $n$ variables $x_1,\dots,x_n$ with degree $\leq1$ in each variable (...
1
vote
1answer
132 views

For every table of interpolating nodes, there is a positive continuous function whose interpolating polynomials are not positive infinitely often

Fix an interval $[a,b]$. Is it true that for every table of interpolating nodes $\{x_{0,n},x_{1,n}...,x_{n,n}\}_{n=1}^{\infty}$, there exists a continuous function $f:[a,b]\to (0,\infty)$ such that ...
5
votes
1answer
137 views

Deg $n$ integral polynomial $P(x)$ with $n+1$ integer solutions to $0\leq P\leq d$

Let $d\in\mathbf{N}$ be as follows: there exists a polynomial $P(x)$ with degree $n>1$ and integer coefficients, such that $P$ has $n+1$ integer solutions to \begin{equation*} 0\leq P(x) \leq d \...
2
votes
0answers
196 views

Algebraically independent vectors in tensor product

$\mathcal L$ and $\mathcal L'$ be full rank lattices in $\mathbb R^n$ with shortest vectors $v_1,\dots,v_n$ and $v_1',\dots,v_n'$ respectively where $$\|v_1\|_2\leq\dots\leq\|v_n\|_2$$ $$\|v_1'\|_2\...
1
vote
1answer
292 views

A product of polynomials

Let $f(n)=1+x^n+x^{2n}+...+x^{n^2}.$ Let $p(x)$ be $1+x+x^2+x^5+x^7+...$ where the exponents are the pentagonal numbers. Let $a(n)$ be the sequence of integers such that the coefficients of the ...
2
votes
1answer
47 views

Lie-algebra-like relation for totally symmetric 4-tensors

There are many totally symmetric real 4-tensors, $T_{ijkl}$, which satisfy the relation $$T_{ijmn}T_{mnkl} + T_{ikmn}T_{mnjl} + T_{ilmn}T_{mnjk} = c T_{ijkl}$$ with some constant $c$. By the way ...
0
votes
1answer
262 views

Reason Coppersmith fails here?

Take classic problem of finding $P,Q$ in balanced semi-prime $N=PQ$. $P$ has a binary expansion and so does $Q$. We can set the binary $0/1$ variables to be $x_1$ through $x_{\lceil\log P\rceil}$ and ...
1
vote
0answers
50 views

Method of Coppersmith optimal for multivariate?

It is shown that Coppersmith method yields optimal integer root extraction for univariate polynomials in https://arxiv.org/abs/1605.08065 and a follow up work attempts this for bivariate polynomials ...
1
vote
1answer
431 views

Conjecture that relates matrix systems with some polynomials of integer coefficients as solution sets

Assume $x$ is a variable belongs to $\mathbb R \setminus \{ 0,-1,+1 \}$ and consider for all $i, j \in \mathbb N$, $$a(i,j) = \frac{(x^{i+1} + 1)^{j-1} + (x-1)}{x}$$ then for all $n \in \mathbb N$ ...
1
vote
0answers
55 views

Relation between lifts of simple roots and lifts of idempotents (Henselian property)

Let $f:A\to B$ be a morphism of commutative rings. Given a monic $\varphi\in A[x]$ write $Z(A,\varphi)$ for the set of simple roots of $\varphi$ in $A$. Consider the following properties of $f:A\to B$....
8
votes
0answers
208 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{\...
1
vote
1answer
166 views

Intersection Solutions of four nonlinear equations

I have four nonlinear equations I want to find the points of intersection of these equations, and I used the software Mathematica, unfortunately after many hours of waiting it does not give me any ...
4
votes
1answer
364 views

Difference between Chebyshev first and second degree iterative methods

Consider linear equation $Au = f$. We want to solve it with iterative method (assuming $A$ is good). First order iterative method is: $$ u^{k+1} = u^k - \alpha_{k+1}(Au^k - f), $$ The second degree ...
3
votes
1answer
114 views

Divergence of a series related to Schinzel's hypothesis H

The Series Consider the series identity $$\Phi(s) = \sum_{n=1}^\infty \frac{\mu(n) (\log n)^k}{n^s} \sum_{r \in R(n)} \zeta(s,r/n) = \sum_{n=1}^\infty \frac{\Lambda_k'(f(n))}{n^s}$$ $$R(n) = \left\...
9
votes
1answer
186 views

Nonnegative coefficients of a product of polynomials

Let $P(x_1,\dots,x_n)\in\mathbb{R}[x_1,\dots,x_n]$. Does there exist an algorithm to decide whether there is a nonzero polynomial $Q(x_1,\dots,x_n)\in\mathbb{R}[x_1,\dots,x_n]$ such that the product $...
2
votes
1answer
249 views

Linear difference inequality

It is well known how to find a solution for the following linear difference equation $$h_{m} = h_{m-1} + a \cdot h_{m-2}$$ Finding the roots $r_1$ and $r_2$ of $r^2 - r - a$, we have that the ...
-2
votes
0answers
97 views

On the sum $\sum_{x=0}^{(p-1)/2}(\frac{x^{4n}+cx^{2n}+d}p) $ with $p$ an odd prime

Let $p$ be an odd prime, and let $n$ be a positive integer. For $c,d\in\mathbb Z$ we define $$F_p^{(n)}(c,d):=\sum_{x=0}^{(p-1)/2}\left(\frac{x^{4n}+cx^{2n}+d}p\right),$$ where $(\frac{\cdot}p)$ is ...
-1
votes
0answers
63 views

Products of different cyclotomic polynomials

Is there a classification of all products of different cyclotomic polynomials with non-negative coefficients? Clearly if the cyclotomic polynomials have only nonnegative coefficients, their products ...
23
votes
0answers
657 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 ...
4
votes
1answer
332 views

Subsets $E$ of $\mathbb{F}_{p^k}$ with vanishing polynomial subset sums

The following question arose in some discussions recently as a misunderstanding of another problem. Question: Which subsets $E\subset \mathbb{F}_{p^k}$ satisfy the property that $ \sum\limits_{x\in E}...
4
votes
1answer
524 views

On a (possible?) equivalence of Bunyakovsky conjecture

Dirichlet's Theorem on primes in arithmetical progressions is equivalent to the following statement: for all integer numbers $a,b$, where $\gcd(a,b)=1$, there exists at least one prime of the form $an+...
11
votes
1answer
170 views

Products of Cyclotomic Polynomials with Nonnegative Coefficients

I'm curious if there are any results that allow us to determine if a product of cyclotomic polynomials (not necessarily all distinct) results in a polynomial having nonnegative coefficients. Some ...
3
votes
1answer
135 views

On a special type of subring of $\mathbb C[x_0,…,x_{q-1}]$

Let $p,q$ be odd primes. Consider the polynomial ring $\mathbb C[x_0,...,x_{q-1}]$. For $m=0,1,...,p-1$, let $$\sigma_m=\sum_{0\le j_0\le p;...;0\le j_{q-1}\le p; j_1+...+j_{q-1}=p; 1.j_1+...+(q-1)...
3
votes
0answers
120 views

Solutions to $w_x=CA_x$, $w_y=CA_y$ other than $w=f(A)$ and $C=f'(A)$?

Let $R \in \{\mathbb{C}[t^2,t^3], \mathbb{Z}[\sqrt{5}]\}$, and let $A=A(x,y) \in R[x,y]$ with $\deg(A) \geq 1$ (total degree). I wish to prove or find a counterexample to the following claim: If ...
1
vote
1answer
91 views

System of polynomial equations with a known root

I have 5 polynomial equations for 5 variables and I know that the set of roots is finite. All coefficients are integers. Ultimately I'd like to find all roots but finding the Groebner basis is ...
33
votes
7answers
1k views

On the polynomial $\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}$

Let $n = 2m$ be an even integer and let $F_n(X)$ be the polynomial $$F_n(X):=\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}.$$ I observed (but cannot prove) that the polynomial $F_n$ is always divisible by $...
4
votes
1answer
114 views

complex polynomial

Let $N$ be a big integer number and consider the equation : $$ x^{N} + a_{N-1} x^{N-1} + ...+a_{1} x + o(\frac{1}{N})=0,$$ where $o(h)$ is by definition a term such that $\lim_{h \to 0} o(h)/h =0$. ...
6
votes
0answers
74 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,...
3
votes
1answer
107 views

Marsden's Identity and B-splines

Marsden's Identity states that for every $\tau$ in $\mathbb{R }$: $$(\cdot -\tau)^{k-1}=\sum_j\Psi_{j,k}(\tau)B_{j,k,t} \, ,$$ with $\Psi_{j,k}=(t_j-\tau)\times...\times(t_{j+k-1}-\tau)$. Following ...
6
votes
0answers
154 views

Maximal subalgebras in polynomial ring $\mathbb{R}[x]$ over the field $\mathbb{R}$ of real numbers

Question. What are the maximal subalgebras of polynomial ring $\mathbb{R}[x]$ over the field of real numbers?
2
votes
1answer
97 views

How do you quickly determine which coefficients are greater than zero when multiplying two univariate positive polynomials?

Suppose that I have two polynomials with a degree of $n$, $A(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_0$ and $B(x) = b_nx^n + b_{n-1}x^{n-1} + ... + b_0$ and the coefficients of these polynomials are ...
17
votes
4answers
3k views

Is there an intuitive explanation for an extremal property of Chebyshev polynomials?

Consider the following optimization problem: Problem: find a monic polynomial $p(x)$ of degree $n$ which minimizes $\max_{x \in [-1,1]} |p(x)|$. The solution is given by Chebyshev polynomials: ...
9
votes
2answers
2k views

Is there an alternative formula for solving cubic equations?

It is known that Cardano's formula for solving cubic equations is not good in the case of positive discriminants. In this case it expresses the solution through cubic roots of complex numbers. ...
23
votes
5answers
3k views

Monic polynomial with integer coefficients with roots on unit circle, not roots of unity?

There are certainly non-monic polynomials of degree 4 with all roots on the unit circle, but no roots are roots of unity; $5 - 6 x^2 + 5 x^4$ for example. Now, for a monic polynomial of degree $n$, ...
4
votes
1answer
255 views

A Conjecture about the integral related to Chebyshev polynomial

I am interested in the following integral related to the Chebyshev polynomials $$I_{n,m}:= \int_0^\pi \left(\frac {\sin nx}{\sin x}\right)^{m} dx,$$ where $n,m\in \mathbb{Z}^+.$ It is easy to see ...
2
votes
0answers
41 views

Bernstein bound on the number of roots of a rectangular multivariable polynomial systems

I would like to know what Bernstein's bound is on multivariate polynomial systems where there are more equations than unknowns. I have a "generic" zero-dimensional multivariable polynomial system with ...
19
votes
1answer
973 views

Symmetric polynomial from graphs

Let $g$ be a directed, connected multigraph, on $n$ vertices, without loops. Define $$P_g(x_1,\dots,x_n) := Sym\left[ \prod_{(i,j) \in g} (x_i-x_j) \right]$$ where $(i,j)$ is the directed edge ...
12
votes
2answers
337 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 ...
3
votes
0answers
69 views

Independence of number fields generated by roots of Littlewood polynomials

Let $\mathcal{R}_d \subset \bar{\mathbb{Q}}$ be the set of all roots of degree $d$ polynomials with $\{-1,0,1\}$ coefficients and $$ c(d) := \min_{\substack{ \alpha, \beta \in \mathcal{R}_d \\ \alpha^...