Questions tagged [polynomials]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
3 answers
454 views

Deciding whether an integer polynomial has an integer root

This is a question written by my instructor Z. Loria . Consider the following problem: Given a polynomial $p(x) = \sum_{i=0}^n a_ix^i$, where $a_i$ are integers, is there a natural number $n \in \...
user avatar
  • 117
1 vote
1 answer
58 views

Does the reliability of polynomial hashing depend on whether the modulus is prime, for coprime base and modulus?

A polynomial hash of a string $s$ with base $b$ and modulus $M$ is defined as $$ H(s) = (s_0 + s_1 b + s_2 b^2 + \dots + s_{n-1} b^{n-1}) \mod M. $$ I have proven (and this is quite obvious) that ...
user avatar
  • 11
2 votes
1 answer
47 views

Is there a simplistic way of describing the proof to the undecidability of David Hilbert's 10th problem?

I recently have been reading a bunch about David Hilbert's famous 10th problem, and trying to understand its proof. I am currently in the process of reading through an explanation of the proof, given ...
user avatar
1 vote
0 answers
32 views

Efficient bit-level implementation of Boolean polynomials with few variables

A Boolean polynomial in $n$ variables $x_1, \dots, x_n$ is an expression of the form $$\sum_{\mathbf{s} \in \{0,1\}^n} c_{\mathbf{s}} x_1^{s_1} \cdots x_n^{s_n}, \quad \text{ where } c_s \in \{0,1\} .$...
user avatar
  • 11
0 votes
0 answers
35 views

From roots to coefficients of a polynomial [duplicate]

Polynomials are usually written as a sum of powers (or various products of generators) and Google gives me lots of results on how to get from that to the form that is a product of degree-$1$ ...
user avatar
  • 121
0 votes
1 answer
74 views

Finding $Aeven(x)$ and $Aodd(x)$ for a Fast Fourier Transform (FFT) problem?

In this article about FFT the author used FFT on this polynomial. $A(x) = 3+2x+3x^2+4x^3$ Using $ A(x)= Aeven(x^2) + xAodd(x^2)$ the author determined the following for $Aeven(x)$ and $Aodd(x)$ $ ...
user avatar
-1 votes
1 answer
22 views

Given x find a polynomial such that pol(x)=a for a known a?

You are given x,a. Find a polynomial p(y) with the leading coafficent 1 such that p(x)=a. How to write an algorithem to solve this efficently? I have no idea where to start
user avatar
1 vote
0 answers
33 views

Finding points of local maximum error in Remez algorithm

So the Remez algorithm is an algorithm for finding optimal polynomial approximations or at the very least for converging towards them. To find an approximation of $f$ by an $N$th degree polynomial the ...
user avatar
  • 3,728
3 votes
1 answer
85 views

Computing coefficients of $p(x)^n$ in time $O(n \log n)$

For homework I've to give an algorithm that computes the coefficients of the polynomial $p(x)^n$ in time $O(n\log n)$, where $p(x)$ is a polynomial of degree 7. As an hint I'm told to consider first ...
user avatar
  • 117
0 votes
0 answers
52 views

Time to evaluate a product of binomials $1 + x^i$

I am considering the asymptotic analysis required to convert a polynomial of the shape $$P(x) = \prod_{i = 1}^{n}(1 + x^{s_i})$$ to its "full" representation, for example $$P(x) = 1+x^3+x^5+...
user avatar
0 votes
1 answer
35 views

Multiplication of polynomials in value representation as done for Fast Fourier Transform

I am trying to understand the discrete Fast Fourier Transform. I get the idea of switching between coefficient and value representations to and then back but I am stuck in figuring out how the ...
user avatar
1 vote
0 answers
55 views

Optimize binary multivariate polynomial multiplication

You have a few variables that can only assume the values 0 or 1 and you use those to form two polynomials. Is there a way to multiply the two polynomials that is faster than O(n²) where n is the ...
user avatar
1 vote
1 answer
32 views

