33

You should refer to Lemma 10 (page-233) in this paper by Schinzel where he proves that for any polynomial $F(x)$ of degree $d$ we have a polynomial $G(x)$ of degree $d-1$ such that their composition is reducible.

32

Consider $Q(x)=x(2x-1)(3x-1)$. This gives an injective map $\mathbb Z\to \mathbb Z$, because $n<m \implies Q(n)<Q(m)$. However, this $Q$ is not injective over $\mathbb Z/p\mathbb Z$ for any $p$ because $Q(x)=0$ has three solutions when $p\geq 5$ and two solutions when $p\in \{2,3\}$.

answered Aug 9 '20 at 17:49

Gjergji Zaimi

79.5k44 gold badges207207 silver badges371371 bronze badges

25

Your first condition yields $$|p(c)|=|p(1)|+\int_{1}^c |p'(x)|dx:=\|p(x)\|.$$
All linear functionals on a finite-dimensional space are bounded, so if $\deg p\leqslant n$, we get $|p(0)|\leqslant C_n \|p(x)\|$ for certain $C_n$. Thus, if $b>C_n$, the second condition is not achievable.

answered Sep 18 '20 at 9:53

Fedor Petrov

80.9k77 gold badges187187 silver badges340340 bronze badges

24

The answer is yes. In fact, an even stronger claim is true: there exists some $N$ such that for all $n \geq N, \ P_{1}^{n}, \dots, P_{k}^n$ are linearly independent over $\mathbb{C}$.
For this we will use a generalization of the Mason-Stother's theorem which appears on the Wikipedia page (though I have taken the special case of the curve $C = \mathbb{P}^{1} (...

22

In general you can't write $p = f^2 + g^2$ in ${\bf Q}[x]$ at all,
let alone do so efficiently.
For example, $2 x^2 + 3$ is positive for all $x$
(and is the sum of three squares, $(x+1)^2 + (x-1)^2 + 1^2$);
but if $2 x^2 + 3 = f(x)^2 + g(x)^2$ then $3 = f(0)^2 + g(0)^2$,
which is impossible because $3$ is not a sum of two rational squares.
(Cf. the comment ...

answered Sep 28 '20 at 0:27

Noam D. Elkies

68.9k1212 gold badges245245 silver badges330330 bronze badges

21

As noted by Paata Ivanishvili, if $f$ is concave on $[0,1]$, then the Bernstein polynomials $B_n(f,p)$ are increasing in $n$.
Here is a probabilistic proof:
Let $I_j$ for $j \ge 1$ be independent variables taking value 1 with probability $p$ and $0$ with probability $1-p$. Then $X_n:=\sum_{j=1}^n I_j$ has a binomial Bin$(n,p)$ distribution and the ...

20

While the original question has been answered, there is a beautiful result of Fried in On a conjecture of Schur which is relevant to such questions. Suppose $Q$ is a polynomial in ${\Bbb Q}[x]$ such that for infinitely many primes the induced map from ${\Bbb Z}/p{\Bbb Z}$ to ${\Bbb Z}/p{\Bbb Z}$ is bijective. Then $Q$ must be of the form
(i) $Q(x) = ax^n + ...

20

$\newcommand\ZZ{\mathbb{Z}}\newcommand\QQ{\mathbb{Q}}$The statement is true.
Notation: I'm going to change the name of the polynomial to $f$, so that $p$ can be a prime. Fix a prime $p$, let $\QQ_p$ be the $p$-adic numbers, $\ZZ_p$ the $p$-adic integers and $v$ the $p$-adic valuation.
Let $\QQ_p^{alg}$ be an algebraic closure of $\QQ_p$, then $v$ extends to ...

answered Dec 21 '20 at 13:27

David E Speyer

130k1111 gold badges339339 silver badges644644 bronze badges

19

The answer for a general $n$ is positive: the discriminant is a sum of squares of polynomials in the entries of $H$. The first formula was given by Ilyushechkin and involves $n!$ squares. This number was improved by Domokos into
$$\binom{2n-1}{n-1}-\binom{2n-3}{n-1}.$$
See Exercise #113 on my page.
Details of Ilyushechkin's solution. Consider the scalar ...

answered Oct 28 '20 at 19:01

Denis Serre

44.5k88 gold badges122122 silver badges255255 bronze badges

18

I don't know how to answer the question as stated, but I believe that by strengthening the question a bit we can see that there does not exist a "reasonable" notion of "polyonomial ring in one-half variable" (unless perhaps we start thinking about enlarging our category or something). That is, let me address the following:
Modified ...

17

In fact,
$$
u_n(x) =
{2}^{n-1}\prod _{k=0}^{n-1}(2x+2k+1)
-{2\,n-1\choose n-1}\prod _{k=0}^{n-1}(x+k) ,
\tag1$$
which is a polynomial with integer coefficients.
P.S. the proof rests on a routine verification that (1) satisfies the given recurrence relation and initial conditions.

answered Dec 9 '20 at 18:41

Gerald Edgar

34.1k44 gold badges102102 silver badges189189 bronze badges

15

Suppose you have a composite $n=ab$, with $a,b>1$. Any function that satisfies $f(0)=0, f(a)=1$ can not be a polynomial otherwise we would have
$$0=b\left(f(a)-f(0)\right)=b$$
in $\mathbb Z/n\mathbb Z$, which is a contradiction. However this is not a problem for $n$ prime, where you can use Lagrange interpolation to represent any function as a polynomial.

answered Nov 22 '20 at 2:47

Gjergji Zaimi

79.5k44 gold badges207207 silver badges371371 bronze badges

15

The result is true for polynomials (or more generally, power series) of the form $p(x) = x + ax^2 + bx^3 + \cdots$ with $a,b \ldots \in \mathbb{Q}$.
Let $p(x) = x + \sum_{n \geq 2} a_n x^n \in \mathbb{Q}[[x]]$ such that $p^{(2)}$ and $p^{(3)}$ belong to $\mathbb{Z}[[x]]$. We will show by induction on $n$ that $a_n \in \mathbb{Z}$. Let $n \geq 2$ such that $...

answered Dec 19 '20 at 17:07

François Brunault

18.5k22 gold badges4343 silver badges8989 bronze badges

15

Yes, it is true. In other words, you ask whether $|X_n|=F_{2n}$ where $$X_n:=\sum_{i=1}^{n-1}\{0,3^{i-1},3^i\}.$$
We have $$X_n=X_{n-1}\cup Y_{n-1}\cup Z_{n-1},\quad (1)$$ where $Y_{n-1}=X_{n-1}+3^{n-1}$, $Z_{n-1}=X_{n-1}+3^n$. We have $(X_{n-1}\cup Y_{n-1})\cap Z_{n-1}=\emptyset$, since $\min Z_{n-1}=3^n>\max (X_{n-1}\cup Y_{n-1})=2\cdot 3^{n-1}+3^{n-2}+\...

15

Making the normalised change of variables $t = ns^2$, $x = 4ny^2$ (with $y \geq 0$ and $s$ of either sign) one can write
$$ f_n(x) = e^{2ny^2} n^n \sqrt{n} \int_{{\bf R}} e^{-n\phi(s)}\ ds$$
where the phase $\phi(s)$ is given by
$$ \phi(s) := s^2 - 2 \log s - 4iy s$$
using the standard branch of the complex logarithm. This phase has stationary points at $iy ...

15

Yes, it is true.
Let $f_0$ be an irreducible divisor of $f$. It suffices to find $g$ such that $f_0^2$ divides $f_0(g(x))$ (which, in turn, divides, $f(g(x))$).
Try to choose $g(x)=x+h(x)f_0(x)$. Then $f_0(g(x))=f_0(x+h(x)f_0(x))\equiv f_0(x)+f_0'(x)h(x)f_0(x) \pmod {f_0^2(x)}$, and we need $1+f_0'(x)h(x)$ to be divisible by $f_0$. Since $f_0'$ and $f_0$ are ...

14

We have
$$\log \sum_{k \ge 0} T_k t^k = \sum_{i=1}^n \log \frac{x_i t}{1 - e^{-x_i t}}$$
so if we write
$$\log \frac{x_i t}{1 - e^{-x_i t}} = \log \sum_{k \ge 0} B_k^{+} x_i^k \frac{t^k}{k!} = \sum_{k \ge 1} b_k x_i^k \frac{t^k}{k!}$$
(using the sign conventions explained on Wikipedia) then we straightforwardly have
$$\sum_{k \ge 0} T_k t^k = \exp \left( \...

answered Nov 22 '20 at 3:53

Qiaochu Yuan

104k3232 gold badges373373 silver badges667667 bronze badges

14

In the second paragraph of the post you ask about those integer-valued polynomials $f(x)$ for which $\frac{f(x)-f(y)}{x-y}$ is an integer for integers $x\ne y$. The basis in this $\mathbb{Z}$-module $M$ may be described as follows. For each $n=1,2,\ldots$ define the minimal positive rational $\alpha_n$ such that $\alpha_nx(x-1)\ldots(x-n+1)\in M$. I claim ...

13

Here is another argument. We have
$$ P_{n+1}(x)=(1+x+x^3)P_n(x^3). $$
Now $P_n(x^3), xP_n(x^3)$, and $x^3P_n(x^3)$ all have $a_n$ monomials. If
a monomial $x^i$ appears in more than one of them, then it must appear
in $P_n(x^3)$ and $x^3P_n(x^3)$, but not $xP_n(x^3)$ (by considering
exponents mod 3). Thus we need to subtract off the number of
monomials $x^i$ ...

answered Jan 9 at 3:29

Richard Stanley

40.7k1010 gold badges138138 silver badges229229 bronze badges

12

Here is a proof that such a polynomial does not exist assuming that every admissible $n$-tuple occurs infinitely often in the sequence of primes.
To see this let $a:=(0, a_1, \dots, a_{n-1})$ be an admissible $n$-tuple. Suppose $P \in \mathbb{Z}[x_1, \dots, x_n]$ is such that the function $f(i):=P(p_i,p_{i+1},\dots p_{i+n-1})$ is bounded. Replacing $x_i$ by $...

12

The answer is Yes in any dimension by a result of Ilyushechkin in Mat. Zametki, 51, 16-23, 1992.
See my previous MO answer
real symmetric matrix has real eigenvalues - elementary proof

answered Oct 28 '20 at 18:57

Abdelmalek Abdesselam

18.2k11 gold badge4848 silver badges9999 bronze badges

12

Commutative algebra is NOT the same as algebraic geometry, especially projective algebraic geometry.
The variety in $\mathbb{P}^9$ defined by $I$ and the variety in $\mathbb{P}^9$ defined by $I_0$ are the same variety.
If you were to work in $\mathbb{A}^{10}$, then $I$ and $I_0$ would define different affine schemes; the scheme defined by $I$ has some extra ...

11

No, it's not possible to construct such a $p$ whose degree $n$ is bounded independently of $b$ and $c$. In fact, it's not possible even if we fix the value of $c$. I'll prove this for $c=2$ below, but the same argument works in general.
Suppose to the contrary that it were possible. Then for every $b>1$ we could choose a polynomial $p_b$ such that
$p_b$ ...

11

This is a partial answer which highlights some of the subtleties of this question. I will use algebraic geometry language as this is the correct set up for such questions.
First, this question is only really interesting for affine varieties as for projective varieties, every rational point is an integral point.
I take the following set-up. Let $U$ be a ...

11

Since the ring of integers of $\mathbb{Q}[\sqrt{-163}]$ is a PID, it follows that a rational prime $p \neq 163$ may be expressed in the form $x^{2} + xy + 41y^{2}$ for rational integers $x$ and $y$ if and only if $p$ is a quadratic residue (mod $163$).(This is well-known). But, as you point out yourself, your question is comparable to asking how many primes ...

10

Edit. See the calculation modulo $2$ below.
This is not an answer, but it is too long for a comment. The matrix $A_n$ can be decomposed as $A_n=D_n^T\Phi_nD_n$ where the entries of $D_n$ (D for divisors, not for diagonal) are either $1$ if $i|j$, or $0$ otherwise, and $\Phi_n={\rm diag}(\phi(1),\ldots,\phi(n))$, $\phi$ being the Euler's totient function.
...

10

For every polynomial $f(x) \in \mathbb{Q}[x]$, let $\mathcal{R}(f) := \{ \alpha \in \mathbb{C} \mid p(\alpha) = 0 \} \subseteq \overline{\mathbb{Q}} \subseteq \mathbb{C}$ be its set of roots.
Then $\mathcal{R}(p) = p^{(2)}(\mathcal{R}(p^{(3)}))$. Suppose that $p(x) \in \mathbb{Q}[x]$ is monic and $p^{(2)}, p^{(3)} \in \mathbb{Z}[x]$. Then $\mathcal{R}(p^{(3)}...

10

While nothing will beat the brilliant probabilistic proof given in Yuval Peres's answer, a more conventional argument goes as follows. Write $$a_{n,k} = \tbinom nk x^k (1-x)^{n-k} $$ and $$ p_{n,k} = \tfrac{k}{n} $$ Observe that
$$ \tfrac{k}{n} = (1 - p_{n,k}) \tfrac{k}{n-1} + p_{n,k} \tfrac{k-1}{n-1} . $$
Thus, if $f$ is concave, then
$$ f(\tfrac{k}{n}) \...

10

We have $\mathrm{Res}(f(x),f(-x))=2^n a_n P(\alpha)^2$, where
$P(\alpha)=\prod_{1\leq i<j\leq n}(\alpha_i+\alpha_j)$. By
e.g. the case $d=2$ of Exercise 7.30 in Enumerative Combinatorics,
vol. 2, we have $P(\alpha)=s_{n-1,n-2,\dots,1}(\alpha)$, where
$s_{n-1,n-2,\dots,1}$ is a Schur function. By the dual Jacobi-Trudi
identity (Corollary 7.16.2 of the ...

answered Jan 29 at 15:10

Richard Stanley

40.7k1010 gold badges138138 silver badges229229 bronze badges

10

As I said in the comments this is very well known: $S$ is the complement of the projection of the semialgebraic set $\{(f,a)\in P_{d,n}\times\mathbb{R}^n:f(a)<0\}$, hence semialgebraic by the Tarski-Seidenberg theorem.

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

polynomials × 2023nt.number-theory × 399

ag.algebraic-geometry × 310

ac.commutative-algebra × 278

co.combinatorics × 193

reference-request × 132

cv.complex-variables × 124

real-analysis × 106

linear-algebra × 101

ra.rings-and-algebras × 97

finite-fields × 91

ca.classical-analysis-and-odes × 79

galois-theory × 77

matrices × 68

approximation-theory × 68

algebraic-number-theory × 54

real-algebraic-geometry × 51

pr.probability × 47

sequences-and-series × 45

fa.functional-analysis × 44

prime-numbers × 44

na.numerical-analysis × 43

algorithms × 41

factorization × 39

inequalities × 37