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\}$.


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.


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 ...


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 ...


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 ...


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.


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.


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 $...


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( \...


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$ ...


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


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 ...


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