How polynomial interpolation of polynomial multiplication algorithm works?

I'm trying to apply the following algorithm from DPV's textbook to an example to see how it works. First, the algorithm is as following: Algorithm [DPV, p. 60] Input: Coefficients of two polynomials. ...
user avatar
  • 697
1 vote
0 answers
56 views

Express polynomial as sum of two lower-degree polynomials, modulo another

Suppose I have a polynomial $p(x)$, and a "modulus" polynomial $q(x)$ of degree $d$. I want to find two polynomials $r_1(x),r_2(x)$ of degree $\le d_1,d_2$ such that $$p(x) \equiv r_1(x) x^...
user avatar
  • 140k
2 votes
0 answers
105 views

Decide whether a polynomial has a root

Let $A$ be a ring such that all elements of $A$ are complex computable numbers. I'm interested in knowing whether the decision problem that asks, given $P\in A[X]$, if $P$ has a root in $A$ is ...
user avatar
  • 21
1 vote
2 answers
58 views

Show that the OR of n variables cannot be expressed as a polynomial over Fp of degree less than n

Here is a question from Computational Complexity by Arora and Barak: Show that representing OR of $n$ variables $x_1,x_2,\dots,x_n$ exactly over a polynomial in $GF(q)$ requires degree exactly $n$. (...
user avatar
1 vote
0 answers
24 views

Binomial basis and the usual basis of polynomial algebra $\mathbb C(X)$

Consider the polynomial algebra $\mathbb C[X]$. Then the set $\{1, X, X^2,\dots,\}$ forms a vector space basis for this algebra. In general, we know that the set $\{P_n(X) \in \mathbb C[X]: n \ge 0 \...
user avatar
  • 111
0 votes
1 answer
29 views

Represent a DNF formula as a multivariate linear formula?

Lets say I have the following DNF: (x or y) and (z or i) / $(x\lor y)\land(z\lor i)$ How do I convert that into a polynomial form?
user avatar
1 vote
0 answers
36 views

How do I decode a received polynomial code with an error?

As a message I get (5,0,1,3), which is coding a sequence of numbers of length 2 in $\mathbb{F}_7$ as polynom with the 4 support points a1 = 0, a2 = 1, a3 = 2, a4 = 6. In the transimission occured an ...
user avatar
  • 21
1 vote
1 answer
169 views

Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$

Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$. For eg. Let the array be $1,2,3$ then my answer will be calculated as- $(2-1)$.$(...
user avatar
2 votes
0 answers
84 views

Understanding CRC Computation with PCLMULQDQ

I am currently reading this paper which shows how to calculate CRC using the instruction PCLMULQDQ. I don't quite understand the equations in it yet. Starting with this one for the definition of ...
user avatar
3 votes
1 answer
149 views

Is deciding solvability of systems of quadratic equations with integer coefficients over the reals in NP?

In the book 'Computational Complexity' by Arora and Barak the following question is posed (exercise 2.20.): Let REALQUADEQ be the language of all satisfiable sets of quadratic equations over real ...
user avatar
  • 33
1 vote
0 answers
57 views

How to compute the first n coefficients using number theoretic transform (NTT)?

I need to find the first $n$ coefficients of $$\prod_{i = 1}^{i = q}(1 + x^{a_i})^{b_i}$$ modulo a NTT favourable prime. Can someone suggest an algorithm with worst-case complexity $O(n\log n)$ or $O(...
user avatar
2 votes
1 answer
126 views

Why does $x^{15}+x^{14}+1$ detect all errors at most 32768 bits apart?

Reference Question from Forouzon Book Computer Network. Find the status of the following generator related to two isolated, single-bit errors. $$x^{15} + x^{14} + 1$$ Answer given : This polynomial ...
user avatar
3 votes
0 answers
26 views

Bit complexity of computing the sign of an expression evaluated at an algebraic number

I have a univariate polynomial $F(t)\in \mathbb{Z}[t]$ of degree $d$ and maximum bitsize of coefficients equal to $\tau$ and $G(t) \in \mathbb{Z}[t]$ of degree $d^2$ and maximum bitsize of ...
user avatar
  • 131
3 votes
1 answer
207 views

Is O(n log n) exponential speedup over O(n^2)?

I would like to know if $O(n \log n)$ is an exponential speedup over $O(n^2)$?
user avatar
0 votes
0 answers
206 views

Multiplying bivariate polynomials using FFT

Consider two bivariate polynomials of degree at most $n-1$ in each variable: $$ F(x,y) = \sum_{i,j=0}^{n-1} f_{i,j} x^i y^j \quad \text{and} \quad G(x,y) = \sum_{i,j=0}^{n-1} g_{i,j} x^i y^j. $$ ...
user avatar
  • 1
14 votes
2 answers
3k views

What is the most efficient algorithm to compute polynomial coefficients from its roots?

Given $n$ roots, $x_1, x_2, \dotsc, x_n$, the corresponding monic polynomial is $$y = (x-x_1)(x-x_2)\dotsm(x-x_n) = \prod_{i}^n (x - x_i)$$ To get the coefficients, i.e., $y = \sum_{i}^n a_i x^i$, a ...
user avatar
  • 243
2 votes
1 answer
183 views

Polynomial multiplications and counting

I came across the following problem. Given a set of $n$ positive integers $A$ and an integer $k$. Let $S$ be the set of integers that are the sum of $k$ distinct integers in $A$. Mathematically ...
user avatar
1 vote
1 answer
195 views

Fitting a polynomial to a set of points or to a skeleton

Available data Available to me is a set of points which can be represented as shown in image 1: Also available to me is a non-continuous path derived from this data. It is not important how this non-...
user avatar
1 vote
0 answers
33 views

Generating a set of divergence-free basis

I'm trying to derive an algorithm that would generate a set of divergence-free vectors, which shall be used as basis vectors later on. Using a simple example, a 2D second-order divergence-free basis ...
user avatar
2 votes
1 answer
82 views

Polynomials - using Newton's method, or not?

I have to find a root of polynomial of degree $n\ge2$. I need to write code to calculate the root for different values of $n$. Only 1 real positive solution is needed. I can use general Newton's ...
user avatar
3 votes
1 answer
78 views

Polynomial size Boolean circuit for counting number of bits

Given a natural number $n \geq 1$, I am looking for a Boolean circuit over $2n$ variables, $\varphi(x_1, y_1, \dots, x_n, y_n)$, such that the output is true if and only if the assignment that makes ...
user avatar
2 votes
1 answer
40 views

Question on the paper ``Self-Testing/Correcting for Polynomials and for Approximate Functions''

I am having some trouble really getting to a precise understanding of some of Self-Testing/Correcting for Polynomials and for Approximate Functions and would greatly appreciate help. Here is my ...
user avatar
2 votes
2 answers
59 views

Search for numerical solutions of underdetermined systems of quadratic equations

I'm looking for an algorithm that can quickly generate an approximate real number solutions of an underdetermined quadratic system. My task is to explore its algebraic variety. I'm interested in a ...
user avatar
  • 21
1 vote
1 answer
343 views

CRC computation speed vs polynomials features

I tried to find information about how features of a CRC polynomials influence computation speed of implementations. It is obvious that (depending from the CPU architecture the algorithm runs on) ...
user avatar
3 votes
1 answer
3k views

Meaning of polynomially larger or smaller in the context of the master method

I'm studying the master method of solving recurrences and I have a somewhat decent math background but I'm having difficulty understanding the concept of $n^{\log_ba}$ being polynomially smaller or ...
user avatar
3 votes
1 answer
117 views

Last digit of polynomial value

There is a simple-looking problem. Given integer coefficients $c_{0}, c_{1}, c_{2}, \dots, c_{n - 1}$ of polynomial $$ p(x) = c_{0} + c_{1} x + c_{2} x^{2} + \dots + c_{n - 1} x^{n - 1} $$ and ...
user avatar
  • 155
0 votes
1 answer
794 views

Polynomial multiplication coefficients

I was wondering about the following interesting questions: Polynomial multiplication can be done in $O(nlog(n))$ using FFT where n is the degree of the polynomial. What about finding a specific ...
user avatar
3 votes
1 answer
284 views

Polylogarithm growth rate proof using Polynomial growth equation

In the CLRS, there's this part, where it's shown that $$\lim_{n\to\infty}\frac{(n^b)}{(a^n)} = 0$$ In the same chapter, it uses the aforementioned equation to prove that any polylogarithm function ...
user avatar
2 votes
0 answers
55 views

An efficient algorithm to find a linear transformation between two ternary quadratic forms

Let $\mathbb{F}_p$ be a prime finite field for $p > 2$. Consider two ternary quadratic forms $$Q_1\!: x^2 - a_1(t)y^2 - b_1(t)z^2,\\ Q_2\!: x^2 - a_2(t)y^2 - b_2(t)z^2$$ over the field $\mathbb{F}...
user avatar
4 votes
1 answer
131 views

Why $\Theta(n^2)$ multiplication of coefficient required for canonical form of polynomial?

I was working through a textbook (Probability & Computing by Michael Mitzenmacher & Eli Upfal) and am not able to understand the following: Let $F(x)$ be given as a product $F(x) = \prod_{...
user avatar
4 votes
1 answer
95 views

Decidability of factoring algebraic equations

Given an arbitrary algebraic equation, say for example the likelihood of the bernoulli distribution: $$\prod_{i}^{n}\theta^{x_i}(1-\theta)^{1-x_i}$$ And some arbitrary factorization constraints, say:...
user avatar
1 vote
1 answer
52 views

How to find sets of polynomially bounded numbers whose subset sums are different?

Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ ...
user avatar
  • 113
2 votes
1 answer
888 views

Calculating a polynomial's coefficients from its roots

Let $P$ be a monic polynomial polynomial given by its roots: $$P(X) = (X-x_1)\times...\times(X-x_n)$$ What is the minimum asymptotic complexity to compute its expansion of the form: $$a_nX^n+...+a_0$$...
user avatar
  • 135
2 votes
1 answer
918 views

Complexity of polynomial interpolation

Polynomial Interpolation in the general case is $O(n^2)$ time complexity, but it can be done better in particular situations. For instance, when the polynomial can be evaluated at the complex roots of ...
user avatar
2 votes
1 answer
46 views

No common terms between polynomials: an efficient check?

The "common term" would be in standard form, but the two input multivariate polynomials needn't be, e.g $x(1+y)+y$ and $y(x+a+b)$ have one common term, $xy$. A brute force solution would be to ...
user avatar
2 votes
2 answers
93 views

How can we prove Schwartz Zippel PIT is applicable to natural polynomials?

The naturals lack subtraction, but SZ polynomial identity testing needs subtraction... I think it's applicable, but how to prove it? Perhaps: SZ shows natural polynomials are equal iff it shows those ...
user avatar
0 votes
0 answers
28 views

custom cc 16 bits with Polynomial and Initial Value , algorithm

I generate crc 16 bits with hex Workshop. Polynomial :1234(hex) Initial Value :5678 (hex) . making it on 010 (ascii) and get 3744. I looking for this algorithm , I prefer it on c#. but I not find it....
user avatar
1 vote
1 answer
193 views

How to handle generator polynomial in CRC if given in (x+1) (x^3+ x^2 +1) form?

I am trying to find the frame check sequence in cyclic redundancy check(CRC). Given that the generator polynomial is $\ g(x)= (x+1)(x^3 + x^2 + 1)$. Let's say the data sequence is $\ 10110001$. In ...
user avatar