Polynomial Algorithm

Credit for this problem goes to Zeke Chin

Does there exist an algorithm for the decision problem:

Given a polynomial over $n$ variables $x_1,\cdots,x_n$ with positive integer coefficients, and a positive integer $c$, is it true that $cx_1\cdots x_n \leq P(x_1,\cdots,x_n)$ for all assignments of positive integers to $x_1,\cdots,x_n$?

For example, for $P = x_1^2 + x_2^2$ and $c=2$, the algorithm should return "Yes" since $2x_1x_2 \leq x_1^2 + x_2^2$

Solution

We can rewrite the problem as follows: if $P$ is a positive integer polynomial defined over positive integers, what is the minimum value of $Q = P/x_1\cdots x_n$? Or, if the minimum value does not exist, what is the infimum of all the achievable values?

Homogeneous polynomials

We first restrict our attention to homogeneous polynomials of degree $k$ (each term in $P$ has a total degree of $k$). If $k < n$ then the infimum is zero, because when we scale up all the $x_i$ by a factor, $P$ decreases accordingly. For example, if $P = ab+b^2+ac$, then $Q = (ab+b^2+ac)/abc$. It is easy to make $Q$ arbitrarily small by multiplying $a,b,c$ by a large factor.

Homogeneous polynomials of degree $n$

If $k=n$, that means $Q$ is homogeneous of degree zero. Thus, if we scale all the $x_i$ by the same factor, $Q$ remains constant. Now, we can assume $P$ is defined over rational numbers for simplicity.

For each coefficient of $P$, we write them as sums of ones. For example, if $P = a^2b^2 + 2bc^3 + 2cd^3$, then we write it as $P = a^2b^2 + bc^3 +bc^3+ cd^3 + cd^3$ such that we can now assume that all terms in $P$ have coefficients 1, even if the terms may repeat themselves.

Then $Q = \frac{ab}{cd} + \frac{c^2}{ad} + \frac{c^2}{ad} + \frac{d^2}{ab} + \frac{d^2}{ab}$

We now define the profile number of each variable as the total number of powers in the polynomial $Q$. For example, $p_a$, the profile number of $a$ is $1-1-1-1-1 = -3$, and $p_b = -1, p_c =3,p_d=1$. Thus we write the profile numbers of $P$ as $(-3,-1,3,1)$.

Let $s = P(1,\cdots,1)$ be the number of terms in $P$. In the example above, $s=5$.

The sum of of all profile numbers $\sum p_{x_i} = 0$, because each term has a total degree of zero. This means that the average number of profile number is zero. If all profile numbers are exactly zero, then the minimum value of $Q$ is $s$. For example, if $Q = (a^2b + abc+bc^2)/abc$, then by AM-GM, $Q \geq 3$. The minimum can be achieved when all $x_i$ is 1.

Not all profile numbers are equal

If not all profile numbers are equal, then some profile numbers are positive and some others negative. Let $x_i,x_j$ be such that $p_{x_i} > 0, p_{x_j} < 0$. Write $x_i = k_1x_j$ and substitute it into $Q$. In the example (before) above, $p_c = 3, p_a=-3$. So we write $c = k_1a$, then

$! \displaystyle Q = \frac{b}{k_1d} + \frac{k_1^2a}{d}+\frac{k_1^2a}{d}+\frac{d^2}{ab}+ \frac{d^2}{ab}$

This operation has 3 effects:

1. It eliminates $c$ from the polynomial. So now the profile of $c$ is guaranteed to be zero.

2. It preserves homogeneity if we view $k_1$ as a dimensionless number. In the example above, each term is still homogeneous with degree zero. This means that the sum of profile numbers are still zero. In fact, now the profile numbers are $(0,-1,0,1)$. In general, replacing $x_i$ with $kx_j$ will cause the transformation $(p_{x_i}', p_{x_j}') = (0, p_{x_i} + p_{x_j})$

3. The "profile number" of $k_1$ in the example above is guaranteed to be positive, by the way we choose $k_1$. We say profile number in quotes because we say that $k_1$ is a dimensionless number, and thus is not given a profile number per se.

We keep doing this operation, choosing a variable with a positive profile number and one with negative profile number, and make a $k$-substitution like above. By the majorization-theorem, we are guaranteed to terminate with a condition that all profile numbers are zero. Furthermore, the "profile numbers" of all the $k_i$s are positive. We continue with the example above, substituting $d=k_2b$ to arrive with:

$! \displaystyle Q = \frac{1}{k_1k_2} + \frac{k_1^2a}{k_2b}+\frac{k_1^2a}{k_2b}+\frac{k_2^2b}{a}+ \frac{k_2^2b}{a}$

Now, according to the AM-GM theorem, if we set each term in the above equation to be equal, then $Q$ will be expressed in terms of $k_i$, all with positive powers. This means we can set $Q$ to be arbitrarily small by setting the variables accordingly. Thus, the infimum of all achievable values of $Q$ is zero.

As an example, if we set $\frac{1}{k_1k_2} = \frac{k_1^2a}{k_2b} = \frac{k_2^2b}{a}$, along with $c=k_1a, d=k_2b$ we get $b = k_1^3a, c = k_1a, d = k_1^{5/3}a$. Substituting this value back to original expression of $Q$, we obtain $Q = 5k_1^{1/3}$.

If we want $Q$ to be really small, say $10^{-2}$, then we set $k_1 = 10^{-6}$ and $a=1$, which gives us $b=10^{-18}, c = 10^{-6}, d=10^{-10}$. For the sake of original problems that $a,b,c,d$ need to be positive integers, we multiply everything by $10^{18}$ to get$(a,b,c,d) = (10^{18}, 1, 10^{12}, 10^{8})$

Missing cases

So far, the missing cases are:

1. Non homogeneous polynomials

2. Homogeneous polynomials of degree greater than $n$. The conjecture here is that we simply test the value of $Q$ for all combinations of $x_i = 1,2$. The output is either an achievable value when all $x_i = 1$, or an infimum of zero.

Final Algorithm

The final algorithm is as follows. The final output values are italicized.

1. Is the polynomial homogeneous?

No: ??

Yes: go to step 2

2. What is the degree of homogeneity?

Less than $n$: infimum value is zero

Exactly $n$: go to step 3.

Greater than $n$: ??

3. Compute the profile numbers of each variable. Are they all zero?

Yes: the minimum values achieved when all variables are one

No: infimum value is zero