All Questions
66 questions
67
votes
6
answers
7k
views
How to recognise that the polynomial method might work
A couple of days ago I was at a nice seminar given by Christian Reiher, during which he told us about a short proof of the following special case of a theorem of Olson.
Theorem. Let $(a_1,b_1),\dots,(...
- 29k
47
votes
1
answer
4k
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,183
37
votes
2
answers
3k
views
A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself
Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...
- 1,730
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
17
votes
2
answers
1k
views
$P(x)=P(y)$ has infinitely many integer solutions
Determine all polynomials $P(x)$ with integer coefficients such that $P(x)=P(y)$ has infinitely many integer solutions in integer $x$ and $y$ with $x \neq y$.
Choose $P(x)=a_n(x-k)^{2n}+a_{n-1}(x-k)^{...
- 501
17
votes
1
answer
687
views
Multiply an integer polynomial with another integer polynomial to get a "big" coefficient
I have copied this question from StackExchange, in the hope that some experts here can provide some relevant insight. Thanks to Greg Martin for improving the question.
Given $f(x) = a_0 + a_1 x + a_2 ...
- 823
17
votes
1
answer
502
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 ...
- 2,753
17
votes
3
answers
2k
views
Recursions which define polynomials
There are many examples (Somos sequences, special polynomials related to rational solutions of the Painleve equations) when a recurrence relation, which a priori produces a sequence of rational ...
- 13.5k
16
votes
2
answers
1k
views
are these polynomials or rationals functions?
Let $x$ be a variable. Define the following family of sequences (reminiscent of Lucas polynomials) according to the rule: $P_0(x):=0, P_1(x):=1$ and for $n\geq2$ by
$$P_n(x)=xP_{n-1}(x)-P_{n-2}(x).$$
...
- 43.2k
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
14
votes
2
answers
1k
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 ...
- 165
14
votes
1
answer
803
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. ...
- 1,197
11
votes
1
answer
332
views
Counting monomials in product polynomials: Part II
Encouraged by the responses to my earlier MO question, here is a follow up and upgraded quest.
Let $e\geq2$ be an integer. Define the polynomials
$$P_{n,e}(x)=\prod_{i=1}^{n-1}\left(1+x^{e^{i-1}}+x^{e^...
- 43.2k
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
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
2
answers
538
views
Counting monomials in product polynomials: Part I
This question is motivated by recent work of R P Stanley, Theorems and conjectures on some rational generating functions. Consider the polynomials
$$P_n(x)=\prod_{i=1}^{n-1}(1+x^{3^{i-1}}+x^{3^i}).$$
...
- 43.2k
9
votes
1
answer
1k
views
"Laurent phenomenon"?
Define the recurrence
\begin{align*}
n(2n+x-3)u_n(x)
&=2(2n+x-2)(4n^2+4nx-8n-3x+3)u_{n-1}(x) \\
&-4(n+x-2)(2n-3)(2n+2x-3)(2n+x-1)u_{n-2}(x)
\end{align*}
with initial conditions $u_0(x)=0$ and $...
- 43.2k
9
votes
2
answers
546
views
Can you tie up these Laurent sequences?
Fix an integer $k\geq3$. Define the two families of sequences $\{x_n\}$ and $\{y_n\}$ according to the rules:
$$x_n=\frac{x_{n-1}^2+x_{n-2}^2+\cdots+x_{n-k+1}^2}{x_{n-k}} \qquad n\geq k$$
and
$$y_n=\...
- 43.2k
9
votes
1
answer
285
views
Multivariate quasipolynomials and where to find them
This question is inspired from thinking about David Speyer's question about complex variable Ehrhart theory.
In one variable, Ehrhart theory has been vastly generalized. For example it has been ...
- 85.6k
8
votes
2
answers
565
views
integral transform of Fibonacci polynomials is integral
The Fibonacci polynomials are defined recursively by $F_0(x)=0, F_1(x)=1$ and $F_n(x)=xF_{n-1}(x)+F_{n-2}(x)$, for $n\geq2$.
While computing certain integrals, I observe the following (numerically) ...
- 43.2k
7
votes
3
answers
735
views
Expanding in Fibonacci powers
Let $F_n$ denote the all-familiar Fibonacci numbers, with $F_0=0, F_1=1, F_2=1$, etc.
There is a plethora of properties for these numbers involving their sums, products, convolutions and so on. Here, ...
- 43.2k
7
votes
4
answers
526
views
If the series Σ pᵃ⁽ʷ⁾·xᴵʷᴵ is rational, is Σ a(w)·xᴵʷᴵ also rational (summation over words w in a regular language)?
Let $p$ be a prime number and let $a_i$ be a sequence of natural numbers such that the series $\sum_{i=1}^\infty p^{a_i} x^i$ is rational. A warm-up question:
Question 1. Does it follow that the ...
- 3,897
7
votes
1
answer
232
views
counting monomials and integrality
For $n\in\mathbb{Z}^{+}$, consider the polynomials
$$P_n(x)=\prod_{k=0}^{n-1}(x^n-x^k).$$
QUESTION. Is it possible to find a closed formula for the number of monomials in $P_n(x)$, after expansion?
...
- 43.2k
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
6
votes
1
answer
521
views
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 + C$ for some $n \geq m \in \mathbb{N}$.
Is it true that for each irreducible ...
- 11.3k
6
votes
1
answer
242
views
$(q,t)$-Fibonacci polynomials: area & bounce statistics
This is related to my earlier (unanswered) MO post. Preserve notations from there.
We take advantage of the one-to-one correspondence between the $(s,s+1)$-core partitions and $(s,s+1)$-Dyck paths. ...
- 43.2k
5
votes
1
answer
358
views
The number of polynomials on a finite group, II
This question is follow up of this MO-post.
First let us recall the necessary definitions.
A function $f:X\to X$ on a group $X$ is called a polynomial if there exists $n\in\mathbb N$ and elements $a_0,...
- 41.8k
5
votes
1
answer
211
views
degree of a polynomial over set-partitions
Denote $(x)_t = x(x-1)(x-2)\cdots(x-t+1)$ and fix some $t_1,\dots,t_n\in\mathbb{N}$. Now consider the polynomials
$$f_n(x)=\sum_{\pi\in L[n]}(-1)^{\vert\pi\vert-1}(\vert\pi\vert-1)!\prod_{A\in\pi}(x)_{...
- 43.2k
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
4
votes
1
answer
539
views
A (mild?) question on the number of monomials
Let $[n]_q=\frac{1-q^n}{1-q}$ with $[0]_q=0$. Recall the $q$-factorials $[n]_q!=[1]_q[2]_q\cdots[n]_q$ (with $[0]_q!=1$) and the $q$-binomials
$$\binom{n}k_q=\frac{[n]_q!}{[k]_q!\,[n-k]_q!}.$$
Now, ...
- 43.2k
4
votes
2
answers
623
views
Transforming numbers of irreducible polynomials
Let $M(n)(q)$, where $q$ is a prime power and $n$ a natural number,
stand for the number of irreducible monic polynomials of degree $n$ in the
polynomial ring $\mathbf{F}_{q}[X]$ over the finite ...
- 481
4
votes
1
answer
139
views
Polynomial expansions via prime-base digits
Fix a prime number $p$. If $n$ is a positive integer, then denote
$$\text{$\omega_{p,k}(n):=\#$ of $k$'s in the $p$-ary expansion of $n$}$$
and the total sum of all its $p$-ary digits by
$$\Omega_p(...
- 43.2k
4
votes
1
answer
382
views
Counting couples of square-free polynomials over finite fields
I have a curve defined by the following equations over the finite field $\mathbb{F}_q$ with $q=p^r$ with $p \geq 3$:
$$C_{h_1,h_2}:\begin{cases} y_1^2=h_1(t) & \\
y_2^2=h_2(t) &...
- 41
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
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
372
views
How many ways can $N$ be written as a sum of terms in the form $2^i3^j$?
Given a positive integer $N$, let $f(N)$ be the number of ways $N$ can be decomposed as a sum of terms of the form $2^i3^j$, where each such term appears at most once in the sum. For example, $f(10) = ...
- 1,703
3
votes
2
answers
459
views
Short sequence beats long sequence
I have encountered some comparison between two binomial sums. It was amusing how the one with "fewer" summands exceeds (in value) than the other which consists of many more terms. In fact, ...
- 43.2k
3
votes
3
answers
233
views
sequencial shift on families =flipped powers. How?
Consider the following family of functions
$$f_n(w):=\sum_{k=0}^{\infty}\frac{(-1)^{k-1}}{k!}(k+n)^{k-1}w^k.$$
QUESTION 1. Does the following hold?
$$f_n(w)=-\frac1{n(f_{-1}(w))^n}.$$
Deeper ...
- 43.2k
3
votes
1
answer
447
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 ...
- 10.5k
3
votes
1
answer
210
views
Powers of $2$ up to $2^{m-1}$ from a polynomial of degree $m-1$
Let $T(n,k)$ be a triangle of coefficients such that $T(n,k)\geqslant0$ for $n>0$, $0<k\leqslant n$, $0$ otherwise. Also
$$T(2n+1,1)=\frac{1}{2n+1}, T(2n,1)=0$$
$$T(n,k)=\frac{1}{n}(T(n-1,k-1)+(...
- 4,938
3
votes
1
answer
194
views
Checking presence of a specific term in product polynomial
I have a multivariate polynomial $P$ which is a product of $M$ low degree polynomials $p_i$
$$P(x_1, x_2, \dotsc, x_n) = \prod_{i=1}^M p_i(x_1, x_2, \dotsc, x_n)$$
where the maximum degree of each $...
- 103
3
votes
2
answers
405
views
Irreducible Polynomials from a Reccurence
This question is inspired by a recent one : Let $c$ be a variable and define a sequence by $a_0=0$ $a_1=1$ and $a_{n+1}=a_{n}c-a_{n-1}$ . So
$$\begin{align*}
a_2 &= c
\\ a_3 &={c}^{2}-1= \...
- 30.1k
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
213
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
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
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
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
2
votes
1
answer
310
views
Generating function for A300483 (related to Chebyshev polynomial of first kind)
Let $a(n)$ be A300483. Here
$$
a(n) = 2\int\limits_{t \geqslant 0}T_n\left(\frac{t+1}{2}\right)\exp(-t)\,dt.
$$
where $T_n(x)$ is $n$-th Chebyshev polynomial of first kind.
Let $b(n)$ be an integer ...
- 4,938
2
votes
1
answer
213
views
Coefficient of a term in a several variable polynomial multipled with Vandermonde determinant
Let $\Delta_n(x_1, \ldots, x_n)$ denote the Vandermonde determinant $\displaystyle \prod_{1 \leq i < j \leq n}(x_j - x_i)$. Let $c_1, \ldots, c_n$ and $K$ be nonnegative integers satisfying
$$c_1 + ...
- 167