Quadratically Independent Monomials

Today Arun asked me the following question:

“Under what conditions will a set \{p_1,\ldots,p_n\} of polynomials be quadratically independent, in the sense that \{p_1^2, p_1p_2, p_2^2, p_1p_3,\ldots,p_{n-1}p_n, p_n^2\} is a linearly independent set?”

I wasn’t able to make much progress on this general question, but in the specific setting where the p_i are all polynomials in one variable, and we further restrict to just monomials, (i.e. p_i(x) = x^{d_i} for some d_i), the condition is just that there are no distinct unordered pairs (i_1,j_1),(i_2,j_2) such that d_{i_1} + d_{j_1} = d_{i_2} + d_{j_2}. Arun was interested in the largest such a set could be for a given maximum degree D, so we are left with the following interesting combinatorics problem:

“What is the largest subset S of \{1,\ldots,D\} such that no two distinct pairs of elements of S have the same sum?”

For convenience of notation let n denote the size of S. A simple upper bound is \binom{N+1}{2} \leq 2D-1, since there are \binom{N+1}{2} pairs to take a sum of, and all pairwise sums lie between 2 and 2D. We therefore have n = O(\sqrt{D}).

What about lower bounds on n? If we let S be the powers of 2 less than or equal to D, then we get a lower bound of \log_2(D); we can do slightly better by taking the Fibonacci numbers instead, but this still only gives us logarithmic growth. So the question is, can we find sets that grow polynomially in D?

It turns out the answer is yes, and we can do so by choosing randomly. Let each element of \{1,\ldots,D\} be placed in S with probability p. Now consider any k, 2 \leq k \leq 2D. If k is odd, then there are (k-1)/2 possible pairs that could add up to k: (1,k-1), (2,k-2),…,((k-1)/2,(k+1)/2). The probability of each such pair existing is p^2. Note that each of these events is independent.

S is invalid if and only if there exists some k such that more than one of these pairs is active in S. The probability of any two given pairs being simultaneously active is p^4, and there are \binom{(k-1)/2}{2} \leq \binom{D}{2} such pairs for a given k, hence (D-1)\binom{D}{2} \leq D^3/2 such pairs total (since we were just looking at odd k). Therefore, the probability of an odd value of k invalidating S is at most p^4D^3/2.

For even k we get much the same result except that the probability for a given value of k comes out to the slightly more complicated formula \binom{k/2-1}{2}p^4 + (k/2-1)p^3 + p^2 \leq D^2p^4/2 + Dp^3 + p^2, so that the total probability of an even value of k invalidating S is at most p^4D^3/2 + p^3D^2 + p^2D.

Putting this all together gives us a bound of p^4D^3 + p^3D^2 + p^2D. If we set p to be $\frac{1}{2}D^{-\frac{3}{4}}$ then the probability of S being invalid is then at most \frac{1}{16} + \frac{1}{8} D^{-\frac{1}{4}} + \frac{1}{4}D^{-\frac{1}{2}} \leq \frac{7}{16}, so with probability at least \frac{7}{16} a set S with elements chosen randomly with probability \frac{1}{2}D^{-\frac{3}{4}} will be valid. On the other hand, such a set has D^{1/4} elements in expectation, and asymptotically the probability of having at least this many elements is \frac{1}{2}. Therefore, with probability at least \frac{1}{16} a randomly chosen set will be both valid and have size greater than \frac{1}{2}, which shows that the largest value of n is at least \Omega\left(D^{1/4}\right).

We can actually do better: if all elements are chosen with probability \frac{1}{2}D^{-2/3}, then one can show that the expected number of invalid pairs is at most \frac{1}{8}D^{1/3} + O(1), and hence we can pick randomly with probability p = \frac{1}{2}D^{-2/3}, remove one element of each of the invalid pairs, and still be left with \Omega(D^{1/3}) elements in S.

So, to recap: choosing elements randomly gives us S of size \Omega(D^{1/4}); choosing randomly and then removing any offending pairs gives us S of size \Omega(D^{1/3}); and we have an upper bound of O(D^{1/2}). What is the actual asymptotic answer? I don’t actually know the answer to this, but I thought I’d share what I have so far because I think the techniques involved are pretty cool.


7 Responses to Quadratically Independent Monomials

  1. Pingback: Log 01/31/2013 | Making Shit Work

  2. Qiaochu Yuan says:

    The upper bound continues to apply to the original problem in one variable, with the cardinality argument replaced by a dimension argument: if the polynomials have degree at most D, then the pairwise products lie in the subspace of polynomials of degree at most 2D, which is 2D+1-dimensional, and there are {n+1 \choose 2} of them. In k variables, the subspace of polynomials of degree at most 2D has dimension {2D+k \choose k}, so then we get an upper bound of n = O \left( D^{k/2} k^{-k/2} \right).

  3. ryan williams says:

    Look up “Sidon sets”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: