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$?

Improve this question
$\endgroup$
1
  • 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
    Commented Jun 27, 2017 at 19:35

3 Answers 3

Reset to default
20
$\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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Jun 27, 2017 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.

Improve this answer
$\endgroup$
4
  • 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
    Commented Jun 27, 2017 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.
    Commented Jun 27, 2017 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
    Commented Jun 27, 2017 at 18:46
  • $\begingroup$ @JoeSilverman oops thanks, I misread "lower bound" to "upper bound". $\endgroup$
    – YCor
    Commented Jun 27, 2017 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .