Master Polynomial Concepts with Comprehensive Resources

VP Definition: Why polynomial bound on the degree?
The complexity class VP (Valiant P) is defined to be the class of all polynomials of polynomially bounded degree which can be realized by an arithmetic circuit family with polynomially bounded size.
My questions are:
1. Why do we require the degree to be polynomially bounded?
2. Which complexity class to we get if we omit this constraint?

Index / Angle of the Real Root in a Cubic Equation
- I am trying to find the roots of a general cubic equation, but with a twist:
In case there is only one real root (the discriminant of the polynomial is less than zero), I want to separate the real root from the pair of complex conjugate roots and treat them differently (replace them by other complex roots specific to the actual problem I am solving).
- I also want to stick to complex numbers (as opposed to explicit trigonometry) because I have to factor out all divisions at the end to represent the roots as homogeneous coordinates.
I currently use the approach described on Wikipedia. But because I use floating point arithmetic (not real numbers) it suffers from a bit of numeric instability, which makes it hard to tell which of the three results was supposed to be the real root (in case the curve is really flat and they are all close to the real line).
My current approach selects the root with the smallest absolute imaginary component. However I think there should be a better way to tell them apart before calculating the result, maybe related to the angles of the root of unity, so that I can get the index (k) of the real root ($x_k$) sooner.

Finding polynomials with a specific property
Show that there exist a $n\in <!--\; \in \; -->\mathbb{N}$ and polynomials $p,q\in <!--\; \in \; -->\mathbb{N}[x_1,\dots <!--\; \dots \; -->,x_n]$ such that neither the formula
$$\mathrm{\varphi <!--\; \varphi \; -->}(n,p,q)=\mathrm{\forall <!--\; \forall \; -->}{x}_1\cdots <!--\; \cdots \; -->\mathrm{\forall <!--\; \forall \; -->}{x}_n:\mathrm{\neg <!--\; \neg \; -->}(p(x_1,\dots <!--\; \dots \; -->,x_n)=q(x_1,\dots <!--\; \dots \; -->,x_n))$$
nor $\mathrm{\neg <!--\; \neg \; -->}\mathrm{\varphi <!--\; \varphi \; -->}$ are not theorems of formal arithmetic.

Cardinalities of R[X] and R
I want to show that the Cardinalities of R[X] and R are equal.
For starters, I tried mapping each polynomial to ${\mathbb{R}}^n$ by mapping it to its coordinates vector, but its not correct (I am limiting my polynomials here)
I can use cardinalities arithmetic and Cantor - Bernstein theorem.
Would love to get some insight.

Calculating of genus of a curve.
Let C be a curve over ${\mathbb{F}}_q$ in projective plane. So C can be done as zeroes of some gomogeneous polynomial $\in <!--\; \in \; -->{\mathbb{F}}_q[x,y,z]$ with degree n. Whether is there algorithm which is polynomial time in n that calculate arithmetic genus of C?

Modular arithmetic polynomial question
Is it possible to find all polynomials of the form $a{n}^2+bn+c$ where a,b, and c are integers and such that
$$a+b+c\equiv <!--\; \equiv \; -->31(\mathrm{mod}54)$$
$$4a+2b+c\equiv <!--\; \equiv \; -->3(\mathrm{mod}54)$$
$$9a+3b+c\equiv <!--\; \equiv \; -->11(\mathrm{mod}54)$$

Compute the arithmetic genus of the union of the three coordinate axes $Z(x_1{x}_2,x_1{x}_3,x_2{x}_3)\subseteq <!--\; \subseteq \; -->{\mathbb{P}}^3$
Compute the arithmetic genus of the union of the three coordinate axes $Z(x_1{x}_2,x_1{x}_3,x_2{x}_3)\subseteq <!--\; \subseteq \; -->{\mathbb{P}}^3$
The arithmetic genus of $X\subseteq <!--\; \subseteq \; -->{\mathbb{P}}^n$ is $g(X)=(-<!--\; -\; -->1{)}^{dim(X)}(\mathrm{\chi <!--\; \chi \; -->}(0)-<!--\; -\; -->1)$, where $\mathrm{\chi <!--\; \chi \; -->}$ is the Hilbert polynomial of X.
Let $X=Z(x_1{x}_2,x_1{x}_3,x_2{x}_3)\subseteq <!--\; \subseteq \; -->{\mathbb{P}}^3.$
I guess that $dim(X)=1$, since the coordinate $x_0$ is free.
I showed that if X is a hypersurface of degree d in ${\mathbb{P}}^n$, then $g(X)=(\genfrac{}{}{0ex}{}{d-<!--\; -\; -->1}{n})$. I don't think that this can be applied to this problem but it's a general result that I know.
I showed also that if X is a complete intersection of two surfaces of degree a and b in ${\mathbb{P}}^3$, then $g(X)=\frac{1}{2}ab(a+b-<!--\; -\; -->4)+1$.
Is there any solution of this problem that does not involve computing the Hilbert polynomial of X? However, if computing the Hilbert polynomial is simplier, that's ok for me.

Smooth curve of genus 1 in P1C×P1C.
Show that
$$\{((x_0:x_1),(y_0:y_1)):(x_0^2+x_1^2)(y_0^2+y_1^2)=x_0{x}_1{y}_0{y}_1\}\subset <!--\; \subset \; -->{\mathbb{P}}_{\mathbb{C}}^1\times <!--\; \times \; -->{\mathbb{P}}_{\mathbb{C}}^1$$is a smooth curve of genus 1.
The author briefly talked about the concept genus in this section without assuming much knowledge in topology. One proposition said that the genus of smooth curve of degree d in ${\mathbb{P}}_{\mathbb{C}}^2$ is $(\genfrac{}{}{0ex}{}{d-<!--\; -\; -->1}{2})$.
Then in one exercise I showed that the arithmetic genus $(-<!--\; -\; -->1{)}^{\dim <!--\; \; -->X}\cdot <!--\; \cdot \; -->({\mathrm{\chi <!--\; \chi \; -->}}_X(0)-<!--\; -\; -->1)$ of a smooth curve in ${\mathbb{P}}_{\mathbb{C}}^2$ agrees with the geometric genus, where ${\mathrm{\chi <!--\; \chi \; -->}}_X$ is the Hilbert polynomial of the projective variety X. The author then stated that this can be generalized to any smooth projective curve over C.
So I think I should use that formula for this exercise. The smoothness can be shown by the Segre embedding. Now the formula says that the genus is
$$1-<!--\; -\; -->{\mathrm{\chi <!--\; \chi \; -->}}_X(0).$$
And ${\mathrm{\chi <!--\; \chi \; -->}}_X(d)=(\genfrac{}{}{0ex}{}{3+d}{3})-<!--\; -\; -->(\genfrac{}{}{0ex}{}{3+d-<!--\; -\; -->4}{3})$. But I cannot get 1. I must have made some mistake when calculating ${\mathrm{\chi <!--\; \chi \; -->}}_X(d)$. But I couldn't figure out where.

Primes modulo which a given quadratic equation has roots
Given a quadratic polynomial $a{x}^2+bx+c$, with a, b and c being integers, is there a characterization of all primes p for which the equation
$$a{x}^2+bx+c\equiv <!--\; \equiv \; -->0(\mathrm{mod}p)$$
has solutions?

Question about The Quadratic Reciprocity Law Proof
In A Course in Arithmetic (Serre) he beings by proving the quadratic reciprocity law (Thereom 6) as follows:
Let p and l be two distinct primes different from 2. Let $\mathrm{\Omega <!--\; \Omega \; -->}$ be an algebraic closure of ${\mathbf{F}}_p$ and let $w\in <!--\; \in \; -->\mathrm{\Omega <!--\; \Omega \; -->}$ be a primitive l-th root of unity. If $x\in <!--\; \in \; -->{\mathbf{F}}_l$, the element $w^x$ is well defined since $w^l=1$...
My question is as follows: I don't understand why $w^x$ is defined at all. I know that $w^n$ is defined if n is an integer but x is an element of the field ${\mathbf{F}}_l$. So what do we even mean by $w^x$ in a precise sense? Does it still reside in $\mathrm{\Omega <!--\; \Omega \; -->}$? I can't think of a polynomial where one of its roots is $w^x$.

