## Can Mathematica factor multivariate polynomials with 4 or more variables? And with high degrees (>10)

The Mathematica documentation clearly states

the Wolfram Language routinely factors degree-100 polynomials in 3 variables

I’m interested in factoring systems of polynomials in as many as 10 or 20 variables. The systems I have are sparse in the sense that if there are 20 variables then likely no more than 3-6 variables will appear per equation and there will likely only be two terms per equation. I’ve used Solve to test on some small systems with success. To be clear, we don’t actually need to factor the polynomials necessarily. If we factor them, then we have what we need. What we really want are the roots to the system with respect to the symbolic coefficients. Solve worked for some small test systems. Factor would also work for a single polynomial, but we need a system of polynomials and I don’t see that Factor will take a system.

I’ve looked at papers by searching scholar.google.com and it seems our problem is a solved problem in mathematics. Algorithms seem to exist for such a problem, but I’m even unclear on this since the papers are too densely packed with math for me to easily understand.

Any help would be appreciated.

Posted on Categories cheapest proxies

## A glitch with importing a list of lists of polynomials

Would anybody know how to import a list of lists of polynomials which I exported earlier?

d = {{3*t^2 + 2*t^(-1), 5*t + 6*t^(-2) + 7*t^(-4)}, {7*t^2 + 8*t^(-1), 9*t + 10*t^(-2)}}  Export["mydata.dat",d]  Import["mydata.dat"]  Out[]={{"2/t", "+", "3*t^2", "7/t^4", "+", "6/t^2", "+", "5*t"}, {"8/t", "+", "7*t^2", "10/t^2", "+", "9*t"}}  imp=Import["mydata.dat", "List"] Out[]={2/t + 3*t^2  7/t^4 + 6/t^2 + 5*t, 8/t + 7*t^2    10/t^2 + 9*t} imp[] Out[]= 2/t + 3*t^2  7/t^4 + 6/t^2 + 5*t imp[][]  error: Part::partd: Part specification 2/t + 3*t^2  7/t^4 + 6/t^2 + 5*t[] is longer than depth of object. Head @ imp[] Out[]=String 

Exporting as "List" does not help.

## Is “Solving two-variable quadratic polynomials over the Integers” is an NP-Complete Problem?

On this Wikipedia article, it claims that given $$A, B, C \geq 0, \; \in \mathbb{Z}$$, finding $$x, \,y \geq 0, \, \in \mathbb{Z}$$ for $$Ax^2+Bx^2-C=0$$ is NP-complete? Given by how easy I can solve some (with nothing but Wolfram), it doesn’t seem right. I’m sure it’s either written incorrectly or I’m just misunderstanding something.

Posted on Categories proxies

## Testing whether polynomial is in algebra of other polynomials

A collection $$\Sigma$$ of polynomials is an algebra if: (1) $$\lambda f + \eta g \in \Sigma$$ for any $$f,g \in \Sigma, \lambda,\eta \in \mathbb{R}$$ and (2) $$f,g \in \Sigma$$ implies $$fg \in \Sigma$$. We say that $$P$$ is in the algebra of $$\{P_1,\dots,P_n\}$$ if $$P$$ is in the smallest algebra containing $$P_1,\dots,P_n$$.

I was wondering if there was a way, on any computer math software, to check whether a given $$P$$ as in the algebra of a given collection $$P_1,\dots,P_n$$.

Example: take $$n \ge 1$$ and let $$P_1 = x_1+\dots+x_n, P_2 = x_1^2+\dots+x_n^2,\dots P_n = x_1^n+\dots+x_n^n$$. Then all $$n$$ of the following symmetric functions are in the algebra generated by $$P_1,\dots,P_n$$: $$x_1+\dots+x_n$$ $$x_1x_2+\dots+x_{n-1}x_n$$ $$x_1x_2x_3+\dots+x_{n-2}x_{n-1}x_n$$ $$\dots$$ $$x_1\dots x_n$$

I’d appreciate any help.

Posted on Categories proxies

## Solving a recurrance relation (Chebyshev polynomials) using RSolve? [closed] I am struggling to answer these questions, so far my attempt at part (a):

RSolve[{T[n + 1] == 2 xT[n] - T[n - 1], T == 1, T == x}, T[n],n] 

