All Questions
Tagged with co.combinatorics polynomials
113 questions with no upvoted or accepted answers
26
votes
0
answers
910
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 ...
- 1,513
22
votes
0
answers
550
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 ...
- 12.7k
17
votes
0
answers
420
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.4k
16
votes
0
answers
558
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$ ...
- 6,292
16
votes
0
answers
910
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 ...
- 13.5k
13
votes
0
answers
385
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 $\...
- 85.6k
11
votes
0
answers
450
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 ...
- 305
11
votes
0
answers
676
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 ...
- 19.7k
11
votes
0
answers
361
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$ ...
- 13.5k
9
votes
1
answer
788
views
Sequence of real-rooted polynomials
I've been interested in proving a log-concavity result via proving that certain family of polynomials is real-rooted. By performing a sequence of transformations, I can reduce that problem to proving ...
- 1,889
9
votes
0
answers
359
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 $...
- 26.5k
9
votes
0
answers
209
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)$ ...
- 91
8
votes
0
answers
176
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 ...
- 291
8
votes
0
answers
407
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-...
- 12.1k
7
votes
0
answers
208
views
How biased is $(x_i x_j)_{i,j}$, $x_i\in \mathbb{F}_2$?
Let $N = \frac{n (n-1)}{2}$. Let $V$ be the $N$-dimensional vector space over $\mathbb{F}_2$ consisting of tuples $(x_{(i,j)})_{1\leq i <j \leq n}$, $x_{(i,j)}\in \mathbb{F}_2$. Let $S$ be the set ...
- 20.2k
7
votes
0
answers
344
views
Irreducibility of a palindromic polynomial
I have strong reasons to believe that the palindromic polynomial $p_n(x)$ defined by
$$p_n(x) = x^{2n}+2x^{2n-1}+3x^{2n-2}+ \cdots+ nx^{n+1}+(n+3)x^{n}+nx^{n-1}+\cdots+2x+1$$
is irreducible in $\...
7
votes
0
answers
579
views
Guises of the noncrossing partitions (NCPs)
From "Noncrossing partitions in surprising locations" by Jon McCammond:
Certain mathematical structures make a habit of reoccuring in the most diverse list of settings. Some obvious ...
- 10.5k
7
votes
0
answers
182
views
Positivity of certain polynomial coefficients
Consider the rational functions (in fact, polynomials)
$$F_n(q)=\frac1{(1-q)^{2n}}\sum_{k=0}^n(-q)^k\frac{2k+1}{n+k+1}\binom{2n}{n-k}
\prod_{j=0,\,j\neq k}^n\frac{1+q^{2j+1}}{1+q}.$$
The numbers $\...
- 43.2k
7
votes
0
answers
229
views
Has anyone seen these binary trees (Catalan-type related to the Gegenbauer polynomials and Motzkin paths)?
The OEIS entry A121448 enumerates binary trees with $n$ edges and $k$ vertices with outdegree 1.
Has anyone seen these trees?
The o.g.f. for this entry, $G(x,t)$, is essentially a discriminant ...
- 10.5k
6
votes
0
answers
184
views
3-term recurrence relation including integral or differential operator for polynomials
Sequences of polynomials with a 3-term recurrence relations are well known for orthogonal polynomials. Do recurrence relations using differential or integral operators also appear in some theories?
I ...
6
votes
0
answers
190
views
The highest degree of a polynomial on a finite group
This question is motivated by the comments and the answer to this MO-question.
First let us recall some definitions.
A function $f:X\to X$ on a group $X$ is called a polynomial if there exists $n\in\...
- 41.9k
6
votes
0
answers
207
views
Parameter independence of Stanley's "content formula". Why?
For a cell $\square$ in the Young diagram of a partition $\lambda$, let $h_{\square}$ and $c_{\square}$ denote the hook length and content of $\square$, respectively.
R. Stanley remarked following ...
- 43.2k
6
votes
0
answers
179
views
Characteristic polynomials of Cartan matrices of Lie algebras
Let $L$ be a simple Lie algebra over $\mathbb{C}$ with Cartan matrix $C_L$ (as in https://de.wikipedia.org/wiki/Cartan-Matrix )
Question 1: Is is true that the characteristic polynomial $f$ of $C_L$ ...
- 26.5k
6
votes
0
answers
115
views
Recursions which define polynomials?
Let $k$ be a positive integer and let
$$h(n,k,q)=\frac{1-(1+q^{k})q^{2k(n-1)+1}+q^{2}}{1-q^{2n-1}}h(n-1,k,q)-\frac{(1-q^{k(2n-3)})(1-q^{2k(n-1)})q^2}{(1-q^{2n-1})(1-q^{2n-3})}h(n-2,k,q)$$
with ...
- 5,622
6
votes
0
answers
257
views
Are the roots of chromatic polynomials plus a fixed constant dense in $\mathbb{C}$?
Alan Sokal proved that chromatic roots are dense in the whole complex plane. I.e., if $P(G;z)$ denotes the chromatic polynomial of a finite simple graph $G$ evaluated at $z \in \mathbb{C}$, then $$\...
- 1,327
5
votes
0
answers
183
views
On the polynomials $\sum_{k=0}^n\binom{n+k}k^m q^k$
A sequence of polynomials
$$P_0(q),\ P_1(q),\ P_2(q),\ \ldots$$
with real coefficients is called $q$-log-convex if for each $n=1,2,3,\ldots$ every coefficient of the polynomial $P_{n+1}(q)P_{n-1}(q)-...
- 15.6k
5
votes
0
answers
115
views
Progress on the result about montonicity of Kazhdan Lustzig polynomials
I am reading the paper Masato Kobayashi---Combinatorics on Bruhat Graphs and
Kazhdan-Lusztig Polynomials.
Let $P_{x,w}$ be the Kazhdan Lusztig polynomial of $W$.
There is a result about ...
- 1,875
5
votes
0
answers
205
views
Polynomials representing locally constant functions
Let $K$ be a finite field with $p$ elements.
(a) Let $f\in K\lbrack x\rbrack$ be such that (i) $\deg(f)<p$ and (ii) $f(2x) = f(x)$ for $\geq (1-\epsilon) p$ values of $x$ in $K$. What can we say ...
- 20.2k
5
votes
0
answers
220
views
Operator connected with Hermite polynomials
For $n \geq 1$, define the following operator $M_n$ on the ring of all polynomials with real coefficients.
$$M_n P(x) = nP(x)^2 - x \int_0^x (P'(t))^2 \, \mathrm{d}t$$
Monomials $x^k$ are mapped to $n ...
- 617
4
votes
0
answers
82
views
Combinatorial interpretation of a pfaffian identity?
Let $n$ be a positive even integer. We introduce three types of skew-symmetric matrices, $A_{n+2}$, $B_n$ and $C_n$ (the subscript denotes the dimension of the matrices)
in terms of the variables $z_1,...
- 451
4
votes
0
answers
263
views
Cosine Modulo $p$?
Consider the integers modulo a prime $p$. I'm looking for a nice polynomial function that acts as a sort of "cosine" on the integers modulo $p$. Specifically, I'm looking for solutions to ...
- 591
4
votes
0
answers
134
views
Irreducibility of polynomials associated to binomial coefficients
Let $n \geq 2$.
Let $M_n$ be the $(n+1) \times (n+1)$ matrix with entries $\binom{l}{k}$ for $0 \leq l,k \leq n$ and $U_n=M_n + M_n^T$ and let $f_n(x)$ denote the characteristic polynomial of $U_n$.
...
- 26.5k
4
votes
0
answers
146
views
Validating a result on evaluating Jack polynomials
I am currently working through the following paper:
Lapointe L., Lascoux A., Morse J.
Determinantal Expression and Recursion for Jack Polynomials
Electron. J. Combin. 7 (2000), Notes 1.
DOI: 10.37236/...
4
votes
0
answers
128
views
Inequality for $q$-binomials
Recall the constructions $[n]_q=\frac{1-q^n}{1-q}, [n]!_q=[1]_q[2]_q\cdots[n]_q$ with $[0]!_q:=1$ and the $q$-binomials (Gaussian polynomials)
$$\binom{n}k_q=\frac{[n]!_q}{[k]!_q[n-k]!_q}.$$
Given two ...
- 43.2k
4
votes
0
answers
186
views
A problem in the spirit of P. Borwein's polynomials
A well-known conjecture (now a theorem) of P. Borwein (see Wang and Krattenthaler - An asymptotic approach to Borwein-type sign pattern theorems) states:
For all positive integers $n$, the sign ...
- 43.2k
3
votes
1
answer
192
views
Density of Pisot polynomials
Recall that a Pisot polynomial $P=x^n+ a_{n-1}x^{n-1}\ldots a_1$ has integer coefficients, a real root $x_1>1$ and all other roots $|x_i|<1$ for $1\leq i \leq n$. One key result is that $\{(...
- 680
3
votes
0
answers
214
views
A family of polynomials related to integer partitions
For a positive integer $n$, let $p(n)$ be the number of partitions of $n$.
For $1\le k\le n$, let $p(n,k)$ denote the number of partitions of $n$ having exactly $k$ terms; in other words, $p(n,k)$ is ...
- 15.6k
3
votes
0
answers
240
views
On thickness of binary polynomials
OEIS A169945 introduces the concept of thickness of a polynomial as the magnitude of the largest coefficient in the expansion of the square of the polynomial. Considering the $2^{n+1}$ polynomials $p(...
- 791
3
votes
0
answers
151
views
Extension of work by Novelli and Thibon on noncommutative symmetric functions and Lagrange inversion
(Edit May 12, 2023: I just put up a brief summary of some of my notes on the partition polynomials described below in my WordPress mini-arXiv at "As Above, So Below". It contains multinomial ...
- 10.5k
3
votes
0
answers
116
views
A theory of refined h- and f-polynomials for the permutahedra, associahedra, noncrossing partitions, and tropical Grassmannians (references)
Looking for references (insights) on a theory encompassing a notion of refined face polynomials and their associated refined h-polynomials that are generalizations of the relation between ordinary f-...
- 10.5k
3
votes
0
answers
107
views
Non-tree models of Lagrange inversion polynomials
The specific Lagrange inversion / series reversion polynomials (LIPs) I'm addressing are illustrated in OEIS A134685 with a general linear term and in Lang's pdf for A176740 with the coefficient of ...
- 10.5k
3
votes
0
answers
203
views
Combinatorial characterizations of complex weight supports
This question is related to my last question and is originally motivated by recent advances in quantum physics.
I am looking for combinatorial characterizations of some algebraically defined families ...
- 5,409
3
votes
0
answers
188
views
Reshuffling power series (aka Melvin–Morton expansion in knot theory)
I am struggling to understand a statement which follows from some change of variables in a power series. I think that the context does not really matter here, so I will put it at the end of the ...
- 601
3
votes
0
answers
144
views
Flat polynomials with factors of big height
Let $p(x)$ be a polynomial of degree $n$ with all coefficients in $\{-1,0,1\}$ (such polynomials are sometimes called flat). I am wondering how big the coefficients of a factor of $p$ can be. Call ...
- 13.4k
3
votes
0
answers
207
views
On a variation of the Vandermonde matrix
The ubiquitous Vandermonde matrix, of entries $(x_i^{j-1})_{i,j}^{1,n}$, and its determinant
$$\prod_{i<j}^{1,n}(x_j-x_i)$$
have found many utilities in Combinatorics and Physics, among other ...
- 43.2k
3
votes
0
answers
195
views
Congruence for the polynomials $(t+1)^n$
An interesting polynomial congruence is given by
$$A_n(t^m)\equiv \left(\frac{1+t+\cdots+t^{m-1}}m\right)^{n+1}A_n(t) \qquad \mod (t-1)^{n+1}, \tag1$$
where $A_n(t)$ are the Eulerian polynomials with ...
- 43.2k
3
votes
0
answers
170
views
Stirling number bounds and polynomials and the Lambert $W$ function
Let $s(n,k)$ be the (signed) Stirling numbers of the first kind. The polynomials
$$L_n(x)=\sum_{j=1}^ns(n,n+1-j)\dfrac{x^j}{j!}$$
enter in the asymptotic expansion of the Lambert $W$ function, see for ...
- 13.1k
3
votes
0
answers
144
views
Noncrossing partitions in Hopf algebras/monoids via compositional inversion
Partition polynomials constructed from the face structures of the associahedra (OEIS A133437) and permutahedra (A133314) comprise the antipodes/compositional inverses in a Faa-di-Bruno-type Hopf ...
- 10.5k
3
votes
0
answers
264
views
Guises of the refined Eulerian numbers, generated by tangent vectors (OEIS A145271)
The Eulerian numbers (OEIS A008292, not to be confused with the Euler numbers) pop up in numerous scenarios in combinatorics and advanced analysis, one as the components of the h-vectors of the ...
- 10.5k
3
votes
0
answers
243
views
Interlacing sequences by polynomials?
Given $t=2^\ell$ where $\ell\in\mathbb N_{>0}$ and $M\in\mathbb Z$ and two sets of integers $\{a_1,\dots,a_t\}$ and $\{b_1,\dots,b_t\}$ with $0<a_1\leq \dots\leq a_t<M$ and $0<b_1\leq \...
- 13.9k