19
$\begingroup$

I am interested in polynomials with few terms ("short polynomials", "fewnomials") in ideals. A simple to state question is

Given an ideal $I\subset k[x_1,\dots,x_n]$, what is the shortest polynomial in $I$?

There are answers for "Does an ideal contain a monomial/binomial?", but the general question seems to be hard. Let's try an easy specific question:

How few terms can a polynomial in $\langle(x-1)(y-1)(x^2y-1)\rangle \subset k[x,y]$ have?

The generator has 8 terms so this is an upper bound for the minimum. A lower bound for the minimum is 6 which can be seen as follows: Let $f$ be the generator. The Newton polytope of $f$ is a hexagon with two interior points. Any polynomial in $I$ is of the form $fg$ for some $g\in k[x,y]$ and its Newton polytope is $\text{Newton}(f) + \text{Newton}(g)$. Since the number of vertices cannot decrease under the Minkowski sum, $fg$ has at least six terms.

Are there polynomials with six or seven terms in $I$?

$\endgroup$
  • 1
    $\begingroup$ A general question is whether it's decidable (given an oracle to compute in $K$), and also whether it's decidable for principal ideals. $\endgroup$ – YCor Jun 27 '17 at 19:35
19
$\begingroup$

A simpler answer is given by $x^4y^2 - x^4y - x^2y^2 + x^2 + y - 1=(x+1)f$, where $f$ is the generator of the ideal.

$\endgroup$
  • 1
    $\begingroup$ ah, it is $(z-1)(y-1)(zy-1)=((zy+1)-(z+y))(zy-1)=z^2y^2-1-z^2y-y^2z+z+y$, where $z=x^2$ $\endgroup$ – Fedor Petrov Jun 27 '17 at 19:03
23
$\begingroup$

$$1-y^3-x^2+y^3x^8+y^4x^2-y^4x^8$$

is divisible by all three brackets, that is seen from three couplings of terms: $(1-y^3)+(y^4x^2-x^2)+(y^3x^8-y^4x^8)$ is divisible by $y-1$, $(1-x^2)+(y^4x^2-y^4x^8)+(y^3x^8-y^3)$ by $x-1$ and $(1-y^4x^8)+(y^4x^2-y^3)+(y^3x^8-x^2)$ by $x^2y-1$. Thus the answer is 6.

It may be easily found by studying the Newton hexagon: its sides and diagonals have prescribed directions.

$\endgroup$
  • 5
    $\begingroup$ @YCor The OP indicated why 6 is optimal. So all that's required is to perform the division to see that the quotient is a polynomial. (Which admittedly is best done using one's computer package of choice.) I agree that it would be nice if Fedor Petrov gave some indication of how he found this solution, but one might equally well say that with the solution in hand, it makes a nice exercise to figure out how one might find it. $\endgroup$ – Joe Silverman Jun 27 '17 at 16:20
  • $\begingroup$ @PeterMueller In fact, Fedor Petrov's example is equal to $-(x^4y^2+x^2y^2+x^2y+y^2+y+1)g$ where $g$ is your polynomial. $\endgroup$ – j.c. Jun 27 '17 at 18:41
  • $\begingroup$ @PeterMueller You should post your answer as an Answer, rather than a Comment. Although the OP didn't ask for the solution of smallest total degree, I think it is worth having such a solution. $\endgroup$ – Joe Silverman Jun 27 '17 at 18:46
  • $\begingroup$ @JoeSilverman oops thanks, I misread "lower bound" to "upper bound". $\endgroup$ – YCor Jun 27 '17 at 19:33
8
$\begingroup$

Your general question for $n=1$ (univariate polynomials) is the subject of "Computing sparse multiples of polynomials" by Mark Giesbrecht, Daniel S. Roche, Hrushikesh Tilak:

We consider the problem of finding a sparse multiple of a polynomial. Given f in F[x] of degree d over a field F, and a desired sparsity t, our goal is to determine if there exists a multiple h in F[x] of f such that h has at most t non-zero terms, and if so, to find such an h. When F=Q and t is constant, we give a polynomial-time algorithm in d and the size of coefficients in h. When F is a finite field, we show that the problem is at least as hard as determining the multiplicative order of elements in an extension field of F (a problem thought to have complexity similar to that of factoring integers), and this lower bound is tight when t=2.

There are some talk slides from 2010 by Roche here which state on the last slide the multivariate case as an open problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.