Which yields a long and incorrect expression. I’ve been staring at this for a while any help is much appreciated!

## 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.$$ Show how to compute the product polynomial in $$O(n^3\log n)$$ time.

I know the product of two bivariate polynomials of degree $$n$$ is $$O(n^2 \log n)$$ but not sure about how to obtain the product at a degree of $$n-1$$ in order to get the answer needed.

Posted on Categories proxies

## Are polynomials in one variable logspace-computable?

Given a polynomial function $$p\quad=\quad \lambda\, x\in\mathbb{N}_0.\ \sum_{i=0}^n a_i x^i$$ with $$a_i\in\mathbb{Z}$$ for all $$i\leqslant n$$, can you compute $$p$$ by a logspace transducer if the input and the output are in binary, the working tape is semi-infinite, and there are no stationary N rules (i.e., all the transducer rules are either L (move left) or R (move right) rules)?

Posted on Categories proxies

## Serre’s special groups and polynomials in Lefschetz element

Consider Grothendieck’s ring of varieties, $$K_0(\mathcal{Var}_k)$$ over a field $$k$$, and the Lefschetz element $$\mathbb{L}=[\mathbb{A}^1_k]$$. Consider also the subring $$\mathcal{L}_k\subset K_0(\mathcal{Var}_k)$$ consisting of all classes which are polynomials in $$\mathbb{L}$$, which for convenience I’ll call the “Lefschetz ring”.

It is known that $$GL_n(k)$$ is in $$\mathcal{L}_k$$, for example: $$[GL_2(k)]=(\mathbb{L}^2-1)(\mathbb{L}^2-\mathbb{L}).$$ Also, $$\mathbb{G}_a\cong \mathbb{A}^1_k$$ and $$\mathbb{G}_m\cong k^\times$$ are clearly in $$\mathcal{L}_k$$. Since the examples above are all examples of special groups, as defined by Serre and classified by Grothendieck ($$G$$ is called special if any principal $$G$$-bundle over a $$k$$-variety is locally trivial in the Zariski topology) (and not having found references with computation of the classes in $$K_0(\mathcal{Var}_k)$$ of orthogonal groups (which are not special, for example)), I wonder if all special groups have their classes in the Lefschetz ring.

More generally, the question is: is there any known relation between special groups and groups whose classes are in $$\mathcal{L}_k$$ (if necessary, one could assume $$k=\mathbb C$$)?

## Interlacing sequences by polynomials?

Given set of integers $$0 and $$0 where $$a_i\leq a_{i+1}$$ and $$b_i\leq b_{i+1}$$ at every $$i\in\{1,\dots,t-1\}$$ and $$a_t< b_t$$ we can find polynomials $$f,g\in\mathbb Z[x]$$ such that

$$f(a_i) holds at every $$i\in\{1,\dots,i-1\}$$ at any given permutation $$\sigma$$.

1. How small (among all permutations $$\sigma$$) will $$\max(f_\infty,g_\infty)$$ when $$d_{\max{}}=\max(\mathsf{deg}(f),\mathsf{deg}(g))$$ is fixed where $$f_\infty$$ and $$g_\infty$$ refers to largest coefficient by magnitude?

2. Same as 1. however we have $$f,g\in\mathbb Z_{\geq0}[x]$$ but with permutation $$\sigma=\mathsf{id}$$.

## Partitions of an integer with polynomials

Determine the coefficients of the polynomial $$a_0 + 𝑎_1𝑥_1 + 𝑎_2𝑥_2 + 𝑎_3𝑥_3 + ⋯ + 𝑎_𝑟𝑥_𝑟$$ that has the property that $$~𝑎_𝑛 = 𝑝~$$ . Where $$p$$ is the number of partitions of $$n$$ composed of two parts, $$p_1$$ and $$p_2$$, where $$1 ≤ p_1 ≤ 100~$$ and $$~ 101 ≤ p_2 ≤ 200~$$ for $$~ 102 ≤ n≤ 300$$. The answer is: $$a_r = 0~ (1≤r≤101)$$ $$a_r = 100 – |r – 201| (102≤r≤300)$$ Can anyone help me in interpreting this statement and in the resolution?