Related To Polynomial Division. How to prove the following result. Show how a polynomial with odd number of term will never be divisible by a divisor with $x+1$ as factor for modulo 2 arithmetic.

Finite field adjunction - isomorphism that maps from the field into a polynomial ring factored over an ideal
A field $(K,+,0,\ast <!--\; \ast \; -->,1)$ is given, and it is a finite field with 25 elements. P is the prime field over K. Further it was given that a polynomial $r(x):=x^2+x+1\in <!--\; \in \; -->P[x]$ is irreducible.
Now, the polynomial $y^2+y+1\in <!--\; \in \; -->K[x]$ has two non-equal zeros in K, say ${\mathrm{\alpha <!--\; \alpha \; -->}}_1\ne <!--\; \ne \; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_2$.
The question is to describe all possible isomorphisms:
$$\mathrm{\phi <!--\; \phi \; -->}:K\to <!--\; \to \; -->P[x]/(r)$$
by giving the values of $\mathrm{\phi <!--\; \phi \; -->}({\mathrm{\alpha <!--\; \alpha \; -->}}_1)$ and $\mathrm{\phi <!--\; \phi \; -->}({\mathrm{\alpha <!--\; \alpha \; -->}}_2)$.
There are a few things that I don't understand about this question.
First of all, what are the properties of K[y] apart from it being a polynomial ring? I think that the additive group $(K,+,0)$ should be isomorph to a cyclic group $C_5\times <!--\; \times \; -->C_5$ - can that help me in any way?
Then - when I try to find the ${\mathrm{\alpha <!--\; \alpha \; -->}}_1$ and ${\mathrm{\alpha <!--\; \alpha \; -->}}_2$ I do my calculations in the Modulo 25 arithmetic - is that right (because I failed to find the zeros)?
And since the $\mathrm{\phi <!--\; \phi \; -->}(k)=k+(r)$ is one of the possibilites to describe this isomorphism, my question is - are there any more of them? Because my textbook doesn't state that this isomorphism is unique.
Any kind of help - or a link to some other question is more than welcome.

Determine the minimal polynomial of T with respect to ${\left(\begin{array}{ccc}0& 0& 1\end{array}\right)}^t.$.
Let $T:{\mathbb{R}}^3\to <!--\; \to \; -->{\mathbb{R}}^3$ be defined by $T(v)=\left(\begin{array}{ccc}2& -<!--\; -\; -->1& 1\\ -<!--\; -\; -->3& 4& -<!--\; -\; -->5\\ -<!--\; -\; -->3& 3& -<!--\; -\; -->4\end{array}\right)v.$
Determine the minimal polynomial of T with respect to $\left(\begin{array}{c}0\\ 0\\ 1\end{array}\right).$
$T(v)=\left(\begin{array}{ccc}2& -<!--\; -\; -->1& 1\\ -<!--\; -\; -->3& 4& -<!--\; -\; -->5\\ -<!--\; -\; -->3& 3& -<!--\; -\; -->4\end{array}\right)\left(\begin{array}{c}0\\ 0\\ 1\end{array}\right)=\left(\begin{array}{c}1\\ -<!--\; -\; -->5\\ -<!--\; -\; -->4\end{array}\right)$
$T^2(v)=\left(\begin{array}{ccc}2& -<!--\; -\; -->1& 1\\ -<!--\; -\; -->3& 4& -<!--\; -\; -->5\\ -<!--\; -\; -->3& 3& -<!--\; -\; -->4\end{array}\right)\left(\begin{array}{c}1\\ -<!--\; -\; -->5\\ -<!--\; -\; -->4\end{array}\right)=\left(\begin{array}{c}3\\ -<!--\; -\; -->3\\ -<!--\; -\; -->2\end{array}\right)$
$T^3(v)=\left(\begin{array}{ccc}2& -<!--\; -\; -->1& 1\\ -<!--\; -\; -->3& 4& -<!--\; -\; -->5\\ -<!--\; -\; -->3& 3& -<!--\; -\; -->4\end{array}\right)\left(\begin{array}{c}3\\ -<!--\; -\; -->3\\ -<!--\; -\; -->2\end{array}\right)=\left(\begin{array}{c}7\\ -<!--\; -\; -->11\\ -<!--\; -\; -->10\end{array}\right)$
The corresponding matrix is
$A=(v,T(v),T^2(v),T^3(v))=\left(\begin{array}{cccc}0& 1& 3& 7\\ 0& -<!--\; -\; -->5& -<!--\; -\; -->3& -<!--\; -\; -->11\\ 1& -<!--\; -\; -->4& -<!--\; -\; -->2& -<!--\; -\; -->10\end{array}\right)$
After row reducing this matrix, we obtain $\left(\begin{array}{cccc}1& 0& 0& -<!--\; -\; -->2\\ 0& 1& 0& 1\\ 0& 0& 1& 2\end{array}\right)$, and so $\text{null}(A)=\text{span}\{\left(\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right),\left(\begin{array}{c}2\\ -<!--\; -\; -->1\\ 0\\ 1\end{array}\right)\}.$ From this we obtain polynomials $f(x)=x^2$ and $g(x)=x^3-<!--\; -\; -->x-<!--\; -\; -->2$ and since $\mathrm{deg}<!--\; \; -->f(x)<\mathrm{deg}<!--\; \; -->g(x),$, $x^2$ is the minimal polynomial.
The back of my book says the minimal polynomial is $x^2-<!--\; -\; -->3x+2.$ What am I doing wrong?

Problem involving polynomial function and prime numbers
Let f be a polynomial function, with integer coefficients, strictly increasing on N such that $f(0)=1$. Show that it doesn't exist any arithmetic progression of natural numbers with ratio $r>0$ such that the value of function f in every term of the progression is a prime number. I noticed that the last term of f is 1, due to the fact that $f(0)=1$. I don't know how to continue.

I have a following task of determining whether this problem is well conditioned. I tried to solve it but I am stuck because I don't know how to understand the last step.
Is a problem of calculating the root of the polynomial $p(x)=ax+b$ well conditioned for variables a,x and b?
Here is my attempt:
I calculate maximal relative error of result, denoted with U(a,x,b) where a,x,b are arguments with a relative error not greater than arithmetic precision denoted by $\mathrm{\nu <!--\; \nu \; -->}$. Here is equation with distorted data for relative error:
$$\frac{|a(1+{\mathrm{ϵ<!--\; ϵ\; -->}}_1)x(1+{\mathrm{ϵ<!--\; ϵ\; -->}}_2)+b(1+{\mathrm{ϵ<!--\; ϵ\; -->}}_3)-<!--\; -\; -->ax-<!--\; -\; -->b|}{|ax+b|}=U(a,x,b)$$
And
$$\underset{|\mathrm{ϵ<!--\; ϵ\; -->}|\le <!--\; \le \; -->\mathrm{\nu <!--\; \nu \; -->}}{sup}U(a,x,b)=\frac{|ax(2\mathrm{\nu <!--\; \nu \; -->}+{\mathrm{\nu <!--\; \nu \; -->}}^2)+b\mathrm{\nu <!--\; \nu \; -->}|}{|ax+b|}$$
$$cond(a,x,b)=\frac{U(a,x,b)}{\mathrm{\nu <!--\; \nu \; -->}}=\frac{|ax(2+\mathrm{\nu <!--\; \nu \; -->})+b|}{|ax+b|}$$
How this translates to statement that problem is well defined or not? I don't specifically understand this step.

For Variety V, function $V\to <!--\; \to \; -->\stackrel{¯<!--\; ¯\; -->}{K}$
I’m reading Silverman’s Arithmetic of Elliptic Curves, and they make the comment “Since an element $f\in \stackrel{¯<!--\; ¯\; -->}{K}[V]$ is well-defined up to a polynomial vanishing on V, it induces a well-defines function $f:V\to <!--\; \to \; -->\stackrel{¯<!--\; ¯\; -->}{K},$ where V denotes an affine algebraic variety. My question:
Let’s start off by using more pedantic notation. Let $\stackrel{¯<!--\; ¯\; -->}{f}\in <!--\; \in \; -->\stackrel{¯<!--\; ¯\; -->}{K}$, and let $\stackrel{¯<!--\; ¯\; -->}{F}$ denote this induced map $V\to <!--\; \to \; -->\stackrel{¯<!--\; ¯\; -->}{K}$. How is $\stackrel{¯<!--\; ¯\; -->}{F}$ defined?

If $C\subseteq <!--\; \subseteq \; -->{\mathbb{P}}^2$ is a plane curve, then $genus(C)=\frac{1}{2}(d-<!--\; -\; -->1)(d-<!--\; -\; -->2)$. Compare with example in the notes
In fact, the first part of the exercise is easy to solve using the Hilbert polynomial of C.
The part of comparing with the example 0.1.3 is what I don't understand.
What do you think the author wants here as an answer?

Can we introduce new operations that make quintics solvable?
I have heard from various sources that the typical arithmetic operations (addition, subtraction, multiplication, division, rational exponentiation) are not sufficient to express in general the roots of a quintic polynomial. This is due to something along the lines of their inability to "express the necessary symmetries."
Would it be possible to introduce new arithmetic operations that allow do "express the necessary symmetries" and therefore allow a quintic formula to be written?

Approximating the cosine by Taylor polynomial
Let $f:=\cos <!--\; \; -->(x)$ I'm asked to find for which values of x we can be sure the 4th degree Taylor polynomial will give an error lesser than $\frac{1}{1000}$.
Now, $\cos <!--\; \; -->(x)=1-<!--\; -\; -->\frac{x^2}{2}+\frac{x^4}{24}+o(x^4)$
Taylor's 4th degree remainder is then $R=\frac{f^{(5)}(\cos <!--\; \; -->(\mathrm{\theta <!--\; \theta \; -->}))}{5!}{x}^5=\frac{-<!--\; -\; -->\sin <!--\; \; -->(\mathrm{\theta <!--\; \theta \; -->})}{5!}{x}^5$
Since I'm only asked about the error, I can get rid of the sign, and can do the following boundering:
$|R|\le <!--\; \le \; -->|\frac{1}{5!}{x}^5|\le <!--\; \le \; -->\frac{1}{1000}$
Since that is strictly increasing, its easy to solve
that last inequation, by doing $\frac{1}{120}{x}^5=\frac{1}{1000}⟶<!--\; ⟶\; -->x=\sqrt[5]{\frac{120}{1000}}\approx <!--\; \approx \; -->0.65$
Which ends up giving $|R|\le <!--\; \le \; -->\frac{1}{1000}\mathrm{\forall <!--\; \forall \; -->}x:|x|\le <!--\; \le \; -->\sqrt[5]{\frac{120}{1000}}(\approx <!--\; \approx \; -->0.65)$
Now, I thought this was an already correct solution, but to my surprise, I checked plotted both the function and its Taylor polynomial, and the error bound that produces below 0.65 is not only lesser than $\frac{1}{1000}$, but actually lesser than $\frac{1}{10000}$
e.g:
$$\cos <!--\; \; -->(0.65)=\mathrm{0.796187...}$$
$$taylor(cos(0.65))=\mathrm{0.796083...}$$
Which means it is overly precise, what is going on here, I'm asuming it must be some arithmetic mistake I made somewhere, but I can't find it and its driving me crazy.

Test whether a given function is polynomial
You have a black box function to which you can give real number inputs and from which you can receive real number outputs. How would you test whether it is likely to be a polynomial?
One expensive idea is to use finite differences:
1. Choose a maximum degree n of the "polynomial" you are testing.
2. Choose a consecutive sequence with random step size, and evaluate the function there to get an output sequence. E.g.,
$$[2,2.3,2.6,2.9,\dots <!--\; \dots \; -->]\to <!--\; \to \; -->[4.81,5.02,5.05,4.90,\dots <!--\; \dots \; -->]$$
3. Using the output sequence as S[0], define S[n] so that its k-th entry $S[n][k]=S[n-<!--\; -\; -->1][k+1]-<!--\; -\; -->S[n-<!--\; -\; -->1][k].E.g.S[1]=[5.02-<!--\; -\; -->4.81,5.05-<!--\; -\; -->5.02,4.90-<!--\; -\; -->5.05,...]=[0.21,0.03,-<!--\; -\; -->0.15,...]$
4. If the function is a polynomial (of degree at most n), then the sequence $S[n+1]$ should be all zeros.
Some issues about programming this method:
Would be expensive for large n
If S[0] has large values, computer arithmetic will produce bad results for S[1] and beyond.