Master Polynomial Concepts with Comprehensive Resources

Prove that $m-<!--\; -\; -->n$ divides p
Let $a_1,a_2,a_3$ be a non constant arithmetic Progression of integers with common difference p and $b_1,b_2,b_3$ be a geometric Progression with common ratio r. Consider 3 polynomials $P_1(x)=x^2+a_{1}x+b_1,P_2(x)=x^2+a_{2}x+b_2,P_3(x)=x^2+a_{3}x+b_3$. Suppose there exist integers m and n such that $gcd(m,n)=1$ and $P_1(m)=P_2(n),P_2(m)=P_3(n)$ and $P_3(m)=P_1(n)$. Prove that $m-<!--\; -\; -->n$ divides p.
I made the 3 equations but am unable to get the result from them. How should I manipulate them.

Is it possible for an irreducible polynomial with rational coefficients to have three zeros in an arithmetic progression?
Assume that $p(x)\in <!--\; \in \; -->\mathbb{Q}[x]$ is irreducible of degree $n\ge <!--\; \ge \; -->3$.
Is it possible that p(x) has three distinct zeros ${\mathrm{\alpha <!--\; \alpha \; -->}}_1,{\mathrm{\alpha <!--\; \alpha \; -->}}_2,{\mathrm{\alpha <!--\; \alpha \; -->}}_3$ such that ${\mathrm{\alpha <!--\; \alpha \; -->}}_1-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_2={\mathrm{\alpha <!--\; \alpha \; -->}}_2-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_3$?
As also observed by Dietrich Burde a cubic won't work here, so we need $\mathrm{deg}<!--\; \; -->p(x)\ge <!--\; \ge \; -->4$. The argument goes as follows. If $p(x)=x^3+c_2{x}^2+c_{1}x+c_0$, then $-<!--\; -\; -->c_2={\mathrm{\alpha <!--\; \alpha \; -->}}_1+{\mathrm{\alpha <!--\; \alpha \; -->}}_2+{\mathrm{\alpha <!--\; \alpha \; -->}}_3=3{\mathrm{\alpha <!--\; \alpha \; -->}}_2$ implying that ${\mathrm{\alpha <!--\; \alpha \; -->}}_2$ would be rational and contradicting the irreducibility of p(x).
This came up when I was pondering this question. There the focus was in minimizing the extension degree $[\mathbb{Q}({\mathrm{\alpha <!--\; \alpha \; -->}}_1-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_2):\mathbb{Q}]$. I had the idea that I want to find a case, where ${\mathrm{\alpha <!--\; \alpha \; -->}}_1-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_2$ is fixed by a large number of elements of the Galois group $G=\mathrm{Gal}<!--\; \; -->(L/\mathbb{Q})$, $L\subseteq <!--\; \subseteq \; -->\mathbb{C}$ the splitting field of p(x). One way of enabling that would be to have a lot of repetitions among the differences ${\mathrm{\alpha <!--\; \alpha \; -->}}_i-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_j$ of the roots ${\mathrm{\alpha <!--\; \alpha \; -->}}_1,\dots <!--\; \dots \; -->,{\mathrm{\alpha <!--\; \alpha \; -->}}_n\in <!--\; \in \; -->\mathbb{C}$ of p(x). For the purposes of that question it turned out to be sufficient to be able to pair up the zeros of p(x) in such a way that the same difference is repeated for each pair (see my answer).
But can we build "chains of zeros" with constant interval, i.e. arithmetic progressions of zeros.
Variants:
- If it is possible for three zeros, what about longer arithmetic progressions?
- Does the scene change, if we replace Q with another field K of characteristic zero? (Artin-Schreier polynomials show that the assumption about the characteristic is relevant.)

