5
$\begingroup$

Suppose I had T points in the interval $[0,1]$. Call them $e_1, \dots, e_T$.

Question 1: What is a good nontrivial bound on the geometric mean of $$\{|e_i - e_j| : 1 \leq i < j \leq T \}, $$ as a function of $T$, independent of our choice of $e_i$?

Question 2: Suppose we can choose $i$ that minimizes the geometric mean of $$E_i = \{ |e_i-e_j| : 1 \leq j \leq T, j \neq i \}.$$What is a good nontrivial upper bound on the geometric mean of $E_i$ as a function of $T$?

Some context:

Suppose I were given an arithmetic circuit that computes $$f(z) = \sum_{i=1}^t c_tz^{e_t},$$ with bounds $D$ on the degree and $T$ on the number of terms, and we would like to test whether $f$ is zero. One way to test this for $f$ over an arbitrary field is to compute images $f \bmod (z^p-1)$ for a set comprised of the smallest primes $p$ whose product exceeds $$\prod_{j \neq 1} (e_1 - e_j),$$ though one could replace $e_1$ with any of the $e_i$'s. A naive upper bound on this product is $D^T$. An answer to either of the questions above could improve this bound.

$\endgroup$
1
  • $\begingroup$ Could you give more explanation of the context, and what you’ve tried? Without any background, this looks a bit like it’s a homework problem or similar, in which case it’s off-topic here (Mathoverflow is aimed at research-level mathematics) and would be a better fit at math.stackexchange.com. $\endgroup$ Commented Oct 18, 2013 at 22:06

1 Answer 1

5
$\begingroup$

The extremal $e_i$ for Question 1 are probably well-known: they are $0$, $1$, and $(1+r)/2$ where $r$ ranges over the roots of the Gegenbauer polynomial $C_{T-2}^{(3/2)}$. The product of the $|e_i-e_j|$ is then a power of $2$ times the square root of $\mathop{\rm disc}\bigl((x^2-1)C_{T-2}^{(3/2)}(x) / c_{T-2}\bigr)$, where $c_n$ the leading coefficient $(2n+1)!/2^n n!^2$ of $C_n^{(3/2)}$. This discriminant can in turn be computed from the values of $C_{T-2}^{(3/2)}$ at $\pm 1$ and the discriminant of $C_{T-2}^{(3/2)} / c_{T-2}$, which is known but somewhat complicated $-$ experimentally it seems to be $$ \prod_{m=1}^{T-2} \frac{(m+2)^{m-2}m^m}{(2m+1)^{2m-3}}. $$ To prove that these are the optimal $e_i$: let $P(x) = \prod_{i=1}^T (x-e_i)$ and suppose $\{e_i\}$ maximizes $\prod_{i<j} |e_i-e_j|$. Then clearly two of them are at $0$ and $1$. I claim that each of the others is a root of $P''$. Indeed $e_i$ is a local maximum of $P(x)/(x-e_i)$, so a root of $\frac{d}{dx}(P(x)/(x-e_i))$, so a triple root of $(x-e_i)P'(x)-P(x)$; but then it's a root of $\frac{d^2}{dx^2}\bigl((x-e_i)P'(x)-P(x)\bigr)$, whose value at $x=e_i$ is $2P''(e)$. It follows that $P$ is a multiple of $(x^2-x)P''$, and by comparing leading coefficients we see that the multiple is $T^2-T$. The resulting differential equation characterizes $(T^2-T)C_{T-2}^{(3/2)}(2x-1)$ among polynomials up to scaling, so we are done.

$\endgroup$

You must log in to answer this question.

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