2
$\begingroup$

Let $f(x_1, \dots, x_n)$ be an $s$-sparse polynomial over a field $\mathbb{F}$, where each variable has individual degree strictly less than $d$ (i.e., $\deg_{x_i}(f) < d$ for all $i$). When we compute $f^2$, the number of monomials is at most $s^2$, but due to cancellations of like terms, the actual sparsity of $f^2$ can be much smaller.

I am interested in understanding or bounding the extent of such cancellations in $f^2$. That is, how many monomial terms can cancel out, and how "bad" can the sparsity loss be? I conjecture that there exists a constant $0<\delta<1$ such that $\|f\|^\delta<\|f^2\|$, where $\|\cdot\|$ denotes the sparsity. The conjecture is supported by many of the recently found results.

Are there algebraic-geometric or combinatorial tools that help explain or control these cancellations?

Here are the relevant results I have already looked at,

1.https://www2.math.ethz.ch/EMIS/classics/Erdos/cit/03200203.htm
2.https://static.renyi.hu/renyi_cikkek/1947_On_the_minimal_number_of_terms_of_the_square_of_a_polynomial.pdf
3. https://arxiv.org/abs/1808.06655

Improve this question
$\endgroup$
6
  • $\begingroup$ What is the definition of sparsity? $\endgroup$ Commented Jun 30 at 13:10
  • $\begingroup$ A similar question for $n=1$ is discussed at math.stackexchange.com/questions/1368825/… with a reference to mathworld.wolfram.com/SparsePolynomialSquare.html which in turn has several references to the literature. It is noted that the square of a one-variable polynomial can have fewer nonzero terms than the original polynomial has. $\endgroup$ Commented Jul 1 at 2:36
  • $\begingroup$ @pinaki Sparsity of a polynomial is the number of distinct monomials having nonzero coefficient, in other words it's the size of its support. $\endgroup$ Commented Jul 1 at 14:43
  • $\begingroup$ @GerryMyerson yes the number of terms can shrink and infact there are related theorems of Erdos and Renyi proving existence of such polynomials, however I am interested in proving a lower bound of the shrinkage. $\endgroup$ Commented Jul 1 at 14:45
  • 2
    $\begingroup$ @GerryMyerson You're right to point that out. So here are the relevant results I have already looked at, 1.www2.math.ethz.ch/EMIS/classics/Erdos/cit/03200203.htm 2.static.renyi.hu/renyi_cikkek/… 3. arxiv.org/abs/1808.06655 So basically, we have a O(d^2logn) bound but we believe that the bound doesn't depend on the number of variables n. I am particularly interested to show that for square polynomials. $\endgroup$ Commented Jul 2 at 6:32

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.