When does a polynomial f(x) generate an arithmetic sequence for consecutive values of integer x?
Given polynomial $f(x)=a_0+a_{1}x+\cdots <!--\; \cdots \; -->+a_n{x}^n,a_n\ne <!--\; \ne \; -->0,n\ge <!--\; \ge \; -->2,k\in <!--\; \in \; -->(0,n),a_k\in <!--\; \in \; -->\{0,1,2,\dots <!--\; \dots \; -->\}$, under what conditions is $f(r),f(r+1),\dots <!--\; \dots \; -->f(r+n)$ an arithmetic sequence for integer r?
When does f(x) not generate an $(n+1)$ term arithmetic sequence? (Update: Never - based on responses to this question).
Updated question: When does f(x) generate an n term arithmetic sequence? Given n values, we can fit an n-degree polynomial. The question is given the polynomial, when does it generate an n-term arithmetic sequence for n consecutive values of x
Note that $a_k$ are fixed in this problem.

Elementary Symmetric Means as Quasi-Arithmetic Means
The elementary symmetric polynomial of degree k in n variables is
$$e_{n,k}(\mathbf{x})=\underset{1\le <!--\; \le \; -->i_1\le <!--\; \le \; -->i_2\le <!--\; \le \; -->\cdots <!--\; \cdots \; -->\le <!--\; \le \; -->i_k\le <!--\; \le \; -->n}{\sum <!--\; \sum \; -->}{x}_{i_1}{x}_{i_2}\cdots <!--\; \cdots \; -->x_{i_k}$$
and for positive data x, the corresponding elementary symmetric mean is
$$s_{n,k}(\mathbf{x}):=\sqrt[k]{\frac{e_{n,k}(\mathbf{x})}{(\genfrac{}{}{0ex}{}{n}{k})}}.$$
Quasi-arithmetic means are defined in terms of an invertible function f, and the arithmetic mean A
$$M_f(\mathbf{x}):=(f^{-<!--\; -\; -->1}\circ <!--\; \circ \; -->A\circ <!--\; \circ \; -->f)(\mathbf{x})=f^{-<!--\; -\; -->1}\left(\frac{f(x_1)+f(x_2)+\cdots <!--\; \cdots \; -->+f(x_n)}{n}\right).$$
For any n, the elementary symmetric mean in n variables of degree n is the geometric mean, which is a quasi-arithmetic mean:
$$s_{n,n}(x_1,\dots <!--\; \dots \; -->,x_n)=\sqrt[n]{x_1{x}_2\cdots <!--\; \cdots \; -->x_n}=\exp <!--\; \; -->\left(\frac{\log <!--\; \; -->(x_1)+\log <!--\; \; -->(x_2)+\cdots <!--\; \cdots \; -->+\log <!--\; \; -->(x_n)}{n}\right).$$
My question is: are the other elementary symmetric means (with $k<n$) also quasi-arithmetic? If so, can the conjugating functions $f_{n,k}$ be described explicitly?
My attempt: Obviously $s_{n,1}=A$ is quasi-arithmetic, so the first nontrivial case is $s_{3,2}$, with the functional equation
$$f_{3,2}\circ <!--\; \circ \; -->s_{3,2}=A\circ <!--\; \circ \; -->f_{3,2},$$
or
$$f_{3,2}\left(\sqrt{\frac{x_1{x}_2+x_1{x}_3+x_2{x}_3}{3}}\right)=\frac{f_{3,2}(x_1)+f_{3,2}(x_2)+f_{3,2}(x_3)}{3}.$$
I tried pre-composing f with a logarithm and differentiation, but it didn't seem to get me anywhere.
I would greatly appreciate any help on this.

Polynomials and Arithmetic: If $p(x_i)=7$ for four integers, then $p(z)\ne <!--\; \ne \; -->14$
Consider the polynomial
$$p(x)=a_0+a_{1}x+a_2{x}^2+···+a_n{x}^n$$
where $a_0,a_1,...,a_n\in \mathbb{Z}$. Show that if $p(x_i)=7$ for 4 distinct integers $x_0,x_1,x_2,x_3$, then $p(z)\ne <!--\; \ne \; -->14$ for any $z\in \mathbb{Z}$.
How do I start this question?

