We changed our privacy policy. Read more.
3

Suppose $n = 2^k$ and for $0\leq i \leq k$, set $p_i(x) = p(x)^{2^i}$. We want to efficiently compute $p_k(x)$. It is clear that for $0\leq i < k$, $p_{i+1}(x) = p_i(x)^2$. Using the Cooley-Tukey algorithm, knowing $p_i(x)$, we can compute $p_{i+1}(x)$ in time complexity $O(d_i\log d_i)$ where $d_i = \deg p_i = \deg p \times 2^i = 7\times 2^i$. We can ...


2

The product $$V=\prod_{i<j}(a_j-a_i)$$ is the determinant of the Vandermonde matrix of the numbers $a_1,a_2,...,a_n$. The square of this number is the discriminant $D$ of the polynomial $$p(x)=\prod_i(x-a_i)$$ This in turn is equal to $$V^2=D=(-1)^{n(n-1)/2}\prod_ip'(a_i)$$ You can quickly compute the coefficients of $p(x)$ and thus $p'(x)$, evaluate it ...


2

You already explained what to do when $k = 2$. Let's see what to do when $k = 3$. Let $P_i$ be the polynomial corresponding to $iS$ (for example, the solution for $k = 2$ is $(P_1^2 - P_2)/2$). We can construct the following table: $$ \begin{array}{c|ccc} & aaa & aab & abc \\\hline P_1^3 & 1 & 1 & 1 \\ 3P_2 P_1 & 3 & 1 & ...


2

If $P, Q, R \in \mathbb{R}[X], R = PQ$, then for any $x \in \mathbb{R}$, $R(x) = P(x)\times Q(x)$. It means that if the value representation of $P$ is $[(x_1, P(x_1)); (x_2, P(x_2)); …, (x_n, P(x_n))]$ and the value representation of $Q$ is $[(x_1, Q(x_1)); (x_2, Q(x_2)); …, (x_n, Q(x_n))]$, then the value representation of $R$ is $[(x_1, P(x_1)Q(x_1)); (x_2,...


1

For a set $S = \{s_1,\dotsc,s_n\}$. Construct a polynomial $P(x): x^{s_1} + x^{s_2} + \dotsc + x^{s_n}$. Multiply the polynomial by itself three times, i.e., $P(x) \cdot P(x) \cdot P(x)$. Let this polynomial be $Q(x)$ Claim: The coefficient of $x^T$ in $Q(x)$ is non-zero if and only if there exist three values in $S$ that sum to $T$. Proof: [You may want to ...


1

For testing, you can use SageMath very easily; you had erros on $$A(x_0) = 0, A(x_1) = 16, A(x_2) = 85, A(x_3)=208, \\B(x_0) = -1, \color{red}{B(x_1) = -2}, \color{red}{B(x_2) = -5},\color{red}{B(x_3) = 8}$$ R = PolynomialRing(QQ, 'x') A = 3 *x^2-4*x+1 B = x -2 a0 = A(1) a1 = A(3) a2 = A(6) a3 = A(9) b0 = B(1) b1 = B(3) ...


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