Why is this arbitrary-looking identity of arithmetic functions "obvious"?
The question asks us the following: if f is a multiplicative arithmetic function, and g is a completely multiplicative arithmetic function, and furthermore for all primes p and $n\ge <!--\; \ge \; -->1$ we have the relation
$$f(p^{n+1})=f(p)f(p^n)-<!--\; -\; -->g(p)f(p^{n-<!--\; -\; -->1}),$$
then for all n,m
$$f(n)f(m)=\underset{d\mid <!--\; \mid \; -->gcd(n,m)}{\sum <!--\; \sum \; -->}g(d)f\left(\frac{nm}{d^2}\right).$$
More than any exercise so far in this book, this looks completely arbitrary to me. I have solved it: you can consider the question only for $n=p^a,m=p^b$, and then it follows for arbitrary n,m by multiplicativity of f,g; and we can prove it for $p^a\le <!--\; \le \; -->p^b$ by induction on a. But that has really taught me nothing: I don't understand why it might make some sense that this is true.
If $g(p)=0$ for all primes p, then the relation we start from becomes $f(p^n)=f(p{)}^n$ - i.e., f is completely multiplicative. Thus maybe we can see the $g(p)f(p^{n-<!--\; -\; -->1})$ as a sort of error term of the complete multiplicativity of f. But this doesn't help me see why the result makes sense.
Another approach I tried was noting that the relation allows us to write $f(p^k)$ as a polynomial in f(p),g(p), but I wrote out a few and I didn't see a pattern I understood.
So my question is: where does this identity come from? How should I understand it, visualize it, "get" it? How would one come up with an exercise like this?

Calculations on GF(16) find 0111/1111
It's my first time doing finite field arithmetics. As an exercise, I want to find $0111/1111\in <!--\; \in \; -->GF(16)$ generated by $\mathrm{\Pi <!--\; \Pi \; -->}(\mathrm{\alpha <!--\; \alpha \; -->})=1+\mathrm{\alpha <!--\; \alpha \; -->}+{\mathrm{\alpha <!--\; \alpha \; -->}}^4$ that is an irreducible polynomial.
In polynomial form we have:
$0111\to <!--\; \to \; -->\mathrm{\alpha <!--\; \alpha \; -->}+{\mathrm{\alpha <!--\; \alpha \; -->}}^2+{\mathrm{\alpha <!--\; \alpha \; -->}}^3$
$1111\to <!--\; \to \; -->1+\mathrm{\alpha <!--\; \alpha \; -->}+{\mathrm{\alpha <!--\; \alpha \; -->}}^2+{\mathrm{\alpha <!--\; \alpha \; -->}}^3$
If I perform the polynomial division, I obtain -1 (that is the same result obtained writing $0111\equiv <!--\; \equiv \; -->-<!--\; -\; -->1(\mathrm{mod}1111)$.
How can I compute this result -1 in the right element of the field? Or perhaps this some kind of sign that the result $\notin GF(16)$?

What does the common difference of a sequence describe
I am given the sequence 1, 7, 21, 43, 73, ... and can derive without any assumption about the nature of the sequence that the ultimate difference is 8, I'm interested in understanding what this difference allows you to deduce about the original polynomial which generates this sequence; and whether it is possible to find this polynomial?
I can see that 1, 7, 21, 43, 73, ... has a difference of 6, 14, 22, 30, ... which is generated by the arithmetic sequence 6 + 8(n-1), but trying to rationalize how the difference of a sequence can then be non-constant (1, 7, 21, 43, 73) it doesn't really make sense.
Can anyone shed some light on how to go about solving this intuitively?

Questions on a self-made theorem about polynomials
For any complex polynomial P degree n:
$$\underset{k=0}{\overset{n+1}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^k(\genfrac{}{}{0ex}{}{n+1}{k})P(a+kb)=0\mathrm{\forall <!--\; \forall \; -->}a,b\in <!--\; \in \; -->\mathbb{C}$$
Basically, if P is quadratic, $P(a)-<!--\; -\; -->3P(a+b)+3P(a+2b)-<!--\; -\; -->P(a+3b)=0$ (inputs of P are consecutive terms of any arithmetic sequence). This can be generalized to any other degrees.
- Has this been discovered? If yes, what's the formal name for this phenomenon?
- Is it significant/Are there important consequences of this being true?
- Can this be generalized to non-polynomials?

Matrix representations and polynomials
I just investigated the following matrix and some of its lower powers:
$$\begin{gathered} \mathbf{M}=\left[\begin{array}{cccc}1& 0& 0& 0\\ 1& 1& 0& 0\\ 1& 1& 1& 0\\ 1& 1& 1& 1\end{array}\right],{\mathbf{M}}^2=\left[\begin{array}{cccc}1& 0& 0& 0\\ 2& 1& 0& 0\\ 3& 2& 1& 0\\ 4& 3& 2& 1\end{array}\right], \\ {\mathbf{M}}^3=\left[\begin{array}{cccc}1& 0& 0& 0\\ 3& 1& 0& 0\\ 6& 3& 1& 0\\ 10& 6& 3& 1\end{array}\right],{\mathbf{M}}^4=\left[\begin{array}{cccc}1& 0& 0& 0\\ 4& 1& 0& 0\\ 10& 4& 1& 0\\ 20& 10& 4& 1\end{array}\right] \end{gathered}$$
As a function of the exponents, indices (1,1) seem to be constant 1, (2,1) seem to be linear function, (3,1) seem to be arithmetic sum and the fourth one seems to be sums of arithmetic sums. I have some faint memory that these should be polynomials of increasing order (well I know it for sure up to the arithmetic sum), but I can't seem to remember what they were called or how to calculate them. Does it make sense to do polynomial regression or is that uneccessary? This is following the train of thought from matrix representation of generating element for parabola, maybe you can see what I'm jabbing away at.
So the question is: is there an easy way to linearly combine the first columns of these matrices to generate the first 4 monomials? I can always do a linear regression with monomial basis functions, but that would be a little silly if this is already a well known way to do it.

Modular Polynomial Arithmetic
For $p=3$ and $n=2$, the $3^2=9$ polynomials in the set are
$$\begin{array}{|ccc|}\hline 0& x& 2x\\ 1& x+1& 2x+1\\ 2& x+2& 2x+2\\ \hline\end{array}$$
For $p=2$ and $n=3$, the $2^3=8$ polynomials in the set are
$$\begin{array}{|ccc|}\hline 0& x+1& x^2+x\\ 1& x^2& x^2+x+1\\ x& x^2+1\\ \hline\end{array}$$
For the first example right, from what I understand it is the polynomial whose coefficient are from $Z_p,\{0,1,...,p-<!--\; -\; -->1\}$. So given $p=3$, I can get 0,1,2. And if given $p=2$, I can get 0,1.
But I not sure how those x are derived. Any ideas?

No common terms in two sequences defined by linear quadratic recurrence relations
Let $x_n$ and $y_n$ be sequences such that $x_0=y_0=1,x_1=y_1=13$ and
$$x_{n+2}=38x_{n+1}-<!--\; -\; -->x_n,$$
$$y_{n+2}=20y_{n+1}-<!--\; -\; -->y_n$$
for $n\ge <!--\; \ge \; -->0$. I want to show that there is no common terms when $n\ge <!--\; \ge \; -->2$. In other words, there are no $n,m\ge <!--\; \ge \; -->2$ such that $x_n=y_m$.
I encountered this problem when tried to make an olympiad-like problem. So I am not sure it is true, but I have checked it with computer for $n\le <!--\; \le \; -->{10}^{200000}$. (Since I am not a good coder, I can't make sure that it does not have an error such as overflow. Sorry...)
Is there any strategy to solve these kind of problems? If there is, and if you gave me just a hint or a related concept

Arithmetic of Polynomials
if k is a field and f,g,h are polynomials such that $f=g+h$, then a polynomial that divides two of the three will divide the third.
I'm having trouble showing doing the problem as polynomials. I know how to do it is f,g,h are integers.

Proof that a polynomial has a minimum in R
I have to prove to following statement and I am having a really hard time here.
There it is:
Prove that the following polynomial has a minimum in R
$$p(x)=x^4+a_3{x}^3+a_2{x}^2+a_{1}x+a_0$$
I tried to make the following proof, but I am stuck:
The polynomial can be shown like this:
$$x^4(1+\frac{a_3}{x}+\frac{a_2}{x^2}+\frac{a_1}{x^3}+\frac{a_0}{x^4})$$
Let
$$g(x)=(1+\frac{a_3}{x}+\frac{a_2}{x^2}+\frac{a_1}{x^3}+\frac{a_0}{x^4})$$
So we can now write the polynomial like
$$p(x)=x^{4}g(x)$$
Since $x,a\in <!--\; \in \; -->\mathbb{R}$ we can say that $\underset{x\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}=\underset{x\to <!--\; \to \; -->-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}=1$ (from limit arithmetic).
We know that it is always the case that $x^4>0$, so the sign of
$$p(x)=x^{4}g(x)$$
is determined by g(x). For certain values, $g(x)<0$ so we can say that there is some $a,b\in <!--\; \in \; -->\mathbb{R}$ such that $g(a)<0$ and $g(b)>0$.
p(x) is continouos everywhere, certainly in [a,b], so from the Extreme Value Theorem, the function has a minimum in [a,b].
There are two problems in my proof:
I can't find any value in which g(x) is negative, only if there is some a which is negative. What if a is always positive?
If the first problem is solved, I managed to prove the statement for some [a,b]. Is it just enough? It seems to me that it isn't.

Is there 'Algebraic number' which cannot display with Arithmetic operation and root
Let $a+bi$ be an algebraic number. Then there is polynomial which coefficients are rational number and one of root is $a+bi$.
I think..
$$x=a+bi$$
we can subtract $c_1$ (which is rational number) from both sides.
$$x-<!--\; -\; -->c_1=a-<!--\; -\; -->c_1+bi$$
and we can power both side.
$$(x-<!--\; -\; -->c_1{)}^n=(a-<!--\; -\; -->c_1+bi{)}^n$$
and repeat we can get polynomial which coefficients are rational number and one of root is $a+bi$.
Therefore, I think there is no 'Algebraic number' which cannot be displayed with arithmetic operations and roots.

Find an optimal solution to a linear program in O(nlogn)
Given $c\in <!--\; \in \; -->{\mathbb{R}}_{+}^n,a\in <!--\; \in \; -->{\mathbb{R}}_{+}^n$ and $\mathrm{\gamma <!--\; \gamma \; -->}\in <!--\; \in \; -->{\mathbb{R}}_{+},$, design an algorithm which, in O(nlogn) operations, computes the optimal solution x∗ to the following linear program :
$$\begin{array}{cl}max& c^{T}x\\ \text{ s.t. }& a^{T}x\le <!--\; \le \; -->\mathrm{\gamma <!--\; \gamma \; -->}\\ & 0\le <!--\; \le \; -->x_i\le <!--\; \le \; -->1,\mathrm{\forall <!--\; \forall \; -->}i\in <!--\; \in \; -->[n]\end{array}$$
You may assume that a set of n real numbers can be sorted in time O(nlogn) and that each arithmetic operation takes constant time.
I tried multiple things without much success.
1. Start with a feasible solution, for example $0^T$ and add $(1/2{)}^k$ to each coordination at each of the k iterations until the constraints aren't satisfied anymore. I'm not sure this solution would be in O(nlogn).
2. Compute the dual of the LP, we know by strong duality that the objective value of the optimal solution of the dual is equal to the objective value of the optimal solution of the primal. However I'm not sure how solving the dual would be any easier.
3. Lastly I tried to see if the simplex method combined with an adequate sorting would work but the simplex algorithm is in polynomial time.

Assuming P(x) is a polynomial, can one deduce that P(x) is a polynomial of degree 0 or 1 from the following condition:
$$2P(x)=P(x-<!--\; -\; -->\frac{2^k}{n})+P(x+\frac{2^k}{n}),\mathrm{\forall <!--\; \forall \; -->}x$$
where n is a fixed positive integer and $k\in <!--\; \in \; -->\mathbb{N}\cup <!--\; \cup \; -->\{0\}$
The identity gives a feeling like the values of P(x) is "equally distributed" and its graph illustrates a straight line since
$$P(x)=\frac{P(x-<!--\; -\; -->\frac{2^k}{n})+P(x+\frac{2^k}{n})}{2}$$
so its value at x is an arithmetic mean of its values at $x-<!--\; -\; -->\frac{2^k}{n}$ and $x+\frac{2^k}{n}$. I don't have a potential argument though.

Polynomials with range containing an arithmetic progression
Can I find a polynomial in a second degree in two variables from the values of which can be found an infinite arithmetic progression?

How to compute exp(x) with correct rounding?
How to compute exp(x) for x∈[0,ln(2)] in double precision with high accuracy, possibly at most 0.5 ulp error?
It is possible to obtain low error. After testing a few libraries I have found one with 1 ulp accuracy. However I am not able to find any reference, which delivers precise error bounds for computed value.
Calculating exp(x) is not a trivial task. Althougth is is easy to obtain fast converging polynomial approximating this function, for example the Taylor series, roundoff errors occuring during evaluation of a polynomial are quite high. For example if we want to evaluate a polynomial p(x)=∑N−1i=0aixi, then apriori relative forward error is bounded as
$$\left|\frac{\mathrm{fl}<!--\; \; -->(p(x))-<!--\; -\; -->p(x)}{p(x)}\right|\le <!--\; \le \; -->\mathrm{cond}<!--\; \; -->(p,x)\times <!--\; \times \; -->u+O(u^2)$$
where
$$\mathrm{cond}<!--\; \; -->(p,x)=\frac{2N}{1-<!--\; -\; -->2Nu}\times <!--\; \times \; -->\left|\frac{\underset{i=0}{\overset{N}{\sum <!--\; \sum \; -->}}|a_i||x{|}^i}{p(x)}\right|\ge <!--\; \ge \; -->2N$$
and u is the unit roundoff (half of the machine precision).
Therefore even if we have a polynomial approximation of exp(x) of order 5 (which is hard by itself), with truncation error at most 0.5 ulp, then still roundoff error is at least 5. However 1 ulp error is possible.
My question is what kind of tricks can be used here to obtain high accuracy (without using high precision arithmetics). Is it even possible to obtain 0.5 ulp error?

Proposition $(S_1,\dots <!--\; \dots \; -->,S_r)$ from commutative algebra
Let k be a field, and I a proper ideal of $k[X_1,\dots <!--\; \dots \; -->,X_n]$. Then there exist a polynomial sub-k-algebra $k[S_1,\dots <!--\; \dots \; -->,S_n]$ of $k[X_1,\dots <!--\; \dots \; -->,X_n]$ and an integer $0\le <!--\; \le \; -->r\le <!--\; \le \; -->n$ such that:
(a) $k[X_1,\dots <!--\; \dots \; -->,X_n]$ is finite over $k[S_1,\dots <!--\; \dots \; -->,S_n]$;
(b) $k[S_1,\dots <!--\; \dots \; -->,S_n]\cap <!--\; \cap \; -->I=(S_1,\dots <!--\; \dots \; -->,S_r)$ (this is the zero ideal if $r=0$);
(c) $k[S_{r+1},\dots <!--\; \dots \; -->,S_n]\to <!--\; \to \; -->k[X_1,\dots <!--\; \dots \; -->,X_n]/I$ is finite injective.
I know that $(S_1,\dots <!--\; \dots \; -->,S_r)$ is the smallest ideal containing $\{S_1,\dots <!--\; \dots \; -->,S_r\}$ but is it the ideal of $k[X_1,\dots <!--\; \dots \; -->,X_n]$ or the ideal of $k[S_1,\dots <!--\; \dots \; -->,S_n]$?